Автор статьи построил статическое дерево поиска S+ tree для ускорения поиска в отсортированных данных — это подготовка к работе с суффиксными массивами в биоинформатике, где нужно искать по геному. Входные данные — сортированный список 32-битных беззнаковых целых чисел vals: Vec<u32>. Нужно для каждого запроса q вернуть первый элемент, который ≥ q, либо u32::MAX. Главная метрика — пропускная способность (throughput), то есть количество запросов в секунду.
Автор протестировал сначала классический бинарный поиск из стандартной библиотеки Rust и Eytzinger layout. Eytzinger переупорядочивает данные: корень дерева — средний элемент, дети — на позициях 2i и 2i+1. Это позволяет упреждающе загружать кэш-линии на несколько шагов вперёд. На данных размером 1 ГБ Eytzinger оказывается в 6 раз быстрее бинарного поиска (200 нс на запрос против 1150 нс). Для тестов автор фиксирует частоту CPU на 2.6 ГГц, использует огромные страницы 2 МБ, так как это снижает нагрузку на TLB.
Но у Eytzinger есть проблема: он использует только одно значение из каждой кэш-линии — это неэффективно по памяти. Решение — S-tree, где в одну кэш-линию (64 байта) упаковываются 16 значений, и за один раз обрабатывается 4 уровня дерева. Базовый узел — TreeNode из 16 u32, выровненных по 64 байтам. Внутренние узлы хранят минимальные значения правых поддеревьев, а все данные дублируются в листьях (S+ tree).
Линейный поиск по узлу с досрочным выходом работает плохо — ветвления убивают производительность. Гораздо лучше считать количество значений, меньших запроса, без ветвления. Компилятор Rust сам векторизует такой код через SIMD (AVX2), и получается в два раза быстрее, чем линейный поиск.
Автор пишет hand-rolled SIMD-код, используя portable_simd и ручные интринсики. В версии find_popcnt сначала делаются сравнения с помощью _mm256_cmpgt_epi32, потом _mm256_packs_epi32 пакует результаты, и _mm256_movemask_epi8 выдаёт 16-битную маску. Остаётся только посчитать единицы через popcntl и поделить на 2. Этот ручной код избавляется от лишних перемешиваний и даёт максимальную производительность.