加入我的hash_map

[ktprime]

https://github.com/ktprime/emhash
其中
emhash7 整数类型k.v速度比较快，负载因子load_factor 可以设置接近1.0
emhash8 是dense_hash_map 实现，迭代，非整数类型k.v 以及查找命中不错性能 , 删除比较慢

[ktprime]

/home/huangyuanbing1/hashmap-benchmark/3rd_party/jstd_hashmap/src/jstd/support/BitUtils.h: In static member function ‘static unsigned int jstd::BitUtils::popcnt64(uint64_t)’:
/home/huangyuanbing1/hashmap-benchmark/3rd_party/jstd_hashmap/src/jstd/support/BitUtils.h:392:9: error: ‘__int64’ was not declared in this scope
__int64 popcount = _mm_popcnt_u64(x);
^~~~~~~
/home/huangyuanbing1/hashmap-benchmark/3rd_party/jstd_hashmap/src/jstd/support/BitUtils.h:392:9: note: suggested alternative: ‘__int64_t’
__int64 popcount = _mm_popcnt_u64(x);
^~~~~~~
__int64_t
/home/huangyuanbing1/hashmap-benchmark/3rd_party/jstd_hashmap/src/jstd/support/BitUtils.h:393:30: error: ‘popcount’ was not declared in this scope
return (unsigned int)popcount;
^~~~~~~~
/home/huangyuanbing1/hashmap-benchmark/3rd_party/jstd_hashmap/src/jstd/support/BitUtils.h:393:30: note: suggested alternative: ‘popcnt’
return (unsigned int)popcount;
^~~~~~~~

[ktprime]

---

hash_map<int, int>

