C - CC 编译器和缓存

Question

我浪费了很多时间来弄清楚为什么一个应该比另一个更有效的算法，然而，在速度方面与另一个算法完全相同。我做了这些操作：我在单独的终端窗口中编译了第一个源代码;而另一个窗口中的第二个源代码。我只是使用了：

$ cc number_v1.c

编译第一个，并且：

$ cc number_v2.c

对于第二个源代码。 我使用的是 Mac OS X 达尔文内核版本 18.7.0：2019 年 8 月 20 日星期二 16：57：14 PDT;根： XNU-4903.271.2 ~ 2/RELEASE_X86_64 x86_64.

作为回应，我得到了完全相同的时间结果。考虑到第二个源代码的最佳算法，这是不可能的。

然后我关闭所有内容，第二天再试一次。令我惊讶的是，我终于看到了差异：第二个源代码的完成时间比第一个要短得多。 似乎编译器第一次没有编译列表的代码，实际上，也许仍然认为旧版本;考虑到我已经尝试多次使用相对编译修改源代码，但结果总是相同的。

不久前，我遇到了另一个源代码(相对浪费时间(。 遗憾的是，该事件不可复制，也不会经常发生。

谁能解释为什么会这样？在这些情况下，是否有一种缓存要重置？

它们各自的源代码如下;这是关于找到从2到1000000的质数。

/* cc number_v1.c */    
#include <stdio.h>
int main(void) {
int i, j, n = 1000000;
for(i = 2; i <= n; i++) {
for(j = 2; j < i && i % j != 0; j++)
;
if(j >= i) printf("%d ", j);    
}           
return 0;
}

/* cc number_v2.c */
#include <stdio.h>
int main(void) {
int i, j, n = 1000000;
for(i = 2; i <= n; i++) {
for(j = 2; j * j <= i && i % j != 0; j++)
;
if(j * j > i) printf("%d ", i); 
}   
return 0;
}

Answer 1

您应该在代码中包含度量。 您的测量显然有问题，您需要清楚地展示您的方法。

我执行了以下修改后的测试，以使用uint64_t来防止alg1()中的算术溢出，并将printf()输出替换为易失性接收器：

{volatile uint64_t x = i ;}

测量包含 I/O 的算法的性能可能会产生误导 - 您可能正在测量系统的 I/O 性能。

#include <stdio.h>
#include <time.h>
#include <stdint.h>
#define MAX 1000000 ;
void alg1( void )
{
uint64_t i, j, n = MAX;
for( i = 2; i <= n; i++ )
{
for( j = 2; j < i && i % j != 0; j++ )
;
if( j >= i ){volatile uint64_t x = i ;}
}
}

void alg2( void )
{
uint64_t i, j, n = MAX;
for( i = 2; i <= n; i++ )
{
for( j = 2; j * j <= i && i % j != 0; j++ )
;
if( j * j > i ){volatile uint64_t x = i ;}
}
}

int main()
{
clock_t start = clock() ;
alg1() ;
int alg1_clocks = clock() - start ;
start = clock() ;
alg2() ;
int alg2_clocks = clock() - start ;
printf( "nalg1() took %f seconds", (double)(alg1_clocks) / CLOCKS_PER_SEC ) ;
printf( "nalg2() took %f seconds", (double)(alg2_clocks) / CLOCKS_PER_SEC ) ;
return 0 ;
}

结果：

alg1() took 336.681000 seconds
alg2() took 0.621000 seconds

所以你的结果不能复制，所以我会怀疑它们的完整性。

Answer 2

首先，代码的输出很可能不相同，但您没有检查。j * j不适合数字大于 46340 的 32 位 int，因此存在未定义的行为是可能的，但我不认为这是这里的原因。

第一个代码执行内部循环O(i( 次，而第二个代码执行内部循环 O(i 1/2( 次，因此这是 O(^n²( 和O(^3n/2(之间的差异，在 1000000 时意味着前者的执行时间是 316 倍(我的电脑给出 89 秒对 0.20，这是 回合 ~446 倍的差异，这足够接近(，而那与-O3.

除非编译需要 89 秒来内联代码，否则您获得相同的低时间是不可能的。 也就是说，您当时没有运行第一个程序。