PHP-разгон: серебряная пуля из автомата Комменца-Вальтера (Commentz-Walter)

Ссылки сюда (1) →

Рабочее название

«PHP-разгон: серебряная пуля из автомата Комменца-Вальтера» (Commentz-Walter)».

Аннотация

Никого не удивишь ситуацией, когда PHP-приложения тормозят под highload-нагрузкой. Однако, с ростом навороченности PHP-based CMS, удивлять стали причины — узким горлом стала не СУБД (старый добрый набор: индексы/блокировки, диски/память), а «алгоритмическая недостаточность», например строковых алгоритмов. Например, в одной из наших MediaWiki-систем, 75 % времени сьедала функция поиска подстрок. Хорошие новости! Мы расскажем о волшебной «серебряной пуле», маленьком PHP-расширении, ускоряющем эти алгоритмы в несколько сотен раз! Так что вы сможете спасти таких «тормозов» практически без «хирургического вмешательства».

Тезисы

• CMS системы на PHP под Highload часто тормозят (Captain Obvious).
• Но если раньше, в эпоху «PHP=Pretty Home Page», бутылочное горлышко обычно лежало на уровне СУБД (старый добрый набор: индексы/блокировки, диски/память), с ростом наворотов в веб-системах, сложных шаблонов, форматирования часто торможение концентрируется исключительно в PHP-части.
• Да, есть ускорители, типа «eAccelerator», но они помогает не всему — проблемы часто алгоритмические, сложные CMS загружены сложным раскрытием шаблонов.
• Ключевое алгоритмическое бутылочное горло — операция поиска подстроки (если, конечно, не используются регулярные выражения). Например, в одной из наших MediaWiki-систем на больших статьях 75% всего времени тратилось именно на это.
• Good news, everyone: этот алгоритм можно ускорить в сотни раз! На помощь идет конечный автомат Комменца-Вальтера!

Автомат Комменца-Вальтера — аналог автомата Ахо-Карасик, но в качестве базового алгоритма выбирается не алгоритм Кнутта-Мориса-Пратта, а алгоритм Бойера-Мура.

• Стандартные реализации php — функции strtr и str_replace — используют наивный алгоритм … сложностью … (визуализация стандартного алгоритма).
• Но можно установить магическое PHP-расширение, созданное авторами MediaWiki и использующее автомат Комменца-Вальтера (визуализация автомата).
• В нашем случае, мы получили выигрыш в поиске подстрок более чем в 500 раз, а с учетом того, что это занимало 75% времени — мы получили выигрыш в 4 раза.
• PROFIT!!! Всем, бесплатно, и никто не уйдет обиженным.

Подробнее

Введение

CMS-системы на PHP под Highload часто тормозят (Captain Obvious). Но если раньше, в эпоху «PHP=Pretty Home Page», бутылочное горлышко обычно лежало на уровне СУБД (старый добрый набор: индексы/блокировки, диски/память), с ростом наворотов в веб-системах, сложных шаблонов, форматирования часто торможение концентрируется исключительно в PHP-части.

Оптимизация приложений многогранна. Есть различные «ускорители» — кэши типа «eAccelerator» — но это не всё. Ещё существуют проблемы чисто алгоритмические — сложные CMS загружены раскрытием сложных шаблонов.

Проблема

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

Например, в одной из наших MediaWiki-систем на больших статьях примерно 75% всего времени тратилось именно на поиск и замену подстрок.

Запустив профилировщик, мы увидели, что самая тяжёлая операция — именно замена подстрок. При парсинге одной большой тестовой статьи (~900 кб) на 1809 вызовов ReplacementArray::replace() из 13.5 секунд уходило примерно 9.5 секунд, то есть примерно 70 %.

Стандартные реализации поиска и замены подстрок в PHP — это функции strtr и str_replace. Обе они используют «наивные» алгоритмы сравнения сложности O(mn) и более (n — длина буфера, m — средняя длина искомой строки — «паттерна»).

Логика их работы немного отличается: str_replace заменяет переданные паттерны по очереди, проходя строку заново, а strtr — все разом за один проход строки. Иными словами, str_replace(A => B, B => C) заменит все вхождения A на C, а strtr(A => B, B => C) — нет.

str_replace использует классический «наивный» алгоритм. То есть, просто ищет паттерн в каждой позиции буфера. Позиций n = длина буфера, сравнений в каждой позиции m = средняя длина паттерна, количество паттернов = k. Итого сложность O(mnk).

strtr обычно ещё хуже: она использует поиск по хешу замен. В каждой позиции буфера (сложность n) выделяются подстроки различной длины (от минимальной до максимальной длины паттерна => сложность M_max-M_min+1), от каждой из них вычисляется хеш (сложность m), и ищется в хеш-таблице паттернов. Итого сложность O((M_max-M_min+1)mn).

Таким образом, сложность strtr сильно зависит от разброса длин паттернов: если все они одной длины, сложность будет всего лишь O(mn) и это быстрее, чем str_replace, а если кратчайший паттерн — длины 1, а длиннейший — длины M, сложность будет уже O(M²n), и это медленнее, чем str_replace.

MediaWiki по умолчанию использует strtr.

