Почему отсортированный массив обрабатывается быстрее, чем не отсортированный?

Вот пример C++ кода, который выглядит очень странно. Почему-то, когда данные отсортированы код выполняется почти в шесть раз быстрее.
#include #include #include
int main() { // Заполнение данными const unsigned arraySize = 32768; int data[arraySize];
for (unsigned c = 0; c < arraySize; ++c) data[c] = std::rand() % 256;
// !!! С этой строкой следующий цикл работает быстрее std::sort(data, data + arraySize);
// Проверка clock_t start = clock(); long long sum = 0;
for (unsigned i = 0; i < 100000; ++i) { // Основной цикл for (unsigned c = 0; c < arraySize; ++c) { if (data[c] >= 128) sum += data[c]; } }
double elapsedTime = static_cast(clock() - start) / CLOCKS_PER_SEC;
std::cout << elapsedTime << std::endl; std::cout << "sum = " << sum << std::endl; }
Без std::sort(data, data + arraySize);, код выполняется 11.54 секунды. С отсортированными данными - 1.93 секунды.
Сначала, я думал что-то не так с языком или компилятором. Поэтому я попробовал использовать Java.
import java.util.Arrays; import java.util.Random;
public class Main { public static void main(String[] args) { // Заполнение данными int arraySize = 32768; int data[] = new int[arraySize];
Random rnd = new Random(0); for (int c = 0; c < arraySize; ++c) data[c] = rnd.nextInt() % 256;
// !!! С этой строкой следующий цикл работает быстрее Arrays.sort(data);
// Проверка long start = System.nanoTime(); long sum = 0;
for (int i = 0; i < 100000; ++i) { // Основной цикл for (int c = 0; c < arraySize; ++c) { if (data[c] >= 128) sum += data[c]; } }
System.out.println((System.nanoTime() - start) / 1000000000.0); System.out.println("sum = " + sum); } }
В итоге получились похожие результаты, но с меньшим разрывом.

Первая мысль была о том, что при сортировке данные попадают в кэш, но потом я подумал, что это глупо, потому что массив был только что создан.
Что происходит? Почему отсортированный массив обрабатывается быстрее, чем не отсортированный?

Перевод вопроса Why is it faster to process a sorted array than an unsorted array?

Ответ

Перевод ответа: @Mysticial
Вы стали жертвой ошибки предсказателя переходов

Что такое Предсказание переходов?
Рассмотрим железнодорожный узел:
Картинка Mecanismo, из Wikimedia Commons. Используется под лицензией CC-By-SA 3.0
Теперь представим, что мы вернулись в XIX век – до изобретения радио.
Вы - оператор железнодорожного узла и слышите что прибывает поезд. У Вас нет идей по какому пути он должен идти. вы останавливаете поезд и спрашиваете машиниста куда ему нужно. И затем устанавливаете переключатель в нужное положение.
Поезда тяжелые и с большой инерцией. Поэтому начало движения и остановка занимают много времени.
Есть ли способ лучше? Вы можете угадать куда пойдет поезд!
Если угадали верно, поезд продолжит движение не останавливаясь. Если ошиблись, машинист остановит поезд, вернется назад, и наорет на Вас, чтобы вы перевели пути. Затем он может продолжить движение.
Если каждый раз угадывать правильно, поезд никогда не остановится. Если ошибаться очень часто, поезд будет терять много времени на остановку, возврат, и разгон.

Рассмотрим if-statement: на уровне процессора - это инструкция ветвления:

Вы процессор и вы видите ветвление. У Вас нет предположений какая ветка будет выбрана. Что Вам делать? Вы останавливаете выполнение и ждете завершение предыдущей инструкции. Затем вы продолжаете выполнение по правильному пути.
Современные процессоры сложны и имеют длинные конвейеры. Поэтому "разогрев" и "остановка" занимают много времени.
Есть ли способ лучше? Вы можете угадать какая ветка будет выполняться!
Если Вы угадали верно, выполнение продолжится. Если ошиблись, необходимо сбросить конвейер и откатиться к ветвлению. Затем можно продолжить с нужной ветки.
Если каждый раз угадывать правильно, выполнение никогда не будет останавливаться. Если ошибаться очень часто, будет тратиться много времени на остановку, откат и перезапуск.

Это предсказание переходов. Я признаю, это не лучшая аналогия, потому что поезд может указать направление подав сигнал флагом. Но в компьютерах, процессор не знает какое будет выбрано направление до самого последнего момента.
Так какую выбрать стратегию при угадывании. чтобы минимизировать количество раз. когда поезд должен возвращаться и идти по другому пути? Вы можете посмотреть историю! Если поезд идет влево в 99% случаев, тогда догадка будет: налево. Если чередуются, то и догадки тоже чередуются. Если один путь выбирается через каждые три раза, можно предположить то же самое...
Другими словами, вы пытаетесь определить шаблон поведения и следовать ему. Примерно так работает предсказатель переходов.
У большинства приложений хорошо определяемые ветвления. Поэтому у современных предсказателей переходов процент верных догадок обычно составляет >90%. Но когда они сталкиваются с непредсказуемыми ветвями с не определяемыми шаблонами, предсказатели переходов практически бесполезны.
Дальнейшее чтение: "Предсказатель переходов" статья на Wikipedia

Как указывалось выше, проблема в этом if-statement:
if (data[c] >= 128) sum += data[c];
Обратите внимание, что данные равномерно распределены в диапазоне от 0 до 255. Когда данные отсортированы, первая половина не будет заходить в if-statement. Затем, в if-statement будут заходить все оставшиеся.
Это очень хорошо для предсказателя, потому что много раз последовательно выбирается одна и та же ветка. Даже простой счетчик с насыщением правильно предскажет направление, за исключением случая после смены направления.
Быстрая визуализация:
T = ветка выбрана N = ветка не выбрана
data[] = 0, 1, 2, 3, 4, ... 126, 127, 128, 129, 130, ... 250, 251, 252, ... branch = N N N N N ... N N T T T ... T T T ...
= NNNNNNNNNNNN ... NNNNNNNTTTTTTTTT ... TTTTTTTTTT (легко прогнозировать)
Но когда данные случайны, предсказатель бесполезен, потому что он не может предсказать случайные данные. Таким образом вероятность неверного прогнозирования может быть около 50%. (не лучше чем случайные догадки)
data[] = 226, 185, 125, 158, 198, 144, 217, 79, 202, 118, 14, 150, 177, 182, 133, ... branch = T, T, N, T, T, T, T, N, T, N, N, T, T, T, N ...
= TTNTTTTNTNNTTTN ... (полностью случайно - тяжело прогнозировать)

Итак, что можно сделать?
Если компилятор не может оптимизировать выбор ветки, Вы можете попробовать использовать несколько хаков, если вы готовы пожертвовать читаемостью ради производительности.
Заменить:
if (data[c] >= 128) sum += data[c];
на:
int t = (data[c] - 128) >> 31; sum += ~t & data[c];
Это устраняет ветвление и заменяет его некоторыми битовыми операциями.
(Обратите внимание, что этот хак не совсем эквивалентен оригинальному условию. Но в данном случае он дает верный результат для всех входящих значений из data[].)
Benchmarks: Core i7 920 @ 3.5 GHz
C++ - Visual Studio 2010 - x64 Release
// Ветвление - случайно seconds = 11.777
// Ветвление - сортировано seconds = 2.352
// Без ветвления - случайно seconds = 2.564
// Без ветвления - сортировано seconds = 2.587
Java - Netbeans 7.1.1 JDK 7 - x64
// Ветвление - случайно seconds = 10.93293813
// Ветвление - сортировано seconds = 5.643797077
// Без ветвления - случайно seconds = 3.113581453
// Без ветвления - сортировано seconds = 3.186068823
Наблюдения:
С ветвлением: огромная разница между отсортированными и не отсортированными данными. С хаком: Нет разницы между сортированными и не сортированными данными. В случае C++, при использовании хака результаты немного медленнее, чем при использования ветвления на сортированных данных.
Общее правило заключается в избегании использования условий зависящих от данных в критических циклах. (как в этом примере)

Update :
GCC 4.6.1 с -O3 или -ftree-vectorize на x64 возможно генерировать CMOV инструкции. В этом случае нет разницы между сортированными или не отсортированными данными - оба случая быстрые. VC++ 2010 не доступно генерирование CMOV для ветвления даже при использовании /Ox Intel Compiler 11 делает что-то удивительное. Он меняет местами два цикла, тем самым поднимая непредсказуемое ветвление во внешний цикл. Так что становится не только не восприимчивым к ошибкам предсказания, но и в два раза быстрее чем VC++ и GCC могут сгенерировать! Другими словами, ICC воспользовался тестовыми циклами для победы над тестом... Если Вы даете Intel Compiler код без ветвления, он векторизует его... и это так же быстро, как и с ветвлением (со сменой циклов).
Это показывает, что даже зрелые компиляторы могут отличаться друг от друга в их способности оптимизировать код...