Robin Hood Hashing 源码分析 | SF-Zhou's Blog

[SF-Zhou]

https://sf-zhou.github.io/programming/robin_hood_hashing.html

[qhsong]

似乎absl也提供了开放寻址的hashmap，上次测试的时候发现性能连std::unordered_map都比不过，有点奇怪。不知道您又没有比较过两者。
https://abseil.io/docs/cpp/guides/container

[ktprime]

absl对hash函数比较敏感，不要使用std::hash（gcc）

[SF-Zhou]

@qhsong
似乎absl也提供了开放寻址的hashmap，上次测试的时候发现性能连std::unordered_map都比不过，有点奇怪。不知道您又没有比较过两者。
https://abseil.io/docs/cpp/guides/container

我自己没有测过，网上可以找到一些 benchmark 数据，比如 Hashmaps Benchmarks，不同测试场景下的性能差别可能很大。

[zhanglistar]

rehash是硬伤。

[ktprime]

对于k.v简单类型千万数据 rehash 也就100ms不到.

[zhanglistar]

之前测试过上亿的数据，可能到几秒。

[ktprime]

之前测试过上亿的数据，可能到几秒。
我感觉问题不大，不喜欢redis那种渐进式rehash方案，毕竟实际场景下几亿数据不会频繁发生rehash（测试只是测试），
如果真海量数据提前reserve或者分桶方法能解决（迭代有点麻烦）。

[ktprime]

欢迎使用我的hashmap https://github.com/ktprime/emhash/blob/master/hash_table7.hpp
负载因子0.99下性能依旧不差, 查找命中性能目前高于各种hashmap实现

[SF-Zhou]

robin_hood::unordered_map 的作者发布了新作 ankerl::unordered_dense::{map, set}，他自己 benchmark 来看整体性能优于前作。核心优化是将 <key, value> 集中存储到一个连续的 std::vector 上，优势是内存连续，迭代器性能最强；劣势是删除麻烦，删除一个元素后需要将 std::vector 最后一个元素搬到删除的位置，同时修改它的索引。另一个优化是留了 24bit 记录元素与哈希目标桶的距离，前作只有 8bit。

[SF-Zhou]

robin_hood::unordered_map 仍然有抛异常的风险，当然概率非常低，一个复现：

#include "robin_hood.h"

struct Hash {
  size_t operator()(int) const { return 0; }
};

int main() {
  robin_hood::unordered_map<int, int, Hash> map;
  for (auto i = 0; i < 128; ++i) map[i] = i;
  return 0;
}

[ktprime]

https://martin.ankerl.com/2022/08/27/hashmap-bench-01/ 测试结果性能不错的emhash7/8 是我实现的，
如果服务器上运行martin的性能测试，absl::flat_hash_map在大部分测试项目中略微领先(我测试好几种不同服务器cpu结果类似，大L3缓存非常有利于swiss table)

robin_hood::unordered_map 抛出异常我认为是相当好的解决方案，有机会让你问题所在及时换其他hash函数，我在线上曾遇到类似问题（hash函数分布太差，服务器运行低效且难以定位）。要知道千万随机数据插入，冲突长度大于9的桶概率几乎没有的。
下面是我随机测试, hash冲突个数桶部分和泊松公式计算对比（几乎相同，hash冲突桶个数符合完美的泊松分布）

  ============== buckets size ration ========
    1   1543981  0.36884964|0.36787944
    2    768655  0.36725597|0.36787944 
    3    256236  0.18364065|0.18393972
    4     64126  0.06127757|0.06131324
    5     12907  0.01541710|0.01532831
    6      2050  0.00293841|0.00306566
    7       310  0.00051840|0.00051094
    8        49  0.00009365|0.00007299
    9         4  0.00000860|0.00000913

