странное поведение инструкции xmp "cmp" - PullRequest
Новая
       42

странное поведение инструкции xmp "cmp"

2 голосов
/ 04 декабря 2011

Вот код: 

#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 раз!).Почему?

Вот листинг разборки: листинг разборки image http://img213.imageshack.us/slideshow/webplayer.php?id=wp000076.jpg

В случае 0 вместо cmp X, 0 используется инструкция test, но даже если вы исправите cmp X, 5(в случае от 5) до cmp X, 0 вы увидите, что это не повлияет на операцию по модулю, но повлияет на операцию деления.

Внимательно следите за тем, как изменяется количество операций и время при измененииTEST_NUM константа.

Если кто-нибудь может, пожалуйста, объясните, как это может произойти?
Спасибо.

1 Ответ

6 голосов
/ 05 декабря 2011

В случае TEST_NUM == 0 первое условие редко выполняется. Предсказание ветвления распознает это и предсказывает условие как всегда ложное. В большинстве случаев этот прогноз будет верным, поэтому выполнение дорогостоящего ветвления с неправильным прогнозом редко требуется.

Почти то же самое относится и к случаю 'TEST_NUM == 5': первое условие редко будет истинным.

Для второго условия abd TEST_NUM == 0 результат деления равен нулю для каждого arr[i] < arr[i+1] с вероятностью около 0,5. Это наихудший случай для предиктора ветвления - ветвление будет предсказываться неправильно в каждом втором случае. В среднем вы получите половину тактовых циклов, необходимых для неправильно предсказанного перехода (в зависимости от архитектуры это может быть от 10 до 20 циклов).

Если у вас есть значение TEST_NUM == 5, второе условие теперь редко выполняется, вероятность будет около 0,1 (здесь не совсем точно). Это гораздо лучше "предсказуемо". Типически предиктор будет предсказывать как (почти) всегда ложное, с некоторыми случайными истинами между ними, но это зависит от внутренних особенностей процессоров. Но в любом случае вы получаете дополнительные циклы для неверно предсказанной ветви не так часто, что является худшим в каждом пятом случае.

...