C++中的HashTable性能优化( 三 ) _C++

可以看到std::unordered_map L1-dcache miss率为3.17% ， absl::node_hash_map为0.74% ， absl::flat_hash_map为0.68% ，验证了上述关于不同内存模型下cpu cache性能表现的推论。
基准测试结果如下（为了显示更清晰，将元素个数小于1024的和大于1024的分开展示）：

文章插图

图4 写操作，元素个数小于等于1024

文章插图

图5 写操作，元素个数大于等于1024

文章插图

图6 读操作，元素个数小于等于1024

文章插图

图7 读操作，元素个数大于等于1024
从测试结果可以看出，写操作耗时：std::unordered_map < absl::flat_hash_map < absl::node_hash_map ， absl::flat_hash_map比std::unordered_map耗时平均增加9%；读操作耗时：absl::flat_hash_map < absl::node_hash_map < std::unordered_map ， absl::flat_hash_map比std::unordered_map耗时平均降低20% 。
总结
三种HashTable对比如下：
HashTable类型
内存模型
性能表现
推荐使用场景
std::unordered_map
以链表存储hash值相同的元素
写操作：rehash友好，性能最好；读操作：内存不连续， cpu cache命中率较低，性能最差
写多读少
absl::node_hash_map
在连续内存中存储hash值相同的元素的指针
写操作：性能最差；读操作：性能略差于absl::flat_hash_map；
读多写少，且需要保证pair的指针稳定性
absl::flat_hash_map
在连续内存中存储hash值相同的元素
写操作：性能略差于std::unordered_map；读操作：内存连续， cpu cache命中率较高，性能最好
读多写少
在读多写少的场景使用HashTable ，可以用absl::flat_hash_map替代std::unordered_map ，获得更好的查询性能。但需注意absl::flat_hash_map在rehash时会将pair move到新的内存地址，导致访问原始地址非法。
absl::flat_hash_map的接口类似于std::unordered_map ，详细介绍可参阅absl官方文档：https://abseil.io/docs/cpp/guides/container#hash-tables

absl::flat_hash_map源码：abseil-cpp/flat_hash_map.h at master · abseil/abseil-cpp · GitHub
std::unordered_map源码：gcc/unordered_map.h at master · gcc-mirror/gcc · GitHub
folly 14-way hash table：folly/F14.md at main · facebook/folly · GitHub
robin_hood hash table：GitHub - martinus/robin-hood-hashing: faster and more memory efficient hashtable based on robin hood hashing for C++11/14/17/20

【C++中的HashTable性能优化】