Почему отсортированный массив обрабатывается в шесть раз быстрее

Тот же алгоритм и те же данные. Разница лишь в порядке элементов, но время исполнения падает с одиннадцати секунд до двух. Всё дело в архитектуре конвейера процессора.

Наткнувшись на if, CPU не ждёт вычисления условия, а угадывает будущее. На отсортированных значениях предсказатель ветвлений ошибается один раз. На хаотичных — постоянно сбрасывает конвейер, сжигая до 20 тактов на каждый промах. Ради оптимизации горячие циклы надёжнее переводить на арифметику без ветвлений.

Заглянем под капот branch-предикторов от базовых счётчиков до TAGE.