c - 何时在程序中首先获取高速缓存行？

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

进一步阅读:请参阅此答案的结尾以获取链接。

高速缓存行的大小为64B，并在64B边界上对齐。 (某些CPU可能使用不同大小的缓存行，但是64B是非常常见的选择)。

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

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

对同一字节(或int或其他)的近期访问将在高速缓存中命中(时间局部性)。对同一高速缓存行中附近字节的近期访问也将受到影响(空间局部性)。以错误的顺序遍历多维数组，或遍历仅访问一个成员的结构数组，确实很糟糕，因为必须加载整个高速缓存行，但只使用其中的一小部分。

预取:在几次顺序访问后，硬件预取器会注意到此模式，并开始加载尚未访问的高速缓存行，因此希望在程序访问它时不会出现高速缓存未命中的情况。对于硬件预取器行为的特定示例，英特尔的优化手册描述了各种特定CPU中的硬件预取器(有关链接，请参见x86标签Wiki)，并指出它们仅在内存系统尚未因需求遗漏而泛滥时才可运行。

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

在未测试是否可以真正加速实际代码的情况下，请勿添加软件预取。即使硬件预取不能很好地完成，SW的预取也可能无济于事或可能会受到伤害。乱序执行通常可以掩盖高速缓存未命中的延迟。

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

以8路关联缓存为例:

64B内存块可以由其映射到的集合中的8个“方式”中的任何一个进行缓存。地址位的一部分用作选择一组标签的“索引”。 (有关将地址拆分为 tag | index | offset-within-cache-line的示例，请参见 this question。OP对它的工作方式感到困惑，但具有有用的ASCII图。)

命中/未命中确定与顺序无关。快速缓存(如L1缓存)通常会并行检查所有8个标记，以找到与地址的高位匹配的一个(如果有的话)。

当我们需要空间来换行时，我们需要选择8个当前标签之一来替换(并将数据放入与其关联的64B存储阵列中)。如果当前处于“无效”状态(不缓存任何内容)，则选择是显而易见的。在正常情况下，所有8个标签都已经有效。

但是我们可以使用标签存储其他数据，足以存储订单。每次发生高速缓存命中时，都会更新集合中标签的顺序，以将命中所在的行置于MRU位置。

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

标准的LRU策略意味着对一个略微太大而无法容纳在缓存中的数组进行循环意味着您将永远不会看到任何缓存命中，因为当您返回相同的地址时，它已被逐出。一些CPU使用复杂的替换策略来避免这种情况:英特尔IvyBridge的大型共享L3缓存使用 an adaptive replacement policy that decides on the fly when to allocate new lines in the LRU position，因此新的分配将逐出其他最近分配的行，从而保留确实具有 future 价值的行。这需要额外的逻辑，因此只能在大型/慢速缓存中完成，而不能在较快的L2和L1缓存中完成。

(为什么即使在程序开始时，所有8个标记通常都有效:

在执行到达程序开始时，内核已经在将要运行程序的同一CPU上运行了许多代码。典型的现代缓存在物理上被索引和标记( the VIPT L1 speed trick avoids aliasing, and is really equivalent to index translation being free, not really to using virtual indexing)，因此不必在上下文切换中刷新缓存。即它们缓存物理内存，而不考虑页表导致的虚拟到物理转换的变化。)

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

乌尔里希(Ulrich)的一些具体建议到现在为止已经过时了。预取线程在Pentium 4上很有用，但现在不再有用。硬件预取器现在更加智能，并且超线程足以运行两个完整线程。

Wikipedia的 CPU Cache article还解释了有关缓存的一些详细信息，包括逐出策略(CPU在加载新行时如何选择要丢弃的行)。