[Bf-blender-cvs] [cfdd273] master: GHash - code reorganization, performance enhancements, add a few missing utils to API.

Bastien Montagne noreply at git.blender.org
Thu Mar 19 19:51:47 CET 2015


Commit: cfdd27381c6730dc0d8d4bb51c132b29337b8af5
Author: Bastien Montagne
Date:   Thu Mar 19 17:36:59 2015 +0100
Branches: master
https://developer.blender.org/rBcfdd27381c6730dc0d8d4bb51c132b29337b8af5

GHash - code reorganization, performance enhancements, add a few missing utils to API.

This patch is the root of the GHash rework, all other diff will be based on it:

Reduce average load from 3.0 to 0.75
----------------------------------

This is the big performance booster part, e.g. makes tracing a dyntopo stroke between 25% and 30% faster.

Not much to say about it, aside that it obviously increase memory footprint (about 25% - 30% too).

Add optional shrinking
----------------------------------

I.e. ghashes/gsets can now shrink their buckets array when you remove enough entries. This remains optional and OFF by default.

Add code to use masking instead of modulo
----------------------------------

Buckets indices are obtained from hashes by “reducing” the hash value into the valid bucket range. This can be done either by bit-masking, or using modulo operation.
The former is quicker, but requires real hashes, while the later is slower (average 10% impact on ghash operations) but can also be used as a 'fake' hashing on raw values, like e.g. indices.

In Blender currently not all ghash usages actually hash their keys, so we stick to modulo for now (masking is ifdef’ed out), we may however investigate the benefits of switching to masking with systematic very basic hashing later…

Add various missing API helpers
----------------------------------

I.e. a way to deep-copy a ghash/gset, and a way to (re-)reserve entries (i.e. manually grow or shrink the ghash after its creation).

Various code refactoring
----------------------------------

* Get rid of the 'hack' regarding ghash size when used as gset (it’s simpler and safer to have two structs defined here, and cast pointers as needed).
* Various re-shuffle and factorization in low-level internal code.
* Some work on hashing helpers, introducing some murmur2a-based hashing too.

Thanks a bunch to Campbell for the extensive review work. :)

Reviewers: sergey, campbellbarton

Subscribers: psy-fi, lukastoenne

Projects: #bf_blender

Maniphest Tasks: T43766

Differential Revision: https://developer.blender.org/D1178

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

M	source/blender/blenlib/BLI_ghash.h
M	source/blender/blenlib/BLI_hash_mm2a.h
M	source/blender/blenlib/intern/BLI_ghash.c
M	source/blender/blenlib/intern/hash_mm2a.c
M	source/blender/makesdna/intern/CMakeLists.txt

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

diff --git a/source/blender/blenlib/BLI_ghash.h b/source/blender/blenlib/BLI_ghash.h
index bf2b412..16d18ef 100644
--- a/source/blender/blenlib/BLI_ghash.h
+++ b/source/blender/blenlib/BLI_ghash.h
@@ -44,6 +44,8 @@ typedef unsigned int  (*GHashHashFP)     (const void *key);
 typedef bool          (*GHashCmpFP)      (const void *a, const void *b);
 typedef void          (*GHashKeyFreeFP)  (void *key);
 typedef void          (*GHashValFreeFP)  (void *val);
+typedef void         *(*GHashKeyCopyFP)  (void *key);
+typedef void         *(*GHashValCopyFP)  (void *val);
 
 typedef struct GHash GHash;
 
@@ -54,7 +56,13 @@ typedef struct GHashIterator {
 } GHashIterator;
 
 enum {
-	GHASH_FLAG_ALLOW_DUPES = (1 << 0),  /* only checked for in debug mode */
+	GHASH_FLAG_ALLOW_DUPES  = (1 << 0),  /* Only checked for in debug mode */
+	GHASH_FLAG_ALLOW_SHRINK = (1 << 1),  /* Allow to shrink buckets' size. */
+
+#ifdef GHASH_INTERNAL_API
+	/* Internal usage only */
+	GHASH_FLAG_IS_GSET      = (1 << 16),  /* Whether the GHash is actually used as GSet (no value storage). */
+#endif
 };
 
 /* *** */
