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

1 files changed, 46 insertions, 7 deletions

diff --git a/source/blender/blenlib/BLI_ghash.h b/source/blender/blenlib/BLI_ghash.h
index bf2b4126453..16d18ef1315 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
 }