Задача поиска позиций с заданным значением excess в битовой строке звучит узкоспециально, но лежит в основе навигации по деревьям через скобочное представление (BP-представление). Если обойти дерево в глубину и записывать 1 при спуске и 0 при подъёме, каждая вершина окажется парой скобок, а поиск парной скобки сводится именно к этой задаче. Формально: дана последовательность битов, определяется функция excess(i) — количество единиц минус количество нулей в первых i битах. Нужно найти все позиции, где excess равен заданному числу.
Универсальная структура для таких запросов — range min-max tree, решающая задачу за O(log n). Для максимальной эффективности она строится поверх небольших блоков, внутри которых поиск ведётся отдельным быстрым методом. Именно для этого внутреннего поиска автор и обратился к GLM-5.1.
| Метод | Размер блока | SIMD | Таблица |
|---|---|---|---|
| sdsl-lite (табличный) | 8 бит | Нет | 256 × target значений |
| GLM-5.1 (pshufb) | 16 бит (4×4 бит) | Да (AVX2) | 4 таблицы по 128–512 бит |
Единственная известная публичная реализация range min-max tree — библиотека sdsl-lite — использует табличный метод: для каждой из 256 возможных 8-битных последовательностей и каждого значения target предподсчитывается маска совпадений. Блоки обрабатываются последовательно, excess обновляется через popcount. Метод работает, но не использует возможности SIMD.
Единственная известная публичная реализация — sdsl-lite — использует табличный метод для блоков по 8 бит без SIMD.
GLM-5.1 предложил иной подход, ориентированный на инструкцию pshufb — параллельный табличный поиск, доступный в SSE/AVX. Идея: разбить блок на 4-битные куски (nibble), для каждого предподсчитать значения excess на каждой из четырёх внутренних позиций. Это четыре таблицы по 128–512 бит. Затем вычислить префиксные суммы excess на границах 4-битных блоков и для каждого куска проверить, совпадает ли локальное значение с целевым.
Для вычисления префиксных сумм алгоритм использует логарифмическую схему вместо линейного прохода: на каждом шаге каждый элемент прибавляет к себе элемент на расстоянии 2^k. Внутренний цикл при этом легко параллелизуется, а внешний делает всего log₂(n) итераций. В AVX2 это выражается четырьмя инструкциями: сдвиг на 1, 2, 4 и 8 байт с накоплением суммы.
Финальный шаг — сравнение через cmpeq, сжатие маски через movemask и расстановка битов через pdep — автор оценивает как рабочий, но избыточный. Проблема в pdep: это 64-битная инструкция из набора BMI2, у которой нет SIMD-аналога. Это ограничивает возможности дальнейшей оптимизации на текущих архитектурах x86.
Автор подчёркивает, что для получения адекватного кода на C++ от языковой модели важен выбор инструмента: в данном случае использовался opencode — специализированный агент для работы с кодом поверх GLM-5.1. Итоговая реализация опубликована в репозитории pixie/bits.h. Алгоритм не претендует на академическую новизну — он собран из известных компонентов (pshufb-таблицы, логарифмические префиксные суммы, BMI2), — но их комбинация для данной задачи в открытом доступе прежде не встречалась.