@@ -62,7 +70,10 @@ enum {
 GHash *BLI_ghash_new_ex(GHashHashFP hashfp, GHashCmpFP cmpfp, const char *info,
                         const unsigned int nentries_reserve) ATTR_MALLOC ATTR_WARN_UNUSED_RESULT;
 GHash *BLI_ghash_new(GHashHashFP hashfp, GHashCmpFP cmpfp, const char *info) ATTR_MALLOC ATTR_WARN_UNUSED_RESULT;
+GHash *BLI_ghash_copy(GHash *gh, GHashKeyCopyFP keycopyfp,
+                      GHashValCopyFP valcopyfp) ATTR_MALLOC ATTR_WARN_UNUSED_RESULT;
 void   BLI_ghash_free(GHash *gh, GHashKeyFreeFP keyfreefp, GHashValFreeFP valfreefp);
+void   BLI_ghash_reserve(GHash *gh, const unsigned int nentries_reserve);
 void   BLI_ghash_insert(GHash *gh, void *key, void *val);
 bool   BLI_ghash_reinsert(GHash *gh, void *key, void *val, GHashKeyFreeFP keyfreefp, GHashValFreeFP valfreefp);
 void  *BLI_ghash_lookup(GHash *gh, const void *key) ATTR_WARN_UNUSED_RESULT;
@@ -127,23 +138,37 @@ unsigned int    BLI_ghashutil_strhash_n(const char *key, size_t n);
                 CHECK_TYPE_ANY(key, char *, const char *, const char * const), \
                 BLI_ghashutil_strhash_p(key))
 unsigned int    BLI_ghashutil_strhash_p(const void *key);
+unsigned int    BLI_ghashutil_strhash_p_murmur(const void *key);
 bool            BLI_ghashutil_strcmp(const void *a, const void *b);
 
 #define         BLI_ghashutil_inthash(key) ( \
                 CHECK_TYPE_ANY(&(key), int *, const int *), \
                 BLI_ghashutil_uinthash((unsigned int)key))
 unsigned int    BLI_ghashutil_uinthash(unsigned int key);
+unsigned int    BLI_ghashutil_inthash_p(const void *ptr);
+unsigned int    BLI_ghashutil_inthash_p_murmur(const void *ptr);
+bool            BLI_ghashutil_intcmp(const void *a, const void *b);
+
+
+unsigned int    BLI_ghashutil_uinthash_v4(const unsigned int key[4]);
 #define         BLI_ghashutil_inthash_v4(key) ( \
                 CHECK_TYPE_ANY(key, int *, const int *), \
                 BLI_ghashutil_uinthash_v4((const unsigned int *)key))
-unsigned int    BLI_ghashutil_uinthash_v4(const unsigned int key[4]);
 #define         BLI_ghashutil_inthash_v4_p \
    ((GSetHashFP)BLI_ghashutil_uinthash_v4)
+#define         BLI_ghashutil_uinthash_v4_p \
+   ((GSetHashFP)BLI_ghashutil_uinthash_v4)
+unsigned int    BLI_ghashutil_uinthash_v4_murmur(const unsigned int key[4]);
+#define         BLI_ghashutil_inthash_v4_murmur(key) ( \
+                CHECK_TYPE_ANY(key, int *, const int *), \
+                BLI_ghashutil_uinthash_v4_murmur((const unsigned int *)key))
+#define         BLI_ghashutil_inthash_v4_p_murmur \
+   ((GSetHashFP)BLI_ghashutil_uinthash_v4_murmur)
+#define         BLI_ghashutil_uinthash_v4_p_murmur \
+   ((GSetHashFP)BLI_ghashutil_uinthash_v4_murmur)
 bool            BLI_ghashutil_uinthash_v4_cmp(const void *a, const void *b);
 #define         BLI_ghashutil_inthash_v4_cmp \
                 BLI_ghashutil_uinthash_v4_cmp
-unsigned int    BLI_ghashutil_inthash_p(const void *ptr);
-bool            BLI_ghashutil_intcmp(const void *a, const void *b);
 
 /** \} */
 
@@ -178,6 +203,7 @@ typedef struct GSet GSet;
 typedef GHashHashFP GSetHashFP;
 typedef GHashCmpFP GSetCmpFP;
 typedef GHashKeyFreeFP GSetKeyFreeFP;
