測量C/C++性能的難點

我寫了一段C代碼來展示關於優化和分支預測的討論中的一點。然後我注意到比我預期的更多樣化的結果。我的目標是用C++和C之間常用的語言編寫它，這兩種語言都符合標準，並且相當便於攜帶。它在不同的Windows電腦上測試過：測量C/C++性能的難點

#include <stdio.h> 
#include <time.h> 

/// @return - time difference between start and stop in milliseconds 
int ms_elapsed(clock_t start, clock_t stop) 
{ 
    return (int)(1000.0 * (stop - start)/CLOCKS_PER_SEC); 
} 

int const Billion = 1000000000; 
/// & with numbers up to Billion gives 0, 0, 2, 2 repeating pattern 
int const Pattern_0_0_2_2 = 0x40000002; 

/// @return - half of Billion 
int unpredictableIfs() 
{ 
    int sum = 0; 
    for (int i = 0; i < Billion; ++i) 
    { 
     // true, true, false, false ... 
     if ((i & Pattern_0_0_2_2) == 0) 
     { 
      ++sum; 
     } 
    } 
    return sum; 
} 

/// @return - half of Billion 
int noIfs() 
{ 
    int sum = 0; 
    for (int i = 0; i < Billion; ++i) 
    { 
     // 1, 1, 0, 0 ... 
     sum += (i & Pattern_0_0_2_2) == 0; 
    } 
    return sum; 
} 

int main() 
{ 
    clock_t volatile start; 
    clock_t volatile stop; 
    int volatile sum; 
    printf("Puzzling measurements:\n"); 

    start = clock(); 
    sum = unpredictableIfs(); 
    stop = clock(); 
    printf("Unpredictable ifs took %d msec; answer was %d\n" 
      , ms_elapsed(start, stop), sum); 

    start = clock(); 
    sum = unpredictableIfs(); 
    stop = clock(); 
    printf("Unpredictable ifs took %d msec; answer was %d\n" 
      , ms_elapsed(start, stop), sum); 

    start = clock(); 
    sum = noIfs(); 
    stop = clock(); 
    printf("Same without ifs took %d msec; answer was %d\n" 
      , ms_elapsed(start, stop), sum); 

    start = clock(); 
    sum = unpredictableIfs(); 
    stop = clock(); 
    printf("Unpredictable ifs took %d msec; answer was %d\n" 
      , ms_elapsed(start, stop), sum); 
}

編譯VS2010;/O2優化的英特爾酷睿2，WinXP的結果：

Puzzling measurements: 
Unpredictable ifs took 1344 msec; answer was 500000000 
Unpredictable ifs took 1016 msec; answer was 500000000 
Same without ifs took 1031 msec; answer was 500000000 
Unpredictable ifs took 4797 msec; answer was 500000000

編輯：編譯器的完整開關：

/紫/ NOLOGO/W3/WX-/ O2 /愛/ Oy-/GL/D「WIN32」/ D「NDEBUG」/ D「_CONSOLE」/ D「_UNICODE」/ D「UNICODE」/ Gm-/EHsc/GS/Gy/fp：精確/ Zc：wchar_t/Zc：forScope/Fp「 \ Trying.pch「/ Fa」Release \「/ Fo」Release \「/Fd"Release\vc100.pdb」/ Gd/analyze-/errorReport：隊列

其他人張貼這樣的......使用MinGW編譯，G ++ 4.71，-O1優化的英特爾酷睿2，WinXP的結果：

Puzzling measurements: 
Unpredictable ifs took 1656 msec; answer was 500000000 
Unpredictable ifs took 0 msec; answer was 500000000 
Same without ifs took 1969 msec; answer was 500000000 
Unpredictable ifs took 0 msec; answer was 500000000

此外，他張貼-O3優化這樣的結果：

