Прежде чем перейти к статье, хочу вам представить, экономическую онлайн игру Brave Knights, в которой вы можете играть и зарабатывать. Регистируйтесь, играйте и зарабатывайте!
Текстовая строка — один из самых распространённых «типов данных» в программировании. Когда программисты думают о строке, то представляют список или массив символов. Это «достаточно хорошее» приближение, но реальность сложнее.
Символы должны быть каким-то образом закодированы в биты. Большинство строк в интернете, включая этот пост на Хабре, закодированы в UTF-8. Формат UTF-8 представляет «символы» в одном, двух, трёх или четырёх байтах. Это обобщение для стандарта ASCII, использующего только один байт на символ. То есть строка ASCII также является строкой UTF-8.
На самом деле всё немного сложнее, потому что технически UTF-8 описывает кодовые точки. Видимый символ типа эмодзи может состоять из нескольких кодовых точек… но большинству программистов эти педантичные формулировки не нужны.
Есть и другие стандарты. Некоторые старые языки программирования, такие как C# и Java, полагаются на UTF-16. Там используется два или четыре байта на символ. В то время это казалось хорошей идеей, но сейчас консенсус движется к использованию UTF-8 всегда и везде.
В большинстве кодировок есть принудительные ограничения. Другими словами, не любая случайная последовательность битов может войти в UTF-8. Таким образом, нужно валидировать строки — проверять, что это действительно UTF-8.
Какое это имеет значение? Большое. Например, в веб-сервере Microsoft есть такая уязвимость: он принимает URI, который кажется действительным и безопасным, но после интерпретации сервером даёт злоумышленнику удалённый доступ к диску. Даже если оставить в стороне вопросы безопасности, вы почти наверняка не захотите сохранять недопустимые строки в своей БД.
Таким образом, языки программирования, веб-серверы, браузеры и движки БД постоянно осуществляют валидацию UTF-8.
Если ваши строки в основном просто ASCII, то проверки выполняются довольно быстро, и проверка UTF-8 не является проблемой. Но уже прошли те дни, когда большинство строк кодировалось в ASCII. Мы живём в мире эмодзи и множества национальных алфавитов.
Ещё в 2018 году я задался вопросом: насколько быстро можно валидировать строки UTF-8? В то время я нашёл вариант валидации в несколько циклов CPU на символ. На этом можно было успокоиться, но меня такой ответ не удовлетворил.
Работа заняла годы, но кажется, теперь мы получили вариант, близкий к идеальному. Новый алгоритм на порядок быстрее, чем другие варианты быстрого поиска. Мы подготовили научную статью: «Валидация UTF-8 менее чем за одну инструкцию на байт» (будет опубликована в журнале Software: Practice and Experience), а также опубликовали утилиту для бенчмаркинга.
Все подробности объясняются в научной статье, так что не будем здесь вдаваться в детали, а только вкратце рассмотрим суть. Основная часть валидации UTF-8 выполняется путём поиска пар последовательных байтов. После проверки всех пар байтов и определения всех возможных нарушений, которые можно найти по этой информации, остаётся сделать относительно немного.
Во всех процессорах есть быстрые инструкции SIMD. Они работают с широкими регистрами (128 бит, 256 бит и т. д.). В большинстве наборов имеется инструкция «векторизованного поиска», которая принимает, скажем, 16-байтовые значения (в диапазоне от 0 до 16) и ищет их в 16-байтовой таблице. В процессорах Intel и AMD этому описанию соответствует инструкция
В нашем алгоритме поиска векторизованная инструкция поиска вызывается три раза: один раз для низкого nibble, один раз для высокого и один раз для высокого nibble следующего байта. У нас три соответствующие 16-байтовые таблицы поиска. Если выбрать их правильно, то побитовое AND из трёх поисков находит любую ошибку.
Подробнее см. в научной статье, но в конечном итоге почти полная валидация UTF-8 выполняется всего пятью строками быстрого кода C++ без каких-либо ветвлений… и эти пять строк за один раз проверяют блоки до 32 байт…
Хотя это сразу не совсем очевидно, но такой валидации достаточно, и она безопасна на 100%. Это действительно так. Остаётся всего несколько недорогих дополнительных технических шагов.
В результате на последних процессорах Intel/AMD требуется чуть меньше одной инструкции на байт для проверки даже самых мусорных, случайных входных данных. Поскольку код исключительно оптимизированный, вы можете выйти на три инструкции за цикл, и даже больше. То есть мы используем небольшую часть цикла (менее трети) на входной байт на современном CPU. Таким образом, скорость обработки надёжно поддерживается на уровне более 12 ГБ/с.
Урок заключается в том, что обычные таблицы поиска полезны, но именно векторизованные таблицы — это фундаментальные строительные блоки для высокоскоростных алгоритмов.
Если вам необходимо использовать функцию быстрой валидации UTF-8 в продакшне, рекомендуем библиотеку simdjson (версия 0.5 или выше). Она хорошо протестирована и имеет полезные встроенные функции, такие как диспетчеризация во время выполнения. Хотя библиотека создана для парсинга JSON, вы можете использовать её чисто для валидации UTF-8, даже если никакого JSON нет. Она поддерживает 64-битные процессоры ARM и x64, а также имеет резервный вариант обработки для других CPU. Мы упаковали её в один заголовочный файл вместе с одним исходным файлом; так что можете просто поместить её в свой проект C++.
Предыдущие работы. Основная заслуга в популяризации метода векторизованной классификации, который является ключом к алгоритму поиска, принадлежит Муле. Насколько мне известно, Кейзер впервые предложил нашу стратегию тройного поиска. Первый практический алгоритм валидации UTF-8 на основе SIMD создал К. Виллетс. Несколько человек, включая З. Вегнера, произвели улучшения в нём. Трэвис Даунс предложил грамотные идеи, как ускорить обычные алгоритмы.
Дальнейшее чтение. Если вам нравится эта работа, то могут понравиться другие статьи на смежные темы: «Кодирование и декодирование Base64 почти со скоростью копирования в памяти» (Software: Practice and Experience, 50 (2), 2020) и «Парсинг гигабайт JSON в секунду» (VLDB Journal, 28 (6), 2019).
Символы должны быть каким-то образом закодированы в биты. Большинство строк в интернете, включая этот пост на Хабре, закодированы в UTF-8. Формат UTF-8 представляет «символы» в одном, двух, трёх или четырёх байтах. Это обобщение для стандарта ASCII, использующего только один байт на символ. То есть строка ASCII также является строкой UTF-8.
На самом деле всё немного сложнее, потому что технически UTF-8 описывает кодовые точки. Видимый символ типа эмодзи может состоять из нескольких кодовых точек… но большинству программистов эти педантичные формулировки не нужны.
Есть и другие стандарты. Некоторые старые языки программирования, такие как C# и Java, полагаются на UTF-16. Там используется два или четыре байта на символ. В то время это казалось хорошей идеей, но сейчас консенсус движется к использованию UTF-8 всегда и везде.
В большинстве кодировок есть принудительные ограничения. Другими словами, не любая случайная последовательность битов может войти в UTF-8. Таким образом, нужно валидировать строки — проверять, что это действительно UTF-8.
Какое это имеет значение? Большое. Например, в веб-сервере Microsoft есть такая уязвимость: он принимает URI, который кажется действительным и безопасным, но после интерпретации сервером даёт злоумышленнику удалённый доступ к диску. Даже если оставить в стороне вопросы безопасности, вы почти наверняка не захотите сохранять недопустимые строки в своей БД.
Таким образом, языки программирования, веб-серверы, браузеры и движки БД постоянно осуществляют валидацию UTF-8.
Если ваши строки в основном просто ASCII, то проверки выполняются довольно быстро, и проверка UTF-8 не является проблемой. Но уже прошли те дни, когда большинство строк кодировалось в ASCII. Мы живём в мире эмодзи и множества национальных алфавитов.
Ещё в 2018 году я задался вопросом: насколько быстро можно валидировать строки UTF-8? В то время я нашёл вариант валидации в несколько циклов CPU на символ. На этом можно было успокоиться, но меня такой ответ не удовлетворил.
Работа заняла годы, но кажется, теперь мы получили вариант, близкий к идеальному. Новый алгоритм на порядок быстрее, чем другие варианты быстрого поиска. Мы подготовили научную статью: «Валидация UTF-8 менее чем за одну инструкцию на байт» (будет опубликована в журнале Software: Practice and Experience), а также опубликовали утилиту для бенчмаркинга.
Все подробности объясняются в научной статье, так что не будем здесь вдаваться в детали, а только вкратце рассмотрим суть. Основная часть валидации UTF-8 выполняется путём поиска пар последовательных байтов. После проверки всех пар байтов и определения всех возможных нарушений, которые можно найти по этой информации, остаётся сделать относительно немного.
Во всех процессорах есть быстрые инструкции SIMD. Они работают с широкими регистрами (128 бит, 256 бит и т. д.). В большинстве наборов имеется инструкция «векторизованного поиска», которая принимает, скажем, 16-байтовые значения (в диапазоне от 0 до 16) и ищет их в 16-байтовой таблице. В процессорах Intel и AMD этому описанию соответствует инструкция
pshufb. Значение в диапазоне от 0 до 16 иногда называют nibble, оно охватывает 4 бита. Байт состоит из двух nibble (низкий и высокий).В нашем алгоритме поиска векторизованная инструкция поиска вызывается три раза: один раз для низкого nibble, один раз для высокого и один раз для высокого nibble следующего байта. У нас три соответствующие 16-байтовые таблицы поиска. Если выбрать их правильно, то побитовое AND из трёх поисков находит любую ошибку.
Подробнее см. в научной статье, но в конечном итоге почти полная валидация UTF-8 выполняется всего пятью строками быстрого кода C++ без каких-либо ветвлений… и эти пять строк за один раз проверяют блоки до 32 байт…
simd8 classify(simd8 input, simd8 previous_input) {
auto prev1 = input.prev<1>(previous_input);
auto byte_1_high = prev1.shift_right <4>().lookup_16(table1);
auto byte_1_low = (prev1 & 0x0F).lookup_16(table2);
auto byte_2_high = input.shift_right <4>().lookup_16(table3);
return (byte_1_high & byte_1_low & byte_2_high);
}Хотя это сразу не совсем очевидно, но такой валидации достаточно, и она безопасна на 100%. Это действительно так. Остаётся всего несколько недорогих дополнительных технических шагов.
В результате на последних процессорах Intel/AMD требуется чуть меньше одной инструкции на байт для проверки даже самых мусорных, случайных входных данных. Поскольку код исключительно оптимизированный, вы можете выйти на три инструкции за цикл, и даже больше. То есть мы используем небольшую часть цикла (менее трети) на входной байт на современном CPU. Таким образом, скорость обработки надёжно поддерживается на уровне более 12 ГБ/с.
Урок заключается в том, что обычные таблицы поиска полезны, но именно векторизованные таблицы — это фундаментальные строительные блоки для высокоскоростных алгоритмов.
Если вам необходимо использовать функцию быстрой валидации UTF-8 в продакшне, рекомендуем библиотеку simdjson (версия 0.5 или выше). Она хорошо протестирована и имеет полезные встроенные функции, такие как диспетчеризация во время выполнения. Хотя библиотека создана для парсинга JSON, вы можете использовать её чисто для валидации UTF-8, даже если никакого JSON нет. Она поддерживает 64-битные процессоры ARM и x64, а также имеет резервный вариант обработки для других CPU. Мы упаковали её в один заголовочный файл вместе с одним исходным файлом; так что можете просто поместить её в свой проект C++.
Предыдущие работы. Основная заслуга в популяризации метода векторизованной классификации, который является ключом к алгоритму поиска, принадлежит Муле. Насколько мне известно, Кейзер впервые предложил нашу стратегию тройного поиска. Первый практический алгоритм валидации UTF-8 на основе SIMD создал К. Виллетс. Несколько человек, включая З. Вегнера, произвели улучшения в нём. Трэвис Даунс предложил грамотные идеи, как ускорить обычные алгоритмы.
Дальнейшее чтение. Если вам нравится эта работа, то могут понравиться другие статьи на смежные темы: «Кодирование и декодирование Base64 почти со скоростью копирования в памяти» (Software: Practice and Experience, 50 (2), 2020) и «Парсинг гигабайт JSON в секунду» (VLDB Journal, 28 (6), 2019).
