Статические деревья поиска: бинарный поиск ускорили в 40 раз

Автор блога Curious Coding опубликовал разбор оптимизации поиска в статичном (неизменяемом) отсортированном массиве 32-битных чисел: нужно быстро находить наименьший элемент, который не меньше заданного запроса. Метрика, не задержка одного запроса, а throughput: сколько независимых запросов структура способна обработать в секунду. Отправная точка, реализация из статьи Хуонга и Морена (Khuong, Morin, 2017) «Array Layouts for Comparison-Based Searching» и серия постов проекта Algorithmica про S+-деревья; автор берёт их идеи из раздела «future work» и доводит до предела, вплоть до чтения ассемблерного кода ради экономии инструкций.

За базовый вариант взят обычный бинарный поиск из стандартной библиотеки Rust. Первое улучшение, раскладка Эйтцингера (Eytzinger layout): массив переупорядочивается так, что бинарный поиск превращается в обход неявного дерева, а первые шаги поиска всегда читают близко расположенные в памяти значения. Это позволяет заранее (спекулятивно) подгружать в кэш нужные строки кэша ещё до того, как известно, в какую сторону пойдёт поиск, и даёт ускорение примерно в 4 раза на больших массивах, не помещающихся в кэш L2.

Далее автор включает hugepages (страницы памяти по 2 МБ вместо обычных 4 КБ), это снижает нагрузку на TLB (буфер трансляции адресов) и заметно ускоряет работу на массивах среднего размера (от 1 до 32 МБ; на практике все выделения памяти округляются вверх до 32 МБ, иначе они не становятся hugepages).

Основная идея, S+-деревья: вместо линейной раскладки данные группируются узлами по 15, 16 значений, чтобы один узел помещался ровно в одну кэш-строку (64 байта = 16 чисел по 4 байта). Такой узел трактуется как 16-арное (а с учётом деталей, 17-арное) поддерево: за одно чтение кэш-линии выполняется сразу несколько шагов поиска. Поверх этого добавлен набор low-level оптимизаций: ручной SIMD на инструкциях AVX2, батчинг запросов (обработка сразу пачки запросов вместо одного), явный префетчинг, оптимизация арифметики указателей (заранее размноженные значения, побайтовая адресация), а также разбиение деревьев по общим префиксам данных (несколько вариантов раскладки, включая компактные поддеревья и отдельную обработку «человеческих» данных). Отдельно измерено поведение в многопоточном режиме.

В сумме все эти слои дают заявленное в заголовке 40-кратное ускорение относительно обычного бинарного поиска. Практический мотив исследования, не абстрактная оптимизация ради оптимизации, а биоинформатика: один из способов индексировать ДНК (геном человека, около 3 млрд пар оснований), это суффиксный массив, по которому классически ищут бинарным поиском; ускорение этого поиска, первый шаг к более быстрому поиску по суффиксным массивам. Весь код, включая бенчмарки и скрипты построения графиков, выложен в открытом доступе на GitHub (репозиторий static-search-tree).

Замеры сделаны на ноутбучном процессоре Intel Core i7-10750H с зафиксированной частотой 2,6 ГГц (L1, 32 КиБ на ядро, L2, 256 КиБ на ядро, L3, 12 МиБ на 6 физических ядер, гипертрейдинг отключён); каждый замер повторён 5 раз, на графиках, медиана и разброс без экстремумов. Автор отдельно поясняет, что измеряет именно пропускную способность (throughput), а не задержку одного запроса, и что заметный «шум» на графике бинарного поиска на самом деле полностью воспроизводим и объясняется эффектами ассоциативности кэша.

Ключевые факты

Итог: статическое дерево поиска (S+-дерево) по отсортированному массиву обгоняет обычный бинарный поиск в 40 раз по пропускной способности (throughput)
Слои ускорения: раскладка Эйтцингера с префетчингом (~4x), hugepages по 2 МБ вместо 4 КБ, узлы дерева размером в одну кэш-линию (15, 16 значений, 64 байта), ручной SIMD на AVX2, батчинг запросов и разбиение по общим префиксам данных
Практическая цель, ускорить поиск по суффиксному массиву при индексации ДНК (геном человека, около 3 млрд пар оснований), где сейчас применяют обычный бинарный поиск
Работа продолжает и доводит до предела идеи из проекта Algorithmica (S+-деревья) и статьи Khuong & Morin 2017 года «Array Layouts for Comparison-Based Searching»
Весь код, бенчмарки и скрипты построения графиков открыты на GitHub (репозиторий static-search-tree); замеры сделаны на процессоре Intel Core i7-10750H с зафиксированной частотой

Почему это важно

Бинарный поиск по отсортированному массиву, один из самых базовых строительных блоков в программировании, от баз данных до поисковых индексов. Автор показывает, что современное железо (кэши, SIMD, механизмы предвыборки) позволяет ускорить эту операцию на порядок без смены алгоритма как такового, только за счёт правильной раскладки данных в памяти и использования возможностей CPU. Итоговый разрыв в 40 раз, это не микрооптимизация, а качественный скачок для любой системы, где поиск по отсортированным данным, узкое место.

Кому это важно

Разработчикам высокопроизводительных систем и баз данных, специалистам по низкоуровневой оптимизации (SIMD, работа с кэшем и памятью на Rust/C++), а также биоинформатикам, авторы прямо указывают на индексацию геномов и поиск по суффиксным массивам ДНК как на практический мотив и следующий шаг работы.

Как это применить

Все техники и код открыты: раскладка Эйтцингера, использование hugepages, упаковка узлов дерева в размер кэш-линии, батчинг запросов, ручной SIMD на AVX2 и разбиение по общим префиксам, это переиспользуемый набор приёмов для любой задачи поиска по статичному отсортированному массиву, а не решение, привязанное к конкретному продукту. Полный исходный код, бенчмарки и графики выложены в открытом репозитории static-search-tree на GitHub.

Можно ли доверять

Методология описана подробно и прозрачно: указана конкретная модель процессора и зафиксированная частота, размеры кэшей всех уровней, число повторов замера (5) и способ агрегации (медиана с отбросом экстремумов), а также разбор природы «шума» на графиках. Работа явно опирается на рецензируемый источник, статью Khuong & Morin (2017), и на предыдущие посты проекта Algorithmica, идеи которых доводятся до практической реализации. Код и данные для воспроизведения результатов опубликованы. Материал прошёл модерацию Hacker News (126 очков), хотя обсуждение под постом небольшое (6 комментариев).

Риски и подводные камни

Ускорения измерены на одном конкретном ноутбучном процессоре и могут не переноситься линейно на серверные CPU или другие архитектуры. Все SIMD-оптимизации завязаны на набор инструкций AVX2 и явно предполагают процессор Intel, автор отдельно отмечает, что не использует более новый AVX512, поскольку его нет на тестовой машине; на ARM или без AVX2 часть ускорений просто недоступна. Сама техника усложняет код: ручной SIMD, побайтовая арифметика указателей и предвыборка кэша делают реализацию заметно менее читаемой, чем обычный бинарный поиск. Наконец, заявленная практическая цель, ускорение поиска по суффиксному массиву ДНК, в этом посте не реализована, а лишь намечена в разделе «future work» вместе с другими нерешёнными задачами (интерполяционный поиск, более компактная упаковка данных, поиск диапазонов).

«В итоге поиск по раскладке Эйтцингера получается примерно в 4 раза быстрее, что хорошо согласуется с возможностью заранее подгружать в кэш 4 итерации кэш-строк за раз.»

— автор поста, блог Curious Coding