在缓存中保存数据的技术，局部性？

Question

对于超快的代码，我们必须保持引用的局部性-在CPU缓存中保留尽可能多的紧密使用的数据：

http://en.wikipedia.org/wiki/Locality_of_reference

有什么技术可以做到这一点呢？人们能举个例子吗？

我对Java和C/C++示例很感兴趣。了解人们用来阻止大量缓存交换的方法很有趣。

问候

Answer 1

这可能太笼统了，没有明确的答案。与Java语言相比，C或C++中的方法会有很大的不同(语言布局对象的方式不同)。

基本的做法是，将要访问的数据放在一起进行闭环。如果您的循环对类型T进行操作，并且其成员为m1...mN，但在关键路径中仅使用m1...m4，请考虑将T分解为包含T1的m1...m4和包含m4...mN的T2。您可能想要向T1添加一个引用T2的指针。尽量避免与缓存边界不对齐的对象(非常依赖于平台)。

使用连续的容器( C中的普通老数组，C++中的向量)，并尝试管理迭代来向上或向下，而不是在容器上随机跳跃。链表是局部性的杀手，列表中的两个连续节点可能位于完全不同的随机位置。

Java中的对象容器(和泛型)也是杀手，而在Vector中，引用是连续的，而实际对象不是(有额外的间接层)。在Java语言中有很多额外的变量(如果你一个接一个地new两个对象，那么这两个对象很可能最终会被放在几乎相邻的内存位置上，即使在它们之间会有一些额外的对象管理数据信息(通常是两个或三个指针)。GC将移动对象，但希望不会使事情变得比它运行之前更糟糕。

如果你专注于Java语言，创建紧凑的数据结构，如果你有一个对象有一个位置，并且要在一个紧密的循环中访问，考虑在你的对象中保留一个x和y原语类型，而不是创建一个Point并保持对它的引用。引用类型需要更新，这意味着不同的分配，额外的间接性和更少的局部性。

Answer 2

两种常见技术包括：

缓存最小化( size/paths)

• Use

的数据大小和/或代码

在光线跟踪(一种3d图形渲染范例)中，使用8字节Kd-来存储静态场景数据是一种常见的方法。遍历算法只需几行代码即可。然后，Kd-树通常以一种方式编译，该方式通过在树的顶部具有大的空节点来最小化遍历步骤的数量(Havran的“Surface Area Heuristic”)。

错误预测的概率通常为50%，但代价很小，因为缓存线中可以容纳许多节点(考虑到每个KiB！有128个节点)，并且两个子节点中的一个始终是内存中的直接邻居。

缓存无关技术的示例:曲线索引( Morton array indexing )，也称为Z顺序曲线索引。如果您通常以不可预测的方向访问附近的数组元素，则这种索引可能是首选的。这对于大图像或体素数据可能很有价值，因为你可能有32甚至64字节的大像素，然后是数百万个(典型的紧凑型相机测量是百万像素，对吧？)甚至数千亿用于科学模拟。

然而，这两种技术有一个共同点:把最常访问的东西放在附近，不太频繁的东西可能离得越远，从主内存到硬盘的整个L1缓存范围，然后是同一房间、隔壁房间、同一国家、世界各地和其他星球上的其他计算机。

Answer 3

一些随机的技巧出现在我的脑海中，其中一些是我最近用过的：

重新思考你的算法。例如，您有一个带有形状的图像，以及查找该形状角点的处理算法。您可以对其进行预处理，将形状的所有像素坐标保存在一个列表中，然后对该列表进行操作，而不是直接对图像数据进行操作。你避免在图像周围随意跳跃

收缩数据类型。常规的int将占用4个字节，如果您设法使用uint16_t，您将缓存2倍以上的内容

有时你可以使用位图，我用它来处理二进制图像。我按位存储像素，因此我可以在单个缓存线中容纳8*32个像素。它确实提高了性能

在Java中，您可以使用JNI (这并不难)，并用C实现关键代码来控制内存