x86"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(而不是RELEASE)模式下编译,如果你使用GCC而不是禁用死代码消除(-fno-dce),否则代码的某些部分将无法工作.

所以问题是:当你将TEST_NUM常量设置为非零(比如说5)时,两个条件(模数和除法)大约同时进行,但是当你设置TEST_NUM为0时,第二个条件执行得更慢(向上)到3次!).为什么？

这是反汇编列表: 反汇编列表图片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(这里不太确定).这更好"可预测".通常,预测器将预测为(几乎)总是假的,其间有一些随机的真实,但这取决于处理器的内部.但无论如何,对于错误预测的分支,你不会经常得到额外的周期,而在每五个案例中都是最差的.