UTF-8: быстрые регулярные выражения в PHP

Утром я написал пост о производительности различных движков регулярных выражений, а весь день перебирал разные варианты, смотрел подробности и так далее.

Как я уже писал, мне понравилась библиотека RE2, я даже скомпилировал её и посмотрел, к сожалению, оказалось, что она использует треды, а в PHP с этим не очень (не все модули PHP thread safe, поэтому чаще всего PHP собирается без поддержки тредов).

Я уже начал смотреть другие библиотеки, когда Алексей Захлестин напомнил мне про модуль PHP Multibyte String (функции mb_*), который содержит в себе движок регулярных выражений Oniguruma.

Я всегда плохо относился к этому движку, так как считал, что у него очень бедные возможности для работы с UTF-8, так как там не работают \p, \P и есть ещё пара недостатков (возможно они имеют место из-за того, что в PHP используется версия 4.7.1, тогда как последняя 5.9.2).

Сегодня я присмотрелся к движку получше. Конечно, PCRE он не заменит, но некоторых случаях вполне сможет его подменить как быстрый аналог, только надо применять несколько правил (речь идёт о версии 4.7.1, которая в PHP):

Во-первых, модификатор „i“ не действует ни на какие буквы, кроме латинских, я перебрал весь Unicode, чтобы в этом убедиться.

Во-вторых, \b и \B внутри […] относятся к backspace, а не к word boundary, а \h и \H к hex digit, а не к horizontal whitespace.

В-третьих, не работают \p и \P, зато (хоть какая-то замена) с UTF-8 работают [[:…:]] (всякие там [[:space:]] и прочие).

В-четвёртых, есть синтаксис [a-w&&[^c-g]z], то есть «&» надо экранировать внутри диапазонов.

В-пятых, части синтаксиса PCRE просто нет, например, нет рекурсии, условных регулярок, но тут уже надо обращаться к документации.

Я погонял тесты, сравнивал PCRE в режиме полном UTF-8 (с «глаголом» UCP) и Oniguruma, по результатам последний в 4…4,5 раза быстрее:
bolk-dev ~/regexp-benchmark $ php test.php
PCRE Full UTF-8: 1.0458080768585
Oniguruma:         0.24942803382874
12 комментариев
22 декабря 2010 21:43

UTF-8: как быстрее получить длину строки

Как я уже писал, сегодня ночью я наткнулся на вариант измерения длины UTF-8 строки, написанный с применением ассемблерных иструкций SSE2. У этого кода есть недостаток — на каких-нибудь ARM он не заработает, с другой стороны, у меня нет такой потребности, запускать PHP на этих процессорах.

Сегодня я почистил код (в PHP известна бинарная длина строки, поэтому я убрал проверки на символ с кодом ноль и соптимизировал код), сгенерировал таблицу HammingWeight, которая отсутствует в коде автора и перевёл проверку в двух крайних циклах на подобную таблицу.

Потом это всё скомпилировал и погонял тесты.

Сначала я получил очень странные результаты и только потом понял что случилось. В общем, разрыв в скорости функций (mb_strlen и той, что на SSE2) тем больше, чем ближе тестируемая строка к однобайтовой. Чаще всего, с SSE2 быстрее встроенной в PHP в 5—8 раз:
thasonic-dev ~/uni/futf-0.1 $ php ../test/test_strlen.php | sort -k2 -t:
SSE2 UTF-8:                 0.025604963302612
mb_strlen:                   0.15917205810547
strlen/utf8_decode:   0.62052989006042
Что совсем странно, прежнего впечатляющего результата с прежними данными и функциями я получить не смог, правда, есть подозрение, что за ночь сменилось оборудование (были аппаратные проблемы на машине) на сервере, где я производил замеры.

В общем, о приросте в 24 раза остаётся только мечтать.

Похоже, это почти предел на сегодняшний момент. Единственная возможность ускорения, которая приходит в голову — использовать GPU на видеокарте. Например, видеокарта GTX275 управляется с 16000 потоков (!), что позволяет подсчитать длину строки порциями по 15,5КБ!

Но это больше из разряда задач-головоломок, чем чего-то практического — у нас на серверах таких видеокарт нет и вряд ли появятся, пока интерпретаторы-флагманы не заявят у себя поддержку GPU.

Так что оставлю как есть, займусь переписываем substr в SSE2, а потом выложу всё в открытый доступ.

Добавлено позднее: в следующем году Intel и AMD выпустят процессоры, поддерживающие набор комманд AVX, интересно там то, что размер регистров SIMD (которые используются и в SSE) расширяется до 256 бит. То есть через годик-другой можно будет читать строку сразу по 32 байта за раз.
Комментировать
21 декабря 2010 16:22

UTF-8: как быстро получить подстроку (+новый вариант strlen)

Из кода быстрой функции strlen для UTF-8 можно получить функцию substr. Николай Захаров, который работает со мной в группе внутренних сервисов, переделал strlen в substr.

