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這樣的操作，它們甚至不需要查看值，但可能需要通過碰撞鍵或三個鍵來導航。