search

shines77 / hashmap-benchmark

A hash map benchmark, include C++, Java, CSharp, golang and so on.
Other
7 stars 0 forks source link

加入我的hash_map #1

Open ktprime opened 2 years ago

ktprime commented 2 years ago

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

ktprime commented 2 years ago

/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 commented 2 years ago

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 commented 2 years ago

谢谢反馈，已经修复了 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 commented 2 years ago

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

shines77 commented 2 years ago

最近写 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 commented 2 years ago

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

shines77 commented 2 years ago

目前关注 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 commented 2 years ago

简单的测试数据 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 commented 2 years ago

我想基于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 commented 2 years ago

不过不知道你说的 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 commented 2 years ago

不过不知道你说的 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 commented 2 years ago 
    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 commented 2 years ago

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 commented 2 years ago

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 commented 2 years ago

所以 Google 的 absl::flat_hash_map 在使用了二次探测法，后面一点的探测都是跳跃性的，metadata 的缓存利用率并不高，他在数据比较大的时候也能比我目前版本好，说明二次探测法还是有意义的，它有利于在比较后面的跳跃中，让中间跳过的地方留下 EmptySlot 的可能性变高，也就变相的缩短了搜索的长度（当然这是随机的，还是得看脸，但是让中间产生更多的空位的可能性应该是增大的），absl::flat_hashmap 还做了另一件事，就是在每次扩容 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 的方法结合起来，效果可能更好。

ktprime commented 2 years ago

我的实现是双线性探测(或线性+二次+随机)，如果当前探测次数超过一定阈值。那么同时从上一个位置last(默认为0)查找，好处是探测速度比较快（可以做到很高负载因子），坏处是查找缓存性能比较差。

shines77 commented 2 years ago

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数据查找成本低

对于 swiss table 或者 robin hood hashmap，Node 本来就是连续的数组啊，它就是

NodeType slots_[slot_capacity]; // std::pair<Key, Value>数组

这种方式只在对象比较大的时候，用指针指向具体的 slot 值（std::pair<Key, Value>）有意义，因为你用 index 的话，每次 rehash 的时候，还是要重新分配内存，再把旧的 slot 数据迁移到新分配的 slot 数组里，如果用指针，std::pair<Key, Value> 就只需要 new 一次，只要数据不变，之后只移动指针的值就行了。如果更细一点，把 Key，Value 也分别出来，Key 比较大，就把 Key 变成指针；Value 比较大，就把 Value 变成指针；如果Key，Value都很大，那么就把 std::pair<Key, Value> 变成指针，这就是我设计的内存布局策略 layout_policy 中的 Key，Value 要不要 inline 的问题。

使用 index 索引值，那么 rehash 的时候就会慢很多，对象越大，消耗的时间就越多。使用指针的话，在find，insert 的时候会慢一点点，因为访问 slot 数据要多跳转一次，而且 64 位CPU下，指针是8字节的，消耗也不小，所以也是非常难以选择的，只有对象真的比较大的时候有意义，比如 std::string 或者别的大对象，其实一般应用中，大概率就只有 string 类型。

而且，即使这样，metadata 也不应该跟 slot 数组或者指针数组放在一起，分开存储的话，的确读取 slot 数组的时候，数据是冷的，但是合在一起，会降低 metadata 的缓存利用率，除非搜索的步长很短，那么就是有收益的，不需要再次去加载一次 slot 的数据，但是如果只是保存 index，还是要去读取一次冷的 slot 数组数据，似乎没有意义，除非是稀疏 sparse_hash_map，那就有意义，因为它不能从 metadata 的索引值直接取得 slot 的索引值。

不过我看了 https://github.com/martinus/unordered_dense_map，还不是很明白，我再看看，也许我没完全理解你说的和他用的这个 slot_index 的意义。似乎他跟我设想的 robin_hash_map 有点类似，我初步的设想是 (8bit - 1) 的 distance + 1 EmptySlot，8bit 的 hash，或者把这两者扩展成 16 bit + 8 bit，8 bit + 16 bit，16 bit + 16 bit 的组合。

ktprime commented 2 years ago

