关于 Swiss Table (absl::flat_hash_map)

[shines77]

最近测试我改进的swiss table- emilib2/3. 我的实现查询性能比官方慢20%，插入则快20%，一直分析对比查找哪里查询慢(我在乎查询性能)，一个区别在于我使用线性探测，而swiss table使用二次探测，还有你之前说的swiss做了随机内存地址优化，这些难道是主要原因？

-------------------------------- function benchmark -----------------------------------------------
erase_50
  85        emilib3                100.0%
  95        emilib2                89.9%
  97        absl_flat              87.5%

erase_reinsert
  62        absl_flat              100.0%
  88        emilib3                70.1%
 100        emilib2                62.2%

find_erase_50
  79        absl_flat              100.0%
  94        emilib3                84.1%
  99        emilib2                80.3%

find_hit_0
  85        absl_flat              100.0%
  92        emilib2                92.8%
  98        emilib3                87.2%

find_hit_100
  83        absl_flat              100.0%
  94        emilib2                88.5%
  97        emilib3                85.7%

find_hit_50
  85        absl_flat              100.0%
  93        emilib2                91.3%
  97        emilib3                87.2%

find_hit_50_erase
  91        absl_flat              100.0%
  94        emilib3                97.2%
  98        emilib2                92.9%

hash_iter
  44        emilib2                100.0%
  44        emilib3                99.0%
 100        absl_flat              44.3%

insert_erase
  71        emilib3                100.0%
  86        absl_flat              82.9%
  97        emilib2                73.0%

insert_find_erase
  76        emilib3                100.0%
  93        emilib2                81.6%
  96        absl_flat              79.0%

insert_hit
  93        emilib3                100.0%
  96        emilib2                96.4%
  97        absl_flat              96.0%

insert_l1_cache
  33        emilib2                100.0%
  35        emilib3                94.5%
 100        absl_flat              33.5%

insert_l3_cache
  86        emilib3                100.0%
  89        emilib2                97.2%
  97        absl_flat              89.0%

insert_no_reserve
  94        emilib3                100.0%
  95        absl_flat              99.7%
  96        emilib2                97.9%

multi_small_ife
  84        emilib3                100.0%
  93        emilib2                90.8%
  95        absl_flat              88.5%

======== hash  top1   top2  top3 =======================
    absl_flat  2.0   4.0   22
      emilib2  0.0  22.0    6
      emilib3 26.0   2.0    0
======== hash    score  weigh ==========================
    absl_flat    85     92.4%
      emilib2    88     95.0%
      emilib3    93     100.0%
--------------------------------------------------------------------

_Originally posted by @ktprime in https://github.com/shines77/jstd_hashmap/issues/1#issuecomment-1236772597_

[shines77]

这是你在 https://github.com/shines77/jstd_hashmap/issues/1 里的回复, 我移至这里了。

Google 的 Swiss Table (也就是 absl::flat_hasp_map) 现在的确使用的是二次探测，由于它的原理，absl::flat_hasp_map 对于小对象 Key (int 和 int64_t)，使用非 gcc/clang 下的 std::hash 哈希函数（因为此时 std::hash(key) = key），查询速度还是不错的，大对象的话，查询性能一般。

我没看过你的 emilib2/3 的代码，不知道性能差异主要在哪，大概率可能是二次探测的原因。 absl::flat_haspmap 没有做随机地址优化，但是它是把 ctrls 和 slots 的内存是统一分配的，并且 slots 做了地址对齐，但是我也对 jstd::robin_hash_map 做了如此的修改，实测下来，性能是下降的。我也没想明白，理论上合并在一起分配内存是更优的（而且做了对齐），但实测却慢了20%左右。

[ktprime]

我的代码在这 https://github.com/ktprime/emhash/blob/master/thirdparty/emilib/emilib2.hpp https://github.com/ktprime/emhash/blob/master/thirdparty/emilib/emilib2s.hpp 第一个查询快，第二个插入快（按16个gourp对齐），

[shines77]

我知道，我看你的更新记录就看到了，但是没时间研究

[ktprime]

看你很久没更新了

[shines77]

看你很久没更新了

嗯, 魔兽世界怀旧服WLK开了, 我去玩了一阵

最后那次更新, 我改进了使用 IndirectKV 版本(使用 index 指向KV)的迭代器 Iterator, 迭代器的效率和 ankerl::unordered_dense::map, emhash8 的一样了.

的确, 两种版本的迭代器还是很不一样的.

另外, 我也分析了我和 ankerl::unordered_dense::map 的差别和差距在哪里. 大概有两点: 一是 max load factor 的区别, 他是0.8, 我是0.5; 二是, 他用了一个 std::vector 保存 KV 数组, buckets的扩容是和 KV 数组的扩容是分开处理的. 传统的 dense hashmap 都是两者同时扩容的, 我写的时候也发现了这个问题, 但没处理.

两者分开处理扩容, 这样迁移整个 KV 数组的总次数就变少了, 使用更高的 mlf, 总的扩容次数也可能变少(只是可能), 但是由于在玩魔兽世界怀旧服, 没什么心情去改, 晚一点可能会更新一下

上次的更新已经更接近的 ankerl::unordered_dense::map 性能了, 不知道改了以后是否更接近.

[shines77]

IndirectKV 版本的 KV 数组扩容的问题和迭代器的问题是类似的, 因为 IndirectKV 的特点, 都应该特殊处理的, 改的过程有发现这个问题, 但没进一步思考. 仔细看了 ankerl::unordered_dense::map 之后, 才确定必须得这么做, 也应该这么做.

[ktprime]

ankerl::unordered_dense::map 在服务器上测试效果没那么好，特别比较旧的cpu上 可能原因是Indirect 访问内存效率低一些

[ktprime]

martinus 似乎又在测试， 你的库整理好给他提PR

[ktprime]

boost 最新版本flat hash_map https://github.com/boostorg/unordered/blob/d3914d71016c12fb7801b5704a8cdda79d8b8198/include/boost/unordered/detail/foa.hpp 似乎超过absl