caching - 局部性原理和调用指令

Question

在讨论局部性原则时，我的教科书作了如下陈述：

除了仅占所有程序指令一小部分的分支和调用指令外，程序执行是顺序的。因此，在大多数情况下，要获取的指令紧跟在最后一条获取的指令之后。

作为一个新手，我觉得这很难相信。我遇到的所有代码都充满了调用指令。事实上，在我看来，调用指令实际上执行了程序中最重要的操作。

如果有人能详细说明为什么这个概念是正确的，我将不胜感激，尽管调用指令在程序中起着重要作用。

Answer 1

我在我的电脑上随机选择了一个二进制文件，cargo包管理器。然后我：

• 拆开它otool -tvV cargo > assembly
• 只得到说明：cat assembly | awk '{print $2}' > instructions
• 计算每条指令：sort instructions | uniq -c | sort -n > count

我将 Libreoffice Calc 中的结果处理成每条指令的出现列表。以下是每个占程序超过 1% 的那些（这些总计占 86%，因此我丢弃了大量杂散操作以进行酿造）：

| 34.83% | movq    |
| 7.30%  | leaq    |
| 7.00%  | callq   |
| 6.90%  | je      |
| 5.61%  | movl    |
| 4.86%  | cmpq    |
| 3.77%  | testq   |
| 3.11%  | jmp     |
| 2.23%  | jne     |
| 2.17%  | popq    |
| 2.05%  | pushq   |
| 1.69%  | addq    |
| 1.29%  | cmpl    |
| 1.20%  | movabsq |
| 1.18%  | movb    |
| 1.05%  | xorl    |

这里肯定有很多分支和调用（callq, jmp, je, jne），但也有很多内存操作。内存操作相对较慢，占程序运行时间的很大一部分。movq只是一个内存操作，它占程序的三分之一以上！

CPU 缓存用于将最近引用的内存数据保存在 CPU 内核附近，从而加快未来对相同数据的内存操作。由于局部性原则，他们可以做到这一点，该原则指出对同一内存的操作通常在时间上接近（时间局部性）。因此可以缓存内存数据，因为您可能很快会再次需要它。