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 бита.
20 декабря 2010 23:31

SiMM (инкогнито)
20 декабря 2010, 23:43

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

bolk (bolknote.ru)
21 декабря 2010, 00:26, ответ предназначен SiMM

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

http://www.twitter.com/gmile (инкогнито)
21 декабря 2010, 01:55

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

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

bolk (bolknote.ru)
21 декабря 2010, 09:12, ответ предназначен http://www.twitter.com/gmile

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

bolk (bolknote.ru)
21 декабря 2010, 09:13, ответ предназначен http://www.twitter.com/gmile

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

hshhhhh.name (hshhhhh.name)
21 декабря 2010, 16:30, ответ предназначен bolk (bolknote.ru):

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

bolk (bolknote.ru)
21 декабря 2010, 17:55, ответ предназначен hshhhhh.name:

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

Leonid Volnitsky (http://volnitsky.com) (инкогнито)
13 февраля 2011, 08:50, ответ предназначен bolk (bolknote.ru):

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

bolk (bolknote.ru)
13 февраля 2011, 11:03, ответ предназначен Leonid Volnitsky (http://volnitsky.com)

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

Leonid Volnitsky (http://volnitsky.com) (инкогнито)
13 февраля 2011, 14:06, ответ предназначен bolk (bolknote.ru):

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

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

bolk (bolknote.ru)
13 февраля 2011, 19:11, ответ предназначен Leonid Volnitsky (http://volnitsky.com)

индекс = результат - адрес строки (в которой ищется)
Что? О чём вы?
А какие строки PHP использует? C-style?
Нет. Но в любом случае, от реализации языка спрятана реализация строк.
Мне интересно что оказалось быстрее: мой алгоритм или SSE?
Да какой алгоритм-то? Вы знаете как устроен UTF-8?

Ваше имя или адрес блога (можно OpenID):

Текст вашего комментария, не HTML:

Кому бы вы хотели ответить (или кликните на его аватару)