大数据集的高效重新排序以最大化内存缓存效率

我一直在研究一个我认为人们可能会感兴趣的问题（也许有人知道预先存在的解决方案）。大数据集的高效重新排序以最大化内存缓存效率

我有一个大的数据集，包括对指针的对象一长串的，是这样的：

[ 
    (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

大数据集的高效重新排序以最大化内存缓存效率

回答

相关问题