Node数据部分可设置较大虚拟内存，可以大大减小发生rehash概率，即使发生rehash都是原地内存搬移，开销都在拷贝 另外遍历速度和数组一致，插入还是保证有序（删除比较慢）。测试表面 k+v 大于24 字节就有直接收益， 如果用指针存对象就没必要使用这种方案，百万long-long rehash 就几个ms。 Node 和 Bucket 可以独立rehash(Node 扩容 不一定是2倍)，大大减少峰值内存

robin_hood 实现更依赖hash 函数，我测试使用比较坏的hash 直接crash（slot 4bit 溢出），我的方案还能运行 比如使用下面的 FIB_HASH = 100000

template<typename T>
struct Int64Hasher
{
    static constexpr uint64_t KC = UINT64_C(11400714819323198485);
    inline std::size_t operator()(T key) const
    {
#if FIB_HASH == 1
        return key;
#elif FIB_HASH == 2
        return hashfib(key);
#elif FIB_HASH == 3
        return hash_mur3(key);
#elif FIB_HASH == 4
        return hashmix(key);
#elif FIB_HASH == 5
        return rrxmrrxmsx_0(key);
#elif FIB_HASH > 10000
        return key % FIB_HASH; //bad hash
#elif FIB_HASH > 100
        return key * FIB_HASH; //bad hash
#elif FIB_HASH == 6
        return wyhash64(key, KC);
#else
        auto x = key;
        x = (x ^ (x >> 30)) * UINT64_C(0xbf58476d1ce4e5b9);
        x = (x ^ (x >> 27)) * UINT64_C(0x94d049bb133111eb);
        x = x ^ (x >> 31);
        return x;
#endif
    }
};
shines77 commented 2 years ago

rehash的时候不能原地迁移的，因为index值可能会变的，而且也不能用 std::memcpy 搬移整个 Node 数组数据，你还是得一个一个的重新计算index，再一个一个的搬迁，嗯，主要的消耗在于拷贝，对于小对象，当然区别是不大的，因为搬迁一个指针也是8个字节啊，当你的Key 或 Value 都 <= 8个字节的时候，基本是一致的。使用指针的收益只有对象大于 sizeof(void *) 的时候才有收益，其实一般来说 std::string 的实现也只有 32 byte，但是如果用指针，还是有收益的，不过收益也只有扩容（rehash，insert导致的扩容）的时候。

重新分配内存这个都是小事情，由于是整块申请的，次数也是很有限的，所以基本可以忽略不记。

ktprime commented 2 years ago

rehash的时候不能原地迁移的，因为index值可能会变的，而且也不能用 std::memcpy 搬移整个 Node 数组数据，你还是得一个一个的重新计算index，再一个一个的搬迁，嗯，主要的消耗在于拷贝，对于小对象，当然区别是不大的，因为搬迁一个指针也是8个字节啊，当你的Key 或 Value 都 <= 8个字节的时候，基本是一致的。使用指针的收益只有对象大于 sizeof(void *) 的时候才有收益，其实一般来说 std::string 的实现也只有 32 byte，但是如果用指针，还是有收益的，不过收益也只有扩容（rehash，insert导致的扩容）的时候。

所谓原地是Node数据槽位index不变，数组中位置按插入顺序固定 (可以做一些优化，经常访问类似LRU，hash相同的排序放在一起 可能rehash 比较慢)

使用指针二次内存访问还是影响性能+浪费内存和flat map hash 理念不符 除非对象实在复杂，拷贝成本很高或没有拷贝函数之类的限制

shines77 commented 2 years ago

我看懂 https://github.com/martinus/unordered_dense_map 了，他把 slot_index 放进 metadata 的原因是，因为 robin hood 哈希表在插入的时候，是可能要交换 metadata 的位置，同时还要交换 Node 数组中 std::pair<Key, Value> 的位置，这种交换可能是很频繁的，所以用 index 的话，就只需要交换 index 的值就可以了，Node 数组中的数据位置保存不变（不动）。但是我对，(distance, hash) 和 index 是否存储在一起持保留意见，有利也有弊，道理和前面说过的一样，搜索的距离比较短，是有收益的，搜索的距离比较长，可能是有害的，或者说收益不高。

