search

skarupke / flat_hash_map

A very fast hashtable
1.69k stars 186 forks source link

Benchmark against tsl::hopscotch map #3

Open gnzlbg opened 7 years ago

gnzlbg commented 7 years ago

Benchmark against @Tessil 's hopscotch-map.

/u/rtessil wrote here:

I Wrote The Fastest Hashtable Really interesting article, but the title is a bit of a stretch no?

I quickly compared ska::flat_hash_map (with prime and power of two) to the tsl::hopscotch_map I wrote. The performances are roughly the same (a bit faster for the power of two version on integers but slower on small std::string, no indirection as they are small enough for SSO). The main difference is that ska::flat_hash_map and ska::flat_hash_map with power of two need, respectively, ~50% and ~100% more memory than tsl::hopscotch_map (raw results:

And provided these benchmarks (description):

# For a description of each test see https://tessil.github.io/2016/08/29/benchmark-hopscotch-map.html
# bench type, nb elements, hash_map, vsz memory, rss memory, nb seconds
sequential,5000000,hopscotch_map,214777856,204021760,0.205127
sequential,5000000,ska_flat_hash_map,329515008,318545920,0.295789
sequential,5000000,ska_flat_hash_map_power_of_two,416067584,405176320,0.333548
sequential,10000000,hopscotch_map,416104448,405319680,0.407490
sequential,10000000,ska_flat_hash_map,645595136,634777600,0.587404
sequential,10000000,ska_flat_hash_map_power_of_two,818720768,807858176,0.662674
sequentialread,5000000,hopscotch_map,214777856,203988992,0.023264
sequentialread,5000000,ska_flat_hash_map,329515008,318726144,0.023356
sequentialread,5000000,ska_flat_hash_map_power_of_two,416067584,405282816,0.015604
sequentialread,10000000,hopscotch_map,416104448,405188608,0.047545
sequentialread,10000000,ska_flat_hash_map,645595136,634810368,0.046600
sequentialread,10000000,ska_flat_hash_map_power_of_two,818720768,807870464,0.031345
randomshufflerange,5000000,hopscotch_map,214777856,204120064,0.565164
randomshufflerange,5000000,ska_flat_hash_map,329515008,318472192,0.561359
randomshufflerange,5000000,ska_flat_hash_map_power_of_two,416067584,405020672,0.611901
randomshufflerange,10000000,hopscotch_map,416104448,405102592,1.149926
randomshufflerange,10000000,ska_flat_hash_map,645595136,634875904,1.136794
randomshufflerange,10000000,ska_flat_hash_map_power_of_two,818720768,807903232,1.236914
randomshufflerangeread,5000000,hopscotch_map,214777856,203952128,0.111159
randomshufflerangeread,5000000,ska_flat_hash_map,329515008,318545920,0.112118
randomshufflerangeread,5000000,ska_flat_hash_map_power_of_two,416067584,405213184,0.091952
randomshufflerangeread,10000000,hopscotch_map,416104448,405262336,0.228280
randomshufflerangeread,10000000,ska_flat_hash_map,645595136,634765312,0.228594
randomshufflerangeread,10000000,ska_flat_hash_map_power_of_two,818720768,807649280,0.189817
randomfull,5000000,hopscotch_map,214777856,203980800,0.741374
randomfull,5000000,ska_flat_hash_map,329515008,318652416,0.848784
randomfull,5000000,ska_flat_hash_map_power_of_two,416067584,405086208,0.721192
randomfull,10000000,hopscotch_map,416104448,405307392,1.511382
randomfull,10000000,ska_flat_hash_map,645595136,634781696,1.775507
randomfull,10000000,ska_flat_hash_map_power_of_two,818720768,807870464,1.461587
randomfullread,5000000,hopscotch_map,214777856,203935744,0.166661
randomfullread,5000000,ska_flat_hash_map,329515008,318492672,0.155278
randomfullread,5000000,ska_flat_hash_map_power_of_two,416067584,405176320,0.125470
randomfullread,10000000,hopscotch_map,416104448,405381120,0.348137
randomfullread,10000000,ska_flat_hash_map,645595136,634703872,0.331349
randomfullread,10000000,ska_flat_hash_map_power_of_two,818720768,807993344,0.275156
randomfullreadmiss,5000000,hopscotch_map,214777856,204025856,0.183873
randomfullreadmiss,5000000,ska_flat_hash_map,329515008,318795776,0.184358
randomfullreadmiss,5000000,ska_flat_hash_map_power_of_two,416067584,405172224,0.158098
randomfullreadmiss,10000000,hopscotch_map,416104448,405348352,0.394217
randomfullreadmiss,10000000,ska_flat_hash_map,645595136,634699776,0.375168
randomfullreadmiss,10000000,ska_flat_hash_map_power_of_two,818720768,808001536,0.329822
iteration,5000000,hopscotch_map,214777856,203878400,0.044455
iteration,5000000,ska_flat_hash_map,329515008,318664704,0.069848
iteration,5000000,ska_flat_hash_map_power_of_two,416067584,405041152,0.073894
iteration,10000000,hopscotch_map,416104448,405123072,0.089261
iteration,10000000,ska_flat_hash_map,645595136,634687488,0.140058
iteration,10000000,ska_flat_hash_map_power_of_two,818720768,807886848,0.148142
delete,5000000,hopscotch_map,214777856,204013568,0.221552
delete,5000000,ska_flat_hash_map,329515008,318623744,0.194737
delete,5000000,ska_flat_hash_map_power_of_two,416067584,405102592,0.155010
delete,10000000,hopscotch_map,416104448,405127168,0.476158
delete,10000000,ska_flat_hash_map,645595136,634785792,0.427231
delete,10000000,ska_flat_hash_map_power_of_two,818720768,807890944,0.363406
insertsmallstring,5000000,hopscotch_map,416100352,405565440,1.860058
insertsmallstring,5000000,ska_flat_hash_map,645595136,634609664,2.281131
insertsmallstring,5000000,ska_flat_hash_map_power_of_two,818720768,807956480,2.103567
insertsmallstring,10000000,hopscotch_map,818753536,808095744,3.881970
insertsmallstring,10000000,ska_flat_hash_map,1277755392,1266814976,4.807635
insertsmallstring,10000000,ska_flat_hash_map_power_of_two,1624027136,1613348864,4.331490
readsmallstring,5000000,hopscotch_map,416100352,405331968,1.129693
readsmallstring,5000000,ska_flat_hash_map,645595136,634679296,1.181751
readsmallstring,5000000,ska_flat_hash_map_power_of_two,818720768,807985152,1.220172
readsmallstring,10000000,hopscotch_map,818753536,807899136,2.476885
readsmallstring,10000000,ska_flat_hash_map,1277755392,1266974720,2.573642
readsmallstring,10000000,ska_flat_hash_map_power_of_two,1624027136,1613090816,2.565422
readsmallstringmiss,5000000,hopscotch_map,416100352,405188608,1.123353
readsmallstringmiss,5000000,ska_flat_hash_map,645595136,634871808,1.166329
readsmallstringmiss,5000000,ska_flat_hash_map_power_of_two,818720768,808042496,1.174861
readsmallstringmiss,10000000,hopscotch_map,818753536,808058880,2.341009
readsmallstringmiss,10000000,ska_flat_hash_map,1277755392,1266839552,2.549118
readsmallstringmiss,10000000,ska_flat_hash_map_power_of_two,1624027136,1613049856,2.503907
deletesmallstring,5000000,hopscotch_map,416100352,405569536,1.176642
deletesmallstring,5000000,ska_flat_hash_map,645595136,634609664,1.198479
deletesmallstring,5000000,ska_flat_hash_map_power_of_two,818720768,808034304,1.175356
deletesmallstring,10000000,hopscotch_map,818753536,807882752,2.451259
deletesmallstring,10000000,ska_flat_hash_map,1277755392,1267023872,2.659608
deletesmallstring,10000000,ska_flat_hash_map_power_of_two,1624027136,1613295616,2.585078
insertstring,5000000,hopscotch_map,814391296,803540992,3.284603
insertstring,5000000,ska_flat_hash_map,1043988480,1033060352,3.503130
insertstring,5000000,ska_flat_hash_map_power_of_two,1217126400,1206075392,3.535146
insertstring,10000000,hopscotch_map,1617141760,1606082560,6.957676
insertstring,10000000,ska_flat_hash_map,2076110848,2065018880,7.598840
insertstring,10000000,ska_flat_hash_map_power_of_two,2422394880,2411331584,7.648912
readstring,5000000,hopscotch_map,814391296,803512320,2.277258
readstring,5000000,ska_flat_hash_map,1043988480,1033179136,2.329161
readstring,5000000,ska_flat_hash_map_power_of_two,1217126400,1206403072,2.267905
readstring,10000000,hopscotch_map,1617141760,1606356992,5.113229
readstring,10000000,ska_flat_hash_map,2076110848,2065104896,5.224593
readstring,10000000,ska_flat_hash_map_power_of_two,2422394880,2411315200,4.914819
readstringmiss,5000000,hopscotch_map,814391296,803504128,1.778059
readstringmiss,5000000,ska_flat_hash_map,1043988480,1033183232,1.759323
readstringmiss,5000000,ska_flat_hash_map_power_of_two,1217126400,1206112256,1.700586
readstringmiss,10000000,hopscotch_map,1617141760,1606344704,3.066333
readstringmiss,10000000,ska_flat_hash_map,2076110848,2065137664,3.337325
readstringmiss,10000000,ska_flat_hash_map_power_of_two,2422394880,2411384832,3.240746
deletestring,5000000,hopscotch_map,814391296,803745792,2.398370
deletestring,5000000,ska_flat_hash_map,1043988480,1032884224,2.618392
deletestring,5000000,ska_flat_hash_map_power_of_two,1216991232,1206231040,2.339883
deletestring,10000000,hopscotch_map,1617141760,1606242304,5.210573
deletestring,10000000,ska_flat_hash_map,2076110848,2065301504,5.291985
deletestring,10000000,ska_flat_hash_map_power_of_two,2422394880,2411339776,5.238803