D hash table comparison benchmark

Eugene Wissner belka at caraus.de
Tue Jun 26 08:38:26 UTC 2018


On Tuesday, 26 June 2018 at 04:17:44 UTC, Nathan S. wrote:
> On Tuesday, 26 June 2018 at 03:45:27 UTC, Seb wrote:
>> Did you by chance also benchmark it with other languages like 
>> C++, Go or Rust?
>
> I didn't since I was evaluating hashtable implementations for 
> use in a D application.
>
>> BTW I'm not sure what your plans are, but are you aware of 
>> this recent article?
>>
>> https://probablydance.com/2018/05/28/a-new-fast-hash-table-in-response-to-googles-new-fast-hash-table
>
> I wasn't, thanks.

It isn't fair to post the benchmarks without giving some time to 
fix the bug :). Just kidding. Thanks a lot for taking time to 
report the bug. tanya's HashTable implementation is very young. I 
fixed the bug in the "bugfix/hashtable-endless" branch (still 
need to fix another rehash() before merging into master). Just 
put in dub.sdl:
dependency "tanya" version="~bugfix/hashtable-endless"

Here are the results from my machine with tanya included. I'm 
posting only optimized version for dmd and ldc. I just say that 
tanya's HashTable sucks in debug mode, I'm using an underlying 
structure to combine common functionality for the hash table and 
hash set. With optimizations a lot of function calls can be 
inlined.

So dmd:

Hashtable benchmark N (size) = 100 (repetitions) = 10000

=Results (new hashtables)=
*Trial #1*
[checksum 1526449824] 139 msecs built-in AA
[checksum 1526449824] 368 msecs containers.hashmap w/Mallocator
[checksum 1526449824] 422 msecs containers.hashmap w/GCAllocator
[checksum 1526449824]  97 msecs memutils.hashmap
[checksum 1526449824] 101 msecs vibe.utils.hashmap
[checksum 1526449824] 181 msecs jive.map
[checksum 1526449824] 242 msecs tanya.container.hashtable
*Trial #2*
[checksum 1526449824] 128 msecs built-in AA
[checksum 1526449824] 361 msecs containers.hashmap w/Mallocator
[checksum 1526449824] 416 msecs containers.hashmap w/GCAllocator
[checksum 1526449824]  95 msecs memutils.hashmap
[checksum 1526449824] 109 msecs vibe.utils.hashmap
[checksum 1526449824] 179 msecs jive.map
[checksum 1526449824] 239 msecs tanya.container.hashtable
*Trial #3*
[checksum 1526449824] 131 msecs built-in AA
[checksum 1526449824] 360 msecs containers.hashmap w/Mallocator
[checksum 1526449824] 421 msecs containers.hashmap w/GCAllocator
[checksum 1526449824]  89 msecs memutils.hashmap
[checksum 1526449824] 105 msecs vibe.utils.hashmap
[checksum 1526449824] 180 msecs jive.map
[checksum 1526449824] 237 msecs tanya.container.hashtable

=Results (reusing hashtables)=

*Trial #1*
(checksum 1526449824) 57.66 msecs built-in AA
(checksum 1526449824) 52.76 msecs containers.hashmap w/Mallocator
(checksum 1526449824) 48.49 msecs containers.hashmap w/GCAllocator
(checksum 1526449824) 31.16 msecs memutils.hashmap
(checksum 1526449824) 45.19 msecs vibe.utils.hashmap
(checksum 1526449824) 47.52 msecs jive.map
(checksum 1526449824) 114.41 msecs tanya.container.hashtable
*Trial #2*
(checksum 1526449824) 54.42 msecs built-in AA
(checksum 1526449824) 52.37 msecs containers.hashmap w/Mallocator
(checksum 1526449824) 53.10 msecs containers.hashmap w/GCAllocator
(checksum 1526449824) 32.39 msecs memutils.hashmap
(checksum 1526449824) 46.94 msecs vibe.utils.hashmap
(checksum 1526449824) 48.90 msecs jive.map
(checksum 1526449824) 113.73 msecs tanya.container.hashtable
*Trial #3*
(checksum 1526449824) 58.06 msecs built-in AA
(checksum 1526449824) 53.29 msecs containers.hashmap w/Mallocator
(checksum 1526449824) 55.08 msecs containers.hashmap w/GCAllocator
(checksum 1526449824) 30.94 msecs memutils.hashmap
(checksum 1526449824) 44.89 msecs vibe.utils.hashmap
(checksum 1526449824) 47.69 msecs jive.map
(checksum 1526449824) 112.62 msecs tanya.container.hashtable

