Blender Git Loki

Add some real ghash tests.

Those checks code behaves as expected, not its performances!

Rename BLI_ghash_test -> BLI_ghash_performance_test.

This is what it is, and those perf tests are not suited for real behavioral tests.
Will add real tests again in a new BLI_ghash_test.

Merge branch 'master' into temp-ghash-experiments

GHash: Some more tests.

GHash: Add explict 'Shrink' flag to allow shrinking.

Also, fix (probable) issue with Entry struct and GSet - since we remove sizeof(void*) from
Entry size for gsets, void *val member must absolutely remain the last one!

GHash: Add hash to entries.

This gives a nice speedup during buckets resizing, but also in mere lookups,
especially when key comparison function is not as cheap as a mere equality
(integer vectors, strings...).

It also increases about 15% the entries' memory footprint (30% on 64bits, due to padding),
but think it's really worth it.

Fix some stupid NULL free.

Merge branch 'master' into temp-ghash-experiments

Some minor cleanup, much better statistics...

Merge branch 'master' into temp-ghash-experiments

Rework ghash to make it fully dynamic, and lower load threshold.

So now, by default, when you remove an entry from a ghash and it gets below
'shrink' load limit, it resizes it buckets' array.

Also, lowered heavily 'grow' load limit, was 3, which is way too big and had important
impact on performances. Now using 3/4 (similar to java or python dict values), this seems
to give several tens of percents quicker insertions and lookups.

Regarding masking vs. modulo, so far all tests have shown that:
* There is no sensible difference in quality (i.e. both seem to yield more or less
the same quite even distribution);
* Masking is slightly quicker than modulo (as expected), but this is not much important globally.

Warnings:
* This code is far from ready for anything else than toying around, for now!
* Kept old 'modulo' code behind a #define for now, makes code slightly confusing though...

GHash: fix/hugely enhance GHash tests.

Also, fix some stupid mistakes in some new murmur hashing helpers,
and rework quality function to simply compute variance in buckets occupation.

Note latest change has some quite funny effects, looks like variance is always
very close to load of the ghash...

As for performances:
* Globally, ghash and murmur have very similar results, both in speed and quality.
* For integers, ghash usually quicker.
* For strings, oddly murmur is much quicker when adding to ghash, but quite slower
when lookingup in the ghash...

Anyway, still much to do in this area!

Fix own stupidity with 'and' ghash version.

Merge branch 'master' into temp-ghash-experiments

Initial GHash-enhancements experiments.

This commit adds:
*Some Murmur-based hasing helpers for GHash;
*A (very basic) switch between key-to-bucketidx using modulo or binary-AND;
*Some gtests to make some comparisons.

First test results seem to show that:
* murmur is much much quicker for string keys, with approximately same hash quality;
* org ghash is much much quicker for int keys, but with much worse hash quality than murmur-based one;
* key-to-bucketidx method does not seem to make much difference so far.

Nothing definitive here yet, obviously.