Skip to content

Latest commit

 

History

History
90 lines (71 loc) · 3.67 KB

README.md

File metadata and controls

90 lines (71 loc) · 3.67 KB
Raw

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 <class Key>
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 <class Key, class Val>
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: