Как сравнить Boost Spirit Parser?

Question

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

Моего анализатор Дух анализатор подталкивание с лексером (с лексическим анализатором :: pos_iterator) и у меня есть грамматик среднего размера. Я разбираю источник в АСТ.

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

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

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

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

Благодаря

Источники для тех, кто заинтересован:

• Parser
• GrammarGrammarGrammar
• Lexer

Answer 1

Я дал вещи быстрое сканирование.

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

В самом деле, просто меняя одну строку в SpiritParser.cpp сохранено 40% времени выполнения (~ 28s до ~ 17s):

lexer::Lexer lexer; 

в

static const lexer::Lexer lexer; 

В настоящее время

• mak статичность грамматики включает в себя создание безгражданства. Я сделал это случилось с

  • перемещение 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 модифицированным пользовательской директивы парсера, который знает, как получить получить begin_position от ци :: местных жителей (?), Так что не было бы никакой необходимости вызывать выражение парсер лениво?)

в любом случае, implementing these further changes²сбрил еще 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); 

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

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

Надеется, что это помогает.

---

^[1] При анализе всех тестовых случаев в test/cases/*.eddi 100 раз like so (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"; 
} 

Timed с простой

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

С md5sum действует в качестве проверки вменяемости.

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