+typedef GHashKeyCopyFP GSetKeyCopyFP;
 
 /* so we can cast but compiler sees as different */
 typedef struct GSetIterator {
@@ -191,6 +217,7 @@ typedef struct GSetIterator {
 GSet  *BLI_gset_new_ex(GSetHashFP hashfp, GSetCmpFP cmpfp, const char *info,
                        const unsigned int nentries_reserve) ATTR_MALLOC ATTR_WARN_UNUSED_RESULT;
 GSet  *BLI_gset_new(GSetHashFP hashfp, GSetCmpFP cmpfp, const char *info) ATTR_MALLOC ATTR_WARN_UNUSED_RESULT;
+GSet  *BLI_gset_copy(GSet *gs, GSetKeyCopyFP keycopyfp) ATTR_MALLOC ATTR_WARN_UNUSED_RESULT;
 int    BLI_gset_size(GSet *gs) ATTR_WARN_UNUSED_RESULT;
 void   BLI_gset_flag_set(GSet *gs, unsigned int flag);
 void   BLI_gset_flag_clear(GSet *gs, unsigned int flag);
@@ -202,7 +229,7 @@ bool   BLI_gset_haskey(GSet *gs, const void *key) ATTR_WARN_UNUSED_RESULT;
 bool   BLI_gset_remove(GSet *gs, void *key, GSetKeyFreeFP keyfreefp);
 void   BLI_gset_clear_ex(GSet *gs, GSetKeyFreeFP keyfreefp,
                          const unsigned int nentries_reserve);
-void  BLI_gset_clear(GSet *gs, GSetKeyFreeFP keyfreefp);
+void   BLI_gset_clear(GSet *gs, GSetKeyFreeFP keyfreefp);
 
 GSet *BLI_gset_ptr_new_ex(const char *info,
                           const unsigned int nentries_reserve) ATTR_MALLOC ATTR_WARN_UNUSED_RESULT;
@@ -229,10 +256,22 @@ BLI_INLINE bool BLI_gsetIterator_done(GSetIterator *gsi) { return BLI_ghashItera
 	     BLI_gsetIterator_done(&gs_iter_) == false;                           \
 	     BLI_gsetIterator_step(&gs_iter_), i_++)
 
-#ifdef DEBUG
+
+/* For testing, debugging only */
+#ifdef GHASH_INTERNAL_API
+int BLI_ghash_buckets_size(GHash *gh);
+int BLI_gset_buckets_size(GSet *gs);
+
+double BLI_ghash_calc_quality_ex(
+        GHash *gh, double *r_load, double *r_variance,
+        double *r_prop_empty_buckets, double *r_prop_overloaded_buckets, int *r_biggest_bucket);
+double BLI_gset_calc_quality_ex(
+        GSet *gs, double *r_load, double *r_variance,
+        double *r_prop_empty_buckets, double *r_prop_overloaded_buckets, int *r_biggest_bucket);
 double BLI_ghash_calc_quality(GHash *gh);
 double BLI_gset_calc_quality(GSet *gs);
-#endif
+#endif  /* GHASH_INTERNAL_API */
+
 
 #ifdef __cplusplus
 }
diff --git a/source/blender/blenlib/BLI_hash_mm2a.h b/source/blender/blenlib/BLI_hash_mm2a.h
index 007dec4..6beaf50 100644
--- a/source/blender/blenlib/BLI_hash_mm2a.h
+++ b/source/blender/blenlib/BLI_hash_mm2a.h
@@ -42,4 +42,6 @@ void BLI_hash_mm2a_add_int(BLI_HashMurmur2A *mm2, int data);
 
 uint32_t BLI_hash_mm2a_end(BLI_HashMurmur2A *mm2);
 
+uint32_t BLI_hash_mm2(const unsigned char *data, size_t len, uint32_t seed);
+
 #endif  /* __BLI_HASH_MM2A_H__ */
diff --git a/source/blender/blenlib/intern/BLI_ghash.c b/source/blender/blenlib/intern/BLI_ghash.c
index 5360ea7..a2233c3 100644
--- a/source/blender/blenlib/intern/BLI_ghash.c
+++ b/source/blender/blenlib/intern/BLI_ghash.c
@@ -36,17 +36,23 @@
 
 #include <string.h>
 #include <stdlib.h>
+#include <stdarg.h>
 #include <limits.h>
 
 #include "MEM_guardedalloc.h"
 
 #include "BLI_sys_types.h"  /* for intptr_t support */
 #include "BLI_utildefines.h"
+#include "BLI_hash_mm2a.h"
 #include "BLI_mempool.h"
+
+#define GHASH_INTERNAL_API
 #include "BLI_ghash.h"
 #include "BLI_strict_flags.h"
 
+#define GHASH_USE_MODULO_BUCKETS
 
+/* Also used by smallhash! */
 const unsigned int hashsizes[] = {
 	5, 11, 17, 37, 67, 131, 257, 521, 1031, 2053, 4099, 8209, 
 	16411, 32771, 65537, 131101, 262147, 524309, 1048583, 2097169, 
@@ -54,24 +60,43 @@ const unsigned int hashsizes[] = {
 	268435459
 };
 
-/* internal flag to ensure sets values aren't used */
-#ifndef NDEBUG
-#  define GHASH_FLAG_IS_SET (1 << 8)
-#  define IS_GHASH_ASSERT(gh) BLI_assert((gh->flag & GHASH_FLAG_IS_SET) == 0)
-// #  define IS_GSET_ASSERT(gs) BLI_assert((gs->flag & GHASH_FLAG_IS_SET) != 0)
+#ifdef GHASH_USE_MODULO_BUCKETS
+#  define GHASH_MAX_SIZE 27
 #else
-#  define IS_GHASH_ASSERT(gh)
-// #  define IS_GSET_ASSERT(eh)
+#  define GHASH_BUCKET_BIT_MIN 2
+#  define GHASH_BUCKET_BIT_MAX 28  /* About 268M of buckets... */
 #endif
 
+/**
+ * \note Max load #GHASH_LIMIT_GROW used to be 3. (pre 2.74).
+ * Python uses 0.6666, tommyhaslib even goes down to 0.5.
+ * Reducing our from 3 to 0.75 gives huge speedup (about twice quicker pure GHash insertions/lookup,
+ * about 25% - 30% quicker 'dynamic-topology' stroke drawing e.g.).
+ * Min load #GHASH_LIMIT_SHRINK is a quarter of max load, to avoid resizing to quickly.
+ */
+#define GHASH_LIMIT_GROW(_nbkt)   (((_nbkt) * 3) /  4)
+#define GHASH_LIMIT_SHRINK(_nbkt) (((_nbkt) * 3) / 16)
+
 /***/
 
+/* WARNING! Keep in sync with ugly _gh_Entry in header!!! */
 typedef struct Entry {
 	struct Entry *next;
 
-	void *key, *val;
+	void *key;
 } Entry;
 
+typedef struct GHashEntry {
+	Entry e;
+
+	void *val;
+} GHashEntry;
+
+typedef Entry GSetEntry;
+
+#define GHASH_ENTRY_SIZE(_is_gset) \
+	((_is_gset) ? sizeof(GSetEntry) : sizeof(GHashEntry))
+
 struct GHash {
 	GHashHashFP hashfp;
 	GHashCmpFP cmpfp;
@@ -79,11 +104,34 @@ struct GHash {
 	Entry **buckets;
 	struct BLI_mempool *entrypool;
 	unsigned int nbuckets;
+	unsigned int limit_grow, limit_shrink;
+#ifdef GHASH_USE_MODULO_BUCKETS
+	unsigned int cursize, size_min;
+#else
+	unsigned int bucket_mask, bucket_bit, bucket_bit_min;
+#endif
+
 	unsigned int nentries;
-	unsigned int cursize, flag;
+	unsigned int flag;
 };
 
 
+BLI_INLINE void ghash_entry_copy(
+        GHash *gh_dst, Entry *dst, GHash *gh_src, Entry *src,
+        GHashKeyCopyFP keycopyfp, GHashValCopyFP valcopyfp)
+{
+	dst->key = (keycopyfp) ? keycopyfp(src->key) : src->key;
+
+	if ((gh_dst->flag & GHASH_FLAG_IS_GSET) == 0) {
+		if ((gh_src->flag & GHASH_FLAG_IS_GSET) == 0) {
+			((GHashEntry *)dst)->val = (valcopyfp) ? valcopyfp(((GHashEntry *)src)->val) : ((GHashEntry *)src)->val;
+		}
+		else {
+			((GHashEntry *)dst)->val = NULL;
+		}
+	}
+}
+
 /* -------------------------------------------------------------------- */
 /* GHash API */
 

@@ Diff output truncated at 10240 characters. @@




More information about the Bf-blender-cvs mailing list