|
Персональные инструменты |
|||
|
PHP-разгон: серебряная пуля из автомата Комменца-Вальтера (Commentz-Walter)Материал из CustisWiki
Содержание[убрать]АннотацияНикого не удивишь ситуацией, когда PHP-приложения тормозят под highload-нагрузкой. Однако, с ростом навороченности PHP-based CMS, удивлять стали причины — узким горлом стала не СУБД (старый добрый набор: индексы/блокировки, диски/память), а «алгоритмическая недостаточность», например строковых алгоритмов. Например, в одной из наших MediaWiki-систем, 75 % времени сьедала функция поиска подстрок. Хорошие новости! Мы расскажем о волшебной «серебряной пуле», маленьком PHP-расширении, ускоряющем эти алгоритмы в несколько сотен раз! Так что вы сможете спасти таких «тормозов» практически без «хирургического вмешательства». Тезисы
ПодробнееВведениеCMS-системы на PHP под Highload часто тормозят (Captain Obvious). Но если раньше, в эпоху «PHP=Pretty Home Page»[3], бутылочное горлышко обычно лежало на уровне СУБД (старый добрый набор: индексы/блокировки, диски/память), с ростом наворотов в веб-системах, сложных шаблонов, форматирования часто торможение концентрируется исключительно в 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) выделяются подстроки различной длины (от минимальной до максимальной длины паттерна => сложность Mmax-Mmin+1), от каждой из них вычисляется хеш (сложность m), и ищется в хеш-таблице паттернов. Итого сложность O((Mmax-Mmin+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[4]. В нашем случае с MediaWiki мы получили выигрыш в поиске подстрок примерно в 500 раз, а с учетом того, что это занимало ~75% времени — мы получили выигрыш производительности примерно в 4 раза. Если приложить немножко больше усилий, чем установка одного экстенжна :-) то можно вообще заменить strtr на функции php5-fss. Единственное, что нужно будет сделать — добавить кэширование конечного автомата по массиву замен. То есть, сделать так, чтобы перед fss_exec_replace() прозрачно вызывалась fss_prep_replace(), строящая автомат. PROFIT!!! Всем, бесплатно, и никто не уйдет обиженным. ЗамерыРавное во всех случаях количество вызовов намекает, что все реализация, скорее всего, отработали корректно. :-)
С расширением php5-fss налицо выигрыш где-то в 478 раз. Будем считать, что в 500. :-) Также налицо тот факт, что str_replace в среднем отработала побыстрее, чем strtr. Это подтверждается и анализом. АлгоритмыПодробно рассказать не получится, за 5 минут-то. Даже ниженаписанное можно не успеть. КМП и Ахо-КорасикАлгоритм КМП (Кнутта-Мориса-Пратта) — вероятно, самый очевидный из всех линейных алгоритмов поиска подстроки. Размышления: Берём наивный алгоритм. |||||||...................... |||||||x----- .||||........................ ||||x-------- ..|||||||||.................. |||||||||x-- Хотим создать линейный. Ну давайте тупо не будем возвращаться назад после найденного несовпадения! |||||||...................... |||||||x----- .......||||........................ ||||x-------- Не выйдет, можем пропустить подстроку :( abxxxabxxxabyyyyyy abxxxabyyyyyy abxxxabxxxabyyyyyy abxxxabyyyyyy А много ли мы пропустим? Чтобы мы что-то пропустили, некоторый суффикс части паттерна «до несовпадения» должен совпасть с некоторым префиксом! Наибольшая длина такого суффикса для некоторой строки называется префикс-функцией этой строки. |||||||...................... |||||||x----- ab...abx----- Вычислим префикс-функцию для каждого префикса паттерна и будем сдвигаться назад на это число, но не дальше: ab...ab||||........................ ab||||......... Останется только доказать линейность, и это тоже очень просто, но за рамками доклада. Алгоритм Ахо-Корасик[5], в свою очередь — это тот же КМП, но для множества паттернов, а не для одного-единственного, и представленный в виде конечного автомата. По суффиксам строится бор (дерево, где каждое ребро подписано символов), префикс-функция превращается в функцию неудач (по сути, та же функция на дереве). БМ и Комменц-ВальтерАлгоритм БМ (Бойера-Мура) похож на КМП, эффективен на больших алфавитах и в своём изначальном виде имеет в худшем случае нелинейную сложность. Существует множество модификаций этого алгоритма, имеющих различные улучшения — чуть меньшую среднюю сложность, линейную худшую сложность и т. п. В двух словах, алгоритм БМ сканирует паттерн от конца к началу, а не от начала к концу, также основан на «пропусках» части буфера после сравнения, и содержит две эвристики:
А автомат Комменца-Вальтера, по аналогии с автоматом Ахо-Корасик, является модификацией алгоритма БМ для множества паттернов. ВидеоВыступление Виталия Филиппова на Highload-2009.
ПрезентацияЛитератураАлсо
Любые правки этой статьи будут перезаписаны при следующем сеансе репликации. Если у вас есть серьезное замечание по тексту статьи, запишите его в раздел «discussion». |
||||||||||||||||||||||