LDC:

Hashtable benchmark N (size) = 100 (repetitions) = 10000

=Results (new hashtables)=
*Trial #1*
[checksum 1526449824] 103 msecs built-in AA
[checksum 1526449824] 261 msecs containers.hashmap w/Mallocator
[checksum 1526449824] 274 msecs containers.hashmap w/GCAllocator
[checksum 1526449824]  64 msecs memutils.hashmap
[checksum 1526449824]  52 msecs vibe.utils.hashmap
[checksum 1526449824] 131 msecs jive.map
[checksum 1526449824] 102 msecs tanya.container.hashtable
*Trial #2*
[checksum 1526449824]  97 msecs built-in AA
[checksum 1526449824] 257 msecs containers.hashmap w/Mallocator
[checksum 1526449824] 274 msecs containers.hashmap w/GCAllocator
[checksum 1526449824]  59 msecs memutils.hashmap
[checksum 1526449824]  50 msecs vibe.utils.hashmap
[checksum 1526449824] 131 msecs jive.map
[checksum 1526449824] 102 msecs tanya.container.hashtable
*Trial #3*
[checksum 1526449824]  96 msecs built-in AA
[checksum 1526449824] 258 msecs containers.hashmap w/Mallocator
[checksum 1526449824] 271 msecs containers.hashmap w/GCAllocator
[checksum 1526449824]  60 msecs memutils.hashmap
[checksum 1526449824]  50 msecs vibe.utils.hashmap
[checksum 1526449824] 131 msecs jive.map
[checksum 1526449824] 102 msecs tanya.container.hashtable

=Results (reusing hashtables)=

*Trial #1*
(checksum 1526449824) 31.89 msecs built-in AA
(checksum 1526449824) 26.17 msecs containers.hashmap w/Mallocator
(checksum 1526449824) 26.55 msecs containers.hashmap w/GCAllocator
(checksum 1526449824) 16.08 msecs memutils.hashmap
(checksum 1526449824) 20.43 msecs vibe.utils.hashmap
(checksum 1526449824) 30.75 msecs jive.map
(checksum 1526449824) 54.34 msecs tanya.container.hashtable
*Trial #2*
(checksum 1526449824) 31.96 msecs built-in AA
(checksum 1526449824) 25.99 msecs containers.hashmap w/Mallocator
(checksum 1526449824) 26.02 msecs containers.hashmap w/GCAllocator
(checksum 1526449824) 16.05 msecs memutils.hashmap
(checksum 1526449824) 20.23 msecs vibe.utils.hashmap
(checksum 1526449824) 30.76 msecs jive.map
(checksum 1526449824) 52.78 msecs tanya.container.hashtable
*Trial #3*
(checksum 1526449824) 36.33 msecs built-in AA
(checksum 1526449824) 29.36 msecs containers.hashmap w/Mallocator
(checksum 1526449824) 27.83 msecs containers.hashmap w/GCAllocator
(checksum 1526449824) 15.97 msecs memutils.hashmap
(checksum 1526449824) 20.28 msecs vibe.utils.hashmap
(checksum 1526449824) 30.19 msecs jive.map
(checksum 1526449824) 53.06 msecs tanya.container.hashtable


More information about the Digitalmars-d mailing list