86怪「CMP」指令

Question

這裏的行爲是代碼：

#include <iostream> 
#include <time.h> 

using namespace std; 

#define ARR_LENGTH 1000000 
#define TEST_NUM 0 
typedef unsigned int uint; 

uint arr[ARR_LENGTH]; 

uint inc_time(uint x) { 
    uint y = 0, tm = clock(); 
    for (uint i = 0; i < x; i++) y++; 
     return clock() - tm; 
} 

int main() { 
    uint div = 0, mod = 0, tm = 0, overall = 0, inc_tm; 
    srand(time(NULL)); 
    for (uint i = 0; i < ARR_LENGTH; i++) arr[i] = (uint)rand() + 2; 

    tm = clock(); 
    for (uint i = 0; i < ARR_LENGTH - 1; i++) 
     if (arr[i] % arr[i+1] != TEST_NUM) mod++; 
    overall = clock() - tm; 
    inc_tm = inc_time(mod); 
    cout << "mods - " << mod << endl; 
    cout << "Overall time - " << overall<< endl; 
    cout << " wasted on increment - " << inc_tm << endl; 
    cout << " wasted on condition - " << overall - inc_tm << endl << endl; 

    tm = clock(); 
    for (uint i = 0; i < ARR_LENGTH - 1; i++) 
     if (arr[i]/arr[i+1] != TEST_NUM) div++; 
    overall = clock()-tm; 
    inc_tm = inc_time(div); 
    cout << "divs - " << div << endl; 
    cout << "Overall time - " << overall << endl; 
    cout << " wasted on increment - " << inc_tm << endl; 
    cout << " wasted on condition - " << overall - inc_tm << endl << endl; 

    return 0; 
} 

如果你正在使用Visual Studio，只是編譯DEBUG（未釋放）模式，如果你使用GCC比禁用死代碼消除（-fno-dce），否則代碼的某些部分將不起作用。

所以問題是：當您將TEST_NUM常量設置爲非零（例如5）時，兩個條件（模數和除法）都近似同時執行，但當您將TEST_NUM設置爲0時，條件執行較慢（最多3次！）。爲什麼？

下面是反彙編列表：disassembly listing image http://img213.imageshack.us/slideshow/webplayer.php?id=wp000076.jpg

在0 test指令的情況下是用來代替cmp X, 0但即使你打補丁cmp X, 5（在5時）至cmp X, 0你會看到，它不會影響模數運算，但會影響分頻運算。

仔細觀察在改變TEST_NUM常數時操作的次數和時間如何變化。

如果有人可以，請解釋這是怎麼發生的？
謝謝。

Answer 1

在TEST_NUM == 0的情況下，第一個條件很少是真的。分支預測會識別這一點，並預測條件始終爲假。這種預測在大多數情況下都是正確的，因此很難執行昂貴的錯誤預測分支。

對於'TEST_NUM == 5'情況幾乎相同：第一個條件很少會成立。

對於第二個條件abd TEST_NUM == 0，每個arr[i] < arr[i+1]的除法結果爲零，其概率約爲0.5。對於分支預測器來說這是最糟糕的情況 - 在每個第二種情況下，分支都會被預測爲錯誤。平均而言，您將得到錯誤預測分支所需的時鐘週期的一半（取決於可能在10到20個週期之間的架構）。

如果你有一個值TEST_NUM == 5，第二個條件現在很少是真的，概率將是大約0.1（這裏不太確定）。這比「可預測」好得多。通常情況下，預測器會預測（幾乎）總是錯誤的，其間有一些隨機變換，但這取決於處理器的內部。但是無論如何，你不會經常得到錯誤預測分支的額外週期，在每第五種情況下都是最差的。