c - 执行次数减少3倍，但执行效率几乎不变。在 C

Question

在C中，我将循环执行总数减少了近3倍，但通过测试执行时间，我发现这样做几乎没有任何改进。所有优化级别都经过测试，结果基本一致(包括O0、O1、O2和O3)。我猜是编译器的问题，但我想知道是什么导致了这种情况。以及如何做才能使结果符合预期。
代码如下:

#include <stdio.h>
#include <time.h>
#include <stdlib.h>

#define Len 10000000

// Two variables that count the number of loops
int count1 = 0;
int count2 = 0;

int main(int argc, const char * argv[]) {
    srandom((unsigned)time(NULL));
    
    // An array to increase the index,
    // the range of its elements is 1-256
    int rand_arr[128];
    for (int i = 0; i < 128; ++i)
        rand_arr[i] = random()%256+1;
    
    // A random text, the range of its elements is 0-127
    char *tex = malloc((sizeof *tex) * Len);
    for (int i = 0; i < Len; ++i)
        tex[i] = random()%128;
    
    // The first testing
    clock_t start = clock();
    for (int i = 0; i < Len; i += rand_arr[tex[i]])
        count1++;
    printf("No.1: %lf s\n", ((double)(clock() - start)) / CLOCKS_PER_SEC);
    
    // The second testing (x3)
    start = clock();
    for (int i = 0; i < Len; i += rand_arr[tex[i]]+256)
        count2++;
    printf("No.2: %lf s\n", ((double)(clock() - start)) / CLOCKS_PER_SEC);
    
    printf("count1: %d\n", count1);
    printf("count2: %d\n", count2);
    
    return 0;
}

打印结果(平均值)如下:

No.1: 0.002213 s
No.2: 0.002209 s
count1: 72661
count2: 25417

Answer 1

问题来自处理器本身而不是编译器。这是一个 复杂问题与 的行为有关CPU 缓存 , CPU预取单元和 随机访问模式 .
两个代码都读取了 tex基于数组 i值 无法轻易预测 由于 rand_arr 中存储的随机增量，处理器提前.因为 tex相对较大，它可能不会完全存储在 L1 缓存中(也不在中间 L2 缓存中，如果有的话)，而是在最后一级缓存 (LLC) 中，甚至在 RAM 中。结果，tex需要在每个循环中从 LLC 缓存或 RAM 重新加载。 延迟 现在，LLC 缓存和 RAM 的容量都比较大。这个东西就是第二个循环更难预测且对缓存不友好 比第一个虽然迭代次数少了!
在 x86 CPU 上，按称为 的 64 字节块缓存包值缓存行 .当从主内存或另一个缓存中获取一个值时(通常是由于缓存未命中)，会获取一个完整的缓存行。以下对同一缓存线的访问速度更快，因为 CPU 不需要再次获取它(只要缓存线没有失效)。
在第一个循环中，平均增量i是 128(因为 rand_arr 的平均值是 128)。这意味着从 tex 中获取的两个项目之间的平均步幅是 128。在最坏的情况下，步幅为 256。在第二个循环中，平均步幅为 256+128=384，在最坏的情况下为 256+256=512。当步幅小于 64 时，很可能在第一种情况下已经提取，而在第二次循环中则永远不会出现这种情况。此外，预取单元当多个访问连续或彼此关闭时，可以预取缓存行。这使处理器能够处理 tex 的大多数项目。在第一个循环中提前数组。同时，在第二个循环中，预取器可能无法识别任何高速缓存行获取访问。预取单元可能不会预取任何东西(因为这样做太昂贵了)，结果是许多具有高延迟的高速缓存未命中而无法减轻，因为访问本质上是顺序且不可预测的。如果预取单元决定预取所有缓存行，那么第二个循环不应比第一个循环快(因为两个循环都受内存层次结构的约束)。
请注意 random和 srandom不是标准功能。
另外，请注意 clock在所有平台上并不总是精确的。实际上，它在我的 Windows 上的精度为 1 毫秒(使用 GCC 和 MinGW)。这也可以在某些 Linux 系统上看到。