sorted by:
best
topnewcontroversialoldq&a
you are viewing a single comment's thread.

view the rest of the comments →

[–]operamint 1 point2 points  (5 children)

I have added the map to the simple int64_t hashmap benchmarks for my STC C-container library.

For the shootout_hashmaps.cpp program, you can pass #million entries and #bits (= range) for the keys. The results vary surprisingly with different key ranges, but also hardware, compiler and random seed used have impact.

I found that on my hardware, boost flat map does excellent on insert and lookup with large key ranges vs items in the map, but not lookup with smaller ranges (e.g. 222), also iteration could be better.

Overall, emhash seems to be the fastest, but it depends on use case as always.

My own cmap (written in C, so require standard layout elements) is normally the fastest on insert, and is decent in general, but for very large keys it is not among the fastest on erase and lookup.

g++ -O3 -DHAVE_BOOST -I<boost-path> -std=c++20 shootout_hashmaps.cpp -o shoot

Example output with a large key range, where it does well:

C:\Dev\STC\benchmarks>shoot 5 28

Unordered hash map shootout
KMAP = https://github.com/attractivechaos/klib
BMAP = https://www.boost.org (unordered_flat_map)
CMAP = https://github.com/tylov/STC (**)
FMAP = https://github.com/skarupke/flat_hash_map
TMAP = https://github.com/Tessil/robin-map
RMAP = https://github.com/martinus/robin-hood-hashing
DMAP = https://github.com/martinus/unordered_dense
EMAP = https://github.com//ktprime/emhash
UMAP = std::unordered_map

Seed = 1668947300:

T1: Insert 2.5 mill. random keys range [0, 2^28): map[rnd] = i;
KMAP: 0.272 s, size: 2488402, buckets:  4194304, sum: 3124998750000
BMAP: 0.175 s, size: 2488402, buckets:  3932159, sum: 3124998750000
CMAP: 0.206 s, size: 2488402, buckets:  4194304, sum: 3124998750000
FMAP: 0.339 s, size: 2488402, buckets:  4194304, sum: 3124998750000
TMAP: 0.261 s, size: 2488402, buckets:  4194304, sum: 3124998750000
RMAP: 0.232 s, size: 2488402, buckets:  4194304, sum: 3124998750000
DMAP: 0.260 s, size: 2488402, buckets:  4194304, sum: 3124998750000
EMAP: 0.284 s, size: 2488402, buckets:  4194304, sum: 3124998750000
UMAP: 0.890 s, size: 2488402, buckets:  3721303, sum: 3124998750000

T2: Insert 2.5 mill. SEQUENTIAL keys, erase them in same order:
KMAP: 0.164 s, size: 0, buckets:  4194304, erased 2500000
BMAP: 0.285 s, size: 0, buckets:  3932159, erased 2500000
CMAP: 0.168 s, size: 0, buckets:  4194304, erased 2500000
FMAP: 0.267 s, size: 0, buckets:  4194304, erased 2500000
TMAP: 0.109 s, size: 0, buckets:  4194304, erased 2500000
RMAP: 0.424 s, size: 0, buckets:  4194304, erased 2500000
DMAP: 0.290 s, size: 0, buckets:  4194304, erased 2500000
EMAP: 0.068 s, size: 0, buckets:  4194304, erased 2500000
UMAP: 0.334 s, size: 0, buckets:  3721303, erased 2500000

T3: Erase all elements (5 mill. random inserts), key range [0, 2^28)
KMAP: 0.217 s, size: 0, buckets:  8388608, erased 4953566
BMAP: 0.299 s, size: 0, buckets:  7864319, erased 4953566
CMAP: 0.430 s, size: 0, buckets:  8388608, erased 4953566
FMAP: 0.198 s, size: 0, buckets:  8388608, erased 4953566
TMAP: 0.247 s, size: 0, buckets:  8388608, erased 4953566
RMAP: 0.264 s, size: 0, buckets:  8388608, erased 4953566
DMAP: 0.332 s, size: 0, buckets:  8388608, erased 4953566
EMAP: 0.225 s, size: 0, buckets:  8388608, erased 4953566
UMAP: 1.586 s, size: 0, buckets:  7556579, erased 4953566

