search

skarupke / flat_hash_map

A very fast hashtable
1.69k stars 186 forks source link

Beat the fastest implementation of the benchmark's game k-nucleotide benchmark #4

Open gnzlbg opened 7 years ago

gnzlbg commented 7 years ago

Scott wrote here: 

It would be nice to add some more maps to the tests because it doesn’t seem to be the fastest one.

I took the k-nucleotide test which has a heavy read load on a hash map (http://benchmarksgame.alioth.debian.org/u64q/program.php?test=knucleotide&lang=gpp&id=3) and changed the `unsigned N = sysconf (_SC_NPROCESSORS_ONLN);` to `unsigned N = 1;` to make it runs on one core only.

g++ -O3 -std=c++14 knucleotide.cpp -o knucleotide -lpthread
time ./knucleotide < input25000000.txt

__gnu_pbds::cc_hash_table: 0m18.297s
std::unordered_map: 0m38.767s
tsl::hopscotch_map (seems to do well from a post on reddit): 0m19.288s
ska::flat_hash_map: 0m25.177s
ska::flat_hash_map power of two: 0m24.454s

Couldn't make it work with google::dense_hash_map.
chadbrewbaker commented 6 years ago

Let me look into this. Could be some interesting SIMD here too for stream loading.