在C中,我将循环执行的总数减少了近3倍,但通过测试执行时间,我发现这样做几乎没有任何改进。所有优化关卡都测试过了,结果基本一致(包括0、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 sn", ((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 sn", ((double)(clock() - start)) / CLOCKS_PER_SEC);
printf("count1: %dn", count1);
printf("count2: %dn", count2);
return 0;
}
打印结果(平均值)如下:
No.1: 0.002213 s
No.2: 0.002209 s
count1: 72661
count2: 25417
问题来自处理器本身,而不是编译器。这是一个复杂的问题与CPU缓存的行为相关,CPU预取单元和随机访问模式.
两个代码都读取基于i
值的tex
数组,不容易预测由于rand_arr
中存储的随机增量,处理器可以提前处理。由于tex
相对较大,它可能不会完全存储在L1缓存中(也不会存储在中间L2缓存中,如果有的话),而是存储在最后一级缓存(LLC)中,甚至存储在RAM中。因此,tex
需要在每个循环中从LLC缓存或RAM中重新加载。有限责任公司的高速缓存和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系统上也可以看到。
有两件事可能导致这个:
-
如果你正在计时你的代码,你应该:
startTime = clock(); CODE endTime = clock();
然后打印结果/对其进行分析。你对它做了一些计算,并使用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
,我建议使用返回int
或unsigned int
的函数以不同的方式执行,因为double会破坏上面所述的计时。如果您担心这一点,我建议您通过以下方式进行测试:startTime = clock() for(int i = 0;i<10000;i++) dummy = clock() endTime = clock() totalTime = (endTime - startTime)/10000;
for循环——这本身可能是基础计时的主要来源(尽管这不太可能,特别是因为它看起来不像你在做任何特别复杂的数学运算。)你可以使用
#pragma unroll
处理器指令来修复这个问题,它基本上会将for
循环的所有迭代复制并粘贴到你的代码中,删除它的时间影响