Как мы ускорили KNN-поиск в Manticore: двухпроходный обход HNSW, пакетная обработка и AVX-512

Вот важная новость с фронта ИИ: ManticoreSearch 26 минут назад Как мы ускорили KNN-поиск в Manticore: двухпроходный обход HNSW, пакетная обработка и AVX-512 6 мин 1. 1K Поисковая оптимизация * Поисковые технологии * Open source * Базы данных * Алгоритмы * Кратко: Три изменения в HNSW-поиске ускоряют KNN-поиск до 29% при больших k и дают более 20% прироста при параллельной нагрузке. Без изменений API, без перестроения индексов и без новых настроек — просто более быстрый поиск.

Как мы ускорили KNN-поиск в ManticoreKNN-поиск в Manticore построен поверх hnswlib , открытой реализации HNSW. Исторически большая часть нашей работы над KNN была связана с собственными функциями расстояния, например для бинарной квантизации, а не с основным поисковым циклом hnswlib. Мы также добавили предфильтрацию с ACORN-1 и раннее завершение , но сам цикл оставался прежним: hnswlib по-прежнему обходил соседей, вычислял расстояния и обновлял набор кандидатов.

Технические детали

На этот раз изменения затрагивают сам основной поисковый цикл hnswlib: то, как он обходит соседей, вызывает функции расстояния и работает с иерархией памяти CPU. В сочетании с новыми реализациями функций расстояния под AVX-512 в колонковой библиотеке они убирают три источника накладных расходов: неэффективный доступ к памяти, повторные загрузки данных и косвенные вызовы функций. Специализация функции расстояния на этапе компиляцииРаньше функция расстояния хранилась в HNSW-индексе как указатель на функцию и выбиралась во время выполнения; её вызывали для каждого кандидата.

Когда HNSW приходится проверять много кандидатов, это даёт множество косвенных вызовов на один запрос. Косвенные вызовы мешают компилятору встроить функцию расстояния в поисковый цикл и ухудшают предсказание ветвлений. В новом коде выбор функции расстояния переносится на этап компиляции с помощью шаблонов C++.

В начале поиска один оператор switch выбирает нужную специализацию шаблона по метрике расстояния и настройкам квантизации. После этого весь внутренний цикл — обход соседей, вычисление расстояния и обновление набора кандидатов — выполняется как единая функция с полностью встроенным расчётом расстояния. Благодаря этому компилятор может оптимизировать распределение регистров, планирование инструкций и разворачивание циклов с учётом вычисления расстояния.

Отраслевые последствия

Двухпроходная обработка соседейАлгоритм HNSW обходит граф: посещает узлы и вычисляет расстояния до их соседей. В исходной реализации каждый сосед обрабатывался за один проход: проверить, посещали ли его раньше, загрузить его векторные данные, вычислить расстояние и обновить набор кандидатов. В таком режиме предзагрузка почти не успевала сработать до того, как данные становились нужны.

Новая реализация делит эту работу на два прохода. На первом проходе код перебирает всех соседей текущего узла, пропускает уже посещённых и собирает непосещённых соседей в небольшой массив для пакетной обработки. Для каждого добавленного соседа сразу выдаётся prefetch-инструкция для его векторных данных.

Событие, по словам экспертов, усилит конкуренцию в сфере ИИ.