大數據集的高效重新排序以最大化內存緩存效率

我一直在研究一個我認爲人們可能會感興趣的問題（也許有人知道預先存在的解決方案）。大數據集的高效重新排序以最大化內存緩存效率

我有一個大的數據集，包括對指針的對象一長串的，是這樣的：

[ 
    (a8576, b3295), 
    (a7856, b2365), 
    (a3566, b5464), 
    ... 
]

有太多的對象在內存中保留在任何時間（可能是數百個千兆字節），因此它們需要存儲在磁盤上，但可以緩存在內存中（可能使用LRU緩存）。

我需要運行這個列表處理每一對，這需要對中的兩個對象都加載到內存中（如果它們尚未被緩存）。

因此，問題是：有沒有一種方法可以對列表中的對進行重新排序，以最大限度地提高內存緩存的效率（換言之：最大限度地減少緩存未命中次數）？

注

顯然，重新排序的算法應該是儘可能地快，而不應依賴於能夠在內存中的整個列表一次（因爲我們不」沒有足夠的內存） - 但它可以在需要的時候多次迭代列表。
如果我們在處理單個對象而不是對，那麼簡單的答案就是對它們進行排序。在這種情況下，這顯然不起作用，因爲您需要考慮對中的兩個元素。
該問題可能與該找minimum graph cut的，但即使問題是等價的，我不認爲解決方案，以最小切割滿足
我的假設是，啓發式會在流將數據從磁盤中取出，並以更好的順序將其重新寫入塊中。它可能需要迭代幾次。
其實它可能不只是成對，它可能是三胞胎，四胞胎或更多。我希望能夠很容易地推廣一種可以簡化對的算法。

來源

2009-01-31 sanity

你的問題涉及到用一個類似計算機圖形硬件：

當一個三角形網格渲染索引的頂點，通常是硬件有最近變換的頂點（〜128的高速緩存中的最後一次，我不得不擔心它，但懷疑這些天數量更大）。未緩存的頂點需要相對昂貴的變換操作進行計算。「網格優化」重構三角網格以優化高速緩存使用率曾經是一個相當熱門的研究課題。谷歌搜索頂點高速緩存優化（或優化：^）可能會找到一些有趣的材料與您的問題相關。正如其他海報所建議的那樣，我懷疑有效地做到這一點將取決於在數據中利用任何固有的一致性。

另一件需要注意的事情是：隨着LRU緩存過載，最好將MRU替換策略改爲至少保存內存中的某些內容（而不是每次傳遞整個緩存）。我似乎記得John Carmack在Direct3D紋理緩存策略方面已經寫了一些關於這個主題的很好的材料。

來源

2009-02-01 10:30:33 timday

我認爲這個問題的答案將嚴重依賴於這對物體的訪問模式。正如你所說的，僅僅對一個簡單的，不匹配的情況進行排序就是最好的。在更復雜的情況下，如果模式是這樣的，那麼這些值的局部性更重要（例如，如果這些是鍵/值對，並且您正在做一個很多搜索，鍵的局部性比值更重要）。

所以，我的答案是，這個問題在一般情況下是無法回答的。

爲了存儲你的結構，你真正想要的可能是B-tree。這些都是爲您所談論的內容而設計的 - 跟蹤您不想（或不能）將整個內容保存在內存中的大型集合。

來源

2009-01-31 21:29:24 SoapBox

訪問第一個或第二個對象的成本是相同的。在一般情況下，我仍然樂觀地認爲有辦法回答這個問題 - 就像最小圖形切割這樣的問題確實有一般情況下的解決方案。 – sanity 2009-01-31 22:44:01

首先，你可以列出mmap。如果有足夠的地址空間而不是內存，那麼這是有效的。在64位CPU上。這使得按順序訪問元素變得更加容易。

您可以根據緩存中考慮這兩個元素的最小距離對列表進行排序，如果對象位於連續空間中，那麼效果很好。排序函數可能類似於：比較（a，b）到（c，d）=（a - c）+（b - d）（看起來像一個漢明距離）。然後你根據列表拉入對象存儲和處理的片段。

編輯：修正了距離的錯誤。

來源

2009-01-31 21:35:55

即使你不只是排序此列表，multiway merge sort的一般模式可能適用 - 也就是說，考慮某種設定的（可能遞歸）細分成可以處理較小的集分別存儲在內存中，然後是第二階段，其中先前處理的小組塊可以全部組合在一起。即使不知道你對這些對的具體性質，可以肯定地說，當你處理排序後的數據時（包括圖形問題，這可能是你對你有什麼問題），許多算法問題變得更直接手在這裏）。

來源

2009-01-31 21:48:12

大數據集的高效重新排序以最大化內存緩存效率

回答

相關問題