Repository files navigation

Comprehensive benchmarks of C++ maps

Please see here.

1. Install dependencies for folly::F14, seehttps://github.com/facebook/folly/#ubuntu-1604-lts
2. Installninja andcmake

git clone --recurse-submodules https://github.com/martinus/map_benchmark.git./map_benchmark/tools/build.sh

git submodule update --force --remote

The implementation if the benchmark is open source, get it here:martinus/map_benchmark. It is split in several parts:

1. external: all map implementations available through github are added as git submodules here.
2. src/hashes: One directory for each hashing algorithm, each directory contains aHash.h which basically contains ausing instruction for the hash, e.g. like this:

template<classKey>using Hash = robin_hood::hash<Key>;

1. src/maps: One directory for each unordered map implementation, each directory contains aMap.h which basically contains ausing instruction for the map. It includesHash.h. E.g. like this:

#include"Hash.h"template<classKey,classVal>using Map = robin_hood::unordered_flat_map<Key, Val, Hash<Key>>;

1. Inexternal, add a submodule:

   cd externalgit submodule add -b master https://github.com/rigtorp/HashMap.git rigtorp__HashMap

2. Create a directory insrc/map/ with a fileHash.h. See the others for example.

• QHash: It's interface is too different to be easily includeable. e.g.iterator->first anditerator->second do not exist.
• rigtorp::HashMap: Doesn't have a default constructor

1. Runlscpu --extended to find out if you have hyperthreadding. E.g. for me it shows

   $ lscpu --extendedCPU NODE SOCKET CORE L1d:L1i:L2:L3 ONLINE MAXMHZ    MINMHZ0   0    0      0    0:0:0:0       yes    4600,0000 800,00001   0    0      1    1:1:1:0       yes    4600,0000 800,00002   0    0      2    2:2:2:0       yes    4600,0000 800,00003   0    0      3    3:3:3:0       yes    4600,0000 800,00004   0    0      4    4:4:4:0       yes    4600,0000 800,00005   0    0      5    5:5:5:0       yes    4600,0000 800,00006   0    0      0    0:0:0:0       yes    4600,0000 800,00007   0    0      1    1:1:1:0       yes    4600,0000 800,00008   0    0      2    2:2:2:0       yes    4600,0000 800,00009   0    0      3    3:3:3:0       yes    4600,0000 800,000010  0    0      4    4:4:4:0       yes    4600,0000 800,000011  0    0      5    5:5:5:0       yes    4600,0000 800,0000

2. Isolate a CPU with it's hyperthreading companion. I'm isolating CPU 5 and 11.
3. Edit/etc/default/grub and change GRUB_CMDLINE_LINUX_DEFAULT so it looks like this:

   GRUB_CMDLINE_LINUX_DEFAULT="quiet splash isolcpus=5,11 rcu_nocbs=5,11"

4. Runsudo update-grub
5. reboot
6. Editbench.rb so thetaskset -c ... prefix is correct.
7. Install Python moduleperf, seehttps://perf.readthedocs.io/en/latest/
8. Runsudo python3 -m perf system tune
9. Start the benchmarks:../tools/bench.rb |tee ../data/all_new.txt

Sources:

• https://wiki.ubuntuusers.de/GRUB_2/Konfiguration/
• https://perf.readthedocs.io/en/latest/system.html