Профилирование Regex Lexer - PullRequest
Новая
       22

Профилирование Regex Lexer

4 голосов
/ 19 августа 2011

Я создал маршрутизатор в PHP, который принимает DSL (на основе маршрута Rails 3) и преобразует его в Regex.Он имеет необязательные сегменты (обозначены (вложенными) круглыми скобками).Ниже приведен текущий алгоритм лексинга: 

private function tokenize($pattern)
{
    $rules = array(
        self::OPEN_PAREN_TYPE  => '/^(\()/',
        self::CLOSE_PAREN_TYPE => '/^(\))/',
        self::VARIABLE_TYPE    => '/^:([a-z0-9_]+)/',
        self::TEXT_TYPE        => '/^([^:()]+)/',
    );

    $cursor = 0;
    $tokens = array();
    $buffer = $pattern;
    $buflen = strlen($buffer);

    while ($cursor < $buflen)
    {
        $chunk = substr($buffer, $cursor);

        $matched = false;
        foreach ($rules as $type => $rule)
        {
            if (preg_match($rule, $chunk, $matches))
            {
                $tokens[] = array(
                    'type'  => $type,
                    'value' => $matches[1],
                );

                $matched = true;
                $cursor += strlen($matches[0]);
            }
        }

        if (!$matched)
        {
            throw new \Exception(sprintf('Problem parsing route "%s" at char "%d".', $pattern, $cursor));
        }
    }

    return $tokens;
}

Существуют ли какие-либо очевидные ускорения, которые мне не хватает?Можно ли вообще отказаться от preg_ * или объединить регулярные выражения в один шаблон и т. Д.?

Вот список вызовов xhprof (в тесте используется ~ 2500 уникальных маршрутов для тестирования):

callgraph

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

РЕДАКТИРОВАТЬ:

Я также написал быструю версию конечного автомата, которая, кажется, работает лучше.Я все еще открыт для предложений по обоим направлениям, так как я считаю, что первый код был более элегантным.

private function tokenize2($pattern)
{
    $buffer = '';
    $invariable = false;

    $tokens = array();
    foreach (str_split($pattern) as $char)
    {
        switch ($char)
        {
            case '(':
                if ($buffer)
                {
                    $tokens[] = array(
                        'type'  => $invariable ? self::VARIABLE_TYPE : self::TEXT_TYPE,
                        'value' => $buffer,
                    );
                    $buffer = '';
                    $invariable = false;
                }

                $tokens[] = array(
                    'type' => self::OPEN_PAREN_TYPE,
                );
                break;
            case ')':
                if ($buffer)
                {
                    $tokens[] = array(
                        'type'  => $invariable ? self::VARIABLE_TYPE : self::TEXT_TYPE,
                        'value' => $buffer,
                    );
                    $buffer = '';
                    $invariable = false;
                }

                $tokens[] = array(
                    'type' => self::CLOSE_PAREN_TYPE,
                );
                break;
            case ':':
                if ($buffer)
                {
                    $tokens[] = array(
                        'type'  => $invariable ? self::VARIABLE_TYPE : self::TEXT_TYPE,
                        'value' => $buffer,
                    );
                    $buffer = '';
                    $invariable = false;
                }

                $invariable = true;
                break;
            default:
                if ($invariable && !(ctype_alnum($char) || '_' == $char ))
                {
                    $invariable = false;
                    $tokens[] = array(
                        'type'  => self::VARIABLE_TYPE,
                        'value' => $buffer,
                    );

                    $buffer = '';
                    $invariable = false;
                }

                $buffer .= $char;
                break;
        }
    }

    if ($buffer)
    {
        $tokens[] = array(
        'type'  => $invariable ? self::VARIABLE_TYPE : self::TEXT_TYPE,
        'value' => $buffer,
        );
        $buffer = '';
    }

    return $tokens;

callgraph

В итоге я просто использовал конечный автомат из соображений производительности и кэшировал весь процесс лексизации с помощью APC (потому что ... почему бы и нет).

Если у кого-то есть что-то, что я могу внести, я с радостью перенесу ответ.

1 Ответ

1 голос
/ 25 октября 2011

Интересный код:).

Я не совсем уверен, что вы говорите, когда «кэшируете весь процесс лексирования с помощью APC», поэтому я могу предположить, что вы уже делаете.

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

...