Персональные инструменты
 

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

Материал из CustisWiki

Перейти к: навигация, поиск
м (1 версия)
(переименовал «PHP-разгон: серебряная пуля из автомата Комменца-Вальтера» (Commentz-Walter)» в «[[PHP-разгон: серебряная пуля из автомата Комменца-Ва)
 
Строка 1: Строка 1:
;Рабочее название: <big>«PHP-разгон: серебряная пуля из автомата Комменца-Вальтера» (Commentz-Walter)».</big>
+
#перенаправление [[PHP-разгон: серебряная пуля из автомата Комменца-Вальтера (Commentz-Walter)]]
 
+
== Аннотация ==
+
 
+
Никого не удивишь ситуацией, когда PHP-приложения тормозят под ''highload''-нагрузкой. Однако, с ростом навороченности PHP-based CMS, удивлять стали причины — узким горлом стала не СУБД (старый добрый набор: индексы/блокировки, диски/память), а «алгоритмическая недостаточность», например строковых алгоритмов. Например, в одной из наших MediaWiki-систем, 75 % времени сьедала функция поиска подстрок. Хорошие новости! Мы расскажем о волшебной «серебряной пуле», маленьком PHP-расширении, ускоряющем эти алгоритмы в несколько сотен раз! Так что вы сможете спасти таких «тормозов» практически без «хирургического вмешательства».
+
 
+
== Тезисы ==
+
 
+
* CMS системы на PHP под Highload часто тормозят (''Captain Obvious'').
+
* Но если раньше, в эпоху «PHP=Pretty Home Page», бутылочное горлышко обычно лежало на уровне СУБД (старый добрый набор: индексы/блокировки, диски/память), с ростом наворотов в веб-системах, сложных шаблонов, форматирования часто торможение концентрируется исключительно в PHP-части.
+
* Да, есть ускорители, типа «eAccelerator», но они помогает не всему — проблемы часто алгоритмические, сложные CMS загружены сложным раскрытием шаблонов.
+
* Ключевое алгоритмическое бутылочное горло — операция поиска подстроки (если, конечно, не используются регулярные выражения). Например, в одной из наших MediaWiki-систем на больших статьях <tt>75%</tt> всего времени тратилось именно на это.
+
* Good news, everyone: этот алгоритм можно ускорить в сотни раз! На помощь идет конечный автомат ''Комменца-Вальтера''!
+
: Автомат Комменца-Вальтера — аналог автомата Ахо-Карасик<ref>А Карасик не склоняется, потому что это не он, а она (самка карасика) — ''Margaret J. Corasick''.</ref>, но в качестве базового алгоритма выбирается не алгоритм Кнутта-Мориса-Пратта, а алгоритм Бойера-Мура.
+
* Стандартные реализации php — функции <tt>strtr</tt> и <tt>str_replace</tt> — используют наивный алгоритм … сложностью … (визуализация стандартного алгоритма). <ref><tt>str_replace</tt> быстрее, чем <tt>strtr</tt>, но в случаях поиска множественных подстрок весьма незначительно! При том, что у неё ещё и немного другая логика работы.</ref>
+
* Но можно установить магическое PHP-расширение, созданное авторами MediaWiki и использующее автомат Комменца-Вальтера (визуализация автомата).
+
* В нашем случае, мы получили выигрыш в поиске подстрок более чем в <tt>500</tt> раз, а с учетом того, что это занимало <tt>75%</tt> времени — мы получили выигрыш в <tt>4</tt> раза.
+
* PROFIT!!! Всем, бесплатно, и никто не уйдет обиженным.
+
 
+
== Подробнее ==
+
 
+
=== Введение ===
+
 
+
CMS-системы на PHP под Highload часто тормозят (''Captain Obvious''). Но если раньше, в эпоху «PHP=Pretty Home Page»<ref>На самом деле, конечно, PHP=Personal Home Page. Но это не важно :-)</ref>, бутылочное горлышко обычно лежало на уровне СУБД (старый добрый набор: индексы/блокировки, диски/память), с ростом наворотов в веб-системах, сложных шаблонов, форматирования часто торможение концентрируется исключительно в PHP-части.
+
 
+
Оптимизация приложений многогранна. Есть различные «ускорители» — кэши типа «eAccelerator» — но это не всё. Ещё существуют проблемы чисто алгоритмические — сложные CMS загружены раскрытием сложных шаблонов.
+
 
+
=== Проблема ===
+
 
+
Мы расскажем об одной важной операции, часто становящейся алгоритмическим бутылочным горлышком: '''операции поиска и замены подстрок'''. Предположим, что наша CMS использует в основном подстроки, а не регулярные выражения (с ними всё ещё сложнее и хуже).
+
 
+
Например, в одной из наших MediaWiki-систем на больших статьях примерно <tt>75%</tt> всего времени тратилось именно на поиск и замену подстрок.
+
 
+
Запустив профилировщик, мы увидели, что '''самая тяжёлая''' операция — именно замена подстрок. При парсинге одной большой тестовой статьи (~900 кб) на 1809 вызовов ReplacementArray::replace() из 13.5 секунд уходило примерно 9.5 секунд, то есть примерно 70 %.
+
 
+
Стандартные реализации поиска и замены подстрок в PHP — это функции <tt>strtr</tt> и <tt>str_replace</tt>. Обе они используют «наивные» алгоритмы сравнения сложности O(mn) и более (n — длина буфера, m — средняя длина искомой строки — «паттерна»).
+
 
+
Логика их работы немного отличается: <tt>str_replace</tt> заменяет переданные паттерны по очереди, проходя строку заново, а <tt>strtr</tt> — все разом за один проход строки. Иными словами, <tt>str_replace(A => B, B => C)</tt> заменит все вхождения A на C, а <tt>strtr(A => B, B => C)</tt> — нет.
+
 
+
<tt>str_replace</tt> использует классический «наивный» алгоритм. То есть, просто ищет паттерн в каждой позиции буфера. Позиций n = длина буфера, сравнений в каждой позиции m = средняя длина паттерна, количество паттернов = k. Итого сложность <tt>'''O(mnk)'''</tt>.
+
 
+
<tt>strtr</tt> обычно ещё хуже: она использует поиск по хешу замен. В каждой позиции буфера (сложность n) выделяются подстроки различной длины (от минимальной до максимальной длины паттерна => сложность M<sub>max</sub>-M<sub>min</sub>+1), от каждой из них вычисляется хеш (сложность m), и ищется в хеш-таблице паттернов. Итого сложность <tt>'''O((M<sub>max</sub>-M<sub>min</sub>+1)mn)'''</tt>.
+
 
+
Таким образом, сложность <tt>strtr</tt> сильно зависит от разброса длин паттернов: если все они одной длины, сложность будет всего лишь <tt>O(mn)</tt> и это '''быстрее, чем str_replace''', а если кратчайший паттерн — длины 1, а длиннейший — длины M, сложность будет уже <tt>O(M²n)</tt>, и это '''медленнее, чем str_replace'''.
+
 
+
{{note}} MediaWiki по умолчанию использует <tt>strtr</tt>.
+
 
+
=== Решение ===
+
 
+
Good news, everyone! Эту операцию можно ускорить в сотни раз! На помощь идет ''конечный автомат Комменца-Вальтера''!
+
 
+
Автомат Комменца-Вальтера — аналог автомата Ахо-Карасик, но в качестве базового алгоритма выбирается не алгоритм Кнутта-Мориса-Пратта, а алгоритм Бойера-Мура. Корасик не склоняется, потому что это не он, а она (самка карасика) — ''Margaret J. Corasick''.
+
 
+
Данный алгоритм имеет реализацию в виде магического PHP-расширения, созданного авторами MediaWiki — <tt>php5-fss</tt><ref>Скачать php5-fss можно здесь: http://apt.wikimedia.org/wikimedia/pool/main/php5-fss/</ref>. В нашем случае с MediaWiki мы получили выигрыш в поиске подстрок примерно в <tt>500</tt> раз, а с учетом того, что это занимало <tt>~75%</tt> времени — мы получили выигрыш производительности примерно в <tt>4</tt> раза.
+
 
+
Если приложить немножко больше усилий, чем установка одного экстенжна :-) то можно вообще заменить <tt>strtr</tt> на функции <tt>php5-fss</tt>. Единственное, что нужно будет сделать — добавить кэширование конечного автомата по массиву замен. То есть, сделать так, чтобы перед <tt>fss_exec_replace()</tt> прозрачно вызывалась <tt>fss_prep_replace()</tt>, строящая автомат.
+
 
