Blender Git Commits

Blender Git "temp-ghash-experiments" branch commits.

Page: 2 / 2

March 1, 2015, 16:40 (GMT)
Add some real ghash tests.

Those checks code behaves as expected, not its performances!
March 1, 2015, 15:47 (GMT)
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.
March 1, 2015, 15:41 (GMT)
Merge branch 'master' into temp-ghash-experiments
February 22, 2015, 14:12 (GMT)
GHash: Some more tests.
February 21, 2015, 17:25 (GMT)
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!
February 21, 2015, 17:24 (GMT)
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.
February 21, 2015, 15:12 (GMT)
Fix some stupid NULL free.
February 21, 2015, 14:58 (GMT)
Merge branch 'master' into temp-ghash-experiments
February 21, 2015, 14:58 (GMT)
Some minor cleanup, much better statistics...
February 21, 2015, 08:51 (GMT)
Merge branch 'master' into temp-ghash-experiments
February 20, 2015, 23:22 (GMT)
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...
February 20, 2015, 19:00 (GMT)
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!
February 20, 2015, 12:15 (GMT)
Fix own stupidity with 'and' ghash version.
February 20, 2015, 11:12 (GMT)
Merge branch 'master' into temp-ghash-experiments
December 13, 2014, 17:49 (GMT)
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.
By: Miika HämäläinenLast update: Nov-07-2014 14:18MiikaHweb | 2003-2021