std::unordered_map<K, V> sum = 3000064 time: 29.906 ms
jstd::flat16_hash_map<K, V> sum = 3000064 time: 1299.420 ms
std::unordered_map<K, V> sum = 3000064 time: 30.020 ms
jstd::flat16_hash_map<K, V> sum = 3000064 time: 1679.443 ms
std::unordered_map<K, V> sum = 0 time: 51.004 ms
jstd::flat16_hash_map<K, V> sum = 0 time: 5.989 ms
std::unordered_map<K, V> sum = 0 time: 29.767 ms
jstd::flat16_hash_map<K, V> sum = 0 time: 7.147 ms
std::unordered_map<K, V> sum = 3000064 time: 182.110 ms
jstd::flat16_hash_map<K, V> sum = 2203172 time: 480.287 ms
std::unordered_map<K, V> sum = 3000064 time: 145.865 ms
jstd::flat16_hash_map<K, V> sum = 2250048 time: 466.021 ms
std::unordered_map<K, V> sum = 3000064 time: 117.878 ms
jstd::flat16_hash_map<K, V> sum = 2250048 time: 280.871 ms
std::unordered_map<K, V> sum = 3000064 time: 184.274 ms
jstd::flat16_hash_map<K, V> sum = 1476594 time: 247.255 ms
std::unordered_map<K, V> sum = 3000064 time: 146.906 ms
jstd::flat16_hash_map<K, V> sum = 2203172 time: 160.230 ms
std::unordered_map<K, V> sum = 3000064 time: 115.932 ms
jstd::flat16_hash_map<K, V> sum = 2250048 time: 99.124 ms
std::unordered_map<K, V> sum = 3000064 time: 98.451 ms
jstd::flat16_hash_map<K, V> sum = 1406280 time: 155.598 ms
std::unordered_map<K, V> sum = 3000064 time: 107.490 ms
jstd::flat16_hash_map<K, V> sum = 3281302 time: 77.424 ms
std::unordered_map<K, V> sum = 6000128 time: 57.493 ms
jstd::flat16_hash_map<K, V> sum = 4500096 time: 21.264 ms
std::unordered_map<K, V> sum = 1175704062 time: 366.389 ms
*** Error in `./bin/benchmark': free(): invalid pointer: 0x00000000006e1710 ***
======= Backtrace: =========
/lib/x86_64-linux-gnu/libc.so.6(+0x777f5)[0x7ffff74887f5]
/lib/x86_64-linux-gnu/libc.so.6(+0x8038a)[0x7ffff749138a]
/lib/x86_64-linux-gnu/libc.so.6(cfree+0x4c)[0x7ffff749558c]
./bin/benchmark[0x417743]
./bin/benchmark[0x44197d]
./bin/benchmark[0x4086a3]
./bin/benchmark[0x402164]
/lib/x86_64-linux-gnu/libc.so.6(__libc_start_main+0xf0)[0x7ffff7431840]
./bin/benchmark[0x4023d9]
======= Memory map: ========
00400000-0048c000 r-xp 00000000 08:01 274668 /home/huangyuanbing1/hashmap-benchmark/bin/benchmark
0068b000-0068c000 r--p 0008b000 08:01 274668 /home/huangyuanbing1/hashmap-benchmark/bin/benchmark
0068c000-0068d000 rw-p 0008c000 08:01 274668 /home/huangyuanbing1/hashmap-benchmark/bin/benchmark
0068d000-00742000 rw-p 00000000 00:00 0 [heap]
7ffff0000000-7ffff0021000 rw-p 00000000 00:00 0
7ffff0021000-7ffff4000000 ---p 00000000 00:00 0
7ffff7108000-7ffff7210000 r-xp 00000000 08:01 666278 /lib/x86_64-linux-gnu/libm-2.23.so
7ffff7210000-7ffff740f000 ---p 00108000 08:01 666278 /lib/x86_64-linux-gnu/libm-2.23.so
7ffff740f000-7ffff7410000 r--p 00107000 08:01 666278 /lib/x86_64-linux-gnu/libm-2.23.so
7ffff7410000-7ffff7411000 rw-p 00108000 08:01 666278 /lib/x86_64-linux-gnu/libm-2.23.so
7ffff7411000-7ffff75d1000 r-xp 00000000 08:01 666319 /lib/x86_64-linux-gnu/libc-2.23.so
7ffff75d1000-7ffff77d1000 ---p 001c0000 08:01 666319 /lib/x86_64-linux-gnu/libc-2.23.so
7ffff77d1000-7ffff77d5000 r--p 001c0000 08:01 666319 /lib/x86_64-linux-gnu/libc-2.23.so
7ffff77d5000-7ffff77d7000 rw-p 001c4000 08:01 666319 /lib/x86_64-linux-gnu/libc-2.23.so
7ffff77d7000-7ffff77db000 rw-p 00000000 00:00 0
7ffff77db000-7ffff77f2000 r-xp 00000000 08:01 660212 /lib/x86_64-linux-gnu/libgcc_s.so.1
7ffff77f2000-7ffff79f1000 ---p 00017000 08:01 660212 /lib/x86_64-linux-gnu/libgcc_s.so.1
7ffff79f1000-7ffff79f2000 r--p 00016000 08:01 660212 /lib/x86_64-linux-gnu/libgcc_s.so.1
7ffff79f2000-7ffff79f3000 rw-p 00017000 08:01 660212 /lib/x86_64-linux-gnu/libgcc_s.so.1
7ffff79f3000-7ffff7bc6000 r-xp 00000000 08:01 1449964 /usr/lib/x86_64-linux-gnu/libstdc++.so.6.0.28
7ffff7bc6000-7ffff7dc6000 ---p 001d3000 08:01 1449964 /usr/lib/x86_64-linux-gnu/libstdc++.so.6.0.28
7ffff7dc6000-7ffff7dd1000 r--p 001d3000 08:01 1449964 /usr/lib/x86_64-linux-gnu/libstdc++.so.6.0.28
7ffff7dd1000-7ffff7dd4000 rw-p 001de000 08:01 1449964 /usr/lib/x86_64-linux-gnu/libstdc++.so.6.0.28
7ffff7dd4000-7ffff7dd7000 rw-p 00000000 00:00 0
7ffff7dd7000-7ffff7dfd000 r-xp 00000000 08:01 666250 /lib/x86_64-linux-gnu/ld-2.23.so
7ffff7fe0000-7ffff7fe6000 rw-p 00000000 00:00 0
7ffff7ff7000-7ffff7ff8000 rw-p 00000000 00:00 0
7ffff7ff8000-7ffff7ffa000 r--p 00000000 00:00 0 [vvar]
7ffff7ffa000-7ffff7ffc000 r-xp 00000000 00:00 0 [vdso]
7ffff7ffc000-7ffff7ffd000 r--p 00025000 08:01 666250 /lib/x86_64-linux-gnu/ld-2.23.so
7ffff7ffd000-7ffff7ffe000 rw-p 00026000 08:01 666250 /lib/x86_64-linux-gnu/ld-2.23.so
7ffff7ffe000-7ffff7fff000 rw-p 00000000 00:00 0
7ffffffde000-7ffffffff000 rw-p 00000000 00:00 0 [stack]
ffffffffff600000-ffffffffff601000 r-xp 00000000 00:00 0 [vsyscall]
Aborted (core dumped)

[shines77]

谢谢反馈，已经修复了 BitUtils.h 的问题。

今天下午在改进和修复 jstd::flat16_hash_map 的问题，把 load_factor 改为 0.75，有时候特别慢，改回 0.5 了。

jstd::unordered_map (也就是原来的 jstd::Dictionary，链表法的哈希表) 已经重构了一半，但是我想了一下，还是罗宾汉哈希算法(Robin Hood)更快一点，也想好了怎么用硬件加速 Robin Hood 算法。

目前的 jstd::flat16_hash_map 依然采用的是跟 Google 的 absl::flat_hash_map 类似的 Swiss Table 算法，不过已经比上一版的 jstd::v1::flat16_hash_map 快了一些，除了没有使用二次探测法，其他跟 absl::flat_hash_map 比较接近了，absl::flat_hash_map 考虑得比较周全一点，我也在吸收和完善。这对后面写 Robin Hood 的哈希表也是有用的。

我已经想好了下一个版本的 jstd::flat16_hash_map 改进方法，改完以后就开始写 Robin Hood 法的哈希表，jstd::unordered_map 链表法可能要放很后面，我已经想好了思路，但是实现起来比较麻烦。

因为最近都在忙着 jstd::unordered_map，比较累（主要是思考设计思路累），所以没空加别的哈希表进 benchmark，可以的话，我想把你的哈希表和你推荐的 benchmark 中表现比较优异的 tsl::robin_map，其实如果哈希表没什么依赖库，是 header-only 的话，加进去是很简单的。不过由于目前我的代码也还不稳定，所以也不是很急。我在加入 abseil 库的时候，真的是被其编译的繁琐感到厌恶，而且 abseil 的文档很多没更新，编译和使用方法都得自己摸索。

另外，重构中的 jstd::unordered_map 中的 kDetectStoreHash 的判定，我觉得比 tsl::robin_map 的判断更合理，他这个设计思路，跟我是不谋而合的，也是我重构的主要目标之一，但是我考虑得比他更全面一点，我还考虑了 Key，Value 值的 inline 的问题，即是直接保存 Key 或 Value 的值，还是保存 Key，Value 的值的指针，这在 Key，Value 是大对象的时候有用，具体我是这样定义的，我定义了一个内存布局的策略 layout_policy，如下所示。但 Key，Value 的 inline 我暂未实现，因为代码量比较大：

template <typename Key, typename Value>
struct layout_policy {
    static constexpr bool isAutoDetectPairLayout = true;
    static constexpr bool keyValueIsIsolated = false;

    static constexpr bool isAutoDetectKeyInlined = true;
    static constexpr bool keyIsInlined = true;

    static constexpr bool isAutoDetectValueInlined = true;
    static constexpr bool valueIsInlined = true;

    static constexpr bool isAutoDetectStoreHash = true;
    static constexpr bool needStoreHash = true;
};

[ktprime]

目前关注 https://github.com/martinus/map_benchmark 测试
数据和结论快出来，算是一个比较权威全面的测试，不足在于作者只在cpu 8700上跑
没有测试服务器cpu 和其他处理器（arm m1 ）以及其他编译器

[shines77]

最近写 jstd::flat16_hash_map，一直都是在一台 AMD EPYC 7K62 48核 的云服务器（2核4G）上测试的，昨天我换到另一台 Intel Xeon Platinum 8255C 24核 的云服务器（同样也是2核4G）上测试了一下，发现 jstd::flat16_hash_map 在跑 ./bin/cardinal_bench 的时候慢了很多，最高的基数下由 2750+ms, 2950+ms 变为 5200+ms, 5400+ms，ska::flat_hah_map 和 absl::flat_hash_map 的耗时增加得很少。这说明，我现在这个版本的 jstd::flat16_hash_map 对于缓存的使用量还是高于后两者的，我猜主要的原因是 insert() 的时候，由于 EmptySlot 分布不好，搜索的长度太长了，看来换成 absl::flat_hash_map 的两次探测法还是很有必要的。

AMD EPYC 7K62 48核 那台云服务器，今天我 google 了一下（以前我搜过，但没找到），才发现这个CPU的三级缓存是 192 MB，着实比我预想的要大很多。Intel Xeon Platinum 8255C（24核）的三级缓存只有 36 MB左右，就算平摊到每个核心上的三级缓存，前者也比后者多一倍多（4 比 1.5）。前者的内存频率是 3200 MHz，后者的内存是 2933 MHz，所以总体性能，肯定是 AMD EPYC 7K62 要更好一点，但没有普遍性，Intel Xeon Platinum 8255C 这款CPU在 Intel 的服务器 CPU 里也不算是高档的，属于中等或中低配置吧，但可能更具有普遍性一点，一般的服务器更接近这样的硬件条件。

目前这个版本的 jstd::flat16_hash_map 的关于 Controls 的循环镜像是我测试的一个版本，比上一个不做循环镜像的版本慢了 5-10%，其实不做 Controls 的循环镜像也能用，但极端情况下，可能会有 bug。absl::flat_hash_map 也做了循环镜像的，他的实现方式更好一点，我也想好了怎么实现，跟他有一点细微的差别，我觉得我的方案更好一点。目前版本的 jstd::flat16_hash_map 在缓存足够的情况下，是比 absl::flat_hash_map 快的。但是 absl::flat_hash_map 是用记录剩余 EmptySlot 的个数来判断是否需要 grow() 扩容的，他这种方式更合理一点，因为在 insert 和 erase 都同时进行的时候，可能会留下很多 Deleted Slot，充满整个 Slot 位，导致无法 insert，如果只判断 size() / capacity() > max_load_factor 才扩容，就会导致无法插入，又不会扩容的情况。这是采用 Swiss Table 这种方式不可避免的情况，所以我也将这么实现，没办法绕过，但是这样做了以后，insert 和 erase 的性能会下降一点点，因为要处理 EmptySlot 的增减，记录剩下的个数。

所以，纵观来看，Swiss Table 这种方式看似很棒，实际上问题很多，Google 的 absl::flat_hash_map 也在修修补补下变成目前这个版本的样子，还是 Robin Hood 的方式更好，它搜索的时候，搜索的长度不依赖于 EmptySlot，可能会更早提前结束，虽然在更新 Distance 的时候，看起来效率不高，但是是值得的，而且我也想好了，它也可以加入类似 Swiss Table 的 Control Byte 的同时（硬件指令），也可以使用硬件指令来更新和判断 Distance，我想应该会取得比 ska::flat_hash_map 更好的效果，能不能超过 tsl::robin_map，目前还不知道，我目前的目标是超过 ska::flat_hash_map 。

[ktprime]

我想基于swiss table 实现dense hash map。内存利用率可以提高但查询可能会慢一点。每次只能搜索4个（avx2 8个）位置
目前我的hashmap 实现是集中式（也有分离式emhash8 8bye metadata），metadata和k.v在一个slot上，查询miss 性能只有robin hood一半，查命中快30% 没有使用墓碑方案。频繁插入删除性能不受影响

[shines77]

目前关注 https://github.com/martinus/map_benchmark 测试 测试数据和结论快出来，算是一个比较权威全面的测试，不足作者只在他自己8700上跑 没有考虑服务器cpu 和其他处理器（arm m1 ）以及其他编译器

https://github.com/martinus/map_benchmark 的测试我看过了的，他 blog 上的图表我也看过了，github 上的测试代码我也看过了，有一定的科学性，大多数都没有什么问题，但是我也看到有不够合理的地方。另外，由于我的云服务器基本都只有4G的内存，所以我不会直接采用他的代码。稍后一点，我会基于他的测试代码，改进一下，放进这个 hashmap_benchmark 仓库里，我会把所有的哈希表的总使用内存都控制在 2-3G 左右，基于我的理解改进一下。

在最近的写代码和 benchmark 过程中，我也有了更多的理解，也在不断的改进之前的测试代码，稍后还会继续改进，我已经有了一套更合理和完整测试方式，当然是在基于目前的测试扩展的。我在测试的过程中也发现了 absl::flat_hash_map 在极端的情况下，会变得很慢的情况，主要的原因是它采用了比较高的 load_factor (约为 7/8 = 0.875)，ska::flat_hash_map 为了提高性能，采用了 0.5 的 load_factor，还是比较有效的，我目前版本的 jstd::flat16_hash_map 也是只能采用 0.5，高了某些情况下会有点慢。absl::flat_hash_map 改为 0.5 可能更好，但 Google 是为了省内存，而且他的 load_factor 是代码里写死的，所以他又弄出来一个整理 Deleted Slot 的方法。

我的基数测试（cardinal_bench），是参考这个写的，HashTable性能测试(CK/phmap/ska)

它只做了 insert(), insert 已经存在的值近似为 find()，所以它相当于测试了 insert 和 find。所以我也联想到，可以基于这个基数测试的方法，同时增加 find(), insert(), erase()，在随机数据生成的时候，也同时随机选择这三种操作，模拟实际使用中的随机 find, insert, erase 事件，基于不用的基数进行测试。

关于低基数，可以参考 ClickHouse 的低基数字段优化：ClickHouse中的低基数字段优化

所以基数测试大概是这么来的。

[ktprime]

简单的测试数据 https://github.com/ktprime/emhash/blob/master/bench/qbench-out.txt
为了测试方便我所有第三方库最大负载因子设置为0.88

大量第三方测试基于一组数据，我采用不用负载因子多组（500）数据，对各个hashmap接口加权进行打分方式判断性能
https://github.com/ktprime/emhash/blob/master/bench/ebench.cpp

10 hashmap	Insert	Fhit	Fmiss	Erase	Iter	LoadFactor
emilib2::HashMap	31.0	13.1	14.6	23.3	11.5	62.5
emilib3::HashMap	17.2	13.2	13.1	17.8	10.8	62.5
absl::f_hash_map	26.6	12.3	13.3	19.7	15.0	66.7
phmap::fhash_map	26.2	12.9	14.4	20.0	14.6	66.7
martinus::fhmap	39.9	17.9	14.3	17.9	12.2	62.5
ska:flat_hashmap	21.0	16.5	18.6	16.0	17.1	62.0
tsl::robin_map	38.1	16.7	18.7	18.4	16.7	62.5
emhash8::HashMap	31.0	14.9	17.4	19.3	11.1	62.5
martinus::dense	25.6	18.0	15.4	23.0	10.6	58.8
jg::den_hash_map	26.1	14.2	16.9	19.5	10.9	62.5
rigtorp::HashMap	19.1	16.1	22.0	21.4	16.6	62.5
emhash7::HashMap	30.4	15.2	17.5	15.1	10.7	62.5
emhash6::HashMap	31.5	14.8	15.6	17.3	10.7	62.5
emhash5::HashMap	30.9	14.5	18.4	16.1	16.7	62.5

200 hashmap	Insert	Fhit	Fmiss	Erase	Iter	LoadFactor
emilib2::HashMap	12.4	3.28	6.95	8.85	1.77	78.1
emilib3::HashMap	10.4	3.91	7.05	5.21	1.74	78.1
absl::f_hash_map	11.1	2.85	6.05	9.85	3.21	78.4
phmap::fhash_map	11.3	3.69	7.15	11.6	2.69	78.4
martinus::fhmap	30.2	11.4	7.02	11.4	3.21	78.1
ska:flat_hashmap	17.1	8.51	9.97	7.93	4.51	66.0
tsl::robin_map	28.7	10.3	11.8	12.5	3.70	78.1
emhash8::HashMap	17.8	5.56	7.38	9.77	1.72	78.1
martinus::dense	21.2	10.9	7.18	16.2	1.72	77.8
jg::den_hash_map	10.9	5.37	7.40	8.22	1.73	78.1
rigtorp::HashMap	10.2	7.57	15.4	16.4	3.29	78.1
emhash7::HashMap	14.9	5.39	6.98	5.49	1.76	78.1
emhash6::HashMap	16.0	4.56	6.47	6.06	1.79	78.1
emhash5::HashMap	18.7	4.98	7.54	5.75	3.85	78.1

3000 hashmap	Insert	Fhit	Fmiss	Erase	Iter	LoadFactor
emilib2::HashMap	11.4	2.59	4.95	7.74	1.26	73.2
emilib3::HashMap	8.88	3.29	5.41	3.41	1.29	73.2
absl::f_hash_map	9.56	2.24	4.38	7.43	2.93	73.3
phmap::fhash_map	9.93	3.05	5.33	9.11	2.35	73.3
martinus::fhmap	28.1	10.5	5.77	9.95	2.56	73.2
ska:flat_hashmap	18.0	8.46	10.1	7.74	4.14	63.4
tsl::robin_map	28.2	10.7	11.9	11.3	3.43	73.2
emhash8::HashMap	16.6	5.07	7.07	9.23	1.29	73.2
martinus::dense	19.5	10.7	5.92	14.5	1.30	73.2
jg::den_hash_map	10.2	5.29	7.68	8.02	1.30	73.2
rigtorp::HashMap	9.31	6.77	14.7	15.0	3.12	73.2
emhash7::HashMap	13.2	4.94	6.94	5.06	1.32	73.2
emhash6::HashMap	14.7	4.01	6.40	5.68	1.31	73.2
emhash5::HashMap	17.4	4.38	7.77	5.30	3.52	73.2

40000 hashmap	Insert	Fhit	Fmiss	Erase	Iter	LoadFactor
emilib2::HashMap	15.2	3.99	3.48	9.94	1.33	61.0
emilib3::HashMap	10.8	4.47	3.66	4.85	1.38	61.0
absl::f_hash_map	11.4	3.58	3.13	7.22	3.85	61.0
phmap::fhash_map	11.8	4.50	3.96	8.62	3.20	61.0
martinus::fhmap	28.5	9.96	4.47	9.03	2.55	61.0
ska:flat_hashmap	13.0	9.26	11.5	8.98	4.38	61.0
tsl::robin_map	32.1	9.56	11.8	10.5	4.88	61.0
emhash8::HashMap	20.8	5.70	8.60	11.1	1.30	61.0
martinus::dense	22.5	10.3	4.86	14.0	1.28	61.0
jg::den_hash_map	13.7	6.38	9.11	10.1	1.27	61.0
rigtorp::HashMap	10.9	7.33	15.7	14.8	4.49	61.0
emhash7::HashMap	15.0	5.51	8.08	5.91	1.27	61.0
emhash6::HashMap	18.0	4.45	7.26	7.22	1.30	61.0
emhash5::HashMap	20.2	4.84	9.26	6.10	4.95	61.0

500000 hashmap	Insert	Fhit	Fmiss	Erase	Iter	LoadFactor
emilib2::HashMap	21.8	12.1	5.29	18.2	2.08	47.7
emilib3::HashMap	16.6	12.4	5.38	14.2	2.04	47.7
absl::f_hash_map	16.3	11.6	5.13	20.3	5.55	47.7
phmap::fhash_map	16.9	13.4	5.76	23.3	4.51	47.7
martinus::fhmap	35.7	13.2	5.97	15.2	3.14	47.7
ska:flat_hashmap	40.3	13.6	16.2	16.5	7.01	47.7
tsl::robin_map	51.4	13.4	15.9	18.7	7.70	47.7
emhash8::HashMap	31.7	7.96	9.21	15.1	1.60	47.7
martinus::dense	30.1	9.66	6.07	14.6	1.52	47.7
jg::den_hash_map	28.6	11.3	13.0	18.6	1.63	47.7
rigtorp::HashMap	33.7	10.1	17.9	19.4	6.76	47.7
emhash7::HashMap	20.6	10.4	10.7	11.7	1.85	47.7
emhash6::HashMap	24.0	7.74	10.7	16.5	1.82	47.7
emhash5::HashMap	25.9	8.27	12.6	12.0	7.31	47.7

7200000 hashmap	Insert	Fhit	Fmiss	Erase	Iter	LoadFactor
emilib2::HashMap	31.8	21.1	20.5	26.6	1.58	85.8
emilib3::HashMap	23.9	20.0	18.9	25.2	1.54	85.8
absl::f_hash_map	27.9	20.4	17.5	28.5	2.41	85.8
phmap::fhash_map	25.5	23.2	19.0	34.1	1.86	85.8
martinus::fhmap	58.5	35.1	22.0	35.7	2.74	85.8
ska:flat_hashmap	55.9	15.4	17.3	18.2	7.43	42.9
tsl::robin_map	72.0	44.2	42.5	40.8	2.56	85.8
emhash8::HashMap	61.5	16.4	15.4	34.6	1.46	85.8
martinus::dense	61.0	33.5	25.0	48.5	1.48	85.8
jg::den_hash_map	57.6	20.1	24.6	36.3	1.61	85.8
rigtorp::HashMap	41.3	31.8	87.6	53.3	2.24	85.8
emhash7::HashMap	32.9	17.6	19.4	18.7	1.59	85.8
emhash6::HashMap	40.4	13.5	16.3	26.4	1.66	85.8
emhash5::HashMap	46.7	14.2	17.4	18.9	2.40	85.8

10000000 hashmap	Insert	Fhit	Fmiss	Erase	Iter	LoadFactor
emilib2::HashMap	39.6	20.9	11.9	33.3	1.96	59.6
emilib3::HashMap	29.9	22.2	12.1	25.5	1.85	59.6
absl::f_hash_map	30.7	20.7	11.2	39.6	4.38	59.6
phmap::fhash_map	35.0	23.3	12.9	42.0	3.49	59.6
martinus::fhmap	59.3	23.8	16.0	26.3	2.90	59.6
ska:flat_hashmap	32.9	18.4	20.9	22.6	5.37	59.6
tsl::robin_map	62.3	21.5	22.6	23.9	5.99	59.6
emhash8::HashMap	54.1	16.1	15.5	32.5	1.46	59.6
martinus::dense	58.9	19.6	18.5	32.4	1.47	59.6
jg::den_hash_map	56.3	17.6	19.8	30.5	1.58	59.6
rigtorp::HashMap	29.6	17.9	33.2	32.6	5.40	59.6
emhash7::HashMap	34.2	14.5	14.9	16.6	1.69	59.6
emhash6::HashMap	40.9	11.4	14.4	24.2	1.65	59.6
emhash5::HashMap	42.4	11.9	15.9	16.6	5.43	59.6

50000000 hashmap	Insert	Fhit	Fmiss	Erase	Iter	LoadFactor
emilib2::HashMap	48.1	24.6	18.6	36.9	2.39	74.5
emilib3::HashMap	34.9	25.2	17.8	29.3	1.65	74.5
absl::f_hash_map	40.1	22.4	16.5	43.5	3.13	74.5
phmap::fhash_map	40.8	26.2	17.2	46.2	2.42	74.5
martinus::fhmap	70.1	31.8	22.7	33.4	2.80	74.5
ska:flat_hashmap	51.7	20.5	21.8	23.9	5.80	55.9
tsl::robin_map	67.1	28.2	28.5	31.7	3.73	74.5
emhash8::HashMap	57.3	17.7	16.1	35.7	1.52	74.5
martinus::dense	60.8	26.1	20.2	41.2	1.48	74.5
jg::den_hash_map	59.9	20.9	25.2	33.9	1.65	74.5
rigtorp::HashMap	36.1	26.4	54.0	44.1	3.30	74.5
emhash7::HashMap	36.2	19.1	21.7	19.7	1.70	74.5
emhash6::HashMap	45.4	13.3	16.3	32.9	1.72	74.5
emhash5::HashMap	46.3	13.4	17.2	18.7	3.63	74.5

[shines77]

我想基于swiss table 实现dense hash map。内存利用率可以提高但查询可能会慢一点。每次只能搜索4个（avx2 8个）位置 目前我的hashmap 实现是集中式（也有分离式emhash8 8bye metadata），metadata和k.v在一个slot上，查询miss 性能只有robin hood一半，查命中快30% 没有使用墓碑方案。频繁插入删除性能不受影响

你说的这种 SSE2 一次搜索4个，AVX2 一次搜索 8个这种方案我也是想过的，但是这是对于 key = int 来说的吧，如果 key = uint64_t，那就 SEE2 一次只能搜2个，AVX2 一次搜4个。所以这种方案很快就推翻了，取而代之的，那就只能用很短的hash值做 metadata，8个bit 或者 7个bit 是一种方案，这样比较省内存，这也是目前 absl::flat_hash_map 的实现方式，但是以目前的 absl::flat_hash_map 的实现来说，我有点怀疑 7 个 bit 是不是够用，把 SSE2 指令转成 AVX2 可以使用 15 bit 的 hash 值，冲突的可能性更小，这也是为什么我的代码中预留了 jstd::flat32_hash_map，虽然我还没有开始写。内存占用大一点，但是比较 key 的次数减少，不知道哪个更优。但是我也有点怀疑，我想 Google 的程序员不可能没想过，但是他没有这么做，可能还是 7 bit 的 hash 值性能更好，不过不自己做过测试不好说。

不过不知道你说的 4 个字节的是比较的 key， 还是 4个 自己的 metadata，但是我想，你应该说的是前者吧，因为你都说了为了内存的利用率更高一点。

[ktprime]

不过不知道你说的 4 个字节的是比较的 key， 还是 4个 自己的 metadata，但是我想，你应该说的是前者吧，因为你都说了为了内存的利用率更高一点。

和key类型没关系，int metadata 分为三部分，slot(24bit more) + hash(7 bit)+empty/deletet/filled(2 bit)
当hashmap size 足够大（千万级）这种实现除了节省内存还能提升性能， hash 位数是动态的，主要受限于size大小。
我的emhash8 就是这种动态hash bit，目前测试性能还不错。8bit 基本是够用的
swiss table 在数据比较大情况下metedata 缓存也是失效的，性能下降厉害

[shines77]

不过不知道你说的 4 个字节的是比较的 key， 还是 4个 自己的 metadata，但是我想，你应该说的是前者吧，因为你都说了为了内存的利用率更高一点。

和key类型没关系，int metadata 分为三部分，slot(24bit more) + hash(7 bit)+empty/deletet/filled(2 bit) 当hashmap size 足够大（千万级）这种实现除了节省内存还能提升性能， hash 位数是动态的，主要受限于size大小。 我的emhash8 就是这种动态hash bit，目前测试性能还不错。8bit 基本是够用的 swiss table 在数据比较大情况下metedata 缓存也是失效的，性能下降厉害

你这里的 slot(24bit more) 是什么？slot_index ? 还是保存的 slot (key, value) 的值？

[ktprime]

    union Bucket
    {
        int    empty: 1；
        int    hash:  7；
        int   index : 24；  //index in node vector
    };

Bucket bucket_[];  //metadata 32 bit.
NodeType node[]; //std::pair<key,value> NodeType;

大致是上面这种布局，index bit位不是固定的，当hash size很大，hash bit可能很小

[shines77]

swiss table 在数据比较大情况下metedata 缓存也是失效的，性能下降厉害

对于 swiss table 的 metedata 缓存也失效的问题，我是这样看的，虽然数据比较大的时候，是会失效，但是在一次 SSE2 搜索没匹配到，由于 metadata 内存是连续的，接下来的几次 SSE2 搜索的内存有可能在缓存里，这样的缓存的利用率是高于 int 大小的 metadata 的。因为，假设搜索同样的长度，比如50个slot，swiss table 只访问了50个byte，最多只能会跨越两条Cache Line，总共影响的缓存也最多只有 128 Bytes，而 int 大小的 metadata，需要访问200个byte，最多可能跨越四条Cache Line，最多可能影响 256 bytes 的缓存，其中很多的24bit slot_index 是无用的占用。

[ktprime]

swiss table 在数据比较大情况下metedata 缓存也是失效的，性能下降厉害

对于 swiss table 的 metedata 缓存也失效的问题，我是这样看的，虽然数据比较大的时候，是会失效，但是在一次 SSE2 搜索没匹配到，由于 metadata 内存是连续的，接下来的几次 SSE2 搜索的内存有可能在缓存里，这样的缓存的利用率是高于 int 大小的 metadata 的。因为，假设搜索同样的长度，比如50个slot，swiss table 只访问了50个byte，最多只能会跨越两条Cache Line，总共影响的缓存也最多只有 128 Bytes，而 int 大小的 metadata，需要访问200个byte，最多可能跨越四条Cache Line，最多可能影响 256 bytes 的缓存，其中很多的24bit slot_index 是无用的占用。

我的方案要结合dense hash map方案使用。因为另外的Node是连续数组内存非常紧凑，
https://github.com/martinus/unordered_dense_map 最近一周出来的，一些性能指标超过他自己原来的实现
https://github.com/martinus/map_benchmark/blob/master/data/all_locked.txt

即使key-value非常大也不影响性能，多查找几次metadata 比在node数据查找成本低

[shines77]

所以 Google 的 absl::flat_hash_map 在使用了二次探测法，后面一点的探测都是跳跃性的，metadata 的缓存利用率并不高，他在数据比较大的时候也能比我目前版本好，说明二次探测法还是有意义的，它有利于在比较后面的跳跃中，让中间跳过的地方留下 EmptySlot 的可能性变高，也就变相的缩短了搜索的长度（当然这是随机的，还是得看脸，但是让中间产生更多的空位的可能性应该是增大的），absl::flat_hash_map 还做了另一件事，就是在每次扩容 rehash() 的时候，计算 index 的时候，是加了盐的，它采用新分配的 ctrl_ 的内存地址右移 12 位，再跟 index 异或，让 rehash 之后的 slot 顺序是离散的，而不是扎堆的，这样间隔的 EmptySlot 会更多，对性能有提升。

例如：

...
index = ((hash_code >> 7) & slot_mask) ^ (ctrl_ >> 12);
...

这个问题在我发现我的 jstd::flat16_hash_map 很慢的时候，有意识到，但还没修改，我甚至想到另外一种方案，rehash 的时候，可以不按从小到大的顺序搬运 slot，可以从大到小逆序搬运 slot，也有一定几率能增加新 slots 的离散性。这种方法和增加盐 slat 的方法结合起来，效果可能更好。