From 7c9b1065895e0a6a12555075980d7a77d1dea8c7 Mon Sep 17 00:00:00 2001 From: Campbell Barton Date: Sun, 2 Feb 2014 02:19:11 +1100 Subject: Smallhash: optimizations - remove static array used only for copying (use alloca on resize) - set SMSTACKSIZE to one of the values in 'hashsizes' since the full available size was never used. - ensure ~1.5x as many buckets as entries, was 3x which caused malloc's quite early on. --- source/blender/blenlib/BLI_smallhash.h | 13 ++++++------- source/blender/blenlib/intern/smallhash.c | 18 +++++++++++------- 2 files changed, 17 insertions(+), 14 deletions(-) (limited to 'source') diff --git a/source/blender/blenlib/BLI_smallhash.h b/source/blender/blenlib/BLI_smallhash.h index 07bd9975467..f394a224ca1 100644 --- a/source/blender/blenlib/BLI_smallhash.h +++ b/source/blender/blenlib/BLI_smallhash.h @@ -39,17 +39,16 @@ typedef struct { void *val; } SmallHashEntry; -/*how much stack space to use before dynamically allocating memory*/ -#define SMSTACKSIZE 64 +/* how much stack space to use before dynamically allocating memory. + * set to match one of the values in 'hashsizes' to avoid too many mallocs */ +#define SMSTACKSIZE 131 typedef struct SmallHash { - SmallHashEntry *buckets; - SmallHashEntry *buckets_stack; - SmallHashEntry *buckets_copy; - SmallHashEntry _buckets_stack[SMSTACKSIZE]; - SmallHashEntry _buckets_copy[SMSTACKSIZE]; unsigned int nbuckets; unsigned int nentries; unsigned int cursize; + + SmallHashEntry *buckets; + SmallHashEntry buckets_stack[SMSTACKSIZE]; } SmallHash; typedef struct { diff --git a/source/blender/blenlib/intern/smallhash.c b/source/blender/blenlib/intern/smallhash.c index 7f9acab1f37..fa953f0e44d 100644 --- a/source/blender/blenlib/intern/smallhash.c +++ b/source/blender/blenlib/intern/smallhash.c @@ -38,7 +38,9 @@ #include #include "MEM_guardedalloc.h" + #include "BLI_utildefines.h" +#include "BLI_alloca.h" #include "BLI_smallhash.h" @@ -70,7 +72,8 @@ extern const unsigned int hashsizes[]; */ BLI_INLINE bool smallhash_test_expand_buckets(const unsigned int nentries, const unsigned int nbuckets) { - return nentries * 3 > nbuckets; + /* (approx * 1.5) */ + return (nentries + (nentries >> 1)) > nbuckets; } BLI_INLINE void smallhash_init_empty(SmallHash *sh) @@ -127,12 +130,15 @@ BLI_INLINE void smallhash_resize_buckets(SmallHash *sh, const unsigned int nbuck { SmallHashEntry *buckets_old = sh->buckets; const unsigned int nbuckets_old = sh->nbuckets; + const bool was_alloc = (buckets_old != sh->buckets_stack); unsigned int i = 0; BLI_assert(sh->nbuckets != nbuckets); + if (nbuckets <= SMSTACKSIZE) { + const size_t size = sizeof(*buckets_old) * nbuckets_old; + buckets_old = alloca(size); + memcpy(buckets_old, sh->buckets, size); - if (buckets_old == sh->buckets_stack && nbuckets <= SMSTACKSIZE) { - SWAP(SmallHashEntry *, sh->buckets_stack, sh->buckets_copy); sh->buckets = sh->buckets_stack; } else { @@ -151,7 +157,7 @@ BLI_INLINE void smallhash_resize_buckets(SmallHash *sh, const unsigned int nbuck } } - if (buckets_old != sh->buckets_stack && buckets_old != sh->buckets_copy) { + if (was_alloc) { MEM_freeN(buckets_old); } } @@ -164,9 +170,7 @@ void BLI_smallhash_init(SmallHash *sh) sh->cursize = 2; sh->nbuckets = hashsizes[sh->cursize]; - sh->buckets = sh->_buckets_stack; - sh->buckets_copy = sh->_buckets_copy; - sh->buckets_stack = sh->_buckets_stack; + sh->buckets = sh->buckets_stack; smallhash_init_empty(sh); } -- cgit v1.2.3