under random hashCodes, the frequency of nodes in bins follows a Poisson
distribution(http://en.wikipedia.org/wiki/Poisson_distribution) with a parameter of about 0.5
on average for the default resizing threshold of 0.75, although with a large variance because
of resizing granularity. Ignoring variance, the expected occurrences of list size k are
(exp(-0.5) * pow(0.5, k)/factorial(k)). The first values are:

[ktprime]

目前性能实现更好的flat hash map 来自boost，从测试看已经超越前辈swiss table（优化版本）.
https://bannalia.blogspot.com/2022/11/inside-boostunorderedflatmap.html

有兴趣可以跑一跑我的hash map benchmark (持续优化3年，10+个主流flat hash map 最新源码).
https://github.com/ktprime/emhash/blob/master/bench/ebench.cpp
https://github.com/ktprime/emhash/blob/master/bench/martinus_bench.cpp

[ktprime]

试试插入 value 改成 uin32_t (em7 可以提速20%， 默认max_laod_factor 0.8). 如果不提前reserve，相同的hash函数，负载因子都一样才相对公平。

[zhanglistar]

ch hashmap不提前reserve比reserve要快。两边的负载因子都是0.5，初始256个bucket。代码在这里:https://github.com/bigo-sg/ClickHouse/blob/667174cf2c260512975bd589c5024441dfaf170a/src/Common/examples/integer_hash_tables_benchmark.cpp
看着ch也没用啥黑魔法，但是这个插入性能真的快。

[zhanglistar]

比em7|8 boost unordered flat hash map, abseil flat, robin hood都要快。

[ktprime]

我刚才也测试了一下 本地测试代码改自 sr-test https://github.com/dirtysalt/codes/blob/master/cc/sr-test/hash_set_perf.cpp
负载因子都是0.5

仅仅单纯插入我测试最快的 是 https://github.com/rigtorp/HashMap

[zhanglistar]

我这边结论不太一样，可能跟硬件有一定关系，robin hood的插入性能还不错，但是跟ck也有一定距离。
➜ bld git:(hashbench) ./src/Common/examples/integer_hash_tables_benchmark 0 UInt64 100000000 < ~/uid.bin
CH HashMap:
Elapsed: 6.989 (14308984.781 elem/sec.), map size: 20987688
➜ bld git:(hashbench) ./src/Common/examples/integer_hash_tables_benchmark 9 UInt64 100000000 < ~/uid.bin
rigtorp::unordered_flat_map:
Elapsed: 10.574 (9457069.772 elem/sec.), map size: 20987688
➜ bld git:(hashbench) ./src/Common/examples/integer_hash_tables_benchmark 6 UInt64 100000000 < ~/uid.bin
robinhood::flat_unordered_map:
Elapsed: 10.440 (9578904.785 elem/sec.), map size: 20987688
➜ bld git:(hashbench) ./src/Common/examples/integer_hash_tables_benchmark 5 UInt64 100000000 < ~/uid.bin
emhash8::flat_unordered_map:
Elapsed: 16.903 (5915958.264 elem/sec.), map size: 20987688
➜ bld git:(hashbench) ./src/Common/examples/integer_hash_tables_benchmark 7 UInt64 100000000 < ~/uid.bin
emhash7::flat_unordered_map:
Elapsed: 12.237 (8171985.827 elem/sec.), map size: 20987688
➜ bld git:(hashbench) ./src/Common/examples/integer_hash_tables_benchmark 8 UInt64 100000000 < ~/uid.bin
boost::unordered_flat_map:
Elapsed: 15.411 (6488806.655 elem/sec.), map size: 20987688

[ktprime]

上面两个测试过于简单，不同平台测试差异非常大，难以断定那个hashmap更快，
我收集20+个（部分太复杂没在我的git库）第三方hash map测试程序，没事每天跑跑各种测试对比，目前martinus的测试算全面且客观，可惜结果仅限于他的笔记本 8700。

下面这个我也经常跑的测试，第三方代码都统一调整相同的 max_load_factor(不少写死0.5，0.8)
https://github.com/ktprime/emhash/blob/master/bench/qbench.cpp

10 hashmap	Insert	Fhit	Fmiss	Erase	Iter	LoadFactor
emilib2::HashMap	13.6	7.16	11.0	19.1	2.54	62.5
emilib3::HashMap	10.3	6.57	7.88	10.2	2.45	62.5
absl::f_hash_map	21.3	6.23	8.93	11.6	5.98	66.7
emhash8::HashMap	40.1	10.4	15.6	14.8	2.20	62.5
martinus::dense	45.4	14.5	9.80	21.5	2.81	62.5
rigtorp::HashMap	12.1	10.6	20.0	22.9	7.27	62.5
jg::den_hash_map	36.3	9.24	14.0	16.2	1.96	62.5
emhash7::HashMap	34.2	9.60	14.0	10.4	2.32	62.5
emhash6::HashMap	32.3	9.30	13.2	12.7	2.38	62.5
emhash5::HashMap	36.6	9.84	13.9	10.5	7.43	62.5

200 hashmap	Insert	Fhit	Fmiss	Erase	Iter	LoadFactor
emilib2::HashMap	14.4	5.17	11.3	11.1	1.25	78.1
emilib3::HashMap	13.7	5.61	10.3	6.11	1.22	78.1
absl::f_hash_map	13.9	4.96	10.7	13.8	2.12	78.4
emhash8::HashMap	27.5	9.25	13.4	14.2	1.24	78.1
martinus::dense	28.2	17.5	12.0	23.4	1.25	78.1
rigtorp::HashMap	13.2	11.4	21.7	31.6	2.70	78.1
jg::den_hash_map	16.1	8.91	13.0	13.7	1.21	78.1
emhash7::HashMap	24.2	8.71	11.6	8.90	1.28	78.1
emhash6::HashMap	22.5	8.34	12.1	9.86	1.26	78.1
emhash5::HashMap	27.9	9.06	11.4	9.41	2.76	78.1

3000 hashmap	Insert	Fhit	Fmiss	Erase	Iter	LoadFactor
emilib2::HashMap	15.5	4.93	9.67	11.1	1.16	73.2
emilib3::HashMap	13.8	5.42	8.68	5.79	1.16	73.2
absl::f_hash_map	14.4	4.88	9.18	12.0	2.16	73.3
emhash8::HashMap	27.3	9.04	13.3	14.0	1.18	73.2
martinus::dense	27.8	17.6	10.6	21.7	1.18	73.2
rigtorp::HashMap	12.4	10.9	21.1	28.6	2.88	73.2
jg::den_hash_map	21.5	9.28	13.9	14.3	1.19	73.2
emhash7::HashMap	24.9	8.56	12.2	8.96	1.21	73.2
emhash6::HashMap	22.2	8.47	12.3	9.94	1.21	73.2
emhash5::HashMap	27.9	8.93	12.2	9.62	3.06	73.2

40000 hashmap	Insert	Fhit	Fmiss	Erase	Iter	LoadFactor
emilib2::HashMap	21.7	7.86	8.00	14.3	1.27	61.0
emilib3::HashMap	19.9	8.47	6.56	7.90	1.27	61.0
absl::f_hash_map	20.4	7.82	7.70	11.3	3.00	61.0
emhash8::HashMap	35.1	10.4	15.6	16.1	1.18	61.0
martinus::dense	31.5	17.5	10.1	22.1	1.18	61.0
rigtorp::HashMap	15.7	11.7	23.6	26.8	4.16	61.0
jg::den_hash_map	29.6	12.0	16.6	18.2	1.20	61.0
emhash7::HashMap	30.8	10.1	13.5	10.7	1.21	61.0
emhash6::HashMap	32.4	9.65	13.6	12.0	1.20	61.0
emhash5::HashMap	36.5	10.1	14.7	11.4	4.48	61.0

500000 hashmap	Insert	Fhit	Fmiss	Erase	Iter	LoadFactor
emilib2::HashMap	29.6	22.0	11.4	29.7	2.06	47.7
emilib3::HashMap	29.2	20.8	9.02	23.1	2.08	47.7
absl::f_hash_map	33.0	21.7	10.9	29.2	4.26	47.7
emhash8::HashMap	58.8	14.6	18.4	22.5	1.48	47.7
martinus::dense	48.7	18.4	13.2	28.0	1.47	47.7
rigtorp::HashMap	44.6	19.2	33.1	38.8	6.29	47.7
jg::den_hash_map	54.1	22.8	33.6	44.5	1.67	47.7
emhash7::HashMap	42.4	20.5	19.4	24.0	1.78	47.7
emhash6::HashMap	41.2	19.7	22.0	38.6	1.79	47.7
emhash5::HashMap	46.4	19.5	23.4	34.8	6.82	47.7

7200000 hashmap	Insert	Fhit	Fmiss	Erase	Iter	LoadFactor
emilib2::HashMap	53.3	38.4	37.2	85.4	1.48	85.8
emilib3::HashMap	54.7	38.8	32.8	84.9	1.49	85.8
absl::f_hash_map	49.3	38.3	32.4	66.1	1.80	85.8
emhash8::HashMap	109.	31.3	33.3	65.0	1.47	85.8
martinus::dense	90.0	60.7	47.9	81.7	1.47	85.8
rigtorp::HashMap	55.0	49.4	112.	96.0	2.15	85.8
jg::den_hash_map	88.1	42.2	69.9	105.	1.68	85.8
emhash7::HashMap	60.2	33.1	34.0	44.2	1.54	85.8
emhash6::HashMap	65.1	31.3	35.4	89.9	1.53	85.8
emhash5::HashMap	74.5	31.9	35.1	86.2	2.23	85.8

10000000 hashmap	Insert	Fhit	Fmiss	Erase	Iter	LoadFactor
emilib2::HashMap	75.8	42.1	29.2	96.7	1.89	59.6
emilib3::HashMap	72.2	41.6	23.4	121.	1.87	59.6
absl::f_hash_map	70.2	42.2	28.3	123.	3.39	59.6
emhash8::HashMap	116.	30.2	34.4	68.7	1.45	59.6
martinus::dense	90.0	42.3	36.0	79.1	1.48	59.6
rigtorp::HashMap	42.9	32.6	60.5	67.2	4.86	59.6
jg::den_hash_map	94.4	38.2	58.0	106.	1.68	59.6
emhash7::HashMap	61.8	30.7	31.5	39.1	1.70	59.6
emhash6::HashMap	66.4	29.2	33.0	97.2	1.69	59.6
emhash5::HashMap	74.0	29.4	34.2	91.2	5.16	59.6

50000000 hashmap	Insert	Fhit	Fmiss	Erase	Iter	LoadFactor
emilib2::HashMap	115.	49.0	57.5	151.	1.60	74.5
emilib3::HashMap	113.	51.9	47.6	160.	1.60	74.5
absl::f_hash_map	111.	48.1	42.1	145.	2.38	74.5
emhash8::HashMap	122.	33.7	37.4	76.6	1.47	74.5
martinus::dense	97.1	52.6	41.8	87.1	1.45	74.5
rigtorp::HashMap	53.0	44.9	94.4	86.9	3.12	74.5
jg::den_hash_map	103.	44.6	75.4	125.	1.71	74.5
emhash7::HashMap	76.5	37.6	41.5	52.7	1.59	74.5
emhash6::HashMap	85.0	31.6	37.7	133.	1.60	74.5
emhash5::HashMap	79.3	32.3	36.1	98.2	3.28	74.5

[ktprime]

ck查找性能一般，估计是用简单的线性探测（且带墓碑方案 ）解决冲突, 这种简单实现对于临时hashmap可以，持续插入删除下性能会越来越差（墓碑难以清除）。如果把absl 改成0.5负载因子，插入性能一样飞起。
qbench测试方法过于单一，可以跑一下mbench（第2-3 个字符相关测试会 ck crash, 需要专门string hash map?）
跳过前面3个测试case ./mbench b4

[zhanglistar]

他没有用墓碑方案，而是参考了一篇论文在删除的时候做了compress，参考https://github.com/ClickHouse/ClickHouse/blob/master/src/Common/HashTable/HashTable.h#L1113

[ktprime]

他没有用墓碑方案，而是参考了一篇论文在删除的时候做了compress，参考https://github.com/ClickHouse/ClickHouse/blob/master/src/Common/HashTable/HashTable.h#L1113

那我理解错了，如果不使用墓碑，删除要做很多查找相关操作会导致变慢，大多使用场景删除不是频繁操作

[zhanglistar]

对 在分析数据库的场景里，很少会有删除，主要是大规模数据的插入和查找。

[zhanglistar]

qbench测试方法过于单一，可以跑一下mbench（第2-3 个字符相关测试会 ck crash, 需要专门string hash map?）
这个需要用https://github.com/ClickHouse/ClickHouse/blob/master/src/Common/HashTable/StringHashMap.h#L85
这里他针对分析场景的不同长度的string进行了区分，论文在这里：https://www.mdpi.com/2076-3417/10/6/1915

[ktprime]

emhash8 只针对复杂key/value 查询方面比较快 插入性能不怎样，迭代和数组一样快
emhash5/7 针对简单k/v查询，少量或海量数据比较快（中等规模，数据都在L3 性能又一般）
我用最新版本gcc. clang, vs 2022 测试结果有时也大不一样

[zhanglistar]

看下这个repo的benchmark？跟你的bench是反的，https://github.com/bigo-sg/ClickHouse/tree/hashbench
clone后，mkdir bld && cd bld && cmake .. "-DWERROR=OFF" && ninja integer_hash_tables_benchmark && ./src/Common/examples/integer_hash_tables_benchmark 2 UInt64 100000000 < ~/uid.bin
uid.bin 我可以传给你。

[zhanglistar]

增加-flto后，ck hashmap的结果看起来还是比较好的了，除了Fmiss比较差。

10000000 hashmap	Insert	Fhit	Fmiss	Erase	Iter	LoadFactor
emilib3::HashMap	159.	42.0	24.0	216.	2.90	59.6
absl::f_hash_map	170.	38.9	22.5	215.	7.26	59.6
emhash8::HashMap	112.	29.9	27.4	127.	2.62	29.8
martinus::dense	107.	31.9	34.1	142.	2.60	29.8
ck::f_hash_map	115.	34.6	170.	57.6	18.8	29.8
emhash7::HashMap	129.	30.9	24.6	42.3	2.32	29.8
emhash6::HashMap	129.	28.4	30.0	44.2	2.35	29.8
emhash5::HashMap	130.	34.9	39.9	44.8	22.1	29.8

50000000 hashmap	Insert	Fhit	Fmiss	Erase	Iter	LoadFactor
emilib3::HashMap	205.	53.7	39.0	280.	2.58	74.5
absl::f_hash_map	223.	48.3	34.0	251.	4.80	74.5
emhash8::HashMap	117.	38.7	35.4	153.	2.62	37.3
martinus::dense	108.	40.4	44.1	169.	2.64	37.3
ck::f_hash_map	114.	44.5	221.	76.4	17.2	37.3
emhash7::HashMap	130.	49.8	41.2	66.5	2.38	37.3
emhash6::HashMap	143.	37.5	40.3	64.6	2.38	37.3
emhash5::HashMap	124.	50.0	54.5	62.4	19.5	37.3

[ktprime]

我在几台不同的服务器测试过，ck 在低负载下目前插入的确是最快的，实现有些黑科技。上面的测试qbench刚加入支持boost了（查找失败是最快），我bench 下面也有拷贝boost 项目的性能测试代码（buint64.cpp），没有把CK加进去

[zhanglistar]

是的，不过ck在unsuccessful lookup上是最慢的，即使是load factor低于0.5。

[ktprime]

老旧的服务器cpu

10000000 hashmap	Insert	Fhit	Fmiss	Erase	Iter	LoadFactor
emilib2::HashMap	208.	40.8	23.5	160.	2.10	59.6
absl::f_hash_map	169.	36.3	21.7	214.	5.37	59.6
boost::fhash_map	199.	44.8	23.3	185.	7.40	63.6
emhash8::HashMap	132.	31.6	26.6	116.	0.00	59.6
martinus::dense	118.	39.4	32.5	119.	0.00	59.6
ck::f_hash_map	101.	33.8	173.	58.2	14.8	29.8
hrd_m::fhash_map	107.	32.3	28.8	42.3	12.7	29.8
rigtorp::HashMap	84.4	21.8	30.3	39.6	15.0	29.8
jg::den_hash_map	127.	36.2	39.8	165.	0.00	59.6
emhash7::HashMap	86.0	29.6	29.5	49.2	0.95	59.6
emhash5::HashMap	93.8	26.1	29.4	46.3	8.86	59.6

50000000 hashmap	Insert	Fhit	Fmiss	Erase	Iter	LoadFactor
emilib2::HashMap	286.	46.5	36.2	238.	1.74	74.5
absl::f_hash_map	213.	41.2	33.2	244.	3.47	74.5
boost::fhash_map	280.	50.9	33.4	228.	7.13	79.5
emhash8::HashMap	141.	37.6	32.6	135.	0.00	74.5
martinus::dense	128.	54.5	41.0	131.	0.00	74.5
ck::f_hash_map	94.3	38.3	190.	68.0	13.3	37.3
hrd_m::fhash_map	105.	40.4	41.0	51.7	11.5	37.3
rigtorp::HashMap	79.2	26.1	39.9	48.8	13.4	37.3
jg::den_hash_map	132.	43.2	50.7	192.	0.00	74.5
emhash7::HashMap	99.7	36.2	40.0	64.6	0.91	74.5
emhash5::HashMap	99.4	30.7	34.9	64.8	5.53	74.5

[ktprime]

下面mbench 中插入 ck 优势非常明显

bench_insert:
absl flat
(lf=0.60) insert 0.69, remove 0.81, reinsert 0.60, clear 0.008, total 10M int time = 2.11 s
(lf=0.74) insert 13.94, remove 15.94, reinsert 13.40, clear 0.088, total 100M int time = 43.37 s
boost_flat
(lf=0.64) insert 0.70, remove 0.71, reinsert 0.66, clear 0.004, total 10M int time = 2.07 s
(lf=0.79) insert 17.83, remove 18.61, reinsert 21.31, clear 0.028, total 100M int time = 57.78 s
ck_hashmap
(lf=0.30) insert 0.71, remove 0.46, reinsert 0.37, clear 0.052, total 10M int time = 1.59 s
(lf=0.37) insert 8.50, remove 5.86, reinsert 4.60, clear 0.456, total 100M int time = 19.42 s
emhash7
(lf=0.60) insert 1.06, remove 0.57, reinsert 0.56, clear 0.000, total 10M int time = 2.19 s
(lf=0.74) insert 13.35, remove 7.66, reinsert 9.06, clear 0.000, total 100M int time = 30.07 s
jg_dense
(lf=0.60) insert 1.66, remove 1.70, reinsert 0.66, clear 0.000, total 10M int time = 4.02 s
(lf=0.74) insert 18.66, remove 20.08, reinsert 7.88, clear 0.000, total 100M int time = 46.63 s
rigtorp
(lf=0.30) insert 1.14, remove 0.45, reinsert 0.40, clear 0.128, total 10M int time = 2.12 s
(lf=0.37) insert 10.73, remove 5.38, reinsert 4.56, clear 1.204, total 100M int time = 21.87 s
martinus dense
(lf=0.60) insert 1.44, remove 0.99, reinsert 0.54, clear 0.024, total 10M int time = 3.00 s
(lf=0.74) insert 17.06, remove 13.48, reinsert 7.67, clear 0.220, total 100M int time = 38.43 s
emhash8
(lf=0.60) insert 1.74, remove 1.20, reinsert 0.75, clear 0.028, total 10M int time = 3.71 s
(lf=0.74) insert 20.28, remove 13.99, reinsert 10.16, clear 0.228, total 100M int time = 44.65 s
emhash6
(lf=0.60) insert 1.20, remove 0.58, reinsert 0.70, clear 0.040, total 10M int time = 2.52 s
(lf=0.74) insert 15.48, remove 8.13, reinsert 10.85, clear 0.340, total 100M int time = 34.80 s
emhash5
(lf=0.60) insert 1.21, remove 0.48, reinsert 0.60, clear 0.040, total 10M int time = 2.32 s
(lf=0.74) insert 12.98, remove 7.00, reinsert 7.74, clear 0.340, total 100M int time = 28.06 s

[ktprime]

intel 9700 统一负载因子

ck_hashmap
    (lf=0.30) insert 0.58, remove 0.28, reinsert 0.22, clear 0.016, total 10M int time = 1.09 s
    (lf=0.37) insert 6.11, remove 3.55, reinsert 2.58, clear 0.062, total 100M int time = 12.30 s
emhash7
    (lf=0.30) insert 0.89, remove 0.28, reinsert 0.25, clear 0.000, total 10M int time = 1.42 s
    (lf=0.37) insert 8.92, remove 4.91, reinsert 4.73, clear 0.000, total 100M int time = 18.56 s
jg_dense
    (lf=0.30) insert 1.44, remove 0.98, reinsert 0.36, clear 0.000, total 10M int time = 2.78 s
    (lf=0.37) insert 13.66, remove 11.58, reinsert 4.44, clear 0.000, total 100M int time = 29.67 s
rigtorp
    (lf=0.30) insert 0.81, remove 0.27, reinsert 0.23, clear 0.094, total 10M int time = 1.41 s
    (lf=0.37) insert 7.00, remove 3.34, reinsert 2.67, clear 0.781, total 100M int time = 13.80 s
martinus dense
    (lf=0.30) insert 1.17, remove 0.88, reinsert 0.30, clear 0.016, total 10M int time = 2.36 s
    (lf=0.37) insert 10.64, remove 9.53, reinsert 3.38, clear 0.078, total 100M int time = 23.62 s
emhash8
    (lf=0.30) insert 1.31, remove 0.78, reinsert 0.38, clear 0.000, total 10M int time = 2.47 s
    (lf=0.37) insert 12.19, remove 8.61, reinsert 4.66, clear 0.078, total 100M int time = 25.53 s
emhash6
    (lf=0.30) insert 1.03, remove 0.30, reinsert 0.33, clear 0.016, total 10M int time = 1.67 s
    (lf=0.37) insert 10.39, remove 4.80, reinsert 5.72, clear 0.109, total 100M int time = 21.02 s
emhash5
    (lf=0.30) insert 0.98, remove 0.23, reinsert 0.28, clear 0.016, total 10M int time = 1.52 s
    (lf=0.37) insert 8.23, remove 2.95, reinsert 3.66, clear 0.109, total 100M int time = 14.95 s

[ktprime]

要研究一下他的实现

[zhanglistar]

我看到的点：1，在内存分配的时候就进行初始化，避免后续频繁引发pagefault；2，插入kv，使用placement new。

[ktprime]

他的实现没用到辅助内存metadata，用一个zero key表示空位，和rigtorp实现是相同的，所以相同负载下更节省内存
rehash 实现也比较快

[ktprime]

ck rehash策略非常激进，负载因子还有低于0.25，似乎hashmap 比较小按4倍扩容

[zhanglistar]

是的这个倒是比较激进的。另外，你能看出为何rigtorp Fmiss性能比ck hashmap高吗？看着两者实现一样，该inline的函数也做了。

[ktprime]

我在不同机器测试，有时候rigtorp 插入快一点，ck在qbench find miss 比较差，但mbench 测试查询性能还行，
可能和测试case有关

[zhanglistar]

在qbench有点差的离谱，感觉也不太对。
10000000 Elements:17 | ck::f_hash_map :16 | rigtorp::HashMap:16 | % Faster:8
---------------------+--------------------+--------------------+----------
InsertReserved:17 | 106 ns | 102 ns | 4 %
AccessPresent:17 | 34 ns | 31 ns | 10 %
AccessEmpty:17 | 162 ns | 41 ns | 295 %
IterateFull:17 | 19 ns | 19 ns | 0 %
IterateHalf:17 | 30 ns | 30 ns | 0 %
Erase:17 | 56 ns | 49 ns | 14 %

50000000 Elements:17 | ck::f_hash_map :16 | rigtorp::HashMap:16 | % Faster:8
---------------------+--------------------+--------------------+----------
InsertReserved:17 | 104 ns | 103 ns | 1 %
AccessPresent:17 | 43 ns | 45 ns | -5 %
AccessEmpty:17 | 222 ns | 57 ns | 289 %
IterateFull:17 | 17 ns | 17 ns | 0 %
IterateHalf:17 | 37 ns | 37 ns | 0 %
Erase:17 | 84 ns | 68 ns | 24 %

[ktprime]

所以跑10几多个不同第三方测性能试收起数据才更准
我本地机器还有很多复杂的第三方测试，有时候相同程序换一个cpu结果都差异较大，全面测试是比较难的， 通常find miss 比find hit 要慢一点（高负载下）

[ktprime]

find命中分别从0 25% 50% 75% 100% 累计耗时

                 rigtorp nums = 1000000 total time = 5.19
                 emilib2 nums = 1000000 total time = 3.54
                 emilib3 nums = 1000000 total time = 3.68
              boost_flat nums = 1000000 total time = 3.42
              ck_hashmap nums = 1000000 total time = 5.57
                 emhash8 nums = 1000000 total time = 3.87
                 emhash5 nums = 1000000 total time = 5.16
                 emhash6 nums = 1000000 total time = 5.04
                 emhash7 nums = 1000000 total time = 4.81

                 rigtorp nums = 10000000 total time = 17.69
                 emilib2 nums = 10000000 total time = 17.09
                 emilib3 nums = 10000000 total time = 17.23
              boost_flat nums = 10000000 total time = 16.81
              ck_hashmap nums = 10000000 total time = 20.60
                 emhash8 nums = 10000000 total time = 19.07
                 emhash5 nums = 10000000 total time = 17.83
                 emhash6 nums = 10000000 total time = 17.88
                 emhash7 nums = 10000000 total time = 16.71

[ktprime]

Model name: Intel(R) Xeon(R) Silver 4210 CPU @ 2.20GHz
Stepping: 7
CPU MHz: 2699.914
CPU max MHz: 3200.0000
CPU min MHz: 1000.0000

                 rigtorp nums = 100 total time = 2.04
              ck_hashmap nums = 100 total time = 2.13
          martinus dense nums = 100 total time = 3.02
                 emhash5 nums = 100 total time = 2.13
                 emhash7 nums = 100 total time = 2.36

                 rigtorp nums = 5000 total time = 2.02
              ck_hashmap nums = 5000 total time = 1.51
          martinus dense nums = 5000 total time = 2.17
                 emhash5 nums = 5000 total time = 1.75
                 emhash7 nums = 5000 total time = 1.78

                 rigtorp nums = 1000000 total time = 6.95
              ck_hashmap nums = 1000000 total time = 6.51
          martinus dense nums = 1000000 total time = 6.93
                 emhash5 nums = 1000000 total time = 7.04
                 emhash7 nums = 1000000 total time = 6.56

                 rigtorp nums = 10000000 total time = 25.79
              ck_hashmap nums = 10000000 total time = 29.35
          martinus dense nums = 10000000 total time = 36.33
                 emhash5 nums = 10000000 total time = 34.48
                 emhash7 nums = 10000000 total time = 31.98

[ktprime]

可以切到mbench， 测试比较全面但比较久可以关掉一些不敢兴趣的， ebench是我写的也不错没集成ck，测试方法与大多数第三方测试大不一样

[zhanglistar]

我简单修了下qbench，提了个PR。

[zhanglistar]

你有改造absl::flat_hash_map为max load factor是0.5的版本吗？

[ktprime]

你有改造absl::flat_hash_map为max load factor是0.5的版本吗？

改动很简单，在rehash 判断条件改就行，目前看absl max_load_factor改成 0.5 插入性能估计也赢不了ck，absl 多一个meta，他的优势是高负载下性能依旧很好，我本地可以测一下

[zhanglistar]

absl这个版本性能不太行。

[ktprime]

低负载因子下使用最简单冲突处理，更少的内存消耗意味着插入更快。同时也意味着需要更多内存，查询性能要下降的
刚才测试abs 性能插入提升很小，在数据规模很大情况下，metadata无法塞入cpu cache 导致更多cache miss 所以absl
面对大量数据插入查找命中性能不会特别出众。

[ktprime]

每个hashmap 设计时应该有一个综合方面权衡，不可能全方面的胜利，上帝是公平的
absl 从2019开始放弃插入性能着重提升查询性能，在数据据百万级性能还是不错的， robin_hood 也是相同的设计理念
emhash 最初目标是做到业界查询命中最快性能（目前基本实现）。如果开启一个编译宏EMH_HIT 查询命中还能
提升10%（仅仅为了减少一次if判断），但是低负载查询miss 性能要下降，插入方面应为设计原因hash冲突后需要做冲突腾挪会损失20%性能，删除和迭代性能目前也是比较突出的（可以去找其他第三方测试），对我的实现做过大量的性能分析，优缺点比较清楚
目前下第三方库定期更新基本都是最新的（每周检查是否有更新）

[zhanglistar]

我去研究下你的hashmap，回头有问题再来交流。

[ktprime]

absl针对复杂的k.v（比如string, value 比较大）优势明显。能充分体现metadata带来的益处

[zhanglistar]

大value一般用node map了吧 也不会走flat map或者自己做pool，还是用flat map但是value用指针，key依然是uint64_t.

[ktprime]

通常这么解决，但会带来大量内存分配和二次内存访问value，性能是有一定开销