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