Smallhash: optimizations
authorCampbell Barton <ideasman42@gmail.com>
Sat, 1 Feb 2014 15:19:11 +0000 (02:19 +1100)
committerCampbell Barton <ideasman42@gmail.com>
Sat, 1 Feb 2014 15:24:48 +0000 (02:24 +1100)
- 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
source/blender/blenlib/intern/smallhash.c

index 07bd9975467bd364bc754e4bdb75ce05d602787f..f394a224ca183945c031167cd7d3b1e1db5e2abf 100644 (file)
@@ -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 {
index 7f9acab1f37ef67db4f75b0effbbcc34780b5f2b..fa953f0e44d0952458c9630e7006c543552b4900 100644 (file)
@@ -38,7 +38,9 @@
 #include <stdlib.h>
 
 #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);
 }