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

Question

我在读下面的文章，

What Every Programmer Should Know About Compiler Optimizations

其他一些重要的优化目前超出了任何编译器的能力--例如，用高效的算法替换效率低下的算法，或者改变数据结构的布局以提高其局部性。

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

所以,

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

在表现上与，

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

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

Answer 1

我不是数据/结构局部性方面的专家，但这与您如何组织数据有关，以避免CPU缓存来自整个CPU的内存位，从而通过不断等待内存获取来减缓程序的速度。

例如，链接列表可以是分散在内存中的列表。但是，如果您将其转换为一个“元素”数组，那么它们都位于连续内存中--如果您需要同时遍历它们的数组，这将节省内存访问时间(这只是一个例子)。

另外，：也不知道一些STL库，我也不能100%确定哪个是最好的，但是其中一些(例如list)在局部性方面非常糟糕。另一个可能更常见的例子是指针数组，指向元素的指针可以分散在内存中。当然，您不能总是容易地避免这种情况，因为有时需要能够动态添加/移动/插入/删除元素.

摘要：--它基本上意味着要注意如何布局与内存访问有关的数据。

Answer 2

根据访问类成员的频率对类成员进行排序。这最大限度地提高了包含类头的缓存行的“热度”，增加了保持缓存的可能性。您关心的另一个因素是打包--由于对齐，重新安排成员声明的顺序可能会导致类大小的减少，从而减少缓存压力。

(当然，它们都不是决定性的。这些经验法则并不能代替分析。)