+
PROFIT!!! Всем, бесплатно, и никто не уйдет обиженным.
+
 
+
==== Замеры ====
+
 
+
Равное во всех случаях количество вызовов намекает, что все реализация, скорее всего, отработали корректно. :-)
+
 
+
<tab sep="comma" head="topleft" class="tableborder1black">
+
Реализация,  Вызовов, Всего (мс),  В среднем (мс), % времени
+
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%
+
</tab>
+
С расширением php5-fss налицо выигрыш где-то в 478 раз. Будем считать, что в 500. :-) Также налицо тот факт, что <tt>str_replace</tt> в среднем отработала побыстрее, чем <tt>strtr</tt>. Это подтверждается и анализом.
+
 
+
=== Алгоритмы ===
+
 
+
Подробно рассказать не получится, за 5 минут-то. Даже ниженаписанное можно не успеть.
+
 
+
==== КМП и Ахо-Корасик ====
+
 
+
Алгоритм КМП (Кнутта-Мориса-Пратта) — вероятно, самый очевидный из всех линейных алгоритмов поиска подстроки. Размышления:
+
 
+
Берём наивный алгоритм.
+
 
+
|||||||......................
+
|||||||x-----
+
 
+
.||||........................
+
  ||||x--------
+
 
+
..|||||||||..................
+
  |||||||||x--
