Почему изменение порядка этих инструкций существенно влияет на производительность?

Для задания в школе я выполняю интенсивную операцию на очень большом массиве чисел. В то время как бенчмаркинг однопоточной версии, работающей на всем массиве, и сравнение моих результатов с моим одноклассником, я заметил какое-то странное поведение.

Функция следующая:

int compute (char a[], int start, int end) {
    int sum = 0;
    int min = a[start];
    int max = a[start];

    for (int i = start; i < end; i++) {
        if (a[i] > max) max = a[i];
        if (a[i] < min) min = a[i];

        int cube = a[i] * a[i] * a[i];
        sum += cube;
    }

    return sum;
}

Но моя одноклассная программа постоянно работает быстрее, часто намного быстрее. Его код идентичен, за исключением порядка инструкций в теле цикла:

for (int i = start; i < end; i++) {
    int cube = a[i] * a[i] * a[i];
    sum += cube;

    if (a[i] > max) max = a[i];
    if (a[i] < min) min = a[i];
}

Здесь вывод, сравнивающий время выполнения каждой версии с входным массивом размером 1,000,000,000 (инициализированным случайными подписанными байтами):

Min/max first:
sum = 5445493143089, min = -128, max = 127
Completed in 1.050268 sec

Product-sum first:
sum = 5445493143089, min = -128, max = 127
Completed in 1.010639 sec

Мы проверили сгенерированную сборку для обеих версий и заметили одни и те же инструкции, просто упорядоченные по-разному. Насколько мне известно, это не должно иметь столь значительного эффекта, как это имеет место, но я могу ошибаться. (Мы также заметили, что используемые регистры сильно различались, но я особенно сомневаюсь в этом.)

Мы сталкиваемся с этим поведением при компиляции как для C (-std=c11), так и для С++ (-std=c++11).

Почему порядок этих строк сильно влияет на поведение последовательной программы? Мы также сравниваем параллельную версию операции, и, напротив, ее поведение практически не изменилось. Я рассматривал переупорядочение памяти в качестве возможного виновника, но это, похоже, не проблема, поскольку параллельная версия практически не затронута (и в любом случае не существует перекрытия в разделах).

Интенсивные тесты "назад-назад" , демонстрирующие поведение. Продукт-сумма всегда быстрее, чем min/max, даже в чередовании и позволяет кэшировать.

Ответ 1

Если мы помещаем явные переходы в код, вы можете видеть, что тот, у кого есть условные выражения в конце, может избежать одного перехода большую часть времени. Это похоже на код, который будет фактически сгенерирован компилятором.

Первая форма, мин/макс первая:

    int i = lo;
    goto start;
loop:
    i++;
start:
    if (!(i < hi)) goto end;
    if (!(a[i] > ret.max)) goto label1;
    ret.max = a[i];
label1:
    if (!(a[i] < ret.min)) goto label2;
    ret.min = a[i];
label2:

    long long square = a[i] * a[i];
    ret.sum += square;
    goto loop;
end:

Вторая форма, мин/макс последняя:

    int i = lo;
    goto start;
loop:
    i++;
start:
    if (!(i < hi)) goto end;
    long long square = a[i] * a[i];
    ret.sum += square;

    if (!(a[i] > ret.max)) goto label1;
    ret.max = a[i];
label1:
    if (!(a[i] < ret.min)) goto loop;
    ret.min = a[i];
    goto loop;
end:

Ответ 2

Это может быть так же просто, как предсказание скачка процессора работает лучше с условными переходами в нижней части цикла...