[C++, Алгоритмы, Программирование, Процессоры, Разработка веб-сайтов] Исключительно быстрая валидация UTF-8 (перевод)
Автор
Сообщение
news_bot ®
Стаж: 6 лет 9 месяцев
Сообщений: 27286
Текстовая строка — один из самых распространённых «типов данных» в программировании. Когда программисты думают о строке, то представляют список или массив символов. Это «достаточно хорошее» приближение, но реальность сложнее.
Символы должны быть каким-то образом закодированы в биты. Большинство строк в интернете, включая этот пост на Хабре, закодированы в 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).
===========
Источник:
habr.com
===========
===========
Автор оригинала: Daniel Lemire
===========Похожие новости:
- [IT-инфраструктура, IT-стандарты, Проектирование и рефакторинг, Процессоры, Управление проектами] Организация рабочего процесса в команде на IT проекте
- [Программирование] LDM. Моя любимая инструкция ARM (перевод)
- [Высокая производительность, Процессоры, Суперкомпьютеры] AMD поставит 200 тысяч ядер для самого мощного суперкомпьютера Австралии
- [Тестирование IT-систем, Программирование, TDD] С чего начинаются тесты
- [JavaScript, Программирование] Из каталога NPM удалили четыре зловредных пакета
- [Информационная безопасность, Разработка веб-сайтов, Habr, Разработка под Linux] Секретная информация? Используй 2FA для VPS/VDS
- [Программирование, Совершенный код, C++, Rust, История IT] Интереснейшее влияние Cyclone (перевод)
- [Laravel, PHP, Symfony, Разработка веб-сайтов] Месяц до релиза PHP8. А на какой версии ты в основном сидишь сейчас?
- [Алгоритмы, Звук] Погружение в алгебру глубоких басов: прекрасные звуки музыкального программирования (перевод)
- [PHP, Программирование, Яндекс API] Эволюция PHP — от 5.6 до 8.0 (Часть 1) (перевод)
Теги для поиска: #_c++, #_algoritmy (Алгоритмы), #_programmirovanie (Программирование), #_protsessory (Процессоры), #_razrabotka_vebsajtov (Разработка веб-сайтов), #_junikod (Юникод), #_utf8, #_utf16, #_ascii, #_validatsija (валидация), #_simd, #_pshufb, #_c++, #_bystryj_kod (быстрый код), #_algoritm_poiska (алгоритм поиска), #_simdjson, #_c++, #_algoritmy (
Алгоритмы
), #_programmirovanie (
Программирование
), #_protsessory (
Процессоры
), #_razrabotka_vebsajtov (
Разработка веб-сайтов
)
Вы не можете начинать темы
Вы не можете отвечать на сообщения
Вы не можете редактировать свои сообщения
Вы не можете удалять свои сообщения
Вы не можете голосовать в опросах
Вы не можете прикреплять файлы к сообщениям
Вы не можете скачивать файлы
Текущее время: 22-Ноя 20:42
Часовой пояс: UTC + 5
| Автор | Сообщение |
|---|---|
|
news_bot ®
Стаж: 6 лет 9 месяцев |
|
|
Текстовая строка — один из самых распространённых «типов данных» в программировании. Когда программисты думают о строке, то представляют список или массив символов. Это «достаточно хорошее» приближение, но реальность сложнее. Символы должны быть каким-то образом закодированы в биты. Большинство строк в интернете, включая этот пост на Хабре, закодированы в 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). =========== Источник: habr.com =========== =========== Автор оригинала: Daniel Lemire ===========Похожие новости:
Алгоритмы ), #_programmirovanie ( Программирование ), #_protsessory ( Процессоры ), #_razrabotka_vebsajtov ( Разработка веб-сайтов ) |
|
Вы не можете начинать темы
Вы не можете отвечать на сообщения
Вы не можете редактировать свои сообщения
Вы не можете удалять свои сообщения
Вы не можете голосовать в опросах
Вы не можете прикреплять файлы к сообщениям
Вы не можете скачивать файлы
Вы не можете отвечать на сообщения
Вы не можете редактировать свои сообщения
Вы не можете удалять свои сообщения
Вы не можете голосовать в опросах
Вы не можете прикреплять файлы к сообщениям
Вы не можете скачивать файлы
Текущее время: 22-Ноя 20:42
Часовой пояс: UTC + 5