c++ hash map

william

2024-06-22 约 900 字预计阅读 2 分钟

我们在组织不同信号、不同策略时，往往需要一个容器存放对应合约标识的容器。这个容器要求具有一定的扩展性（即事先无法知晓容器大小），具有良好的插入效率、以及较高性能的查找性能。对于一般的算法，我们直接使用标准库里的哈希容器即可，这包括 std::unordered_map。

然后，对于一个低延迟的交易系统，我们总是对性能有着极致的渴望，尽力开发性的数据容器，提升查找性能。

1. 对于特化容器，如 <int, typename T>，可以更加快速的实现查找
1. 对于较大对象，如 <std::string, typename T>, 则尽量避免运行期的构造开销，例如在确认不同的合约标识肯定的唯一情况下，可以大胆使用类型转化，直接 cast 为 int 类型。

代码测试

  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`