Разработчики Manticore Search выпустили версию 27.1.5 с тремя изменениями в поисковом цикле HNSW, которые ускоряют KNN-запросы до 29% при больших k и дают прирост более 20% под параллельной нагрузкой. Обновление не требует изменений в коде, перестроения индексов или новых настроек.
Оптимизации касаются основного цикла hnswlib — открытой реализации HNSW, на которой построен KNN-поиск в Manticore. Первое изменение переносит выбор функции расстояния на этап компиляции через шаблоны C++. Раньше функция вызывалась через указатель для каждого кандидата, что мешало компилятору встроить её в цикл и ухудшало предсказание ветвлений. Теперь один switch в начале поиска выбирает нужную специализацию шаблона, после чего весь цикл — обход соседей, расчёт расстояния и обновление кандидатов — выполняется как единая функция с полностью встроенным вычислением.
Второе изменение — двухпроходная обработка соседей. Раньше каждый сосед обрабатывался за один проход: проверка посещения, загрузка векторных данных, расчёт расстояния. Предзагрузка не успевала сработать до момента обращения к данным. Теперь первый проход собирает непосещённых соседей в массив и выдаёт prefetch-инструкции для их векторов. Второй проход вычисляет расстояния — к этому времени данные уже в кэше. Двухпроходная схема также позволяет обрабатывать кандидатов парами: вектор запроса загружается один раз и используется для обоих вычислений, что убирает повторные загрузки.
Третье изменение — функции расстояния под AVX-512, обрабатывающие 16 чисел с плавающей точкой за итерацию вместо 8 в AVX2. Для скалярного произведения и L2 используются fused multiply-add инструкции, для бинарной квантизации — расширение VPOPCNTDQ. Manticore теперь поставляется в трёх сборках библиотеки (базовая, AVX2, AVX-512) и автоматически загружает подходящую по возможностям CPU.
Бенчмарки на датасете dbpedia-openai-1M (1 млн векторов, 1536 измерений) на AMD Ryzen 7 9700X показали: в однопоточном режиме прирост от +3% при k=10 до +29% при k=1000. В многопоточном — до +22–24% при k=1000 независимо от числа потоков. Наибольший эффект заметен на векторах высокой размерности, больших k и запросах с oversampling, потому что чем больше доля вычисления расстояний в общей нагрузке, тем сильнее работают оптимизации.
По материалам Habr SEO.