Решение

Good news, everyone! Эту операцию можно ускорить в сотни раз! На помощь идет конечный автомат Комменца-Вальтера!

Автомат Комменца-Вальтера — аналог автомата Ахо-Карасик, но в качестве базового алгоритма выбирается не алгоритм Кнутта-Мориса-Пратта, а алгоритм Бойера-Мура. Корасик не склоняется, потому что это не он, а она (самка карасика) — Margaret J. Corasick.

Данный алгоритм имеет реализацию в виде магического PHP-расширения, созданного авторами MediaWiki — php5-fss. В нашем случае с MediaWiki мы получили выигрыш в поиске подстрок примерно в 500 раз, а с учетом того, что это занимало ~75% времени — мы получили выигрыш производительности примерно в 4 раза.

Если приложить немножко больше усилий, чем установка одного экстенжна :-) то можно вообще заменить strtr на функции php5-fss. Единственное, что нужно будет сделать — добавить кэширование конечного автомата по массиву замен. То есть, сделать так, чтобы перед fss_exec_replace() прозрачно вызывалась fss_prep_replace(), строящая автомат.

PROFIT!!! Всем, бесплатно, и никто не уйдет обиженным.

Замеры

Равное во всех случаях количество вызовов намекает, что все реализация, скорее всего, отработали корректно. :-)

Реализация	Вызовов	Всего (мс)	В среднем (мс)	% времени
strtr	1809	9505.825	5.255	70.564%
str_replace	1809	3557.285	1.966	49.037%
fss	1809	19.874	0.011	0.560%

С расширением php5-fss налицо выигрыш где-то в 478 раз. Будем считать, что в 500. :-) Также налицо тот факт, что str_replace в среднем отработала побыстрее, чем strtr. Это подтверждается и анализом.

Алгоритмы

Подробно рассказать не получится, за 5 минут-то. Даже ниженаписанное можно не успеть.

КМП и Ахо-Корасик

Алгоритм КМП (Кнутта-Мориса-Пратта) — вероятно, самый очевидный из всех линейных алгоритмов поиска подстроки. Размышления:

Берём наивный алгоритм.

|||||||......................
|||||||x-----

.||||........................
 ||||x--------

..|||||||||..................
  |||||||||x--

Хотим создать линейный. Ну давайте тупо не будем возвращаться назад после найденного несовпадения!

|||||||......................
|||||||x-----

.......||||........................
       ||||x--------

Не выйдет, можем пропустить подстроку :(

abxxxabxxxabyyyyyy
abxxxabyyyyyy

abxxxabxxxabyyyyyy
       abxxxabyyyyyy

А много ли мы пропустим? Чтобы мы что-то пропустили, некоторый суффикс части паттерна «до несовпадения» должен совпасть с некоторым префиксом! Наибольшая длина такого суффикса для некоторой строки называется префикс-функцией этой строки.

|||||||......................
|||||||x-----
ab...abx-----

Вычислим префикс-функцию для каждого префикса паттерна и будем сдвигаться назад на это число, но не дальше:

ab...ab||||........................
     ab||||.........

Останется только доказать линейность, и это тоже очень просто, но за рамками доклада.

Алгоритм Ахо-Корасик, в свою очередь — это тот же КМП, но для множества паттернов, а не для одного-единственного, и представленный в виде конечного автомата. По суффиксам строится бор (дерево, где каждое ребро подписано символов), префикс-функция превращается в функцию неудач (по сути, та же функция на дереве).

БМ и Комменц-Вальтер

Алгоритм БМ (Бойера-Мура) похож на КМП, эффективен на больших алфавитах и в своём изначальном виде имеет в худшем случае нелинейную сложность. Существует множество модификаций этого алгоритма, имеющих различные улучшения — чуть меньшую среднюю сложность, линейную худшую сложность и т. п.

В двух словах, алгоритм БМ сканирует паттерн от конца к началу, а не от начала к концу, также основан на «пропусках» части буфера после сравнения, и содержит две эвристики:

Эвристика «плохого символа» (стоп-символа)

При найденном несовпадении можно сдвинуть паттерн вдоль буфера так, чтобы не совпавший с символом паттерна символ буфера оказался напротив последнего вхождения этого символа в паттерн, и при этом не будет потеряна ни одна подстрока. Для нахождения таких позиций используется хеш-таблица позиций символов в паттерне (символ => позиция).

Эвристика «хорошего суффикса» (безопасного суффикса)

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

А автомат Комменца-Вальтера, по аналогии с автоматом Ахо-Корасик, является модификацией алгоритма БМ для множества паттернов.

Видео

Выступление Виталия Филиппова на Highload-2009.

• Видео всей секции блиц-докладов.

Презентация

Файл:FastStringSearch.odp

Литература

• Методы и алгоритмы вычислений на строках

Алсо

.

---

Репликация: База Знаний «Заказных Информ Систем» → «PHP-разгон: серебряная пуля из автомата Комменца-Вальтера (Commentz-Walter)»

Любые правки этой статьи будут перезаписаны при следующем сеансе репликации. Если у вас есть серьезное замечание по тексту статьи, запишите его в раздел «discussion».