+
 
+
Хотим создать линейный. Ну давайте тупо не будем возвращаться назад после найденного несовпадения!
+
 
+
|||||||......................
+
|||||||x-----
+
 
+
.......||||........................
+
        ||||x--------
+
 
+
Не выйдет, можем пропустить подстроку :(
+
 
+
abxxxabxxxabyyyyyy
+
abxxxabyyyyyy
+
 
+
abxxxabxxxabyyyyyy
+
        abxxxabyyyyyy
+
 
+
А много ли мы пропустим? Чтобы мы что-то пропустили, некоторый суффикс части паттерна «до несовпадения» должен совпасть с некоторым префиксом! Наибольшая длина такого суффикса для некоторой строки называется ''префикс-функцией'' этой строки.
+
 
+
|||||||......................
+
|||||||x-----
+
ab...abx-----
+
 
+
Вычислим ''префикс-функцию'' для каждого префикса паттерна и будем сдвигаться назад на это число, но не дальше:
+
 
+
ab...ab||||........................
+
      ab||||.........
+
 
+
Останется только доказать линейность, и это тоже очень просто, но за рамками доклада.
+
 
+
Алгоритм Ахо-Корасик<ref>Про алгоритм Ахо-Корасик можно подробно и доступно прочитать, например, здесь: http://e-maxx.ru/algo/aho_corasick</ref>, в свою очередь — это тот же КМП, но для множества паттернов, а не для одного-единственного, и представленный в виде конечного автомата. По суффиксам строится бор (дерево, где каждое ребро подписано символов), префикс-функция превращается в функцию неудач (по сути, та же функция на дереве).
+
 
+
==== БМ и Комменц-Вальтер ====
+
 
+
Алгоритм БМ (Бойера-Мура) похож на КМП, эффективен на больших алфавитах и в своём изначальном виде имеет в худшем случае нелинейную сложность. Существует множество модификаций этого алгоритма, имеющих различные улучшения — чуть меньшую среднюю сложность, линейную худшую сложность и т. п.
+
 
+
В двух словах, алгоритм БМ сканирует паттерн от конца к началу, а не от начала к концу, также основан на «пропусках» части буфера после сравнения, и содержит две эвристики:
+
 
+
; Эвристика «плохого символа» (стоп-символа): При найденном несовпадении можно сдвинуть паттерн вдоль буфера так, чтобы не совпавший с символом паттерна символ буфера оказался напротив последнего вхождения этого символа в паттерн, и при этом не будет потеряна ни одна подстрока. Для нахождения таких позиций используется хеш-таблица позиций символов в паттерне (символ => позиция).
+
; Эвристика «хорошего суффикса» (безопасного суффикса): При найденном несовпадении можно сдвинуть паттерн вдоль буфера так, чтобы совпавший суффикс паттерна оказался напротив последнего своего собственного вхождения в паттерн, и при этом не будет потеряна ни одна подстрока. Для нахождения таких позиций используется специальная функция, которая строится с помощью префикс-функции.
+
 
+
А автомат Комменца-Вальтера, по аналогии с автоматом Ахо-Корасик, является модификацией алгоритма БМ для множества паттернов.
+
 
+
== Формат ==
+
 
+
Это будет выступление под заранее записанное видео. Таким образом гарантируется соблюдение 5-минутного тайм-фрейма,
+
плюс все будет живо и динамично.
+
 
+
Презентация: [[Изображение:FastStringSearch.odp]]
+
 
+
== Литература ==
+
* [[Методы и алгоритмы вычислений на строках]]
+
 
+
== Алсо ==
+
 
+
<div style="display:none"><ref>http://xpoint.ru/forums/programming/PHP/thread/20999.xhtml — обсуждение strtr vs str_replace…</ref>.</div>
+
 
+
<references />
+
 
+
{{replicate-from-custiswiki-to-lib}}
+

Текущая версия на 20:15, 12 января 2010