什么时候第一次在程序中获取缓存行？

Question

假设我有一个像这样的简单 C 程序：

void print_character(char);

int main(int argc, char* argv[]){

  char loads_of_text[1024];
  int count = strlen(argv[1]);
  memcpy(loads_of_text, argv[1], count);

  for(int i = 0; i < count; ++i)
    print_character(loads_of_text[i]);

  return 0;
}

据我理解缓存的概念，就是处理器在请求提升性能时，由于获取内存时的延迟，会获取比需要的更多的数据。这只有在我顺序使用内存直到整个缓存行被读取然后它会获取另一个时才有效。

但是我很难准确地想象处理器何时获取和处理高速缓存行，在上面的代码这样的示例中，这到底发生在哪里？什么时候处理高速缓存行？

Answer 1

我很难理解它的作用：

int count = strlen(argv);

你应该得到一个警告。顺便说一句 argv[0] 是你的可执行文件的路径。

首先确保了解您的代码是如何工作的，然后，也只有这样，请转到更高级的主题，例如了解缓存。

给你直觉：

缓存将加载尽可能多的数据（例如数组的数据），希望您的程序稍后会请求它（因为例如从主内存加载数据很昂贵）。

如果缓存已满，则选择 victim（使用缓存实现的任何策略，例如 LRU）并替换为新请求的数据块.

Answer 2

进一步阅读：请参阅此答案末尾的链接。

缓存行大小为 64B，并在 64B 边界上对齐。（有些 CPU 可能使用不同大小的缓存行，但 64B 是一个很常见的选择）。

缓存加载数据有两个原因：

需求未命中：加载或存储指令访问了不在任何当前热缓存行中的字节。

近期对同一字节（或 int 或其他）的访问将命中缓存（时间局部性）。近期访问同一缓存行中的附近字节也会命中（空间局部性）。以错误的顺序遍历多维数组，或者遍历仅访问一个成员的结构数组，这真的很糟糕，因为必须加载整个缓存行，但您只使用了其中的一小部分。
prefetching：在几次顺序访问之后，硬件预取器注意到这种模式并开始加载尚未访问的缓存行，所以希望有当程序确实访问它时，不会是缓存未命中。对于 HW 预取器行为的具体示例，Intel 的优化手册描述了各种特定 CPUs 中的 HW 预取器（链接参见 x86 标签 wiki），并指出它们仅在内存系统时运行尚未充斥着需求失误。

还有软件预取：软件可以运行一条指令告诉 CPU 它将很快访问某些内容。但是即使内存还没有准备好，程序也会保持运行ning，因为这只是一个提示。该程序不会因等待高速缓存未命中而卡住。现代硬件预取非常好，软件预取通常是浪费时间。它对于像二进制搜索这样的东西很有用，你可以在查看新的中间位置之前预取 1/4 和 3/4 位置。

如果没有测试它实际上可以加速您的实际代码，请不要添加软件预取。即使硬件预取做得不好，软件预取也可能无济于事，或者可能有害。一般来说，乱序执行在很大程度上隐藏了缓存未命中延迟。

通常缓存是"full"，加载新行需要丢弃旧行。缓存通常通过对集合内的标签进行排序来实现 LRU replacement policy，因此每次访问缓存行都会将其移动到最近使用的位置。

以8路关联缓存为例：

一个64B的内存块可以被它映射到的集合中的8个"ways"中的任何一个缓存。部分地址位用作"index"到select的一组标签。（有关将地址拆分为 tag | index | offset-within-cache-line 的示例，请参阅。OP 对它的工作原理感到困惑，但有一个有用的 ASCII 图。）

Hit/miss判断不依赖顺序。快速缓存（如 L1 缓存）通常会并行检查所有 8 个标签，以找到与地址高位匹配的标签（如果有的话）。

当我们需要space换行时，我们需要从当前的8个标签中选择一个来替换（并将数据放入其关联的64B存储数组中）。如果有任何当前处于无效状态（未缓存任何内容），那么选择是显而易见的。在正常情况下，所有 8 个标签都已经有效。

但是我们可以用标签存储额外的数据，足以存储一个订单。每次发生缓存命中时，集合内标签的排序都会更新，以将命中的行放在 MRU 位置。

需要分配新行时，逐出LRU标签，在MRU位置插入新行。

标准的 LRU 策略意味着循环遍历一个稍大而无法放入缓存的数组意味着您永远不会看到任何缓存命中，因为当您返回到同一地址时，它已被逐出。一些 CPU 使用复杂的替换策略来避免这种情况：例如Intel IvyBridge 的大型共享 L3 高速缓存使用 an adaptive replacement policy that decides on the fly when to allocate new lines in the LRU position，因此新分配会逐出其他最近分配的行，保留具有未来价值的行。这需要额外的逻辑，所以只在大型/慢速缓存中完成，而不是在更快的 L2 和 L1 缓存中。

（为什么所有 8 个标签通常都有效，即使在程序开始时也是如此：

当执行到达您的程序开始时，内核已经运行同一个 CPU 上的一堆代码将运行编译您的程序。典型的现代缓存是物理索引和标记的 ()，因此不必在上下文切换时刷新缓存。即它们缓存物理内存，而不管页表导致的虚拟到物理转换的变化。）

您应该阅读 Ulrich Drepper 的 What Every Programmer Should Know About Memory 文章。 IIRC，他介绍了触发负载的基础知识。

Ulrich 的一些具体建议现在有点过时了；预取线程在 Pentium 4 上很有用，但通常不再有用了。硬件预取器现在更智能，超线程足以运行两个完整线程。

维基百科的 CPU Cache article 也解释了一些关于缓存的细节，包括逐出策略（CPU 如何选择在加载新行时丢弃哪一行）。

什么时候第一次在程序中获取缓存行？

When is a cache line first fetched in a program?

c

arrays

performance

caching

processor