java - 使用结构/类来增加缓存空间局部性？

Question

如果使用 1000 行计算机代码而不是独立声明变量，而是将它们组合在一起（显然这确实取决于所使用的变量大小）到类和结构中，这是否会直接增加缓存空间局部性（因此降低缓存未命中率）？

我的印象是通过将类/结构中的变量关联起来，它们将被分配连续的内存地址？

Answer 1

如果不做出一些非常不合理的假设，就不可能回答这个问题。空间局部性与算法和数据结构一样重要，因此根据您使用的算法将逻辑相关的数据元素组合在一起可能没有任何意义，甚至更糟。

例如，考虑 3D 空间中 100 个点的表示。您可以将它们放在三个单独的数组中，或者创建一个 3 元组结构/类，然后将它们组成一个数组。

如果您的算法必须在每一步中一次获取每个点的所有三个坐标，则元组表示获胜。但是，想想如果你想构建一个在每个维度上独立运行的算法，并在三个独立线程之间进行三向并行化，会发生什么情况。在这种情况下，三个单独的数组将胜出，因为该布局将避免错误共享，并就一次一维算法而言改善空间局部性。

这个例子表明没有“一刀切”的解决方案。应始终在特定算法的上下文中考虑空间局部性；在一种情况下，一个好的解决方案可能会在其他看似相似的情况下变得糟糕。

Answer 2

如果您在谈论方法局部变量，它们在堆栈上已经是连续的，或者严格来说在几乎总是在堆栈上的激活记录中。如果您正在谈论对 Java 对象的引用，或指向动态分配的 C++ 对象的指针，那么将它们放入包含类中不会有任何区别，因为另一个原因：相关对象仍将位于堆中的任意位置。

Answer 3

如果您询问是否将局部变量分组到明确定义的结构中，则不会有优势。局部变量是根据激活记录实现的，对于任何同时具有这两者的语言，它通常与类结构的实现密切相关。

因此，局部变量应该已经具有良好的空间局部性，除非语言实现正在做一些奇怪的事情来搞砸它。

您可以通过将递归期间未使用的大块本地状态隔离到单独的非递归函数中来改善局部性。这将是一个微优化，因此您需要先检查机器代码以确保它不会浪费时间。无论如何，这与将本地人移动到class.