执行次数减少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

有几个原因可能导致此问题：

如果您正在为代码计时，您应该：

startTime = clock();
CODE
endTime = clock();

然后打印你的 results/do 分析。您对其进行一些数学运算并使用 PRINTF 函数，就时间而言，该函数效率极低。此外，强制转换为 double 不是必需的，并且可能会占用您的大部分时间，因为双重数学非常慢。坚持 int，因为这可能会快 1000 倍

奇数for循环代码-for循环方程的标准是：
```
for(int i = 0;i<length;i++)
      Code
```

你有

  for(int i = 0;i<length;code)
       i++;

就语法而言这很奇怪，可能会影响您的时间安排

clock() - 这可能会影响您的计时。如果 clock() 返回 double，我建议以不同的方式进行，使用 returns int 或 unsigned int 的函数，因为双打会破坏你的计时多于。如果您担心这一点，我建议您通过以下方式进行测试：
```
startTime = clock()
for(int i = 0;i<10000;i++)
     dummy = clock()
endTime = clock()
totalTime = (endTime - startTime)/10000;
```
for 循环 - 这本身就是你的基本计时的主要来源（虽然这不太可能，特别是因为它看起来不像你在做任何特别复杂的数学。你可以使用 #pragma unroll 处理器指令修复此购买，该指令基本上会将 for 循环的所有迭代复制并粘贴到您的代码中，删除它的时间影响

Answer 2

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

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

在 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 系统上看到。

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

Reduce the number of executions by 3 times, but the execution efficiency is almost unchanged. In C

c

performance

x86-64

compiler-optimization