Как оценивать Boost Spirit Parser? - программирование

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

Мой парсер - парсер Boost Spirit с lexer (с lexer:: pos_iterator), и у меня есть грамматика среднего размера. Я разбираю источник в АСТ.

Моя проблема заключается в том, что я понятия не имею, что занимает больше всего времени при разборе: копии узлов AST, lexer, правил парсера или памяти.

Я не думаю, что это проблема ввода-вывода, поскольку я работаю над SSD и что я полностью читаю файл в начале, а затем использую только версию памяти.

Я пробовал использовать профилировщики, но методы, требующие времени, - это некоторые методы из Boost с именами длиной в сотни символов, и я точно не знаю, что они делают...

Итак, есть ли предпочтительный способ сравнить Boost Spirit Parser и его грамматику? Или существуют некоторые правила, которые можно использовать для проверки эффективности в некоторых конкретных точках?

Ответы

Ответ 1

Я быстро прочитал все.

Мой профайлер быстро сказал мне, что построение грамматики и (особенно) объекта lexer заняло довольно много ресурсов.

Действительно, просто изменение одной строки в SpiritParser.cpp сохранено 40% времени выполнения ¹ (от ~ 28 с до ~ 17 с):

    lexer::Lexer lexer;

    static const lexer::Lexer lexer;

Теперь

делает статичность грамматики подразумевающей ее безгражданность. Я сделал это через
- перемещение position_begin в qi::_a (с помощью qi::locals) и
- передать его как унаследованный атрибут в соответствующие моменты
  - грамматики EDDIGrammar и ValueGrammar, например
```
start %= qi::eps [ qi::_a = qi::_r1 ] >> program;
```
  - а также отдельные правила из ValueGrammar, которые используются снаружи).
Это имело ряд субоптимальных побочных эффектов:
- Отладка правил закомментирована, потому что lexer::pos_iterator_type не имеет перегрузки по потоку вывода по умолчанию
- выражение qi::position(position_begin) было "подделано" с довольно сложной заменой:
```
auto local_pos = qi::lazy (
        boost::phoenix::construct<qi::position>(qi::_a)
    );
```
  Это не кажется идеальным. (В идеале хотелось бы заменить qi::position на модифицированную настраиваемую директиву парсера, которая знает, как получить get begin_position из qi:: locals (?), Поэтому не нужно было бы призывать выражение парсера лениво?)

В любом случае применяя эти дальнейшие изменения ² сбрил еще ~ 15% времени выполнения:

static const lexer::Lexer lexer;
static const parser::EddiGrammar grammar(lexer); 

try {
    bool r = spirit::lex::tokenize_and_parse(
            position_begin, position_end,
            lexer, 
            grammar(boost::phoenix::cref(position_begin)),
            program);

Свободные идеи:

Рассматривали ли вы создание статического лексера (Генерация статического анализатора)
Рассматривали ли вы возможность использовать точки ожидания, чтобы потенциально уменьшить количество обратного отслеживания (примечание: я ничего не измерял в этой области).
Рассматривали ли вы альтернативы для Position::file и Position::theLine? Копирование строк кажется более тяжелым, чем необходимо. Я предпочитаю хранить const char *. Вы также можете посмотреть Boost Flyweight
Требуется ли предварительный провал внутри вашей директивы qi::position?
(Немного несерьезно: считаете ли вы портирование на Spirit X3? Кажется, обещают потенциальные преимущества в форме семантики движения.)

Надеюсь, что это поможет.

^[1] При синтаксическом анализе всех тестовых примеров в test/cases/*.eddi 100 раз так (github):

for (int i=0; i<100; i++)
    for (auto& fname : argv)
{
    eddic::ast::SourceFile program;
    std::cout << fname << ": " << std::boolalpha << parser.parse(fname, program, nullptr) << "\n";
}

С простыми

time ./test ../../test/cases/*.eddi | md5sum

С помощью md5sum, действующего как проверка работоспособности.

^[2] Я создал запрос на перенос с рефакторингом доказательной концепции здесь https://github.com/wichtounet/eddic/pull/52