[Bf-blender-cvs] [7c9b106] master: Smallhash: optimizations
Campbell Barton
noreply at git.blender.org
Sat Feb 1 16:25:06 CET 2014
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);
}
More information about the Bf-blender-cvs
mailing list