CPU C中使用链表缓存的缺点
CPU Cache disadvantages of using linked lists in C
我想知道与 C 中的连续数组相比，链表的优点和缺点是什么。因此，我阅读了一篇关于链表的维基百科文章。
https://en.wikipedia.org/wiki/Linked_list#Disadvantages
根据这篇文章，缺点如下：
- They use more memory than arrays because of the storage used by their pointers.
- Nodes in a linked list must be read in order from the beginning as linked lists are inherently sequential access.
Difficulties arise in linked lists when it comes to reverse traversing. For instance, singly linked lists are cumbersome to navigate backwards and while doubly linked lists are somewhat easier to read, memory is wasted in allocating.
Nodes are stored incontiguously, greatly increasing the time required to access individual elements within the list, especially with a CPU cache.
我理解前 3 点，但我很难理解最后一点：
节点存储不连续，大大增加了访问列表中单个元素所需的时间，尤其是使用 CPU 缓存时。
关于CPU缓存的文章没有提到任何关于非连续内存数组的内容。据我所知 CPU 缓存只缓存经常使用的地址，总共有 10^-6 次缓存未命中。
因此，我不明白为什么 CPU 缓存在处理非连续内存阵列时效率应该较低。
CPU缓存实际上做了两件事。
你说的是缓存最近使用的内存。
然而，另一个是预测在不久的将来将使用哪个内存。该算法通常非常简单 - 它假设程序处理大量数据，并且每当它访问一些内存时，它都会预取更多的字节。
这不适用于链表，因为节点是随机放置在内存中的。
此外，CPU 加载更大的内存块（64、128 字节）。同样，对于单次读取的 int64 数组，它具有用于处理 8 或 16 个元素的数据。对于链表，它读取一个块，其余的可能会被浪费，因为下一个节点可能位于完全不同的内存块中。
最后但同样重要的是，与上一节相关 - 链表需要更多内存用于其管理，最简单的版本至少需要额外的 sizeof(pointer) 字节用于指向下一个节点的指针。但它不再是 CPU 缓存。
CPU 缓存通常会占用一定大小的页面 例如（常见的） 4096 字节 或 4kB 并从那里访问所需的信息。要获取页面，会消耗相当多的时间，比方说 1000 个周期。如果说我们有一个连续的 4096 字节数组，我们将从缓存内存中获取一个 4096 字节的页面，并且可能大部分数据都在那里。如果不是，我们可能需要获取另一个页面来获取其余数据。
示例： 我们有 0-8191 的 2 个页面，数组在 2048 和 6244 之间，然后我们将从 0-4095 获取第 1 页以获得所需的元素然后 page#2 从 4096-8191 获取我们想要的所有数组元素。这导致从内存中获取 2 页到我们的缓存以获取我们的数据。
但是列表中会发生什么？在列表中，数据是不连续的，这意味着元素在内存中不在连续的位置，因此它们可能分散在各个页面中。这意味着 CPU 必须从内存中获取大量页面到缓存才能获得所需的数据。
示例： 节点#1 mem_address = 1000，节点#2 mem_address = 5000，节点#3 mem_address = 18000。如果 CPU 能够看到 4k 页面大小，那么它必须从内存中获取 3 个不同的页面才能找到它想要的数据。
此外，内存使用 prefetch 技术在需要之前获取内存页面，因此如果链表很小，假设 A -> B -> C，那么第一个周期会很慢，因为预取器无法预测要获取的下一个块。但是，在下一个周期，我们说预取器已经预热，它可以开始预测链表的路径并按时获取正确的块。
总结数组很容易被硬件预测并且在一个地方所以它们很容易获取，而链表是不可预测的并且分散在整个内存中，这使得预测器和 CPU 的生命更难.
这篇文章只是触及表面，并有一些错误（或至少是有问题的），但总体结果通常是差不多的：链表要慢得多。
需要注意的一件事是 "nodes are stored incontiguously [sic]" 是一个过于强烈的声明。确实，一般情况下，例如 malloc 返回的节点可能会散布在内存中，尤其是当节点在不同时间或从不同线程分配时。然而，在实践中，许多节点通常同时分配在同一个线程上，并且这些节点通常最终会在内存中非常连续，因为好的 malloc 实现是，好，好！此外，当性能是一个问题时，您可能经常在每个对象的基础上使用特殊的分配器，它从一个或多个连续的内存块中分配固定大小的注释，这将提供很好的空间局部性。
因此您可以假设至少在某些情况下，链表将为您提供合理到良好的空间局部性。这在很大程度上取决于您是一次添加所有列表元素中的大部分（链表可以），还是在较长时间内不断添加元素（链表的空间局部性较差）。
现在，除了列表速度慢之外，链表所掩盖的主要问题之一是与数组变体相关的某些操作相关的大常数因子。大家都知道根据索引访问一个元素，在链表中是O(n)，在数组中是O(1)，所以如果你打算通过索引进行大量访问，就不要使用链表.同样，大家都知道在链表中向列表中间添加一个元素需要 O(1) 时间，而在数组中需要 O(n) 时间，所以在这种情况下前者获胜。
他们没有解决的是，即使是具有相同算法复杂度的操作在一种实现中实际上也可能慢很多...
让我们迭代列表中的所有元素（也许是寻找特定值）。无论您使用链接还是数组表示，这都是一个 O(n) 操作。所以这是平局，对吧？
没那么快！实际性能可能相差很大！ Here is what 典型的 find() 实现在 x86 gcc 中以 -O2 优化级别编译时看起来像，感谢 godbolt 这使得这很容易。
数组
C 代码
int find_array(int val, int *array, unsigned int size) {
for (unsigned int i=0; i < size; i++) {
if (array[i] == val)
return i;
}
return -1;
}
程序集（仅循环）1
.L6:
add rsi, 4
cmp DWORD PTR [rsi-4], edi
je .done
add eax, 1
cmp edx, eax
jne .notfound
链表
C 代码
struct Node {
struct Node *next;
int item;
};
Node * find_list(int val, Node *listptr) {
while (listptr) {
if (listptr->item == val)
return listptr;
listptr = listptr->next;
}
return 0;
}
程序集（仅限循环）
.L20:
cmp DWORD PTR [rax+8], edi
je .done
mov rax, QWORD PTR [rax]
test rax, rax
jne .notfound
只看 C 代码，这两种方法看起来都很有竞争力。数组方法将具有 i 的增量、几次比较和一次内存访问以从数组中读取值。链接列表版本如果要有几个（相邻的）内存访问来读取 Node.val 和 Node.next 成员，以及几个比较。
程序集似乎证实了这一点：链表版本有 5 条指令，数组版本2 有 6 条。所有指令都是简单的指令，吞吐量为在现代硬件上每个周期 1 个或更多。
如果你测试它 - 两个列表都完全驻留在 L1，你会发现数组版本每次迭代执行大约 1.5 个周期，而链表版本大约需要 4 个！那是因为链表版本受限于它对 listptr 的循环携带依赖。一行 listptr = listptr->next 归结为一条指令，但这条指令每 4 个周期执行一次不会超过一次，因为每次执行都取决于前一条指令的完成（您需要完成阅读 listptr->next在你可以计算 listptr->next->next 之前）。尽管现代 CPUs 可以在每个周期执行大约 2 个加载周期，但这些加载需要大约 4 个周期才能完成，因此您会在这里遇到串行瓶颈。
数组版本也有加载，但地址不依赖于之前的加载：
add rsi, 4
cmp DWORD PTR [rsi-4], edi
只依赖于rsi，每次迭代加4简单计算。 add 在现代硬件上有一个周期的延迟，所以这不会造成瓶颈（除非你低于 1 cycle/iteration）。所以数组循环能够使用 CPU 的全部功能，并行执行许多指令。链表版本没有。
这不是 "find" 所独有的 - 任何需要遍历许多元素的链接操作都会有这种 指针追逐 行为，这在现代上本来就很慢硬件。
1我省略了每个汇编函数的结语和序言，因为它确实没有做任何有趣的事情。这两个版本实际上都没有结尾，而且两个版本的序言都非常相似，从第一个迭代中剥离并跳入循环的中间。无论如何，完整代码是available for inspection。
2值得注意的是，gcc 并没有真正做到这里应该做的那么好，因为它维护了 rsi 作为指向数组的指针，和 eax 作为索引 i。这意味着两个单独的 cmp 指令和两个增量。更好的做法是在循环中只维护指针 rsi，并将 (array + 4*size) 作为 "not found" 条件进行比较。这将消除一个增量。此外，您可以通过使 rsi 运行 从 -4*size 到零来消除一个 cmp，并使用 [rdi + rsi] 索引到数组，其中 rdi 是 array + 4*size.表明即使在今天，优化编译器也没有把所有事情都做对！
BeeOnRope 的回答很好，强调了遍历链表与遍历数组的循环计数开销，但正如他明确表示的那样，这是假设 "both lists fully resident in L1"。但是，数组比链表更适合 L1 的可能性要大得多，而且当您开始使用缓存时，性能差异就会变得巨大。 RAM 可能比 L1 慢 100 倍以上，而 L2 和 L3（如果您的 CPU 有）慢 3 到 14 倍。
在 64 位架构上，每个指针占用 8 个字节，双向链表需要两个或 16 个字节的开销。如果每个条目只需要一个 4 字节 uint32，则意味着 dlist 需要的存储空间是数组所需存储空间的 5 倍。数组保证了局部性，尽管如果您以正确的顺序将东西分配在一起，malloc 可以在局部性上做得很好，但您通常不能。让我们通过说它需要 space 的 2 倍来近似较差的局部性，因此 dlist 使用的 "locality space" 是数组的 10 倍。这足以让你从适应 L1 到溢出到 L3，甚至更糟的是从 L2 进入 RAM。
我想知道与 C 中的连续数组相比，链表的优点和缺点是什么。因此，我阅读了一篇关于链表的维基百科文章。 https://en.wikipedia.org/wiki/Linked_list#Disadvantages
根据这篇文章，缺点如下：
- They use more memory than arrays because of the storage used by their pointers.
- Nodes in a linked list must be read in order from the beginning as linked lists are inherently sequential access.
Difficulties arise in linked lists when it comes to reverse traversing. For instance, singly linked lists are cumbersome to navigate backwards and while doubly linked lists are somewhat easier to read, memory is wasted in allocating.
Nodes are stored incontiguously, greatly increasing the time required to access individual elements within the list, especially with a CPU cache.
我理解前 3 点，但我很难理解最后一点：
节点存储不连续，大大增加了访问列表中单个元素所需的时间，尤其是使用 CPU 缓存时。
关于CPU缓存的文章没有提到任何关于非连续内存数组的内容。据我所知 CPU 缓存只缓存经常使用的地址，总共有 10^-6 次缓存未命中。
因此，我不明白为什么 CPU 缓存在处理非连续内存阵列时效率应该较低。
CPU缓存实际上做了两件事。
你说的是缓存最近使用的内存。
然而，另一个是预测在不久的将来将使用哪个内存。该算法通常非常简单 - 它假设程序处理大量数据，并且每当它访问一些内存时，它都会预取更多的字节。
这不适用于链表，因为节点是随机放置在内存中的。
此外，CPU 加载更大的内存块（64、128 字节）。同样，对于单次读取的 int64 数组，它具有用于处理 8 或 16 个元素的数据。对于链表，它读取一个块，其余的可能会被浪费，因为下一个节点可能位于完全不同的内存块中。
最后但同样重要的是，与上一节相关 - 链表需要更多内存用于其管理，最简单的版本至少需要额外的 sizeof(pointer) 字节用于指向下一个节点的指针。但它不再是 CPU 缓存。
CPU 缓存通常会占用一定大小的页面 例如（常见的） 4096 字节 或 4kB 并从那里访问所需的信息。要获取页面，会消耗相当多的时间，比方说 1000 个周期。如果说我们有一个连续的 4096 字节数组，我们将从缓存内存中获取一个 4096 字节的页面，并且可能大部分数据都在那里。如果不是，我们可能需要获取另一个页面来获取其余数据。
示例： 我们有 0-8191 的 2 个页面，数组在 2048 和 6244 之间，然后我们将从 0-4095 获取第 1 页以获得所需的元素然后 page#2 从 4096-8191 获取我们想要的所有数组元素。这导致从内存中获取 2 页到我们的缓存以获取我们的数据。
但是列表中会发生什么？在列表中，数据是不连续的，这意味着元素在内存中不在连续的位置，因此它们可能分散在各个页面中。这意味着 CPU 必须从内存中获取大量页面到缓存才能获得所需的数据。
示例： 节点#1 mem_address = 1000，节点#2 mem_address = 5000，节点#3 mem_address = 18000。如果 CPU 能够看到 4k 页面大小，那么它必须从内存中获取 3 个不同的页面才能找到它想要的数据。
此外，内存使用 prefetch 技术在需要之前获取内存页面，因此如果链表很小，假设 A -> B -> C，那么第一个周期会很慢，因为预取器无法预测要获取的下一个块。但是，在下一个周期，我们说预取器已经预热，它可以开始预测链表的路径并按时获取正确的块。
总结数组很容易被硬件预测并且在一个地方所以它们很容易获取，而链表是不可预测的并且分散在整个内存中，这使得预测器和 CPU 的生命更难.
这篇文章只是触及表面，并有一些错误（或至少是有问题的），但总体结果通常是差不多的：链表要慢得多。
需要注意的一件事是 "nodes are stored incontiguously [sic]" 是一个过于强烈的声明。确实，一般情况下，例如 malloc 返回的节点可能会散布在内存中，尤其是当节点在不同时间或从不同线程分配时。然而，在实践中，许多节点通常同时分配在同一个线程上，并且这些节点通常最终会在内存中非常连续，因为好的 malloc 实现是，好，好！此外，当性能是一个问题时，您可能经常在每个对象的基础上使用特殊的分配器，它从一个或多个连续的内存块中分配固定大小的注释，这将提供很好的空间局部性。
因此您可以假设至少在某些情况下，链表将为您提供合理到良好的空间局部性。这在很大程度上取决于您是一次添加所有列表元素中的大部分（链表可以），还是在较长时间内不断添加元素（链表的空间局部性较差）。
现在，除了列表速度慢之外，链表所掩盖的主要问题之一是与数组变体相关的某些操作相关的大常数因子。大家都知道根据索引访问一个元素，在链表中是O(n)，在数组中是O(1)，所以如果你打算通过索引进行大量访问，就不要使用链表.同样，大家都知道在链表中向列表中间添加一个元素需要 O(1) 时间，而在数组中需要 O(n) 时间，所以在这种情况下前者获胜。
他们没有解决的是，即使是具有相同算法复杂度的操作在一种实现中实际上也可能慢很多...
让我们迭代列表中的所有元素（也许是寻找特定值）。无论您使用链接还是数组表示，这都是一个 O(n) 操作。所以这是平局，对吧？
没那么快！实际性能可能相差很大！ Here is what 典型的 find() 实现在 x86 gcc 中以 -O2 优化级别编译时看起来像，感谢 godbolt 这使得这很容易。
数组
C 代码
int find_array(int val, int *array, unsigned int size) {
for (unsigned int i=0; i < size; i++) {
if (array[i] == val)
return i;
}
return -1;
}
程序集（仅循环）1
.L6:
add rsi, 4
cmp DWORD PTR [rsi-4], edi
je .done
add eax, 1
cmp edx, eax
jne .notfound
链表
C 代码
struct Node {
struct Node *next;
int item;
};
Node * find_list(int val, Node *listptr) {
while (listptr) {
if (listptr->item == val)
return listptr;
listptr = listptr->next;
}
return 0;
}
程序集（仅限循环）
.L20:
cmp DWORD PTR [rax+8], edi
je .done
mov rax, QWORD PTR [rax]
test rax, rax
jne .notfound
只看 C 代码，这两种方法看起来都很有竞争力。数组方法将具有 i 的增量、几次比较和一次内存访问以从数组中读取值。链接列表版本如果要有几个（相邻的）内存访问来读取 Node.val 和 Node.next 成员，以及几个比较。
程序集似乎证实了这一点：链表版本有 5 条指令，数组版本2 有 6 条。所有指令都是简单的指令，吞吐量为在现代硬件上每个周期 1 个或更多。
如果你测试它 - 两个列表都完全驻留在 L1，你会发现数组版本每次迭代执行大约 1.5 个周期，而链表版本大约需要 4 个！那是因为链表版本受限于它对 listptr 的循环携带依赖。一行 listptr = listptr->next 归结为一条指令，但这条指令每 4 个周期执行一次不会超过一次，因为每次执行都取决于前一条指令的完成（您需要完成阅读 listptr->next在你可以计算 listptr->next->next 之前）。尽管现代 CPUs 可以在每个周期执行大约 2 个加载周期，但这些加载需要大约 4 个周期才能完成，因此您会在这里遇到串行瓶颈。
数组版本也有加载，但地址不依赖于之前的加载：
add rsi, 4
cmp DWORD PTR [rsi-4], edi
只依赖于rsi，每次迭代加4简单计算。 add 在现代硬件上有一个周期的延迟，所以这不会造成瓶颈（除非你低于 1 cycle/iteration）。所以数组循环能够使用 CPU 的全部功能，并行执行许多指令。链表版本没有。
这不是 "find" 所独有的 - 任何需要遍历许多元素的链接操作都会有这种 指针追逐 行为，这在现代上本来就很慢硬件。
1我省略了每个汇编函数的结语和序言，因为它确实没有做任何有趣的事情。这两个版本实际上都没有结尾，而且两个版本的序言都非常相似，从第一个迭代中剥离并跳入循环的中间。无论如何，完整代码是available for inspection。
2值得注意的是，gcc 并没有真正做到这里应该做的那么好，因为它维护了 rsi 作为指向数组的指针，和 eax 作为索引 i。这意味着两个单独的 cmp 指令和两个增量。更好的做法是在循环中只维护指针 rsi，并将 (array + 4*size) 作为 "not found" 条件进行比较。这将消除一个增量。此外，您可以通过使 rsi 运行 从 -4*size 到零来消除一个 cmp，并使用 [rdi + rsi] 索引到数组，其中 rdi 是 array + 4*size.表明即使在今天，优化编译器也没有把所有事情都做对！
BeeOnRope 的回答很好，强调了遍历链表与遍历数组的循环计数开销，但正如他明确表示的那样，这是假设 "both lists fully resident in L1"。但是，数组比链表更适合 L1 的可能性要大得多，而且当您开始使用缓存时，性能差异就会变得巨大。 RAM 可能比 L1 慢 100 倍以上，而 L2 和 L3（如果您的 CPU 有）慢 3 到 14 倍。
在 64 位架构上，每个指针占用 8 个字节，双向链表需要两个或 16 个字节的开销。如果每个条目只需要一个 4 字节 uint32，则意味着 dlist 需要的存储空间是数组所需存储空间的 5 倍。数组保证了局部性，尽管如果您以正确的顺序将东西分配在一起，malloc 可以在局部性上做得很好，但您通常不能。让我们通过说它需要 space 的 2 倍来近似较差的局部性，因此 dlist 使用的 "locality space" 是数组的 10 倍。这足以让你从适应 L1 到溢出到 L3，甚至更糟的是从 L2 进入 RAM。