Ads
Comments 20
UFO landed and left these words here
+3
Есть у меня смутное подозрение, что самописный конечный автомат будет для этой задачи сильно производительней (и, возможно, проще для понимания)

PS Теги для поиска по ним, а не для чтения. Спасибо за статью! :)
0
Fesor уже пытался запилить его следуя этой же логике, адаптировав для этой цели re2c. Но что получилось в итоге не совсем понятно. Думаю, когда увидит моё упоминание — сможет поподробнее написать к чему пришёл в комментах.

Но почему-то лично меня терзают смутные сомнения в успехе мероприятия, т.к. простой цикл с проходом по буковкам в PHP довольно тормозной.
0
простой цикл с проходом по буковкам в PHP довольно тормозной.
Это да. С другой стороны, никто не мешает работать не со строкой, а с массивом байт. Оно, по идее, должно быть сильно быстрее.
+1
Заголовок спойлера
<?php
$data = \file_get_contents(__FILE__);
$attempts = 100000;

$before = \microtime(true);

for ($i = 0; $i < $attempts; $i++) {
    foreach (\str_split($data) as $chars => $char) {
        // Do something
    }
}


/// =====================================


echo \number_format(\microtime(true) - $before, 4) . 's / ' . $chars . "\n";

$before = \microtime(true);

for ($i = 0; $i < $attempts; $i++) {
    foreach (\unpack('C*', $data) as $bytes => $byte) {
        // Do something
    }
}

echo \number_format(\microtime(true) - $before, 4) . 's / ' . $bytes . "\n";



1) 1.6975s на 573 символа для str_split
2) 11.5845s на 574 байта для unpack

UPD:
3) Ну и ~1.06s на тоже количество для "for" + "$byte = $data[$i]"
0
Как чувствовал — убрал упоминание unpack раньше появления вашего ответа. :)
Про массив байт — это я конечно маху дал, PHP же, какой массив байт?..

Зато добавил к вашему «тесту» третий вариант, с интересным результатом.

Заголовок спойлера
<?php
$data = \file_get_contents(__FILE__);
$attempts = 10000;

$before = \microtime(true);

for ($i = 0; $i < $attempts; $i++) {
    $data = \file_get_contents(__FILE__);
    foreach (\str_split($data) as $chars => $char) {
        // Do something
    }
}

echo 'str_split: ' . \number_format(\microtime(true) - $before, 4) . 's / ' . $chars . "\n";

$before = \microtime(true);

for ($i = 0; $i < $attempts; $i++) {
    $data = \file_get_contents(__FILE__);
    foreach (\unpack('C*', $data) as $bytes => $byte) {
        // Do something
    }
}

echo 'unpack   : ' . \number_format(\microtime(true) - $before, 4) . 's / ' . $bytes . "\n";

$before = \microtime(true);

for ($i = 0; $i < $attempts; $i++) {
    $handle=fopen(__FILE__,"r");
    while ($char = fread($handle,1)) {
        // Do something
    }
    fclose($handle);
}

echo 'fread    : ' . \number_format(\microtime(true) - $before, 4) . 's / ' . $bytes . "\n";



str_split: 0.5737s / 967
unpack   : 0.7472s / 968
fread    : 0.1524s / 968
0
fread: 0.1524s / 968


Я пробовал этот вариант, и он медленнее оказался побуквенного чтения из строки. Но зато сейчас проверил с чтением из памяти, а он уже оказался самым быстрым. Не буду томить:
Код тестов
<?php
$data = \file_get_contents(__FILE__);
$attempts = 10000;

function test(string $title, int $attempts, \Closure $expression)
{
    $before = \microtime(true);

    for ($i = 0; $i < $attempts; $i++) {
        $expression();
    }

    $after = number_format(\microtime(true) - $before, 4);

    echo \sprintf('%-13s: %ss', $title, $after) . "\n";
}



test('str_split', $attempts, function() {
    $data = \file_get_contents(__FILE__);

    foreach (\str_split($data) as $chars => $char) {
        // Do something
    }
});

test('unpack', $attempts, function() {
    $data = \file_get_contents(__FILE__);

    foreach (\unpack('C*', $data) as $bytes => $byte) {
        // Do something
    }
});

test('fread', $attempts, function() {
    $handle = fopen(__FILE__, 'rb+');

    while (! feof($handle)) {
        $char = fread($handle, 1);
    }

    fclose($handle);
});

test('$data[$i]', $attempts, function() {
    $data = \file_get_contents(__FILE__);

    for ($i = 0, $bytes = strlen($data); $i < $bytes; ++$i) {
        $char = $data[$i];
    }
});

test('fread + mem', $attempts, function() {
    $handle = fopen('php://memory', 'ab+');
    stream_copy_to_stream(fopen(__FILE__, 'rb+'), $handle);

    while (! feof($handle)) {
        $char = fread($handle, 1);
    }

    fclose($handle);
});



str_split    : 0.8728s
unpack       : 3.9583s
fread        : 1.4985s
$data[$i]    : 0.8127s
fread + mem  : 0.7095s

0

В тесте ошибка, после stream_copy_to_stream указатель не сбрасывается

0
Это не обязательно. Интерпретатор автоматом закрывает потоки чтения/записи при refcount=0 (т.е. в данном случае при выходе за пределы анонимной функции). Но да, действительно так писать не очень хорошо и с моей стороны была допущена опечатка.