Puzzling measurements: 
Unpredictable ifs took 1890 msec; answer was 500000000 
Unpredictable ifs took 2516 msec; answer was 500000000 
Same without ifs took 1422 msec; answer was 500000000 
Unpredictable ifs took 2516 msec; answer was 500000000

現在我有題。這裏發生了什麼？

更具體地說......一個固定功能如何採取如此不同的時間量？我的代碼有問題嗎？英特爾處理器有一些棘手的問題嗎？編譯器是否奇怪？這是因爲32位代碼在64位處理器上運行？

感謝您的關注！

編輯： 我接受g ++ -O1只是在其他兩個調用中重用返回的值。我也接受g ++ -O2和g ++ -O3有缺陷，將優化排除在外。測量速度的顯着差異（450％!!!）似乎仍然很神祕。

我看着由VS2010生成的代碼的反彙編。它做了3次內聯unpredictableIfs。內聯代碼非常相似;循環是一樣的。它沒有內聯noIfs。它確實滾動了noIfs。一次迭代需要4個步驟。 noIfs計算得像是寫過，而unpredictableIfs使用jne跳過增量。

來源

2013-02-19 Öö Tiib

你真的檢查過你的「if」和「noIfs」實際上是不同的，一旦編譯？現在許多編譯器都會發現，對於你正在做的事情，最好做一些數學運算而不是條件跳轉...... – 2013-02-19 19:20:47

@MatsPetersson與VS2010生成的代碼是完全不同的。我會編輯帖子來解釋。 – 2013-02-19 19:31:08

@ÖöTiib務必向我們展示您在使用VS2010進行編譯時使用的命令行開關。 – 2013-02-19 19:31:38

對於-O1，gcc-4.7.1只會調用unpredictableIfs一次並重新使用結果，因爲它認識到它是純函數，所以每次調用結果都是一樣的。（我通過查看生成的程序集進行了驗證）。

隨着更高的優化級別，函數被內聯，編譯器不再識別它是相同的代碼，因此每次函數調用時都會運行它出現在源文件中。

除此之外，我的gcc-4.7。當使用-O1或-O2（除了重用問題，兩者產生相同的代碼）時，使用unpredictableIfs最好，而noIfs使用多得多使用-O3更好。然而，相同代碼的不同運行之間的時間點在這裏是一致的 - 相差10毫秒（粒度爲clock），所以我不知道什麼可能會導致您報告的unpredictableIfs的實際不同時間爲-O3。

隨着-O2，用於unpredictableIfs循環是相同的與-O1生成的代碼（除寄存器交換）：

.L12: 
    movl %eax, %ecx 
    andl $1073741826, %ecx 
    cmpl $1, %ecx 
    adcl $0, %edx 
    addl $1, %eax 
    cmpl $1000000000, %eax 
    jne .L12

和noIfs它類似於：

.L15: 
    xorl %ecx, %ecx 
    testl $1073741826, %eax 
    sete %cl 
    addl $1, %eax 
    addl %ecx, %edx 
    cmpl $1000000000, %eax 
    jne .L15

在那裏是

.L7: 
    testl $1073741826, %edx 
    sete %cl 
    movzbl %cl, %ecx 
    addl %ecx, %eax 
    addl $1, %edx 
    cmpl $1000000000, %edx 
    jne .L7

與-O1。兩個循環運行時間相似，unpredictableIfs快一點。

隨着-O3，爲unpredictableIfs循環變差，

.L14: 
    leal 1(%rdx), %ecx 
    testl $1073741826, %eax 
    cmove %ecx, %edx 
    addl $1, %eax 
    cmpl $1000000000, %eax 
    jne  .L14

和noIfs（包括這裏的設置代碼），它變得更好：

pxor %xmm2, %xmm2 
    movq %rax, 32(%rsp) 
    movdqa .LC3(%rip), %xmm6 
    xorl %eax, %eax 
    movdqa .LC2(%rip), %xmm1 
    movdqa %xmm2, %xmm3 
    movdqa .LC4(%rip), %xmm5 
    movdqa .LC5(%rip), %xmm4 
    .p2align 4,,10 
    .p2align 3 