但是，这是在 robin hood 哈希表才有的现象，之前我也想过这个问题，在 ska::flat_hash_map 里，我觉得比这个 unordered_dense_map 做得更好一点，交换的次数要比传统的 robin hood 哈希表要少很多，因为他交换的条件是 current_distance > bucket.distance，这样不必在插入一个位置以后，后面的位置都要腾挪，只有当满足这个条件的时候才会交换。

而在 Google 的 Swiss Table 里，插入的时候是不需要挪动 metadata 的位置的，找到合适的位置，计算出相对于 ctrl 基值的 index，直接 emplace 数据到 Node 数组里的 index 位置就好。所以保存 slotindex 值没有意义，因为你当前搜索的 control 的指针 减去 ctrl 数组的指针，再除以 control_byte 的大小就是 slot_index 。

在 robin hood 哈希表里保存 slot_index 的意义还是挺大的，除了上面的好处，还有另一个好处就是 rehash() 的时候，只需要拷贝 slot_index 就可以了。

看了 https://github.com/martinus/unordered_dense 的代码，我又想了一下，其实使用指针是不一定比 slot_index 慢的，你访问一个 Node 的时候，对比一下：

Node * node = node_[bucket->slot_index];

Node * node = bucket->node;

前者需要先从 slotindex * sizeof(Node)，再加上 node 的值，虽然很多时候 sizeof(Node) 的大小是 2 的幂次倍，可能也就是一条指令的事，这个时候跟直接取指针是等价的，但如果不是2的幂次倍，就需要加一下，使用 lea ecx, [ecx * 8 + ecx] 这种寻址方式，可能也是一条指令，但是不能说使用指针访问内存就比使用 index 访问慢，刚好是相反的，前者的效率是 大于或等于 后者的，只不过指针占 8 个字节非常不划算，使用 4 个字节的索引值也不一定比指针慢，或者说差距可以忽略不计。

ktprime commented 2 years ago

我很早实现 dense_hash_map https://github.com/ktprime/emhash/blob/master/hash_table8.hpp 和unordered_dense_map 差异在于冲突解决方案不同，没有使用robin hood 和 simd 查找，一种独创冲突解决方案（主bucket 不可占据，有点类似布谷鸟hashing，冲突节点使用int index 串起来，类似标准库方案，查找算法复杂度较低 ）。 性能和unordered_dense_map 接近, find hit 快和 finds miss 慢。

考虑到现实场景尤其是服务器应用，大多hash map 分离缓存（带metadata）实现 查找至少2次cache miss 使用集中可能性能更好，但benchmark测试不一样，loop循环metadata 都在缓存中，看起来测试不错。

shines77 commented 2 years ago

jstd::robin16_hash_map 大约10天前就完成了，本来想在这里更新一些讨论的，但是一直在忙着完善另一个改进版本 jstd::robin_hash_map, 目前虽然已基本调试通过, 但是性能不如预期, 还在改进中.

你提交的两个 PR 已经合并，为了照顾访问 github 困难的朋友，我把你的 https://github.com/ktprime/emhash 在 gitee.com 做了一份镜像: https://gitee.com/shines77/emhash, 但是由于 gitee.com 需要 1-2 天审核才能成为公开仓库，目前还更新不了 submodule。

可以先使用下面命令更新 https://github.com/shines77/hashmap-benchmark 到最新版：

git pull
git submodule update --init --recursive

再手动把 emhash 整个仓库的代码拷贝到 /3rd_party/emhash 目录，临时用一下，等 gitee 审核完了就可以正常更新了。如果有需要，我会及时更新 gitee 上的镜像仓库。

shines77 commented 2 years ago

哦，另外，我会稍微修改一下你提交的代码，因为 #define USE_STD_HASH_MAP 1 的测试已经是不再使用了的，虽然测试代码还保留着。USE_STD_UNORDERED_MAP 才是 std::unordered_map，另外，我也会加入新的版本 jstd::robin_hash_map 的测试 （jstd::robin_hash_map 本来的目标是不用 SIMD 指令，仿 ska::flat_hash_map 和 https://github.com/martinus/unordered_dense 写的版本，目前发现不用 SIMD 有点慢，而且我发现 /martinus/unordered_dense 可能会有 bug，有待进一步验证）。

