奇妙な行動「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回！）。どうして？ここで

は逆アセンブリリストである：0の場合disassembly listing image http://img213.imageshack.us/slideshow/webplayer.php?id=wp000076.jpg

test命令が代わりにcmp X, 0の使用されていますが、cmp X, 0に（5の場合）cmp X, 5にパッチを当てても、あなたはそれがないということがわかりますモジュロ演算に影響しますが、除算演算に影響します。

TEST_NUM定数を変更している間に、操作の回数と時間がどのように変化しているか注意してください。

誰でもできる場合は、どうすればこのことが起こるのか説明してください。
ありがとうございます。

Answer 1

TEST_NUM == 0の場合、最初の条件はほとんど当てはまりません。分岐予測はこれを認識し、条件を常に偽と予測する。この予測はほとんどの場合正しいでしょう。したがって、高価な間違った予測ブランチをめったに実行する必要はありません。

「TEST_NUM == 5」の場合もほぼ同じです。最初の条件はほとんど当てはまりません。

第2の条件がabdTEST_NUM == 0の場合、約0.5の確率を有するarr[i] < arr[i+1]ごとに除算の結果はゼロになります。これは分岐予測子にとって最悪の場合です。分岐は1秒ごとに間違って予測されます。平均して、間違った予測分岐に必要なクロックサイクルの半分を得ます（アーキテクチャに応じて、これは10〜20サイクルです）。

値がTEST_NUM == 5の場合、2番目の条件はほとんど当てはまりません。確率は約0.1になります（ここではあまり確かではありません）。これははるかに良い "予測可能"です。 Tpicallyでは、予測子は（ほとんど）常に間違っていると予測しますが、プロセッサの内部に依存します。しかし、いずれにしても間違った予測ブランチの追加サイクルがそれほど頻繁ではなく、5回ごとに最悪になります。