.L18: 
    movdqa %xmm1, %xmm0 
    addl $1, %eax 
    paddd %xmm6, %xmm1 
    cmpl $250000000, %eax 
    pand %xmm5, %xmm0 
    pcmpeqd %xmm3, %xmm0 
    pand %xmm4, %xmm0 
    paddd %xmm0, %xmm2 
    jne .L18 

.LC2: 
    .long 0 
    .long 1 
    .long 2 
    .long 3 
    .align 16 
.LC3: 
    .long 4 
    .long 4 
    .long 4 
    .long 4 
    .align 16 
.LC4: 
    .long 1073741826 
    .long 1073741826 
    .long 1073741826 
    .long 1073741826 
    .align 16 
.LC5: 
    .long 1 
    .long 1 
    .long 1 
    .long 1

它計算四次迭代一次，因此，noIfs的運行速度幾乎是當時的四倍。

來源

2013-02-19 19:25:40

4.7.2驗證。當一個副作用（如printf）插入函數中時，-O1上的優化也不會發生。 – thiton 2013-02-19 19:27:14

什麼？不知何故，我覺得這應該是一個GCC錯誤。 – 2013-02-19 19:28:35

@JonasWielicki爲什麼？ 'unpredictableIfs'的結果總是相同的，並且可以在編譯時計算。或者你是否感到困惑，爲什麼它沒有被更多的攻擊性優化重用？ – 2013-02-19 19:29:42

對，在64位Linux上查看gcc的彙編代碼，第一種情況下，使用-O1，函數UnpredictableIfs確實只調用一次，結果被重用。

使用-O2和-O3時，函數是內聯的，所花費的時間應該相同。在任一位代碼中也沒有實際分支，但兩位代碼的翻譯有所不同，我已刪除了更新「總和」的行[在兩種情況下都在%edx]

UnpredictableIfs：

movl %eax, %ecx 
andl $1073741826, %ecx 
cmpl $1, %ecx 
adcl $0, %edx 
addl $1, %eax

NoIfs：

xorl %ecx, %ecx 
testl $1073741826, %eax 
sete %cl 
addl $1, %eax 
addl %ecx, %edx

正如你所看到的，這是不完全相同，但它確實非常類似的事情。

來源

2013-02-19 19:31:40

關於Windows上的結果範圍（從1016毫秒到4797毫秒）：您應該知道MSVC中的clock()返回elapsed wall time。該標準說clock()應返回CPU time spent by the process的近似值，其他實現可以做得更好。

鑑於MSVC給出了時間上的限制，如果您的進程在運行一次迭代測試時被搶佔，即使代碼的CPU時間大約相同，它也可以給出更大的結果。

另外請注意，很多Windows電腦上的clock()的分辨率非常糟糕，通常爲11-19毫秒。你已經做了足夠的迭代，只有大約1％，所以我不認爲它是差異的一部分，但是在嘗試編寫基準測試時很好記。我知道你打算使用可移植性，但是如果你需要在Windows上進行更好的測量，你可以使用QueryPerformanceCounter，這幾乎肯定會給你提供更好的分辨率，儘管它仍然只是延遲了牆壁時間。

UPDATE：當我得知一個案例的長運行時間一直在發生之後，我激活了VS2010並再現了結果。我通常在1000毫秒左右運行一些，其他運行時間爲750毫秒，而不可思議的運行時間爲5000毫秒以上。

觀察：

在unpredictableIfs（）代碼被內聯的所有病例。
刪除noIfs（）代碼沒有影響（所以很長一段時間不是該代碼的副作用）。
將線程關聯設置爲單個處理器不起作用。
5000毫秒時間總是後面的情況。我注意到後面的例子在循環的開始之前有一個額外的指令：lea ecx,[ecx]。我不明白爲什麼這會造成5倍的差距。除此之外，早期和後期的實例都是相同的代碼。