ktprime commented 2 years ago

我看测试都是基于和unordered_map对比，直接可以对比参与测试的hash map更直接一些

ktprime commented 2 years ago

clang++8 编译有点问题

In file included from /home/huangyuanbing1/hashmap-benchmark/bench/time_hash_map/time_hash_map.cpp:1068: /home/huangyuanbing1/hashmap-benchmark/bench/time_hash_map/time_hash_map_func.hpp:716:25: error: no member named 'load_factor' in 'StdHashMap<HashObject<std::uint32_t, sizeof(std::uint32_t), sizeof(std::uint32_t)>, unsigned int, HashFn<unsigned int, 4, 4, false> >' double lf = hashmap.load_factor();


/home/huangyuanbing1/hashmap-benchmark/bench/time_hash_map/time_hash_map.cpp:1128:12: note: in instantiation of function template specialization
      'map_random_insert_predicted<StdHashMap<HashObject<std::uint32_t, sizeof(std::uint32_t), sizeof(std::uint32_t)>, unsigned int, HashFn<unsigned int, 4, 4, false> >, std::vector<unsigned int,
      std::allocator<unsigned int> > >' requested here
    if (1) map_random_insert_predicted<MapType>(iters, rndIndices);
           ^
/home/huangyuanbing1/hashmap-benchmark/bench/time_hash_map/time_hash_map.cpp:1176:9: note: in instantiation of function template specialization 'measure_hashmap<StdHashMap<HashObject<std::uint32_t,
      sizeof(std::uint32_t), sizeof(std::uint32_t)>, unsigned int, HashFn<unsigned int, 4, 4, false> >, StdHashMap<HashObject<std::uint32_t, sizeof(std::uint32_t), sizeof(std::uint32_t)> *, unsigned
      int, HashFn<unsigned int, 4, 4, false> > >' requested here
        measure_hashmap<StdHashMap<HashObj,   Value, HashFn<Value, HashObj::cSize, HashObj::cHashSize>>,
        ^
/home/huangyuanbing1/hashmap-benchmark/bench/time_hash_map/time_hash_map.cpp:1264:9: note: in instantiation of function template specialization 'test_all_hashmaps<HashObject<std::uint32_t,
      sizeof(std::uint32_t), sizeof(std::uint32_t)>, unsigned int>' requested here
        test_all_hashmaps<HashObject<std::uint32_t, 4, 4>, std::uint32_t>(4, iters / 1);
        ^
fatal error: too many errors emitted, stopping now [-ferror-limit=]
shines77 commented 2 years ago

先用 gcc 编译吧，clang 我还没试过，clang 比 gcc 严格，可能有些代码不够严谨，晚一点再修正。

shines77 commented 2 years ago

我看测试都是基于和unordered_map对比，直接可以对比参与测试的hash map更直接一些

对啊，USE_STD_HASH_MAP 是很古老的 stdext::hash_map 或者 __gnu_cxx::hash_map，已经废弃了，这是 https://github.com/sparsehash/sparsehash 的 [time_hash_map.cc] 代码遗留下来的，我保留了，但已经不用了。

ktprime commented 2 years ago

win32 上安装clang 非常方便，和gcc用法几乎一致，一些情况下性能更好。 默认情况 std::unordered_map 不需参与测试，太慢费时间

shines77 commented 2 years ago

Windows 上我没装 clang，也没装 gcc，我在 Linux 也经常用 clang 的，你可以从这里看到：

https://github.com/shines77/gudoku/tree/master/clang https://github.com/shines77/gz_sudoku/tree/master/clang

只不过我不会一开始就用 clang，一般是 Visual Studio (Windows) 和 GCC (Linux) 下测试，最后再用 clang 。

ktprime commented 2 years ago

Visual Studio 2017-2022 都支持clang的 安装一下llvm工具

shines77 commented 2 years ago

我有装 LLVM 的，但是我用的是 VS 2015 update 3，以前很早有 VS 2015 update 3 可以用的 clang toolset 的，但是现在找不到，懒得搞了，在 Linux 调试也一样的。

shines77 commented 2 years ago

