将执行次数减少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)中，甚至存储在内存中。因此，需要从LLC缓存或RAM在每个循环中重新加载tex。目前LLC缓存和内存的延迟都比较大。这是因为第二个循环比第一个循环更难预测，对缓存的友好性也比第一个更低，尽管迭代次数更少！

在x86 CPU上，缓存按64个字节的块打包值，称为缓存行。当从主内存或另一个缓存(通常由于缓存丢失)获取值时，将获取完整的缓存行。以下对同一缓存行的访问速度更快，因为CPU不需要再次获取它(只要缓存行没有失效)。

在第一个循环中，i的平均增量为128 (因为rand_arr的平均值为128)。这意味着来自tex的两个获取项之间的平均步长为128。在最坏的情况下，步幅是256。在第二个循环中，平均步长是256+128=384，最坏的情况是256+256=512。当步长小于64时，在第一种情况下就会有很高的概率，而在第二次循环中则不会这样。此外，预取单元可以在多个访问连续或彼此关闭时预取缓存行。这使处理器能够提前在第一个循环中对tex数组的大多数项进行处理。同时，在第二个循环中，预取程序可能无法识别任何缓存行获取访问。预取单元可能不会预取任何东西(因为这样做成本太高)，结果是许多缓存丢失，延迟很高，而这些延迟无法减轻，因为访问本身是顺序的和不可预测的。如果预保护单元决定预取所有缓存行，那么第二个循环不应该比第一个循环更快(因为这两个循环都被内存层次结构绑定)。

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

Answer 2

有几件事可能会导致这种情况：

如果您正在计时您的代码，则应该有：

1. ：

startTime = clock()；代码endTime = clock();

然后打印你的结果/在上面做分析。你做了一些数学，并使用PRINTF函数，这是可怕的低效，就时间而言。另外，对double的转换也不是必要的，而且可能会导致您的大部分时间，因为双重计算的速度非常慢。坚持使用int，因为这可能会快1000倍

用于循环代码的

1. 奇数-循环方程的标准是：

用于(int i= 0;i

你有

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

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

1. clock() --这可能会影响您的计时。如果clock()返回一个double，我建议以另一种方式执行它，函数返回int或unsigned int，因为双倍会破坏您的计时。如果您对此感到担心，我建议通过以下方式进行测试：

startTime =startTime() for(int = 0;i<10000;i++) dummy = endTime ()endTime= clock() totalTime = (endTime -0；i<10000；i++)

1. for循环--这本身可以是基本计时的主要来源(尽管这不太可能，特别是因为它看起来并不像在做任何特别复杂的计算。您可以使用#pragma unroll处理器指令修复这个问题，它基本上会将for循环的所有迭代复制并粘贴到代码中，删除它的定时会影响