map_benchmark

Comprehensive benchmarks of C++ maps

Results

Please see here.

building

1. Install dependencies for folly::F14, see https://github.com/facebook/folly/#ubuntu-1604-lts
2. Install ninja and cmake

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

Updating Submodules

git submodule update --force --remote 

Sourcecode Layout

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 a Hash.h which basically contains a using 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 a Map.h which basically contains a using instruction for the map. It includes Hash.h. E.g. like this:

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

Add a new Hashmap

1. In external, add a submodule:

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

2. Create a directory in src/map/ with a file Hash.h. See the others for example.

Maps I couldn't add

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

Reliable Benchmarks

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

   $ lscpu --extended
   CPU NODE SOCKET CORE L1d:L1i:L2:L3 ONLINE MAXMHZ MINMHZ
   0 0 0 0 0:0:0:0 yes 4600,0000 800,0000
   1 0 0 1 1:1:1:0 yes 4600,0000 800,0000
   2 0 0 2 2:2:2:0 yes 4600,0000 800,0000
   3 0 0 3 3:3:3:0 yes 4600,0000 800,0000
   4 0 0 4 4:4:4:0 yes 4600,0000 800,0000
   5 0 0 5 5:5:5:0 yes 4600,0000 800,0000
   6 0 0 0 0:0:0:0 yes 4600,0000 800,0000
   7 0 0 1 1:1:1:0 yes 4600,0000 800,0000
   8 0 0 2 2:2:2:0 yes 4600,0000 800,0000
   9 0 0 3 3:3:3:0 yes 4600,0000 800,0000
   10 0 0 4 4:4:4:0 yes 4600,0000 800,0000
   11 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. Run sudo update-grub
5. reboot
6. Edit bench.rb so the taskset -c ... prefix is correct.
7. Install Python module perf, see https://perf.readthedocs.io/en/latest/
8. Run sudo 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