下面的内容可能有点长，汇报一下这些天的一些心得和进展。

  1. robin hood 哈希表的 distance 问题

其实 jstd::robin16_hash_map 大约10天前就写完并调通了，由于同时处理两个字节的 metadata ：

struct meta_data {
    uint8_t hash;
    uint8_t distance;
};

所以使用的是 AVX2 指令，一开始是叫 jstd::robin32_hash_map 的，可是后来发现，虽然一次比较 32 个字节，但是每次的宽度还是 16 个 metadata，所以改为 jstd::robin16_hash_map 了。

写了 AVX2 指令才发现，处理 distance 的比较没有合适的指令，必须加载一个 __m256i 常量：

const __m256i kDistanceBase =
    _mm256_setr_epi16(0x0000, 0x0001, 0x0002, 0x0003, 0x0004, 0x0005, 0x0006, 0x0007,
                      0x0008, 0x0009, 0x000A, 0x000B, 0x000C, 0x000D, 0x000E, 0x000F);

再加上其他处理代码，SIMD 代码过于复杂，效率不是很高，SIMD 代码的指令周期（延迟）至少是仿 Google Swiss Table 哈希表的 jstd::flat_hash_map 的两倍以上。

虽然比较巧合的，你也刚好推荐了 https://github.com/martinus/unordered_dense 给我，他的使用 index 指向 entry 实体的方式算是一个比较重要的技巧，但我目前暂时还没用上。

ska::flat_hash_map 使用一个 std::int8_t 表示 distance，但我为了让 distance 的范围能更大一点，在 jstd::robin16_hash_map 中是采用的是 std::uint8_t distance，这样 distance 最大可以到 253（其中 254 是 iterator 的终止标识，255 表示空的 entry），但是后来发现，其实一般情况下，distance 到不了那么大，一般也就 0 - 20，0 - 30 的范围，很多时候最大 distance 只有个位数。

这一点，ska::flat_hash_map 的设计是比较特殊的，他取 num_buckets 的 2 的幂次方，设为 max_lookups，一旦插入的时候 distance 大于 max_lookups 就扩容，这个设计还不错，但有一个缺点，就是有时候可能会提早扩容，表现出来的问题就是如果会 out of memory，一般 ska::flat_hash_map 是最早 out of memory 的那一个。

因为 max_lookups = log2(num_buckets)，所以其实 ska::flat_hash_map 支持的最大 distance 也只能到 64, uint64_t 最多是2的64次方，所以我的 jstd::robin16_hash_map 的 distance 其实最大也只用到 128（虽然理论上最大可以用到 253），越大，查找的元素就越多，性能就越慢，发现 distance 比较大，就提前扩容，这可能是 ska::flat_hash_map 比较高效的其中一个原因，但缺点也有，就是可能会过早扩容。我在新版的 jstd::robin_hash_map （没有16字样），也没有采用跟他一样的设计，我使用了 max_lookups = log2(num_buckets) 2 或 log2(num_buckets) 4 的混合模式，某些时候可能性能差一些，但能规避部分过早扩容的问题。

我在新版的 jstd::robin_hash_map 改用了 std::int8_t 表示 distance，并且采用了类似 https://github.com/martinus/unordered_dense 的设计，把 distance 和 hash 合并为 dist_and_hash，但是在调试的过程中发现，这种合并的方式比较 distance 的时候可能会有 bug 的，我目前还没看明白他是怎么规避这个 bug 的，虽然这种合并处理的方式看起来有提升，但实际的提升不是很大。

jstd::robin_hash_map 的 SIMD 代码经过改进，是比较简洁的，虽然代码写了也调试OK了，但实际上暂时还未启用。且由于 dist_and_hash 合并处理是有 bug 的，所以有些 SIMD 代码还要修改，但是相比 jstd::robin16_hash_map 的 SIMD 代码，是有提升的。

ktprime commented 2 years ago

AVX2 比SSE2 这种情况提升不大， 大多查找都是一次指令(用测试统计)。我测试发现性能swiss table还有一点下降 不必过于在意一次查询16个还是8个

ktprime commented 2 years ago

image

随机测试用gcov 统计我改的swiss table SSE2查找命中率 代码在 https://github.com/ktprime/emhash/blob/master/thirdparty/emilib/emilib2.hpp