Я вкомпилил эту функцию в PHP, помог найти ошибки и отладить и сделал замеры:
bolk-dev ~/uni/futf-0.1 $ php ../test/test_substr.php  | sort -k2 -t:
Fast UTF-8: 0.18010711669922
mb_substr:  0.87068700790405
Разница примерно в 4 раза. Я ещё попробовал отрезать строку через функцию preg_match, сравнимо по скорости с mb_substr, но медленнее и есть ограничение — квантификатор preg_match не захватывает больше 65535 символов.

Добавлено позднее: после того как мы отладили эту функцию, я вспомнил про команды ассемблера SSE — это наборы команд (сейчас их пять — SSE1, 2, 3, 4.1 и 4.2), которые оперируют восемью регистрами размером 128 бит.

Как я рассказывал, самый быстрый алгоритм для strlen, который я нашёл, работает следующим образом: сначала указатель на строку первым циклом выравнивается по границе 4 или 8 байт (в зависимости от архитектуры процессора), чтобы процессор смог быстрее читать дальше, потом, работая сразу с числом длиной 4 или 8 байт, одной операцией подсчитывается сколько в выделенной строке содержится начальных байт символов.

Если внутри нашего рабочего участка встречается символ с кодом ноль (признак конца строки), то происходит выход в последний цикл, который занимается тем, что просматривает побайтно получившийся «хвост».

128-битные регистры, соотвественно, позволяют читать участки сразу по 16 бит, что должно дать солидную экономию на длинных текстах. Хороши они ещё и тем, что многие операции позволяют работать с регистром, как с набором байт, производя групповые операции над каждым байтом в регистре.

Час назад я поставил себе gcc под Windows и стал потихоньку писать примерный код, читать документацию, изучать команды в интернете, пока совершенно случайно не наткнулся на уже готовый вариант, написанный с применением инструкций SSE2.

Нашёл в интернете тест для таких функций, включил туда найденную и сделал замеры:
C:\MinGW\bin\test.exe
cp_strlen_utf8:          0.105706
cp_strlen_utf8_sse2: 0.030002
В 3,5 раза обгоняет предыдущий вариант, то есть, смею надеяться, обгонит встроенную в PHP функцию примерно в 24 раза. Завтра попробую.

Немаловажно, что даже на машинах с архитектурой 32 бита рассматриваемый вариант покажет ту же скорость, что и на машинах 64 бита.
11 комментариев
21 декабря 2010 00:31

Судьба PHP6

Поговорил с одним из разработчиков PHP по поводу судьбы PHP6, самое ожидаемое изменение которого — переход на юникодные строки. Так вот Антон Довгаль рассказал, что проект, по сути, заброшен. Те несколько человек, которые занимались проектом, либо уволились, либо потеряли к нему интерес и сейчас считается, что поддержка юникодных строк в языке не так уж и нужна.

На примере своего опыта разработки и перевода проектов на PHP на UTF-8, скажу это не так. В Пайтоне, где таких проблем нет, работать гораздо проще и приятнее.

То, что в PHP приходится для поддержки Юникода работать с UTF-8, а не с UTF-32 сильно снижает производительность всех строковых операций. И добро бы, если бы для всех функций были юникодные аналоги, так это ведь не так.

Работать в PHP с UTF-32 нельзя, если вы собираетесь использовать регулярные выражения: библиотека PCRE, предназначенная для работы с регулярными выражениями, понимает только две кодировки: latin-1 (по всей видимости) и UTF-8. Кроме того, функции, использующие локаль или ICU так же работают только с UTF-8.

Если бы этот язык нативно поддерживал UTF-32… Мечты-мечты.
15 комментариев
16 декабря 2010 17:34

UTF-8: как быстрее измерить длину строки в PHP

Я потихоньку буду писать как получается оптимизировать самые важные функции работы с UTF-8 в PHP. Оформлять буду как продолжение своей эпопеи перевода наше внутренней «Вики» на UTF-8 (в ближайшее время добавлю оглавление).

Сейчас, после перевода «Вики» мы столкнулись с тем, что некоторые операции занимают непозволительно много времени. Кое-какие проблемы решаются моими итераторами для строки (прямым и обратным), но и другие оптимизации приходится делать.

Простые оптимизации я уже применил: выкинул из класса UTF-8 проверки на self::ON (по этой константе я определял включена ли в проекте поддержка UTF-8, сейчас в ней необходимости уже нет) и сделал другие микрооптимизации, теперь пора посмотреть на методы моего класса UTF.

Одна из самых частоиспользуемых функций — strlen, которая определяет длину строки. Я всегда считал, что самый быстрый способ подсчитать длину UTF-строки в PHP, это вызывать strlen(utf8_decode(…)).

