2

コードは次のとおりです。

#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 (RELEASE ではない) モードでコンパイルするだけです。GCC を使用している場合は、デッド コードの削除 ( -fno-dce) を無効にしないと、コードの一部が機能しません。

問題は次のとおりです。TEST_NUM 定数をゼロ以外 (5 など) に設定すると、両方の条件 (モジュロと除算) がほぼ同時に実行されますがTEST_NUM、0 に設定すると、2 番目の条件の実行が遅くなります (上3倍に！）。なんで？

分解リストは次のとおりです。 分解リストの画像 http://img213.imageshack.us/slideshow/webplayer.php?id=wp000076.jpg

0 の場合はtest代わりに命令が使用されますが、(5 の場合) にcmp X, 0パッチを適用しても、モジュロ演算には影響しませんが、除算演算には影響することがわかります。cmp X, 5cmp X, 0

定数を変更するときは、操作のカウントと時間がどのように変化するかを注意深く観察してくださいTEST_NUM。

誰かができる場合は、これがどのように起こるか説明してください。
ありがとう。

4

1 に答える 1

6

の場合TEST_NUM == 0、最初の条件が真になることはめったにありません。分岐予測はこれを認識し、条件が常に false であると予測します。この予測はほとんどの場合正しいので、コストのかかる間違った予測分岐を実行する必要はほとんどありません。

'TEST_NUM == 5' の場合もほぼ同じです。最初の条件が真になることはめったにありません。

2 番目の条件 abdTEST_NUM == 0の場合、それぞれの除算の結果はゼロでarr[i] < arr[i+1]、確率は約 0.5 です。これは、分岐予測子にとって最悪のケースです。分岐は、1 つおきのケースで間違って予測されます。平均すると、間違った予測分岐に必要なクロック サイクルの半分が得られます (アーキテクチャによっては、10 ～ 20 サイクルになる場合があります)。

の値がある場合TEST_NUM == 5、2 番目の条件が真になることはめったになく、確率は約 0.1 になります (ここではよくわかりません)。これは、はるかに優れた「予測可能」です。通常、予測子は (ほぼ) 常に false として予測し、その間にいくつかのランダムな true がありますが、それはプロセッサの内部に依存します。しかし、いずれにせよ、間違った予測分岐に対して追加のサイクルが発生することはそれほど多くなく、最悪の場合は 5 回に 1 回発生します。

于 2011-12-04T23:51:53.027 に答える