C++缓存友好哈希映射分隔键/值

Question

在这个CppCon视频，迈克·阿克顿谈到哈希映射隔离键/值：

https://www.youtube.com/watch?v=rX0ItVEVjHc

但是他给很少的解释他的意思。

我试图找到关于该主题的更多信息，但是我发现了任何东西。

有没有人能解释我他的确切含义？

Answer 1

我不记得他发言中的哈希映射部分，但它必须是关于缓存未命中的。

他说，至少从去年开始留在我心中;我们在学校学到的理论信息（例如，在二进制映射logN中搜索，散列常数...）是好的，但我们正在使用机器，我们不能忽视它们的工作方式。例如，他给出了关于延迟的例子。他给出了关于l1，l2缓存未命中的不同例子。并且只是改变数据的内存布局（他将一些数据循环到另一个结构中，帮助CPU适应循环到64位寄存器的所有数据），他可以使相同的代码运行速度提高10倍。 “我也对他的报价印象深刻” “我们必须了解数据，不同的数据意味着不同的算法”。

Answer 2

你还没有给出任何你对混淆的看法，所以我将从最一般的概述开始 - 如果你有更具体的问题的话。

我还没有看过YouTube视频，但是从他的其他作品中可以看出，他的观点是，有时候将键保存在一个内存区域与映射值分开，有时会更高效。这与存储std::pair<const key_type, mapped_type>值的std::unordered_map形成对比 - 清楚地将键和值并列存储在内存中。把键放在一起意味着更少的缓存未命中，特别是对于像count这样的操作，它们甚至不需要查看值，但可能需要通过碰撞键或三个键来导航。