c++ - llvm::DenseMap 和 std::map 之间的差异/相似之处

Question

最近我遇到了在 llvm 中广泛使用的 DenseMap 数据结构。我认为它是 std::map(?) 的某种优化版本。谁能帮助我了解它们之间的区别或相似之处？

Answer 1

llvm::DenseMap 是 std::unordered_map 的替代品，所以它并不是要替代 std::map(在至少如果您根据有序属性和无序属性仔细选择的话，则不会。

与 std::unordered_map 不同，std::map 保证容器的迭代顺序与比较器定义的顺序相匹配(默认情况下，std::更少)。在许多情况下，您不关心迭代顺序...但在少数情况下它很重要，DenseMap 不是一个选项。

现在，将 DenseMap 与 std::unordered_map 进行对比:与 std 容器不同，DenseMap 保留所有它的数据在一个内存分配中，并且它取消了桶，有利于在内存中保持键和值彼此相邻。这两个功能都是 data locality 的一大胜利从而在几乎所有情况下都能提高速度。

此外，DenseMap 默认分配大量键/值对(实际上是 64 个)，因此在小尺寸时，插入几乎是免费的。当然，这样做的缺点是，如果您要创建很多非常小的映射，或者如果您的类型本身很大，那么内存效率会很低；如果您的容器永远不会增长到 64 个元素，那么您就是在浪费内存。根据您的用例，这可能会或可能不会真正伤害您。

与 std::unordered_map 相比的最后一个区别可能会让一些人措手不及:DenseMap 的迭代器在每次 插入后失效(与 std::map 和 std::unordered_map 不同，其中迭代器仅在发生缓存重新散列时才会失效)。这在我看来主要是一个理论问题，因为您当然可以只存储键而不是迭代器。 (与 vector 不同的是，很难找到保留映射迭代器的真实代码。)

我整理了一些 benchmarks将 DenseMap 与 std 容器以及 a GitHub repo 进行比较如果您想在自己的机器上运行基准测试。下面是四个选定的图表，显示了各种尺寸的 map 的插入和随机查找速度。

小 map 的插入速度

大 map 中的插入速度

小 map 中的随机查找

大 map 中的随机查找