Пишу, по большей части, про историю, свою жизнь и немного про программирование.

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 комментариев
SiMM 2010

квартификатор

квантификатор (от «квант», полагаю)

Евгений Степанищев (bolknote.ru) 2010

Комментарий для SiMM:

Опечатка. «Квантификатор» от quantity.

www.twitter.com/gmile 2010

К слову, совсем недавно некто Леонид Вольницкий изобрел сверхбыстрый поиск подстроки в строке (с unicode’ом, к сожалению, ничего общего): http://volnitsky.com/project/str_search/

Судя по бенчмаркам обгоняет все существующие аналогичные алгоритмы

Евгений Степанищев (bolknote.ru) 2010

Комментарий для http://www.twitter.com/gmile:

Надо будет попробовать сравнить его вариант с вариантом, который сравнивает сразу по 16 байт одной командой SSE.

Евгений Степанищев (bolknote.ru) 2010

Комментарий для http://www.twitter.com/gmile:

За ссылку спасибо, кстати! Команды поиска вполне UTF-8-safe, только возвращают, к сожалению, бесполезное бинарное смещение.

hshhhhh.name 2010

Комментарий для Евгения Степанищева:

болк, а ты маниак! переводил вику на утф, а уже почти на ассемблере кодишь :)

Евгений Степанищев (bolknote.ru) 2010

Комментарий для hshhhhh.name:

Не почти, уже на ассемблере, пусть и окружённом Си :)

Leonid Volnitsky (http://volnitsky.com) 2011

Комментарий для Евгения Степанищева:

только возвращают, к сожалению, бесполезное бинарное смещение.

Я не очень понял что ты имеешь в виду. Возвращается адрес найденной подстроки или если не найдена — адрес последнего байта+1. Так как в std::search(). А тебе надо индекс?

Евгений Степанищев (bolknote.ru) 2011

Комментарий для Leonid Volnitsky (http://volnitsky.com):

Мне надо индекс, конечно. Иначе что мне передать остальным функциям, которые уже с индексом работают?

Leonid Volnitsky (http://volnitsky.com) 2011

Комментарий для Евгения Степанищева:

Если найдена:
индекс = результат — адрес строки (в которой ищеться)
А какие строки PHP использует? C-style?

Мне интересно что оказалось быстрее: мой алгоритм или SSE?

Евгений Степанищев (bolknote.ru) 2011

Комментарий для Leonid Volnitsky (http://volnitsky.com):

индекс = результат — адрес строки (в которой ищется)

Что? О чём вы?

А какие строки PHP использует? C-style?

Нет. Но в любом случае, от реализации языка спрятана реализация строк.

Мне интересно что оказалось быстрее: мой алгоритм или SSE?

Да какой алгоритм-то? Вы знаете как устроен UTF-8?