Супер быстрый бинарный поиск⚡️

Бинарный поиск знаком любому школьнику и студенту. Всего 5 строк кода, казалось бы - разве там вообще можно что-то ускорить?

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

Итак, доклад CppCon от Сергея Слотина, где он за час проходит от простых до сложных методов и сравнивает их с std::lower_bound, доходя по итогу до ускорения в 15 раз 💪

1️⃣ Branchless binary search.
If в котором мы решаем в какую половину массива пойти, плохо предсказывается branch predictor-ом процессора и стопорит работу. С помощью пары махинаций этот иф можно переписать чуть по другому (но всё ещё в 3 строчки) - бранч исчезает из ассемблера и заменяется инструкцией cmov (conditional move). Очень простое и изящное ускорение в 3 раза на маленьких массивах

2️⃣ Eytzinger Binary Search
Переставляем элементы массива по мотивам бинарной кучи для улучшения кэш локальности. Пусть есть элемент с позицией k, тогда его непосредственные потомки в поиске будут на позициях 2k, 2k + 1. Получим расклад, где часто нужные элементы лежат рядом в соседних кэш-линиях. Например в начале массива лягут элементы с оригинальными позициями ½n, ¼n, ¾n, ⅛n, ⅜n ..., всегда нужные на первых итерациях. С небольшим тюнингом получаем ускорение уже в 4 раза на больших массивах.

3️⃣ B-trees + SIMD
Наворачиваем на предыдущий подход деревья, где в нодах лежат несколько элементов + SIMD, постепенно получается результат в 15 раз и это не предел. Впрочем реализация и работа с индексами уже становится заметно сложными.

📙 Прислушиваюсь к просьбе посоветовать, что почитать - например, в начале доклада Сергей рекламирует свою книгу Algorithms for Modern Hardware, где эта оптимизация и многие другие вещи объяснены подробнее. Я читал её сколько-то лет назад и мне понравилось.

https://www.youtube.com/watch?v=1RIPMQQRBWk