Оптимизируем бинарный поиск – Сергей Слотин

Доклады об ускорении условных баз данных на 5−10% большинству людей не интересны: да, это то, за что программистам платят, но эти оптимизации обычно слишком сложные и специфичные, чтобы их можно было сразу применить где-нибудь еще. Другое дело — оптимизация базовых алгоритмов из учебников — тех, которые кажутся настолько простыми, что пытаться ускорять их даже в голову не придет. Такие оптимизации, как правило, просты, поучительны, многократны и, на удивление, не так редки, как многие думают. В этом докладе мы сосредоточимся на одном из таких фундаментальных алгоритмов — бинарном поиске. Рассмотрим ряд способов ускорить его с помощью branchless-программирования, оптимизации доступов к памяти и использования SIMD-инструкций и постепенно выведем алгоритм до 15 раз быстрее std::lower_bound.