PHP-разгон: серебряная пуля из автомата Комменца-Вальтера
PHP-разгон: серебряная пуля из автомата Комменца-Вальтера
http://events.kapranoff.ru/proposals/4
Докладчик Виталий Филиппов
Компания Заказные ИнформСистемы
О себе
ведущий веб-программист
Описание
* CMS системы на PHP под Highload часто тормозят (Captain Obvious).
* Но если раньше, в эпоху «PHP=Pretty Home Page», бутылочное горлышко обычно лежало на уровне СУБД (старый добрый набор: индексы/блокировки, диски/память), с ростом наворотов в веб-системах, сложных шаблонов, форматирования часто торможение концентрируется исключительно в PHP-части.
* Да, есть ускорители, типа «eAccelerator», но они помогает не всему — проблемы часто алгоритмические, сложные CMS загружены сложным раскрытием шаблонов.
* Ключевое алгоритмическое бутылочное горло — операция поиска подстроки (если, конечно, не используются регулярные выражения). Например, в одной из наших MediaWiki-систем на больших статьях 75% всего времени тратилось именно на это.
* Good news, everyone: этот алгоритм можно ускорить в сотни раз! На помощь идет «конечный автомат Комменца-Вальтера»!
Автомат Комменца-Вальтера — аналог автомата Ахо-Карасик[1], но в качестве базового алгоритма выбирается не алгоритм Кнутта-Мориса-Пратта, а алгоритм Бойера-Мура.
* Стандартные реализации php — функции strtr и str_replace — используют наивный алгоритм … сложностью … (визуализация стандартного алгоритма). [2]
* Но можно установить магическое PHP-расширение, созданное авторами MediaWiki и использующее автомат Комменца-Вальтера (визуализация автомата).
* В нашем случае, мы получили выигрыш в поиске подстрок более чем в 500 раз, а с учетом того, что это занимало 75% времени — мы получили выигрыш в 4 раза.
* PROFIT!!! Всем, бесплатно, и никто не уйдет обиженным.
==Примечания==
1. ↑ А Карасик не склоняется, потому что это не он, а она (самка карасика) — Margaret J. Corasick.
2. ↑ str_replace быстрее, чем strtr, но в случаях поиска множественных подстрок весьма незначительно! При том, что у неё ещё и немного другая логика работы.
3. ↑ http://xpoint.ru/forums/programming/PHP/thread/20999.xhtml — обсуждение strtr vs str_replace…
P.S. Хотел сначала в юмор.. но решил в оффтопик..
PHP-разгон: серебряная пуля из автомата Комменца-Вальтера
http://events.kapranoff.ru/proposals/4
Докладчик Виталий Филиппов
Компания Заказные ИнформСистемы
О себе
ведущий веб-программист
Описание
* CMS системы на PHP под Highload часто тормозят (Captain Obvious).
* Но если раньше, в эпоху «PHP=Pretty Home Page», бутылочное горлышко обычно лежало на уровне СУБД (старый добрый набор: индексы/блокировки, диски/память), с ростом наворотов в веб-системах, сложных шаблонов, форматирования часто торможение концентрируется исключительно в PHP-части.
* Да, есть ускорители, типа «eAccelerator», но они помогает не всему — проблемы часто алгоритмические, сложные CMS загружены сложным раскрытием шаблонов.
* Ключевое алгоритмическое бутылочное горло — операция поиска подстроки (если, конечно, не используются регулярные выражения). Например, в одной из наших MediaWiki-систем на больших статьях 75% всего времени тратилось именно на это.
* Good news, everyone: этот алгоритм можно ускорить в сотни раз! На помощь идет «конечный автомат Комменца-Вальтера»!
Автомат Комменца-Вальтера — аналог автомата Ахо-Карасик[1], но в качестве базового алгоритма выбирается не алгоритм Кнутта-Мориса-Пратта, а алгоритм Бойера-Мура.
* Стандартные реализации php — функции strtr и str_replace — используют наивный алгоритм … сложностью … (визуализация стандартного алгоритма). [2]
* Но можно установить магическое PHP-расширение, созданное авторами MediaWiki и использующее автомат Комменца-Вальтера (визуализация автомата).
* В нашем случае, мы получили выигрыш в поиске подстрок более чем в 500 раз, а с учетом того, что это занимало 75% времени — мы получили выигрыш в 4 раза.
* PROFIT!!! Всем, бесплатно, и никто не уйдет обиженным.
==Примечания==
1. ↑ А Карасик не склоняется, потому что это не он, а она (самка карасика) — Margaret J. Corasick.
2. ↑ str_replace быстрее, чем strtr, но в случаях поиска множественных подстрок весьма незначительно! При том, что у неё ещё и немного другая логика работы.
3. ↑ http://xpoint.ru/forums/programming/PHP/thread/20999.xhtml — обсуждение strtr vs str_replace…
P.S. Хотел сначала в юмор.. но решил в оффтопик..
