Ускоряем валидацию UTF-8 в 10 раз (>10 ГБ/с): реализация алгоритма Lemire-Keiser на Go с ARM NEON

UTF-8 валидация — одна из базовых операций при работе с текстом, которая выполняется миллионы раз в секунду в современных приложениях. Стандартная реализация в Go, хоть и корректная, далека от оптимальной по производительности. В этой статье расскажу, как мне удалось ускорить валидацию UTF-8 в 10 раз, используя SIMD‑инструкции ARM NEON и алгоритм из статьи «Validating UTF-8 In Less Than One Instruction Per Byte» Джона Кейзера и Дэниела Лемира.

Проблема стандартной валидации

Стандартная реализация utf8.Valid() в Go имеет несколько фундаментальных ограничений:

• Множественные условные переходы

• Последовательная обработка

• Кэш-промахи lookup таблиц

• Избыточные проверки границ

Измерения производительности stdlib показывают:

• На тестовых данных 4 КБ — 256 МБ: ~1.2-1.3 ГБ/с

• Производительность стабильна независимо от размера данных

• Основное ограничение: последовательная обработка и branch misprediction

• На больших объемах (256 МБ): небольшая деградация до ~1.25 ГБ/с

Эти результаты показывают, что стандартная реализация далека от теоретического предела пропускной способности памяти, оставляя значительное пространство для оптимизации

Алгоритм Lemire-Keiser

Концептуальная основа

Алгоритм Lemire-Keiser представляет радикально новый подход к валидации UTF-8, основанный на векторизованной классификации и принципе «проверки без ветвлений». Ключевая идея заключается в том, что практически все ошибки UTF-8 можно детектировать, анализируя только первые два байта каждой последовательности.

Статьи подробно расматривабшие алгоритм:

• Валидация UTF-8 меньше чем за одну инструкцию на байт

• Ridiculously fast unicode (UTF-8) validation

Математическая основа

Алгоритм базируется на теории конечных автоматов и битовых масках. Каждая комбинация двух соседних байтов может быть классифицирована в одну из 12 категорий:

1. ASCII (00000000…01111111)

2. Continuation Low (10|000000…001111)

3. Continuation (10|010000…001111)

4. Continuation High (10|100000…111111)

5. 2-Byte Start (110|00010…11111)

6. 3-Byte Start Low (1110|0000)

7. 3-Byte Start (1110|0001…1100, 1110|1110…1111)

8. 3-Byte Surrogate (1110|1101)

9. 4-Byte Start Low (11110|000)

10. 4-Byte Start (11110|001…011)

11. 4-Byte Start High (11110|100)

12. Invalid (все остальные)

Lookup таблицы реализуют функцию классификации f: {0..255} → {0..255}, где результат кодирует битовую маску принадлежности к различным категориям ошибок.

Моя реализация на Go с ARM NEON

