Review Request 124539: Optimize KDevHash for integral types.

[Olivier Jean de Gaalon]

-----------------------------------------------------------
This is an automatically generated e-mail. To reply, visit:
https://git.reviewboard.kde.org/r/124539/#review83272
-----------------------------------------------------------


(actually looking at the code)

qHash for integral types is just a cast to uint, maybe would be clearer to do that directly.

Often you end up having to balance the cost of hashing vs the cost of collisions, so a cheaper hash isn't in and of itself a win.

My benchmarking was focused on reducing collisions, so in retrospect it's likely the current implementation is sacrificing real performance. Possibly we shouldn't be taking byte-sized chunks of /any/ data type size (though then padding doesn't help the hash much).

OTOH, benching the hash seems like an exercise in futility: the best hash by this measurement will be "return 0". The cost of any other hash is pure waste unless it's improving the overall performance of the system via reduced collisions. Changes to the hash should then be ignoring these benchmarks and testing if real insertion and lookup patterns are improved... unfortunately benchmarking that is quite a bit more work.

- Olivier Jean de Gaalon


On July 30, 2015, 10:04 p.m., Milian Wolff wrote:
> 
> -----------------------------------------------------------
> This is an automatically generated e-mail. To reply, visit:
> https://git.reviewboard.kde.org/r/124539/
> -----------------------------------------------------------
> 
> (Updated July 30, 2015, 10:04 p.m.)
> 
> 
> Review request for KDevelop.
> 
> 
> Repository: kdevplatform
> 
> 
> Description
> -------
> 
> Optimize KDevHash for integral types.
> 
> For integral types, we now reuse qHash internally and only
> fall back to the O(sizeof(T)) implementation for other
> types.
> 
> Before:
> 
> ********* Start testing of TestKDevHash *********
> Config: Using QtTest library 5.5.0, Qt 5.5.0 (x86_64-little_endian-lp64 shared (dynamic) release build; by GCC 5.1.0)
> PASS   : TestKDevHash::initTestCase()
> PASS   : TestKDevHash::benchHash_int()
> RESULT : TestKDevHash::benchHash_int():
>      0.075 msecs per iteration (total: 77, iterations: 1024)
> PASS   : TestKDevHash::benchHash_uint()
> RESULT : TestKDevHash::benchHash_uint():
>      0.075 msecs per iteration (total: 77, iterations: 1024)
> PASS   : TestKDevHash::benchHash_quint64()
> RESULT : TestKDevHash::benchHash_quint64():
>      0.15 msecs per iteration (total: 77, iterations: 512)
> PASS   : TestKDevHash::benchHash_bool()
> RESULT : TestKDevHash::benchHash_bool():
>      0.018 msecs per iteration (total: 77, iterations: 4096)
> PASS   : TestKDevHash::cleanupTestCase()
> Totals: 6 passed, 0 failed, 0 skipped, 0 blacklisted
> ********* Finished testing of TestKDevHash *********
> 
> After:
> 
> ********* Start testing of TestKDevHash *********
> Config: Using QtTest library 5.5.0, Qt 5.5.0 (x86_64-little_endian-lp64 shared (dynamic) release build; by GCC 5.1.0)
> PASS   : TestKDevHash::initTestCase()
> PASS   : TestKDevHash::benchHash_int()
> RESULT : TestKDevHash::benchHash_int():
>      0.024 msecs per iteration (total: 51, iterations: 2048)
> PASS   : TestKDevHash::benchHash_uint()
> RESULT : TestKDevHash::benchHash_uint():
>      0.024 msecs per iteration (total: 51, iterations: 2048)
> PASS   : TestKDevHash::benchHash_quint64()
> RESULT : TestKDevHash::benchHash_quint64():
>      0.026 msecs per iteration (total: 54, iterations: 2048)
> PASS   : TestKDevHash::benchHash_bool()
> RESULT : TestKDevHash::benchHash_bool():
>      0.022 msecs per iteration (total: 92, iterations: 4096)
> PASS   : TestKDevHash::cleanupTestCase()
> Totals: 6 passed, 0 failed, 0 skipped, 0 blacklisted
> ********* Finished testing of TestKDevHash *********
> 
> 
> Diffs
> -----
> 
>   language/CMakeLists.txt 2c2b0285b68d209e07af185c43dcf157507f5a54 
>   language/util/kdevhash.h 40c32935aec9c7e5552769e780c033e96cf63166 
>   language/util/tests/CMakeLists.txt PRE-CREATION 
>   language/util/tests/test_kdevhash.cpp PRE-CREATION 
>   plugins/projectfilter/projectfilter.h 014e5a1eabbb3a2d9e71baeee3e38643cb8649e7 
> 
> Diff: https://git.reviewboard.kde.org/r/124539/diff/
> 
> 
> Testing
> -------
> 
> 
> Thanks,
> 
> Milian Wolff
> 
>

-------------- next part --------------
An HTML attachment was scrubbed...
URL: <http://mail.kde.org/pipermail/kdevelop-devel/attachments/20150801/0f72950b/attachment.html>