刪除從start和stop變量volatile產生少長期運行多個750下毫秒運行的，也沒有1000毫秒運行。（生成的循環代碼在所有情況下看起來完全相同，而不是lea s）。

從sum變量中除去volatile變量（但保留時鐘計時器），長時間運行可能發生在任何位置。

如果刪除所有volatile限定符，則可以獲得一致的快速（750毫秒）運行。（代碼看起來等同於早期的，但edi被選爲sum而不是ecx）

我不知道該怎麼從所有這一切的結論，除了volatile與MSVC不可預知的性能後果，所以只有在必要時才應用它。

UPDATE 2：我看到了一致的運行時間差異與使用volatile有關，即使反彙編幾乎相同。

揮發性：

Puzzling measurements: Unpredictable ifs took 643 msec; answer was 500000000 Unpredictable ifs took 1248 msec; answer was 500000000 Unpredictable ifs took 605 msec; answer was 500000000 Unpredictable ifs took 4611 msec; answer was 500000000 Unpredictable ifs took 4706 msec; answer was 500000000 Unpredictable ifs took 4516 msec; answer was 500000000 Unpredictable ifs took 4382 msec; answer was 500000000

每個實例的拆卸是這樣的：

start = clock(); 010D1015 mov esi,dword ptr [__imp__clock (10D20A0h)] 010D101B add esp,4 010D101E call esi 010D1020 mov dword ptr [start],eax sum = unpredictableIfs(); 010D1023 xor ecx,ecx 010D1025 xor eax,eax 010D1027 test eax,40000002h 010D102C jne main+2Fh (10D102Fh) 010D102E inc ecx 010D102F inc eax 010D1030 cmp eax,3B9ACA00h 010D1035 jl main+27h (10D1027h) 010D1037 mov dword ptr [sum],ecx stop = clock(); 010D103A call esi 010D103C mov dword ptr [stop],eax

無揮發性：

Puzzling measurements: Unpredictable ifs took 644 msec; answer was 500000000 Unpredictable ifs took 624 msec; answer was 500000000 Unpredictable ifs took 624 msec; answer was 500000000 Unpredictable ifs took 605 msec; answer was 500000000 Unpredictable ifs took 599 msec; answer was 500000000 Unpredictable ifs took 599 msec; answer was 500000000 Unpredictable ifs took 599 msec; answer was 500000000 start = clock(); 14 mov esi,dword ptr [__imp__clock (3220A0h)] 1A add esp,4 1D call esi 1F mov dword ptr [start],eax sum = unpredictableIfs(); 22 xor ebx,ebx 24 xor eax,eax 26 test eax,40000002h 2B jne main+2Eh (32102Eh) 2D inc ebx 2E inc eax 2F cmp eax,3B9ACA00h 34 jl main+26h (321026h) stop = clock(); 36 call esi // The only optimization I see is here, where eax isn't explicitly stored // in stop but is instead immediately used to compute the value for the // printf that follows.

除了寄存器選擇，我沒有看到有顯着差異。

來源

2013-02-20 13:56:49

這通常是一個將微小測量變爲無用的問題。當測量持續一秒鐘的事物時，它也可能導致測試之間1-2％的波動。它無法解釋472％的差異。差異是可重複的。再次運行測試我經常得到完全相同的數字。 – 2013-02-20 15:52:34

我沒有意識到長期以來一直在發生。 – 2013-02-20 17:26:59

刪除volatile是個壞主意。 volatile函數將函數調用的結果以與代碼中完全相同的順序分配給變量。編譯器可以證明函數clock（）和noIfs（）是不相關的，但仍然無法利用volatile來優化時序。沒有其他揮發性的影響。被測量的測試不包含任何變化，所以不可能如何影響它們的性能。 – 2013-02-20 20:02:20

測量C/C++性能的難點

回答

相關問題