golang

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

  • вторник, 1 июля 2025 г. в 00:00:09
https://habr.com/ru/articles/923242/

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 можно детектировать, анализируя только первые два байта каждой последовательности.

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

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

Алгоритм базируется на теории конечных автоматов и битовых масках. Каждая комбинация двух соседних байтов может быть классифицирована в одну из 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):

Stdlib

27.78 ns/op

1079.80 MB/s

charcoal

14.88 ns/op

2036.79 MB/s

SIMD

5.922 ns/op

5065.75 MB/s (4.7x быстрее stdlib)

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

Stdlib

893.5 ns/op

1146.01 MB/s

charcoal

421.7 ns/op

2428.44 MB/s

SIMD

106.2 ns/op

9641.60 MB/s (8.4x быстрее stdlib)

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

Stdlib

916612 ns/op

1143.97 MB/s

charcoal

416901 ns/op

2515.17 MB/s

SIMD

102415 ns/op

10238.46 MB/s (9.0x быстрее stdlib)

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

Размер данных

Stdlib (MB/s)

charcoal (MB/s)

SIMD (MB/s)

Ускорение SIMD/Stdlib

4 КБ

1280.09

1645.04

10030.39

7.8x

32 КБ

1283.78

1658.71

10239.46

8.0x

64 КБ

1282.96

1660.01

10260.09

8.0x

256 КБ

1253.47

1646.61

10268.56

8.2x

4 МБ

1218.62

1609.69

10262.59

8.4x

32 МБ

1248.65

1648.06

10233.27

8.2x

128 МБ

1244.03

1624.76

10220.27

8.2x

256 МБ

1250.01

1644.33

9319.34

7.5x

абсолютная производительность: >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