数据结构的局部性是什么意思？

Question

我正在阅读以下文章,

还有其他重要的优化目前超出了任何编译器的功能 - 例如,用有效的算法替换低效算法,或者改变数据结构的布局以改善其局部性.

这是否意味着如果我改变类中数据成员的顺序(布局),它会影响性能？

所以,

class One
{
int data0;
abstract-data-type data1;
};

性能差异,

class One
{
abstract-data-type data0;
int data1;
};

如果这是真的,那么在定义类或数据结构时,经验法则是什么？

Answer 1

从这个意义上讲，局部性主要是指缓存局部性。编写主要在缓存外运行的数据结构和算法可以使算法尽可能快地运行。缓存局部性是快速排序快速的原因之一。

对于数据结构，您希望保持数据结构中相互引用的部分彼此相对靠近，以避免刷新有用的缓存行。

此外，您还可以重新排列数据结构，以便编译器将使用保存所有成员所需的最小内存量并仍然有效地访问它们。这有助于确保您的数据结构消耗最少数量的缓存行。

_{当前 x86-64 架构（核心 i7）上的单个缓存行为 64 字节。}