shines77 commented 2 years ago

这里顺带提一下，我后来在一个新的机器上测试，发现 https://github.com/shines77/hashmap-benchmark 和 https://github.com/shines77/jstd_hashmap 的 CMakeLists.txt 里都启用了 NASM, YASM 汇编支持，然后我就给关掉了，因为目前还没有用到外部的汇编文件，这是从 https://github.com/shines77/jstd 复制过来的 CMakeLists.txt 遗留下来的问题。一直想告诉你这个问题，因为你更早之前编译 /shines77/hashmap-benchmark 的时候，可能遇到过这个问题。

shines77 commented 2 years ago
  1. AVX2 和 SSE2 指令的问题

既然你提到了这个，那就聊聊这个吧，原本不是这么安排的，但一样也可以聊到我想说的。

一般来说，AVX2 对 SSE2 还是有提升的，一般介于 SSE2 的 120-160% 之间，视场景而定。但是，这个提升也仅对于数据密集型的计算更显著一些，用在哈希表里，提升确实不是很大。前面也提到了，对于 robin hood 哈希表而言，distance 其实不会特别大，也就是说搜索的长度不会特别长，有时候长度就只是个位数。SIMD 唯一比较大的优势，就是能够减少一些 branch 分支的判断，减少 CPU 流水线的停滞（pipeline stall），虽然 SIMD 本身也会有分支语句，但是毕竟平均上来说，能合并一些 if 分支的判断。所以，对于平均 distance 为个位数或很小的时候，SIMD 的作用就变得比较小，SIMD 还有一个缺点就是比较厚重、笨重。即使可能只需要两次判断就能得到的结果，它却可能要花四次或更多判断的同等时间才能得到结果。再加上 robin hood 哈希表除了要比较 ctrl_hash 以外，还要处理 distance 的比较，这是比只需要比较 ctrl_hash 的 Swiss Table 更复杂的，所以效率就更低。所以我在 jstd::robin16_hash_map 里借鉴了 https://github.com/martinus/unordered_dense 的思路，前面两次查询先展开循环 (unroll loop) ，再进行两次循环，最后再进入 SIMD 指令的循环，我形容为 "2+2" + SIMD 模式，我没有做更进一步的深入比较，但是 “2+2” + SIMD 是比关闭 "2+2" 直接使用 SIMD 性能更好一点，但也许可以尝试 "2 + 0" + SIMD 。

ktprime commented 2 years ago

emhash搜索空bucket 用你说的2+2模式，性能提升很小， unordered_dense 和我emhash8 性能非常接近，主要实现思路差不多（我早一年实现） 唯一差别冲突策略不一样(他使用robin hood)，查找命中我的快，不命中他的快

shines77 commented 2 years ago

emhash8 是 hash_table8.hpp 吗？

ktprime commented 2 years ago

emhash8 是 hash_table8.hpp 吗？

是的。我还在改进探测算法，比较适合场景是k+v size > 24，删除比较慢(尾部删除 2次查找 一次交换 一次释放)

shines77 commented 2 years ago

你上次最后提到过是布谷鸟哈希表的改进，晚上我就去查了一下布谷鸟哈希，有了一点心得，具体可以看这里：

https://blog.csdn.net/nannanxiami/article/details/109568254

跟你的 emhash8 还是有点不一样的，它是把 4 个 slot 映射到一个 bucket 里，这样有利于 Cache Line，进一步的改进可以动态的设置一个 bucket 的 slot 个数，尽量让一个 bucket 里的 slot 刚好塞进一条 Cache Line 里，比如对于 <int, int>，那就可以塞 8 个 slot，对于 <size_t, size_t> 那就只塞 4 个 slot，对于 <std::string, std::string>, std::string 一般是 32 个字节，那就只放一个或者两个 slot，或者 bucket 里放 16 个 指向 slot 的 uint32_t index，不对，这种情况还要保存 8 bit 左右大小的 hash 值，那就是 index 最多是 24 bit，或者使用你的动态 bit 大小的 hash 值，看起来还不错。