Мои тесты показывают что это не так. Самый быстрый способ (по крайней мере в PHP 5.3.2) — это mb_strlen, strlen/utf8_decode — на втором месте, потом идёт sizeof+preg_split, а самый медленный — iconv_strlen.

Для интереса я вкомпилил в PHP функцию для быстрого подсчёта длины строки в UTF-8, найденную в интернете, выигрыш по сравнению с mb_strlen незначителен:
bolk-dev ~/uni/ $ php ../test/test_strlen.php | sort -k2 -t:
Fast UTF-8: 0.68232107162476
mb_strlen: 0.88710689544678
strlen/utf8_decode: 1.5211808681488
Это тысяча итераций на файле в 400КБ.

Я оставил функцию mb_strlen.

Добавлено позднее: другая быстрая функция дала ещё худший результат: 0,79, против прежнего варианта в 0,68.

Добавлено ещё позже: а вот третья функция показала действительно впечатляющие результаты:
bolk-dev ~/uni/ $ php ../test/test_strlen.php | sort -k2 -t:
More Fast UTF-8:  0.12948799133301
mb_strlen: 0.88710689544678
strlen/utf8_decode: 1.5211808681488
Это уже дело — она почти в 7 раз быстрее лучшего результата PHP.

Вкратце, алгоритм такой: строка циклом выравнивается по границе четырёх (на 64-битных системах — 8) байт, далее читается сразу по четыре (или восемь) байт и внутри каждого кусочка одним выражением считается сколько там байт, с которых начинается символ. Поэтому на моей 64-битной системе семикратный выигрыш (на 32 битах будет примерно в три раза).

Добавлено через несколько дней: есть и ещё более быстрая функция.
16 комментариев
16 декабря 2010 15:45

PHP, UTF-8: восьмой этап, заключительный

Прошло уже немало времени, с тех пор как я описал предыдущий этап перевода на UTF-8 нашей внутренней Вики. Этот этап заключительный, после него пришлось поправить несколько шероховатостей и сегодня с него, так сказать, сняли строительные леса.

Что же дальше?
6 комментариев
30 ноября 2010 23:50

PHP, UTF-8: седьмой этап, давайте что-нибудь сделаем с регулярными выражениями

В прошлый раз я рассматривал, по сути, самый сложный этап — замену всех вхождений $var[$index] и им подобных на вызов моей функции. В процессе замены я несколько раз корректировал заметку и доводил некоторые вещи руками.

Что же дальше?
3 комментария
11 ноября 2010 00:14

PHP, UTF-8: шестой этап, она же «строки, часть II». Заменяем

В прошлой части я пытался упростить себе задачу, посчитав сколько различных видов операций получения символа из строки по индексу есть у нас в коде. Но для того, чтобы подсчитать эти ситуации, нужен парсер, который эти случаи выделит.

Угу, и?
4 комментария
22 октября 2010 23:15

PHP, UTF-8, всё ещё строки: упрощаем задачу, часть I

Итак, я достаточно долго думал над задачей как мне заменить все операции получения символа из строки по индексу, чтобы понять насколько она сложна. Решить её можно, но скучно и не нужно. Я подумал, что очень вряд ли у меня в коде встречаются все возможные случаи, которые я рассмотрел в прошлый раз, поэтому я решил посмотреть что же у меня встречается на самом делом.

Что же дальше?
Комментировать
13 октября 2010 18:51

PHP, UTF-8, рассуждения по поводу строк

Тёмная материя (18.16КиБ) Работаю с низким приоритетом над автоматической заменой операций получения символа в строке по индексу на такую же операцию, но которая умела бы работать с UTF-8. Оказалось, что задача очень сложная.

Что дальше?
5 комментариев
9 октября 2010 13:47

Чем быстрее всего отрезать строку в кодировке UTF-8

Решил протестировать — чем быстрее всего можно отрезать строку в кодировке UTF-8. В PHP для этой цели (помимо использования извращений, типа SQL-запроса) можно использовать: mb_substr из модуля «Multibyte string function», iconv_substr из модуля iconv, preg_replace в режиме UTF-8 из Perl-Compatible regular expression function и собственную реализацию прохода по UTF-8 строке.

Я взял строку в 700 UTF-8-символов и отрезал от неё 500 разными функциями. Вот что получилось (PHP 5.2.4 без акселераторов): Если кому интересно, вот моя функция по проходу по строке в кодировке UTF-8:
    $len = strlen($text);
    for ($pos = $cutted = 0; $cutted < $cut && $pos < $len; ++$cutted)
    {
            $ch = ord($text[$pos]);

            // multibyte char
            if (0x80 & $ch)
            {
                    for (; $ch & 0x80; ++$pos, $ch <<= 1);
            }
            else
            {
                    $pos++;
            }
    }
Итак, лучший способ отрезать первые $N символов UTF-8 таков:
preg_replace('/^(.{'.$N.'}).*$/uSs', '$1', $text)
17 комментариев
7 марта 2008 17:56