Добавил fclose внутреннего ресурса. Соотношение по скорости, естественно, не изменилось (всё на уровне погрешностей).
Заголовок спойлера
test('fread + mem', $attempts, function() {
    $handle = fopen('php://memory', 'ab+');
    stream_copy_to_stream($fp = fopen(__FILE__, 'rb+'), $handle);

    while (! feof($handle)) {
        $char = fread($handle, 1);
    }

    fclose($handle);
    fclose($fp);
});


str_split    : 0.8551s
unpack       : 3.0591s
fread        : 1.2792s
$data[$i]    : 0.7279s
fread + mem  : 0.5827s
+1

код во while не выполняется


test('fread + mem',$attempts, function () {
        $handle = fopen('php://memory', 'ab+');
        stream_copy_to_stream($fp = fopen(__FILE__, 'rb+'), $handle);

        echo 'ftell:', ftell($handle), ', feof:', feof($handle) ? 'true' : 'false', PHP_EOL;
        while (!feof($handle)) {
            $char = fread($handle, 1);
        }

        fclose($handle);
        fclose($fp);
    }
);
+1
> Есть у меня смутное подозрение, что самописный конечный автомат будет для этой задачи сильно производительней (и, возможно, проще для понимания)

Для освоения идеи — наверно, да. Но постоянно такое писать слишком неудобно, а часто и сопровождать.

К счастью, такие возможности медленно, но планомерно проникают в средства.
Даже во flex есть, там это зовётся conditions. re2c — аналогично; вообще, слово conditions тут, похоже, становится основным, хотя я бы предпочёл contexts.
0

Вот, кстати и ответ на вопрос. Реализация на чистом конечном автомате (webonyx) проигрывает по скорости регуляркам примерно в два раза. Ну и прямо пропорционально по потреблению памяти в случае увеличения объёма сгружаемых туда данных. Можно попробовать самому убедиться, т.к. бенчи прилагаются: https://github.com/SerafimArts/graphql-bench

0
Есть два вопроса:
Почему бы не сделать конечный автомат, а апгрейдить регулярки?
Зачем использовать php для такого хардкора?

Я понимаю, что можно и даже проще так, особенно если пока нет более глубокого понимания, но очень хочется, но всё же…

И да, ещё более странно, что говоря о компиляторах, парсерах, лексерах — ни разу не всплыл термин «грамматика», и далее уж КС, ЛКС и вот это вот все…
0
Почему бы не сделать конечный автомат, а апгрейдить регулярки?

Насколько я понял вопрос — имеется ввиду «почему не запилить НКА, вместо использования регулярок»?

Если есть желание поэкспериментировать с этим и/или переписать какой-нибудь re2c на php с сомнительным результатом (т.е. я намекаю на то, что в PREG, написанном на сях вполне возможно будет это дело работать быстрее, нежели на нативном php), то пожалуйста. Лично мне было откровенно лениво это всё писать, а задачи ДКА/НКА переложил на LL(k) парсер.

Зачем использовать php для такого хардкора?

Потому что для PHP есть огромное количество задач, требующих качественного разбора текста в AST. В эпилоге я перечислил большинство из них.

Заголовок спойлера
В моём случае это был GraphQL SDL, который я реализовал полностью с нуля, включая парсер и «комплятор-компиляторов» грамматик: github.com/railt/railt/blob/master/resources/grammar/grammar.pp2, реализацию полноценного интерпретатора с прикручиванием отладчиков:

Но пилить до стабильной версии там ещё довольно много чего, хотя на продакшене уже кое-где используется.


И да, ещё более странно, что говоря о компиляторах, парсерах, лексерах — ни разу не всплыл термин «грамматика», и далее уж КС, ЛКС и вот это вот все…


Ну, как можно заметить по тексту — я сознательно постарался обойти остальные темы, упомянув их лишь вскользь и общими словами, чтобы просто иметь представление. А про BNF и EBNF стоит писать уже после раскрытия тем LL/LR/LALR/SLR парсеров, про которые понаписать можно довольно много чего.

P.S.
и далее уж КС, ЛКС

Эм? Что это за термины? Даже не гуглится ничего.
+1
Рискну предположить, что в терминах грамматик под КС подразумевалась группа контекстно-свободных грамматик (то, что идет у вас под перечислением LL/LR/LALR/SLR)
0
Хоть совершенно не люблю php и стараюсь его обходить, было интересно, особенно удивила обработка 600000 t/s.
Большое спасибо за материалы, сам сейчас занимаюсь разработкой языка, очень кстати подобные статьи, пилите еще, пожалуйста!))
P.S. А любителям Питона зайдет SLY, я думаю
+1

Я бы не хотел писать новую статью на эту тему, поэтому дополню в комментариях, думаю никто не будет против:


Есть один интересный ишью, который я создавал в группе Hoa: https://github.com/hoaproject/Compiler/issues/81


В комментариях к нему один из участников подсказал интересный способ — использовать *MARK символ + preg_match_all, вместо именованных групп + preg_replace_callback, о котором я написал в посте выше. Оказывается, этот вариант даёт ощутимый прирост производительности при использовании встроенного PCRE.


Для примера:
1) вот бенчмарки для multistate реализации preg_match (Hoa) vs preg_replace_callback + named groups (Railt): https://travis-ci.org/SerafimArts/lexer-benchmarks/jobs/506062681
2) а вот бенчмарки с обновлённой версией preg_match (Hoa) vs preg_match_all + mark (Railt): https://travis-ci.org/SerafimArts/lexer-benchmarks/jobs/508295208


И даже не учитывая того факта, что воркер для второго прогона в CI оказался чуть помедленнее первого — всё равно использование *MARK маркера даёт пятикратное ускорение.

Only those users with full accounts are able to leave comments.  , please.