[Bf-blender-cvs] [7c9b106] master: Smallhash: optimizations

[Campbell Barton]

Commit: 7c9b1065895e0a6a12555075980d7a77d1dea8c7
Author: Campbell Barton
Date:   Sun Feb 2 02:19:11 2014 +1100
https://developer.blender.org/rB7c9b1065895e0a6a12555075980d7a77d1dea8c7

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.

===================================================================

M	source/blender/blenlib/BLI_smallhash.h
M	source/blender/blenlib/intern/smallhash.c

===================================================================

diff --git a/source/blender/blenlib/BLI_smallhash.h b/source/blender/blenlib/BLI_smallhash.h
index 07bd997..f394a22 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 7f9acab..fa953f0 100644
--- a/source/blender/blenlib/intern/smallhash.c
+++ b/source/blender/blenlib/intern/smallhash.c
@@ -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);
 }