c++ hash map

  1
  2
  3
  4
  5
  6
  7
  8
  9
 10
 11
 12
 13
 14
 15
 16
 17
 18
 19
 20
 21
 22
 23
 24
 25
 26
 27
 28
 29
 30
 31
 32
 33
 34
 35
 36
 37
 38
 39
 40
 41
 42
 43
 44
 45
 46
 47
 48
 49
 50
 51
 52
 53
 54
 55
 56
 57
 58
 59
 60
 61
 62
 63
 64
 65
 66
 67
 68
 69
 70
 71
 72
 73
 74
 75
 76
 77
 78
 79
 80
 81
 82
 83
 84
 85
 86
 87
 88
 89
 90
 91
 92
 93
 94
 95
 96
 97
 98
 99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143

// https://github.com/martinus/nanobench
// g++ -O2 -I../../include main.cpp -o m

#include <cstdint>
#define ANKERL_NANOBENCH_IMPLEMENT
#include <nanobench.h>

#include <unordered_map>
#include <emhash/hash_table7.hpp>
#include <emhash/hash_table8.hpp>
#include <util/str_util.hpp>

std::unordered_map<std::string, std::string> stl_map =
{
   {"stl_hash", "unordered_map"},
   {"stl_map", "stl_map"},
   {"fmap", "flat_map"},
   {"btree", "btree_map"},

   {"emhash2", "emhash2"},
   {"emhash3", "emhash3"},
   {"emhash4", "emhash4"},
   {"emhash5", "emhash5"},
   {"emhash6", "emhash6"},
   {"emhash7", "emhash7"},
   {"emhash8", "emhash8"},

   {"emilib2", "emilib2"},
   {"emilib1", "emilib1"},
   {"emilib3", "emilib3"},
   {"martind", "martin_dense"},
};

emhash7::HashMap<int, std::string> emhash7_map =
{
   {0, "unordered_map"},
   {1, "stl_map"},
   {2, "flat_map"},
   {3, "btree_map"},

   {4, "emhash2"},
   {5, "emhash3"},
   {6, "emhash4"},
   {7, "emhash5"},
   {8, "emhash6"},
   {9, "emhash7"},
   {10, "emhash8"},

   {11, "emilib2"},
   {12, "emilib1"},
   {13, "emilib3"},
   {14, "martin_dense"},
};

emhash8::HashMap<std::string, std::string> emhash8_map =
{
   {"stl_hash", "unordered_map"},
   {"stl_map", "stl_map"},
   {"fmap", "flat_map"},
   {"btree", "btree_map"},

   {"emhash2", "emhash2"},
   {"emhash3", "emhash3"},
   {"emhash4", "emhash4"},
   {"emhash5", "emhash5"},
   {"emhash6", "emhash6"},
   {"emhash7", "emhash7"},
   {"emhash8", "emhash8"},

   {"emilib2", "emilib2"},
   {"emilib1", "emilib1"},
   {"emilib3", "emilib3"},
   {"martind", "martin_dense"},
};

emhash8::HashMap<int64_t, std::string> emhash8_map_int64 =
{
   {snail::str2i64("stl_hash"), "unordered_map"},
   {snail::str2i64("stl_map"), "stl_map"},
   {snail::str2i64("fmap"), "flat_map"},
   {snail::str2i64("btree"), "btree_map"},

   {snail::str2i64("emhash2"), "emhash2"},
   {snail::str2i64("emhash3"), "emhash3"},
   {snail::str2i64("emhash4"), "emhash4"},
   {snail::str2i64("emhash5"), "emhash5"},
   {snail::str2i64("emhash6"), "emhash6"},
   {snail::str2i64("emhash7"), "emhash7"},
   {snail::str2i64("emhash8"), "emhash8"},

   {snail::str2i64("emilib2"), "emilib2"},
   {snail::str2i64("emilib1"), "emilib1"},
   {snail::str2i64("emilib3"), "emilib3"},
   {snail::str2i64("martind"), "martin_dense"},
};

int main(int, char**)
{
    ankerl::nanobench::Bench().run("stl_map", [&]()
    {
        auto itor = stl_map.find("stl_hash");
        if (stl_map.end() != itor)
        {}
    });

    ankerl::nanobench::Bench().run("emhash7_map", [&]()
    {
        auto itor = emhash7_map.find(0);
        if (emhash7_map.end() != itor)
        {}

        ankerl::nanobench::doNotOptimizeAway(itor);
    });

    ankerl::nanobench::Bench().run("emhash8_map::find", [&]()
    {
        auto itor = emhash8_map.find("emhash8");
        if (emhash8_map.end() != itor)
        {}

        ankerl::nanobench::doNotOptimizeAway(itor);
    });

    ankerl::nanobench::Bench().run("emhash8_map_int64::find", [&]()
    {
        auto itor = emhash8_map_int64.find(snail::str2i64("emhash8"));
        if (emhash8_map_int64.end() != itor)
        {}

        ankerl::nanobench::doNotOptimizeAway(itor);
    });

    ankerl::nanobench::Bench().run("emhash8_map::try_get", [&]()
    {
        auto e = emhash8_map.try_get("emhash8");
        if (e)
        {}

        ankerl::nanobench::doNotOptimizeAway(e);
    });

    return 0;
}

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15

Warning, results might be unstable:
* CPU frequency scaling enabled: CPU 0 between 800.0 and 4,500.0 MHz
* CPU governor is 'powersave' but should be 'performance'
* Turbo is enabled, CPU frequency will fluctuate

Recommendations
* Use 'pyperf system tune' before benchmarking. See https://github.com/psf/pyperf

|               ns/op |                op/s |    err% |     total | benchmark
|--------------------:|--------------------:|--------:|----------:|:----------
|               11.97 |       83,558,711.04 |    0.1% |      0.01 | `stl_map`
|                4.82 |      207,602,617.74 |    0.7% |      0.01 | `emhash7_map`
|                8.60 |      116,226,532.44 |    4.9% |      0.01 | `emhash8_map::find`
|                7.01 |      142,642,133.00 |    1.4% |      0.01 | `emhash8_map_int64::find`
|               10.67 |       93,758,813.86 |    2.0% |      0.01 | `emhash8_map::try_get`