//go:build !purego  #include "textflag.h"  // func validateNEON(p []byte) bool // Функция валидации UTF-8 строки с использованием ARM64 NEON SIMD инструкций TEXT ·Valid(SB),NOSPLIT,$0-25     // Загружаем параметры функции из стека     MOVD    s_base+0(FP), R10      // Указатель на начало строки в R10     MOVD    s_len+8(FP), R11       // Длина строки в R11     CBZ     R11, valid             // Если длина = 0, строка валидна     CMP     $16, R11                    BLT     small                  // Если длина < 16 байт, обрабатываем отдельно      // Инициализация маски для проверки ASCII символов (бит 7 = 1 означает не-ASCII)     VMOVQ   $0x8080808080808080, $0x8080808080808080, V0  ascii_loop:     // Быстрая проверка на ASCII символы (оптимизация для чисто ASCII строк)     CMP     $16, R11     BLT     small                  // Если осталось < 16 байт, переходим к обработке остатка      VLD1    (R10), [V1.B16]        // Загружаем 16 байт в SIMD регистр V1     VCMTST  V1.B16, V0.B16, V2.B16 // Тестируем биты 0x80 (проверка на не-ASCII)     VMOV    V2.D[0], R2            // Перемещаем результат в скалярные регистры     VMOV    V2.D[1], R3     ORR     R2, R3, R2             // Объединяем результаты     CBNZ    R2, stop_ascii         // Если найден не-ASCII символ, прекращаем ASCII цикл      ADD     $16, R10               // Переходим к следующему блоку     SUB     $16, R11               // Уменьшаем счетчик оставшихся байт     B       ascii_loop             // Продолжаем ASCII цикл  stop_ascii:     // Инициализация констант для алгоритма Мулы (Lemire) валидации UTF-8     // Эти константы используются в lookup таблицах для быстрой валидации UTF-8     VMOVQ   $0x0202020202020202, $0x4915012180808080, V11  // Lookup таблица 1     VMOVQ   $0xcbcbcb8b8383a3e7, $0xcbcbdbcbcbcbcbcb, V13  // Lookup таблица 2       VMOVQ   $0x0101010101010101, $0x01010101babaaee6, V15  // Lookup таблица 3     VMOVQ   $0x0F0F0F0F0F0F0F0F, $0x0F0F0F0F0F0F0F0F, V18  // Маска для младших 4 бит     VMOVQ   $0x0707070707070707, $0x0707070707070707, V12  // Маска 0x07     VMOVQ   $0xFFFFFFFFFFFFFFFF, $0xFFFFFFFFFFFFFFFF, V14  // Маска всех единиц     VMOVQ   $0x7F7F7F7F7F7F7F7F, $0x7F7F7F7F7F7F7F7F, V16  // Маска 0x7F     VMOVQ   $0xDFDFDFDFDFDFDFDF, $0xDFDFDFDFDFDFDFDF, V17  // Маска 0xDF     VMOVQ   $0x0808080808080808, $0x0808080808080808, V19  // Маска 0x08     VMOVQ   $0x8080808080808080, $0x8080808080808080, V20  // Маска 0x80     VMOVQ   $0x0000000000000000, $0x0000000000000000, V30  // Нулевой вектор     VMOVQ   $0x0000000000000000, $0x0000000000000000, V3   // Предыдущий блок данных  aligned_loop:     // Основной цикл валидации UTF-8 с использованием алгоритма Мулы     VLD1.P  16(R10), [V4.B16]      // Загружаем 16 байт и увеличиваем указатель          // Сдвигаем данные для анализа переходов между байтами     VEXT    $15, V4.B16, V3.B16, V5.B16  // Берем последний байт предыдущего блока + текущий     VUSHR   $4, V5.B16, V6.B16     // Сдвигаем на 4 бита вправо (старшие 4 бита)     VTBL    V6.B16, [V11.B16], V6.B16    // Lookup в первой таблице     VAND    V5.B16, V18.B16, V7.B16      // Выделяем младшие 4 бита     VTBL    V7.B16, [V13.B16], V7.B16    // Lookup во второй таблице     VUSHR   $4, V4.B16, V8.B16     // Старшие 4 бита текущего блока     VTBL    V8.B16, [V15.B16], V8.B16    // Lookup в третьей таблице          // Комбинируем результаты lookup'ов     VAND    V6.B16, V7.B16, V9.B16     VAND    V9.B16, V8.B16, V10.B16          // Дополнительные проверки для специальных случаев UTF-8     VEXT    $14, V4.B16, V3.B16, V5.B16  // Проверка на позиции -2     VUSHR   $5, V5.B16, V6.B16     // Сдвиг на 5 бит для проверки старших битов     VCMEQ   V12.B16, V6.B16, V6.B16      // Сравнение с 0x07          VEXT    $13, V4.B16, V3.B16, V5.B16  // Проверка на позиции -3     VUSHR   $4, V5.B16, V9.B16     // Сдвиг на 4 бита     VCMEQ   V18.B16, V9.B16, V9.B16      // Сравнение с 0x0F     VORR    V6.B16, V9.B16, V9.B16       // Объединение результатов          // Финальная проверка валидности     VAND    V9.B16, V20.B16, V9.B16      // Применяем маску 0x80     VSUB    V9.B16, V10.B16, V9.B16      // Вычитаем из основного результата     VMOV    V9.D[0], R1            // Перемещаем результат в скалярные регистры     VMOV    V9.D[1], R2     ORR     R1, R2, R1             // Объединяем половины результата     CBNZ    R1, no_valid           // Если результат не ноль, строка невалидна          VMOV    V4.B16, V3.B16         // Сохраняем текущий блок как предыдущий     SUB     $16, R11, R11          // Уменьшаем счетчик оставшихся байт     CMP     $16, R11                     BGE     aligned_loop           // Если осталось >= 16 байт, продолжаем цикл      B small_no_const               // Переходим к обработке остатка  small:     // Обработка небольших строк (< 16 байт)     CBZ     R11, valid             // Если байт не осталось, строка валидна  tail_loop:     // Простая проверка по одному байту для маленьких строк     MOVBU   (R10), R2              // Загружаем один байт     AND     $0x80, R2              // Проверяем старший бит     CBNZ    R2, check_utf8         // Если установлен, нужна полная проверка UTF-8     ADD     $1, R10                // Переходим к следующему байту     SUB     $1, R11                // Уменьшаем счетчик     CBNZ    R11, tail_loop         // Продолжаем пока есть байты     B       valid                  // Все байты ASCII - строка валидна  check_utf8:     // Инициализация констант для полной проверки UTF-8     // (те же константы, что и выше)     VMOVQ   $0x0202020202020202, $0x4915012180808080, V11     VMOVQ   $0xcbcbcb8b8383a3e7, $0xcbcbdbcbcbcbcbcb, V13     VMOVQ   $0x0101010101010101, $0x01010101babaaee6, V15     VMOVQ   $0x0F0F0F0F0F0F0F0F, $0x0F0F0F0F0F0F0F0F, V18     VMOVQ   $0x0707070707070707, $0x0707070707070707, V12     VMOVQ   $0xFFFFFFFFFFFFFFFF, $0xFFFFFFFFFFFFFFFF, V14     VMOVQ   $0x7F7F7F7F7F7F7F7F, $0x7F7F7F7F7F7F7F7F, V16     VMOVQ   $0xDFDFDFDFDFDFDFDF, $0xDFDFDFDFDFDFDFDF, V17     VMOVQ   $0x0808080808080808, $0x0808080808080808, V19     VMOVQ   $0x8080808080808080, $0x8080808080808080, V20     VMOVQ   $0x0000000000000000, $0x0000000000000000, V30     VMOVQ   $0x0000000000000000, $0x0000000000000000, V3  small_no_const:     // Подготовка данных для обработки остатка < 16 байт     SUB $16, R10, R10              // Откатываемся на 16 байт назад     ADD R11, R10, R10              // Добавляем количество оставшихся байт     VLD1.P  16(R10), [V4.B16]      // Загружаем 16 байт (включая "мусор")      // Использование таблицы переходов для маскирования лишних байт     ADR  shift_table, R2           // Адрес таблицы переходов     MOVW R11, R3                   // Количество валидных байт     LSL $2,  R3                    // Умножаем на 4 (размер инструкции)     ADD R3, R2                     // Вычисляем адрес перехода     B (R2)                         // Переходим к соответствующему обработчику  shift_table:     // Таблица переходов для обработки 0-15 байт     B do_shift_0                   // 0 байт - заполняем ASCII символами     B do_shift_1                   // 1 байт валидный     B do_shift_2                   // 2 байта валидных     B do_shift_3                   // 3 байта валидных     B do_shift_4                   // 4 байта валидных     B do_shift_5                   // 5 байт валидных     B do_shift_6                   // 6 байт валидных     B do_shift_7                   // 7 байт валидных     B do_shift_8                   // 8 байт валидных     B do_shift_9                   // 9 байт валидных     B do_shift_10                  // 10 байт валидных     B do_shift_11                  // 11 байт валидных     B do_shift_12                  // 12 байт валидных     B do_shift_13                  // 13 байт валидных     B do_shift_14                  // 14 байт валидных     B do_shift_15                  // 15 байт валидных  do_shift_0:     // 0 валидных байт - заполняем вектор ASCII символами 'a' (0x61)     VMOVQ   $0x6161616161616161, $0x6161616161616161, V4     B end_swith do_shift_1:     // 1 валидный байт - сдвигаем на 15 позиций (маскируем 15 байт)     VEXT    $15, V30.B16, V4.B16, V4.B16     B end_swith do_shift_2:     // 2 валидных байта - сдвигаем на 14 позиций     VEXT    $14, V30.B16, V4.B16, V4.B16     B end_swith do_shift_3:     // 3 валидных байта - сдвигаем на 13 позиций     VEXT    $13, V30.B16, V4.B16, V4.B16     B end_swith do_shift_4:     // 4 валидных байта - сдвигаем на 12 позиций     VEXT    $12, V30.B16, V4.B16, V4.B16     B end_swith do_shift_5:     // 5 валидных байт - сдвигаем на 11 позиций     VEXT    $11, V30.B16, V4.B16, V4.B16     B end_swith do_shift_6:     // 6 валидных байт - сдвигаем на 10 позиций     VEXT    $10, V30.B16, V4.B16, V4.B16     B end_swith do_shift_7:     // 7 валидных байт - сдвигаем на 9 позиций     VEXT    $9, V30.B16, V4.B16, V4.B16     B end_swith do_shift_8:     // 8 валидных байт - сдвигаем на 8 позиций     VEXT    $8, V30.B16, V4.B16, V4.B16     B end_swith do_shift_9:     // 9 валидных байт - сдвигаем на 7 позиций     VEXT    $7, V30.B16, V4.B16, V4.B16     B end_swith do_shift_10:     // 10 валидных байт - сдвигаем на 6 позиций     VEXT    $6, V30.B16, V4.B16, V4.B16     B end_swith do_shift_11:     // 11 валидных байт - сдвигаем на 5 позиций     VEXT    $5, V30.B16, V4.B16, V4.B16     B end_swith do_shift_12:     // 12 валидных байт - сдвигаем на 4 позиции     VEXT    $4, V30.B16, V4.B16, V4.B16     B end_swith do_shift_13:     // 13 валидных байт - сдвигаем на 3 позиции     VEXT    $3, V30.B16, V4.B16, V4.B16     B end_swith do_shift_14:     // 14 валидных байт - сдвигаем на 2 позиции     VEXT    $2, V30.B16, V4.B16, V4.B16     B end_swith do_shift_15:     // 15 валидных байт - сдвигаем на 1 позицию     VEXT    $1, V30.B16, V4.B16, V4.B16     B end_swith  end_swith:     // Выполняем ту же валидацию UTF-8, что и в основном цикле     VEXT    $15, V4.B16, V3.B16, V5.B16   // Анализ переходов между байтами     VUSHR   $4, V5.B16, V6.B16            // Старшие 4 бита     VTBL    V6.B16, [V11.B16], V6.B16     // Lookup таблица 1     VAND    V5.B16, V18.B16, V7.B16       // Младшие 4 бита     VTBL    V7.B16, [V13.B16], V7.B16     // Lookup таблица 2     VUSHR   $4, V4.B16, V8.B16            // Старшие 4 бита текущих байт     VTBL    V8.B16, [V15.B16], V8.B16     // Lookup таблица 3     VAND    V6.B16, V7.B16, V9.B16        // Комбинирование результатов     VAND    V9.B16, V8.B16, V10.B16      // Дополнительные проверки     VEXT    $14, V4.B16, V3.B16, V5.B16   // Проверка позиции -2     VUSHR   $5, V5.B16, V6.B16     VCMEQ   V12.B16, V6.B16, V6.B16      VEXT    $13, V4.B16, V3.B16, V5.B16   // Проверка позиции -3     VUSHR   $4, V5.B16, V9.B16     VCMEQ   V18.B16, V9.B16, V9.B16     VORR    V6.B16, V9.B16, V9.B16      // Финальная валидация     VAND    V9.B16, V20.B16, V9.B16     VSUB    V9.B16, V10.B16, V9.B16     VMOV    V9.D[0], R1                   // Получаем результат     VMOV    V9.D[1], R2     ORR     R1, R2, R1     CBNZ    R1, no_valid                  // Если не ноль, строка невалидна  valid:     // Строка валидна - возвращаем true (1)     MOVD    $1, R0     MOVD    R0, ret+24(FP)     RET  no_valid:     // Строка невалидна - возвращаем false (0)     MOVD    $0, R0     MOVD    R0, ret+24(FP)     RET 

Результаты бенчмарков

Тестовая платформа

• Процессор: Apple M1 Pro (ARM64)

• Операционная система: macOS (darwin)

• Go версия: 1.24.4

Сравниваемые реализации:

• Stdlib — стандартная utf8.Valid() из Go

• charcoal — оптимизированная библиотека без SIMD

• SIMD — моя реализация с ARM NEON

Малые строки (10 байт)

Японский текст (UTF-8):

Средние файлы (1 КБ)

Большие файлы (1 МБ)

Детальное сравнение по размерам данных

абсолютная производительность: >10 ГБ/с приближается к пределам пропускной способности памяти DDR4

Практическое применение

Библиотека особенно эффективна для:

• JSON-парсеров: валидация больших JSON-документов

• Баз данных: валидация при вставке текстовых данных

Rust simdutf8::basic::from_utf8

Стоит отметить, что библиотека simdutf8 для Rust, показывает аналогичные результаты производительности на ARM64 платформах:

На больших данных (>1 МБ)**: ~10 ГБ/с

Перспективы развития:

— Портирование на x86-64 с использованием AVX2/AVX-512

Исходный код доступен на GitHub: https://github.com/AndreyyTs/utf8simd