Изменения

;Рабочее название: <big>«PHP#перенаправление [[PHP-разгон: серебряная пуля из автомата Комменца-Вальтера» Вальтера (Commentz-Walter)».</big> == Аннотация == Никого не удивишь ситуацией, когда 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_max-M_min+1), от каждой из них вычисляется хеш (сложность m), и ищется в хеш-таблице паттернов. Итого сложность <tt>'''O((M_max-M_min+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}}