noexcept 影响 libstdc++ 的 unordered_set

主要观点:

  • GNU libstdc++的基于哈希的关联容器的节点结构布局会根据哈希函数的noexcept特性而改变,这在文档中虽有提及但较易被忽略。
  • std::unordered_set本质上是由“桶”和“节点”组成,删除元素时若先比较哈希值可能更优,但哈希函数较慢时则是反优化。
  • 可以在节点中预计算并存储哈希值,这样在erase(const T&)erase(const_iterator)和重新哈希时都能受益,但对于unordered_set<int>等简单类型,存储哈希值可能较傻。
  • libstdc++的unordered_set性能特性依赖于哈希函数的真实名称和noexcept特性,用户定义的哈希函数在不同noexcept设置下会有不同的性能表现。
  • 有一个基准测试展示了libstdc++启发式算法的一些后果,不同类型在不同哈希函数设置下的节点大小和重新哈希时间不同。
  • 总体而言,这一现象在实际编程中大多无关紧要,但比特币核心曾因类似问题而受到影响,若性能受单个哈希表数据结构主导,可能需要优化该结构。

关键信息:

  • unordered_set的数据结构及erase函数的实现细节。
  • 存储哈希值在节点中的好处及不同情况下的适用性。
  • libstdc++中影响unordered_set性能的哈希函数特性及相关判断条件。
  • 基准测试的结果及不同类型和哈希函数设置下的表现。

重要细节:

  • unordered_set中通过桶和节点存储元素,删除元素时遍历桶中的节点并比较元素值或哈希值。
  • 存储哈希值可节省erase(const T&)的时间,在erase(const_iterator)和重新哈希时也需要哈希值。
  • libstdc++中根据哈希函数是否在黑名单、是否为noexcept来决定是否存储哈希值。
  • 基准测试中不同类型(int*stringvector<bool>)在不同哈希函数设置下的节点大小和重新哈希时间。
  • 比特币核心因哈希函数未标记noexcept而导致unordered_map内存占用增加,添加noexcept关键字后降低了内存使用。
阅读 11
0 条评论