cpu 缓存行和预取策略

我读了这篇文章http://igoro.com/archive/gallery-of-processor-cache-effects/ http://igoro.com/archive/gallery-of-processor-cache-effects/。文章中说因为cacheline延迟，代码：

int[] arr = new int[64 * 1024 * 1024];

// Loop 1
for (int i = 0; i < arr.Length; i++) arr[i] *= 3;

// Loop 2
for (int i = 0; i < arr.Length; i += 16) arr[i] *= 3;

几乎有相同的执行时间，我编写了一些示例 c 代码来测试它。我在采用 Ubuntu 64 位、ARMv6 兼容处理器 rev 7 和 Debian 的 Xeon(R) E3-1230 V2 上运行代码，也在 Core 2 T6600 上运行。所有的结果都不是文章说的那样。

我的代码如下：

long int jobTime(struct timespec start, struct timespec stop) {
    long int seconds = stop.tv_sec - start.tv_sec;
    long int nsec = stop.tv_nsec - start.tv_nsec;
    return seconds * 1000 * 1000 * 1000 + nsec;
}

int main() {
    struct timespec start;
    struct timespec stop;
    int i = 0;
    struct sched_param param;
    int * arr = malloc(LENGTH * 4);

    printf("---------sieofint %d\n", sizeof(int));
    param.sched_priority = 0;
    sched_setscheduler(0, SCHED_FIFO, &param);
    //clock_gettime(CLOCK_MONOTONIC, &start);
    //for (i = 0; i < LENGTH; i++) arr[i] *= 5;
    //clock_gettime(CLOCK_MONOTONIC, &stop);

    //printf("step %d : time %ld\n", 1, jobTime(start, stop));

    clock_gettime(CLOCK_MONOTONIC, &start);
    for (i = 0; i < LENGTH; i += 2) arr[i] *= 5;
    clock_gettime(CLOCK_MONOTONIC, &stop);

    printf("step %d : time %ld\n", 2, jobTime(start, stop));
}

每次我选择一个片段来编译和运行（注释一个并取消注释另一个）。 编译：

gcc -O0 -o cache cache.c -lrt

在至强上我得到这个：

step 1 : 258791478
step 2 : 97875746

我想知道这篇文章说的是否正确？或者，最新的 cpu 是否具有更高级的预取策略？

简短回答（TL；DR）：如果您正在访问未初始化的数据，则第一个循环必须在定时循环内为整个数组分配新的物理页。

当我运行您的代码并依次注释每个部分时，我得到两个循环几乎相同的时间。但是，当我取消注释这两个部分并逐一运行它们时，我确实得到了与您报告的相同的结果。这让我怀疑你也这么做了，并且遭受了痛苦冷启动将第一个循环与第二个循环进行比较时的效果。检查起来很容易——只需更换循环的顺序，看看第一个循环是否仍然较慢。

为了避免，要么选择足够大的LENGTH（取决于您的系统），这样您就不会从第一个循环帮助第二个循环中获得任何缓存优势，或者只是添加一次不定时的整个数组的遍历。

请注意，第二个选项并不能完全证明博客想要说的内容 - 内存延迟掩盖了执行延迟，因此无论您使用缓存行的多少个元素，您仍然受到内存访问的瓶颈时间（或更准确地说是带宽）

另外 - 对代码进行基准测试-O0这是一个非常糟糕的做法

Edit:

这就是我得到的（删除了日程安排，因为它不相关）。
这段代码：

for (i = 0; i < LENGTH; i++) arr[i] = 1;   // warmup!

clock_gettime(CLOCK_MONOTONIC, &start);
for (i = 0; i < LENGTH; i++) arr[i] *= 5;
clock_gettime(CLOCK_MONOTONIC, &stop);
printf("step %d : time %ld\n", 1, jobTime(start, stop));

clock_gettime(CLOCK_MONOTONIC, &start);
for (i = 0; i < LENGTH; i+=16) arr[i] *= 5;
clock_gettime(CLOCK_MONOTONIC, &stop);

Gives :

---------sieofint 4
step 1 : time 58862552
step 16 : time 50215446

在评论时，预热线具有与您在第二个循环中报告的相同的优势：

---------sieofint 4
step 1 : time 279772411
step 16 : time 50615420

替换循环的顺序（热身仍然被注释）表明它确实与步长无关，而是与顺序相关：

---------sieofint 4
step 16 : time 250033980
step 1 : time 59168310

（gcc 版本 4.6.3，在 Opteron 6272 上）

现在请注意这里发生的情况 - 理论上，只有当数组小到足以位于某个缓存中时，您才会期望预热才有意义 - 在这种情况下LENGTH即使对于大多数机器上的 L3 来说，您使用的也太大了。然而，您忘记了页面地图 - 您不仅仅是跳过了数据本身的预热 - 您避免了初始化它首先。这永远不会在现实生活中给你带来有意义的结果，但由于这是一个基准，你没有注意到这一点，你只是将垃圾数据乘以它的延迟。

这意味着您在第一个循环中访问的每个新页面不仅会进入内存，它可能会出现页面错误，并且必须调用操作系统为其映射新的物理页面。这是一个漫长的过程，乘以您使用的 4K 页面数量 - 累积到很长一段时间。在这个阵列大小下，您甚至无法从 TLB 中受益（您有 16k 个不同的物理 4k 页，远远超过大多数 TLB 即使有 2 个级别也能支持的数量），因此这只是故障流的问题。这可能可以通过任何分析工具来测量。

同一数组上的第二次迭代不会产生这种效果，并且速度会快得多 - 尽管仍然必须在每个新页面上执行完整的页面遍历（纯粹在硬件中完成），然后从内存中获取数据。

顺便说一句，这也是当您对某些行为进行基准测试时，您多次重复同一件事的原因（在这种情况下，如果您以相同的步幅多次运行数组，并忽略第一个，那么它就会解决您的问题）几轮）。