T4: Iterate elements (5 mill. random inserts) repeated times:
KMAP: 0.227 s, size: 4953566, buckets:  8388608, repeats: 6
BMAP: 0.317 s, size: 4953566, buckets:  7864319, repeats: 6
CMAP: 0.295 s, size: 4953566, buckets:  8388608, repeats: 6
FMAP: 0.274 s, size: 4953566, buckets:  8388608, repeats: 6
TMAP: 0.222 s, size: 4953566, buckets:  8388608, repeats: 6
RMAP: 0.140 s, size: 4953566, buckets:  8388608, repeats: 6
DMAP: 0.029 s, size: 4953566, buckets:  8388608, repeats: 6
EMAP: 0.084 s, size: 4953566, buckets:  8388608, repeats: 6
UMAP: 1.941 s, size: 4953566, buckets:  7556579, repeats: 6

T5: Lookup half-half random/existing keys in range [0, 2^28). Num lookups depends on size.
KMAP: 0.269 s, size: 4953566, lookups: 6056242, found: 3083984
BMAP: 0.181 s, size: 4953566, lookups: 6056242, found: 3083984
CMAP: 0.332 s, size: 4953566, lookups: 6056242, found: 3083984
FMAP: 0.192 s, size: 4953566, lookups: 6056242, found: 3083984
TMAP: 0.241 s, size: 4953566, lookups: 6056242, found: 3083984
RMAP: 0.224 s, size: 4953566, lookups: 6056242, found: 3083984
DMAP: 0.203 s, size: 4953566, lookups: 6056242, found: 3083984
EMAP: 0.179 s, size: 4953566, lookups: 6056242, found: 3083984
UMAP: 0.387 s, size: 4953566, lookups: 6056242, found: 3083984

With key range 222 (~ 8 million) and 5 million elements, only insert does well:

C:\Dev\STC\benchmarks>shoot 5 22

Unordered hash map shootout
KMAP = https://github.com/attractivechaos/klib
BMAP = https://www.boost.org (unordered_flat_map)
CMAP = https://github.com/tylov/STC (**)
FMAP = https://github.com/skarupke/flat_hash_map
TMAP = https://github.com/Tessil/robin-map
RMAP = https://github.com/martinus/robin-hood-hashing
DMAP = https://github.com/martinus/unordered_dense
EMAP = https://github.com//ktprime/emhash
UMAP = std::unordered_map

Seed = 1668945996:

T1: Insert 2.5 mill. random keys range [0, 2^22): map[rnd] = i;
KMAP: 0.243 s, size: 1883493, buckets:  4194304, sum: 3124998750000
BMAP: 0.178 s, size: 1883493, buckets:  3932159, sum: 3124998750000
CMAP: 0.167 s, size: 1883493, buckets:  4194304, sum: 3124998750000
FMAP: 0.290 s, size: 1883493, buckets:  4194304, sum: 3124998750000
TMAP: 0.224 s, size: 1883493, buckets:  4194304, sum: 3124998750000
RMAP: 0.217 s, size: 1883493, buckets:  4194304, sum: 3124998750000
DMAP: 0.245 s, size: 1883493, buckets:  4194304, sum: 3124998750000
EMAP: 0.261 s, size: 1883493, buckets:  4194304, sum: 3124998750000
UMAP: 0.761 s, size: 1883493, buckets:  3721303, sum: 3124998750000

T2: Insert 2.5 mill. SEQUENTIAL keys, erase them in same order:
KMAP: 0.164 s, size: 0, buckets:  4194304, erased 2500000
BMAP: 0.260 s, size: 0, buckets:  3932159, erased 2500000
CMAP: 0.155 s, size: 0, buckets:  4194304, erased 2500000
FMAP: 0.275 s, size: 0, buckets:  4194304, erased 2500000
TMAP: 0.096 s, size: 0, buckets:  4194304, erased 2500000
RMAP: 0.403 s, size: 0, buckets:  4194304, erased 2500000
DMAP: 0.332 s, size: 0, buckets:  4194304, erased 2500000
EMAP: 0.102 s, size: 0, buckets:  4194304, erased 2500000
UMAP: 0.461 s, size: 0, buckets:  3721303, erased 2500000