但是布谷鸟哈希和类布谷鸟哈希，和 robin hood 哈希表两者还是很不一样的，robin hood 哈希表遇到冲突，是顺序往后挪的，布谷鸟哈希的腾挪是跳跃性的。robin hood 哈希表可能要挪的数据会更多（视尾部终止位置或空格位的长度），但是它们在内存上是连续的。布谷鸟要挪数据可能会少很多，但位置是跳跃性的，内存局部性差一些。所以像上面那篇文章那样，在一个 bucket 里存放多个 slot，腾挪的时候也是以一个 bucket 为单位寻找 slot，内存局部性可能更好一点。

ktprime commented 2 years ago

优缺点正如你说的那样，你再看我emhash7 实现，一次可以查找连续64个空位（大量插入尤其负载因子接近0.999，依旧很高性能）， 数据冲突不严重基本一次命中附近空位，我之前建议dense map 使用动态位hash（没听我的），我可以做大很高的负载因子，他的实现比较难（插入太慢） 我的和布谷鸟hash差异比较大单又有一点类似，主槽位不可以抢占，所以插入查找都是从这里开始

ktprime commented 2 years ago

如果你测试case 满足 key_size%8 != value_size %8，那么大部分场景下我的实现emhash5/7更高效（比他实现更节省内存）

shines77 commented 2 years ago

哦，这一次，我对 time_hash_map.cpp 做了一个比较大的改进，因为数据插入哈希表的先后顺序对于哈希表性能还是有一定的影响的，所以我同时采用了顺序插入 sequential_xxxxxx() 和随机插入 random_xxxxxx() 两套测试，但在我写下这句话的时候，我知道我目前的顺序插入和随机插入存在什么问题，它的问题是，顺序插入就不说了，key 是连续的也是 OK 的，这才符合顺序插入的测试。

虽然我看了，好像你的 emhash5 和 ska::flat_hash_map 都对 hash 值做了二次哈希，顺序插入和随机插入的用时几乎是一样的，这说明哈希表内部已经用二次哈希打乱了顺序的key。

但是目前我的随机插入存在的问题是，随机key的范围是固定在 [0, max_iters] 直接的值，这样插入之后还是有可能是连续的，这不太科学，应该像 cardinal_bench 那样，在一个更打的范围值随机取 max_iters 个 key，这样测试才更符合实际。

另外，为了保证顺序插入的连续性，Linux 下我使用的是默认的 std::hash （其实大多数哈希表默认哈希函数也是 std::hash），我目前写的三个版本的哈希表，都没有开启二次哈希，虽然我有写二次哈希的代码，但是开启了，像目前我这种测试代码下性能会稍稍减低一点，但我想了一下，还是要开启一下，尤其是 robin hood 哈希表，还是很有必要的，这样外部的哈希函数的好坏对数据的离散性基本没有影响。

ska::flat_hash_map 的处理方式是最特别的，它把二次哈希和 hash_code & slot_mask 或 hash_code % slot_capacity 合并成一个函数，他使用的是 second_hash_func(hash_code) >> log2(num_buckets) 这种方式。

ktprime commented 2 years ago

可以考虑另外一种find 命中测试，大多测试把整个输入数据查找都命中一次，而实际情况是（比如10%数据）重复、尤其是hash map 非常大的时候用户数据输入复合局部性原理。

我的实现内部没有做2次hash，编译宏默认是不开的。

shines77 commented 2 years ago

对，我知道，比如说还有像 /martinus/map_benchmark 那种 find_25, find_50, find_75, find_100，25%命中，50%命中，但是这样测试的项目太多了，我想了一下，time_hash_map 目前就做偏理论上一点的单项测试，你说的这种，更接近于 cardinal_bench 这种测试，目前我还没有想好。

其实还有一个问题，time_hash_map 里面的 16 byte 的对象和 256 byte 对象的测试还是有点不够科学，因为 256 byte 对象的哈希值计算为了弱化哈希函数的影响，哈希值计算是不符合实际的。我可能会单独另写一个 <size_t, std::string>, <std::string, std::string>, <std::string_view, std::string_view> 的测试。对于 std::string 的随机生成我已经准备了一些词条，还有 Linux 系统有一个 dict_word，可以用来生成字符串 key，尽量让它更接近实际的英文单词。

