В эпоху больших данных и искусственного интеллекта эффективность обработки и поиска информации становится ключевым фактором успеха для многих технологий и бизнесов. Одной из фундаментальных задач во многих системах поиска и рекомендательных сервисах является задача поиска приближенных ближайших соседей (Approximate Nearest Neighbor, ANN). Для поиска по бинарным векторам важнейшим компонентом вычислений является подсчёт расстояния Хэмминга — метрики, измеряющей различия на уровне отдельных битов. Оптимизация именно этой операции способна значительно повлиять на общую производительность системы, особенно при обработке миллиардных объемов данных и тысяч запросов в секунду. Недавно компания TopK представила новые подходы к реализации вычисления расстояния Хэмминга с помощью SIMD-инструкций ARM NEON, достигая впечатляющей пропускной способности в 350 ГБ/с.
Расстояние Хэмминга используется для оценки различий между двумя бинарными векторами одинаковой длины, вычисляя количество позиций, в которых значения битов отличаются. В классическом варианте эта операция реализуется через посимвольное XOR и подсчёт количества единичных битов результата. Однако простой перебор и последовательная реализация на языках высокого уровня часто не используют все возможности современных процессоров, особенно их векторные и параллельные инструкции. Исходная реализация в TopK была выполнена на языке Rust, где в цикле по байтам вычислялся XOR и применялся встроенный метод count_ones() для подсчёта единичных битов. Хотя такой код легко читается и работает корректно, его производительность оставляла желать лучшего, особенно в масштабах высоконагруженных систем, где счёт запросов идёт на миллионы в секунду.
Для повышения производительности применены инструкции ARM NEON, предназначенные для SIMD-вычислений, позволяющие обрабатывать 128-битные регистры одновременно. В частности, операции XOR и подсчёт количества единичных битов были заменены на векторные аналоги — veorq_u8 и vcntq_u8, которые работают параллельно над 16 байтами. Кроме того, сумма элементов вектора собиралась горизонтально с помощью vaddvq_u8. Такая трансформация уже в первой итерации предоставила двукратное улучшение скорости в однопоточной среде, а при использовании 10 потоков пропускная способность достигла более 300 гигабайт в секунду. Однако чтобы раскрыть полный потенциал NEON, разработчики решили устранить узкое место, связанное с накоплением результата в одном регистрах, который создавал цепочку зависимостей и снижал параллелизм инструкций (Instruction Level Parallelism, ILP).
В новой версии использовалось два аккумулятора, что фактически позволяло процессору обрабатывать два потока данных независимо, задействовав большее число исполнительных устройств и сократив количество пауз в выполнении команд. Данная оптимизация позволила ещё чуть улучшить производительность, особенно в многоядерных и многопоточных сценариях, повысив эффективность использования системных ресурсов. Это важное достижение, учитывая, что современные смартфоны, серверные ARM-системы и встраиваемые устройства широко используют NEON-инструкции для ускорения мультимедийных, криптографических и машинных вычислений. Следующий этап совершенствования касался особенностей задач с фиксированной размерностью векторов, традиционно применяющихся в поисковых системах и рекомендательных алгоритмах. В TopK размер бинарных векторов варьируется в пределах от 384 до 1536 бит.
Это позволило разработчикам полностью распаковать циклы и реализовать полностью развёрнутые вычислительные ядра без ветвлений и управляющих инструкций, которые обычно уменьшают производительность из-за переключений и контролей потоков. Полное развёртывание цикла позволяет компилятору оптимально разместить регистры, сократить накладные расходы на управление циклами и повысить конвейерность выполнения команд. В итоге реализована версия, которая обрабатывает сразу 1024 бита данных (64 байта) за одну операцию, использует два аккумулятора и выполняет горизонтальное суммирование для подсчёта расстояния Хэмминга без использования дополнительных циклов для оставшихся частей массива. Практические экспериментальные результаты улучшенной реализации показали невероятную скорость — почти 350 гигабайт обработанных данных в секунду при многопоточном использовании и около 63 ГБ/с при однопоточном режиме. Это значение приближается к архитектурным ограничениям современных ARM процессоров с поддержкой NEON и демонстрирует, насколько можно быстро обрабатывать большие объёмы бинарных данных, когда задача грамотно адаптирована под аппаратные возможности.
Такой уровень быстродействия открывает новые возможности для построения высокоэффективных систем поиска и анализа больших массивов информации на устройствах с ARM-архитектурой, включая серверы с энергоэффективными процессорами и мобильные девайсы. Это особенно актуально для приложений, работающих с поиском текстов, изображений, аудиофайлов или видео через векторные представления с бинарным кодированием, что позволяет экономить память и значительно ускорять запросы. Опыт TopK подчёркивает важность глубокой низкоуровневой оптимизации и понимания архитектуры процессора при создании производительных программных решений. Внедрение двух аккумуляторов и развёртывание циклов, использование специализированных SIMD-наборов инструкций помогают извлечь максимальную пользу из аппаратных возможностей. Параллельно это снижает энергопотребление за счёт уменьшения времени работы и повышает общую пропускную способность систем.
Достижение скорости порядка 350 ГБ/с для вычисления расстояния Хэмминга — уникальный показатель, подтверждающий, что даже для таких казалось бы простых операций оптимизация на уровне отдельных инструкций и тщательно продуманная архитектура алгоритма могут радикально улучшить производительность. Это особенно важно в сфере AI, где жёсткие требования к латентности и пропускной способности требуют нестандартных подходов и инноваций. Для специалистов в области компьютерных наук, инженерии и AI-стартапов пример TopK служит вдохновением для поиска эффективных методов оптимизации и демонстрирует возможности ARM-платформ, которые активно развиваются и конкурируют с традиционными x86 системами. В заключение, сочетание эффективных алгоритмов, продвинутых инструкций ARM NEON и техники оптимизации ILP позволяет создавать поисковые движки нового поколения, способные обрабатывать огромные объёмы данных с минимальными задержками. Эти технологии находят применение не только в сфере поиска, но и в обработке мультимедиа, биоинформатике, криптографии и везде, где требуется быстрый и точный анализ бинарных векторов.
Для тех, кто заинтересован в подобных глубоких технических решениях, TopK предлагает ознакомиться с их публикациями, исходным кодом на GitHub и присоединиться к команде разработчиков, чтобы вместе продолжать двигать границы производительности в мире AI и поиска.
