java - 将数据保存在缓存、位置的技术？

Question

对于超快的代码，我们必须保持引用的位置 - 将尽可能多的紧密使用的数据保存在 CPU 缓存中:

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

实现这一目标的技术是什么？有没有人能举个例子？

我对 Java 和 C/C++ 示例感兴趣。很想知道人们用来停止大量缓存交换的方法。

问候

Answer 1

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

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

使用连续的容器(C 中的普通旧数组，C++ 中的 vector )并尝试管理迭代向上或向下，但不要随机跳遍整个容器。链表是局部性的 killer ，列表中的两个连续节点可能位于完全不同的随机位置。

Java 中的对象容器(和泛型)也是一个 killer ，而在 Vector 中引用是连续的，实际对象不是(有额外的间接级别)。在 Java 中有很多额外的变量(如果你一个接一个地 new 两个对象，这些对象可能最终会位于几乎连续的内存位置，即使会有一些额外的信息(通常是两个或三个指针)之间的对象管理数据。GC 会四处移动对象，但希望不会使事情比运行前更糟。

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