数据结构的局部性是什么意思？
What is meaning of locality of data structure?
我正在阅读以下文章，
What Every Programmer Should Know About Compiler Optimizations
There are other important optimizations that are currently beyond the
capabilities of any compiler—for example, replacing an inefficient
algorithm with an efficient one, or changing the layout of a data
structure to improve its locality.
这是否意味着如果我更改 class 中数据成员的顺序 (layout)，它会影响性能吗？
所以，
class One
{
int data0;
abstract-data-type data1;
};
性能不同于
class One
{
abstract-data-type data0;
int data1;
};
如果这是真的，定义 classes 或数据结构时的经验法则是什么？
Locality 在这个意义上主要是指 cache locality。编写数据结构和算法以主要在缓存外运行使算法 运行 尽可能快。缓存局部性是 快速排序 快速的原因之一。
对于数据结构，您希望使数据结构中相互引用的部分彼此相对靠近，以避免清除有用的缓存行。
此外，您可以重新安排数据结构，以便编译器使用最少的内存来容纳所有成员并仍然有效地访问它们。这有助于确保您的数据结构使用最少数量的缓存行。
A single cache line on a current x86-64 architecture (core i7) is 64 bytes.
我不是 data/structure 局部性方面的专家，但这与您组织数据的方式有关，以避免 CPU 缓存来自整个 CPU 的内存位从而通过不断等待内存获取来减慢您的程序。
例如，链表可以散布在您的整个内存中。但是，如果您将其更改为 "elements" 的数组，那么它们都在连续的内存中 - 如果您需要一次遍历它们的数组，这将节省内存访问时间（这只是一个示例）
另外：
还要注意一些 STL 库，我也不是 100% 确定哪个是最好的，但其中一些（例如列表）在局部性方面非常糟糕。
另一个可能更常见的例子是指针数组，其中指向的元素可以分散在内存中。
当然，您不能总是轻易避免这种情况，因为有时您需要能够动态 add/move/insert/delete 元素...
总结：
它基本上意味着注意如何根据内存访问布局数据。
按您访问成员的频率对 class 成员进行排序。这最大化了包含 class 头部的缓存行的 "hotness"，增加了它保持缓存的可能性。您关心的另一个因素是打包 - 由于对齐，重新排列成员声明的顺序可能会导致 class 大小的减少，从而减少缓存压力。
（当然，None 是确定的。这些经验法则不能代替分析。）
我正在阅读以下文章，
What Every Programmer Should Know About Compiler Optimizations
There are other important optimizations that are currently beyond the capabilities of any compiler—for example, replacing an inefficient algorithm with an efficient one, or changing the layout of a data structure to improve its locality.
这是否意味着如果我更改 class 中数据成员的顺序 (layout)，它会影响性能吗？
所以，
class One
{
int data0;
abstract-data-type data1;
};
性能不同于
class One
{
abstract-data-type data0;
int data1;
};
如果这是真的，定义 classes 或数据结构时的经验法则是什么？
Locality 在这个意义上主要是指 cache locality。编写数据结构和算法以主要在缓存外运行使算法 运行 尽可能快。缓存局部性是 快速排序 快速的原因之一。
对于数据结构，您希望使数据结构中相互引用的部分彼此相对靠近，以避免清除有用的缓存行。
此外，您可以重新安排数据结构，以便编译器使用最少的内存来容纳所有成员并仍然有效地访问它们。这有助于确保您的数据结构使用最少数量的缓存行。
A single cache line on a current x86-64 architecture (core i7) is 64 bytes.
我不是 data/structure 局部性方面的专家，但这与您组织数据的方式有关，以避免 CPU 缓存来自整个 CPU 的内存位从而通过不断等待内存获取来减慢您的程序。
例如，链表可以散布在您的整个内存中。但是，如果您将其更改为 "elements" 的数组，那么它们都在连续的内存中 - 如果您需要一次遍历它们的数组，这将节省内存访问时间（这只是一个示例）
另外： 还要注意一些 STL 库，我也不是 100% 确定哪个是最好的，但其中一些（例如列表）在局部性方面非常糟糕。 另一个可能更常见的例子是指针数组，其中指向的元素可以分散在内存中。 当然，您不能总是轻易避免这种情况，因为有时您需要能够动态 add/move/insert/delete 元素...
总结： 它基本上意味着注意如何根据内存访问布局数据。
按您访问成员的频率对 class 成员进行排序。这最大化了包含 class 头部的缓存行的 "hotness"，增加了它保持缓存的可能性。您关心的另一个因素是打包 - 由于对齐，重新排列成员声明的顺序可能会导致 class 大小的减少，从而减少缓存压力。
（当然，None 是确定的。这些经验法则不能代替分析。）