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

Question

在C中，我将循环执行总数减少了近3倍，但是通过测试执行时间，我发现这样做几乎没有任何改进。所有优化级别均已测试，结果基本相同（包括O0、O1、O2和O3）。我猜它\xe2\x80\x99是编译器的问题，但我想知道是什么原因导致这种情况。以及如何做才能使结果达到预期。

\n

代码如下：

\n

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

\n

打印结果（平均值）如下\xef\xbc\x9a

\n

No.1: 0.002213 s\nNo.2: 0.002209 s\ncount1: 72661\ncount2: 25417\n

\n

Answer 1

问题来自处理器本身，而不是编译器。这是一个与CPU 高速缓存、CPU 预取单元和随机访问模式的行为相关的复杂问题。

两个代码都读取基于tex数组的i值，由于存储在. 由于相对较大，它可能不会完全存储在 L1 缓存中（也不会存储在中间 L2 缓存中，如果有的话），而是存储在最后一级缓存 (LLC) 甚至 RAM 中。因此，需要在每个循环中从 LLC 缓存或 RAM 重新加载。目前LLC缓存和RAM的延迟比较大。问题在于，尽管迭代次数较少，但第二个循环比第一个循环更难预测，并且对缓存更不友好！rand_arrtextex

在 x86 CPU 上，通过称为缓存行的 64 字节块缓存包值。当从主存储器或另一个高速缓存中获取值时（通常由于高速缓存未命中），将获取完整的高速缓存行。接下来对同一缓存行的访问速度更快，因为 CPU 不需要再次读取它（只要缓存行没有失效）。

在第一个循环中， 的平均增量i为 128（因为 的平均值rand_arr为 128）。这意味着两个从中获取的项目之间的平均步幅tex为 128。在最坏的情况下，步幅为 256。在第二个循环中，平均步幅为 256+128=384，在最坏的情况下为 256+256=512 。当步幅小于 64 时，在第一种情况下很有可能已经获取到，而在第二个循环中则不会出现这种情况。此外，当多个访问连续或彼此接近时，预取单元可以预取高速缓存行。这使得处理器能够tex在第一个循环中提前处理数组的大多数项目。同时，在第二个循环中，预取器可能无法识别任何缓存行获取访问。预取单元可能不会预取任何内容（因为这样做成本太高），结果是许多缓存未命中，延迟很高，无法缓解，因为访问本质上是顺序的且不可预测的。如果预取单元决定预取所有高速缓存行，则第二个循环不应比第一个循环快（因为两个循环都受内存层次结构约束）。

请注意，random和srandom不是标准函数。另外，请注意，这clock在所有平台上并不总是准确的。实际上，在我的 Windows 上（使用 GCC 和 MinGW）它的精度为 1 毫秒。在某些Linux系统上也可以看到这一点。