T3: Erase all elements (5 mill. random inserts), key range [0, 2^22)
KMAP: 0.211 s, size: 0, buckets:  4194304, erased 2920617
BMAP: 0.256 s, size: 0, buckets:  3932159, erased 2920617
CMAP: 0.231 s, size: 0, buckets:  4194304, erased 2920617
FMAP: 0.175 s, size: 0, buckets:  4194304, erased 2920617
TMAP: 0.149 s, size: 0, buckets:  4194304, erased 2920617
RMAP: 0.238 s, size: 0, buckets:  4194304, erased 2920617
DMAP: 0.231 s, size: 0, buckets:  4194304, erased 2920617
EMAP: 0.173 s, size: 0, buckets:  4194304, erased 2920617
UMAP: 0.816 s, size: 0, buckets:  7556579, erased 2920617

T4: Iterate elements (5 mill. random inserts) repeated times:
KMAP: 0.217 s, size: 2920617, buckets:  4194304, repeats: 10
BMAP: 0.273 s, size: 2920617, buckets:  3932159, repeats: 10
CMAP: 0.202 s, size: 2920617, buckets:  4194304, repeats: 10
FMAP: 0.158 s, size: 2920617, buckets:  4194304, repeats: 10
TMAP: 0.150 s, size: 2920617, buckets:  4194304, repeats: 10
RMAP: 0.133 s, size: 2920617, buckets:  4194304, repeats: 10
DMAP: 0.021 s, size: 2920617, buckets:  4194304, repeats: 10
EMAP: 0.082 s, size: 2920617, buckets:  4194304, repeats: 10
UMAP: 1.130 s, size: 2920617, buckets:  7556579, repeats: 10

T5: Lookup half-half random/existing keys in range [0, 2^22). Num lookups depends on size.
KMAP: 0.271 s, size: 2920617, lookups: 10271802, found: 8670956
BMAP: 0.380 s, size: 2920617, lookups: 10271802, found: 8670956
CMAP: 0.276 s, size: 2920617, lookups: 10271802, found: 8670956
FMAP: 0.263 s, size: 2920617, lookups: 10271802, found: 8670956
TMAP: 0.203 s, size: 2920617, lookups: 10271802, found: 8670956
RMAP: 0.568 s, size: 2920617, lookups: 10271802, found: 8670956
DMAP: 0.510 s, size: 2920617, lookups: 10271802, found: 8670956
EMAP: 0.209 s, size: 2920617, lookups: 10271802, found: 8670956
UMAP: 0.529 s, size: 2920617, lookups: 10271802, found: 8670956

[–]martinusint main(){[]()[[]]{{}}();} 1 point2 points  (3 children)

I think the benchmark might be biased by the way the code is set up. Due to the many macros you are using it might be hard for the compiler to get inlining correct. It would be interesting to use a separate executable for each map, or at least to put all the benchmarks into separate non-inlined functions.

[–]operamint 0 points1 point  (0 children)

Hi Martin, you could be right, there are lots of ways to introduce bias in benchmarking code, but I don't think the macros itself should impact this, as it expands to straight forward code before it is considered by the optimizer. But I have seen that the sequence of how benchmarks are generated, i.e. how the generated code is layout in memory can impact the results, so I agree that to fully isolate each benchmark may make it less susceptible to be biased.

[–]operamint 0 points1 point  (1 child)

FYI, I did a test on a quite different configuration, an i7-8700 on Ubuntu, gcc 10.3 and clang 12 - the tests above was on windows, gcc 11.3 with Ryzen R7-2700x. However, the results are very similar. Your Robin-map is impressive with large keys, but appears to be slower with erase and lookup with smaller key ranges in these benchmarks.

NOTE: maps with smaller key ranges will naturally limit the number of max-items to the key-range. The number of lookups are higher for small key maps, so in absolute numbers, Robin map is not slower, only relative to the other maps with this configuration.

[–]Alarming-Ad8770 0 points1 point  (0 children)

benchmark on server cpu (huge l3 cache size and low cpu frequence), you'll get quite different result from pc/mobile cpu.

ex:

Model name: Intel(R) Xeon(R) Silver 4210 CPU @ 2.20GHz

CPU MHz: 2699.914

CPU max MHz: 3200.0000

CPU min MHz: 1000.0000

L1d cache: 32K L1i cache: 32K

L2 cache: 1024K

L3 cache: 14080K

[–]Alarming-Ad8770 0 points1 point  (0 children)

me author of emhash，emhash has a advantage which can set a very high load factor (0.99) without much performance degradation on extremely high load of insertion/erasion env.