shines77 commented 2 years ago

另外，在 cardinal_bench 的测试里，jstd::robin16_hash_map 和 jstd::robin_hash_map 性能已经超越了 ska::flat_hash_map 和 absl::flat_hash_map 了，主要的原因第一个是 robin hood 的关系，另一个是内存占用，jstd::robin16_hash_map 和 jstd::robin_hash_map 都是只加了两个 byte 的 metadata，ska::flat_hash_map 虽然只加了一个byte 的 metadata，但它的 metadata 是和 entry 保存在一起的，而我的 metadata 和 entry 都是分体式存储。

和我很早之前分析的差不多，分开保存能省总的内存使用量，但是访问数据比较少的时候，可能读缓存的次数要比合在一起保存的多，所以 ska::flat_hash_map 在数据量级比较小的时候更快，而分开保存在数据量级比较大，缓存占满的情况优势大一点。

Google 的 absl::flat_hash_map 则是比较特别的，它数据量级小的时候相对比较慢，但是在数据量级比较大的时候，它反而也不差，毕竟它只用一个 byte 保存 metadata，但是我的 jstd::flat16_hash_map 也只用了一个 byte，跟它一样也是分开保存的，但是量级比较大的时候，却比它慢很多，这其中的原因是 absl::flat_hash_map 使用了多次哈希探测，以快速跳脱到更远的地方，避免空格位过于远的问题。

但是 absl::flat_hash_map 是 H1(hash_code) 和 H2(hash_code) 的这套固定算法是有问题的，所以在 time_hash_map 里面，在使用 std::hash 作为哈希函数的时候，absl::flat_hash_map 是会非常非常慢的，比正常慢 100 倍以上，所以我在 time_hash_map 里面是做了特殊化处理的，不然它非常非常慢。

shines77 commented 2 years ago

这是因为 absl::flat_hash_map 里面是这么定义 H1, H2 函数的：

注：Google 的 Swiss Table 从最初公布的版本，经过几个版本的改进，才变为目前这种实现方式，总的来说还是很有想法的，但是有缺陷。但 H1, H2 这个设定从一开始就基本没有改变过。

// 用来取 bucket_index
size_t H1(size_t hash_code) {
    return (hash_code >> 7);
}

// 用来做 metadata 的 hash 值
uint8_t H2(size_t hash_code) {
    return (uint8_t)(hash_code & 0x7F);
}

他的设计思想是不管你的 hash_code 是连续的还是离散的，离散的更好，让它们每128个连续的 key (hash_code) 扎堆于同一个 bucket，一直往后堆，只有堆得够长，这样 SIMD 收益就更大一点，但是太长也不行，所以它用了一个多次探测哈希函数，步长越来越大的往后跳，这样即保证有一定量的数据扎堆，也能缓解搜索长度过大的问题。

我的 jstd::flat16_hash_map 虽然 index 计算没有采用他这样的 H1, H2 函数设计，也就是扎堆的情况不至于那么严重，但是没有采用多次探测哈希函数，一旦有一定长度的扎堆（即空格位间隔比较远），就会变得比较慢，总体性能一般。

ktprime commented 2 years ago

absl 基本不能用std::hash,性能退化很严重的， 下面是我改进计算H2

# ifdef EMH_H2
     #define hash_key2(key_hash, key) ((uint8_t)(key_hash >> 24)) << 1
# else
     template<typename UType, typename std::enable_if<!std::is_integral<UType>::value, uint8_t>::type = 0>
     inline uint8_t hash_key2(uint64_t key_hash, const UType& key) const
     {
         return (uint8_t)(key_hash >> 28) << 1;
     }

     template<typename UType, typename std::enable_if<std::is_integral<UType>::value, uint8_t>::type = 0>
     inline uint8_t hash_key2(uint64_t key_hash, const UType& key) const
     {
         return (uint8_t)((uint64_t)key * 0x9FB21C651E98DF25ull >> 50) << 1;
     }
# endif
ktprime commented 2 years ago

我的hashmap 里面有一个性能分析函数dump_statics()（宏开启），统计查找命中，失败，冲突率，cache miss 之类非常全面性能数据