Come eseguire il benchmark del parser di Spirit Boost?

Question

Sto lavorando su un compilatore e vorrei migliorare le sue prestazioni. Ho scoperto che circa il 50% del tempo è dedicato all'analisi dei file sorgente. Dato che il file sorgente è piuttosto piccolo e dopo molte trasformazioni, mi sembra che sia perfetto.

Il mio parser è un parser Boost Spirit con un lexer (con lexer :: pos_iterator) e ho una grammatica di medie dimensioni. Sto analizzando la fonte in un AST.

Il mio problema è che non ho idea di cosa impiega più tempo durante l'analisi: copie di nodi AST, lexer, regole del parser o memoria.

Non penso che sia un problema I/O dal momento che sto lavorando su un SSD e che sto leggendo il file interamente all'inizio e quindi utilizzando solo la versione di memoria.

Ho provato ad utilizzare profiler, ma i metodi che richiede tempo sono alcuni metodi da Boost con i nomi centinaia di caratteri e non so esattamente quello che fanno ...

Quindi, c'è un modo preferito per valutare un Boost Spirit Parser e la sua grammatica? O ci sono alcune regole che possono essere utilizzate per verificare l'efficienza in alcuni punti specifici?

Grazie

Fonti per chi è interessato:

• Parser
• GrammarGrammarGrammar
• Lexer

Answer 1

ho dato le cose una scansione rapida.

Il mio profiler mi ha detto rapidamente che la costruzione della grammatica e (soprattutto) l'oggetto lexer ha richiesto un bel po 'di risorse.

Infatti, cambiando solo una singola linea in SpiritParser.cpp risparmiato il 40% del tempo di esecuzione (~ 28s fino a ~ 17s):

lexer::Lexer lexer; 

in

static const lexer::Lexer lexer; 

Ora,

• mak la grammatica statica implica renderla stateless. Ho fatto che questo avvenga,

  • movimento position_begin in qi::_a (utilizzando qi::locals) e

  • passandolo come un attributo ereditato nei momenti opportuni

    • grammatiche EDDIGrammar e ValueGrammar, ad esempio

      start %= qi::eps [ qi::_a = qi::_r1 ] >> program; 
      

    • nonché le singole regole dalla ValueGrammar che vengono utilizzati esternamente).

  Ciò ha avuto un certo numero di effetti collaterali non ottimali:

  • regola il debug è commentata perché il lexer::pos_iterator_type non ha output predefinito in streaming sovraccarico

  • l'espressione qi::position(position_begin) è stato 'falsificato 'con una sostituzione piuttosto elaborata:

    auto local_pos = qi::lazy (
         boost::phoenix::construct<qi::position>(qi::_a) 
        ); 
    

    Non sembra l'ideale. (Idealmente, si vorrebbe sostituire qi::position da una versione modificata di direttiva parser personalizzato che sa come ottenere ottenere begin_position da Qi :: gente del posto (?) Quindi non ci sarebbe alcun bisogno di invocare un parser di espressioni pigramente?)

in ogni modo, implementing these further changes²radere altri ~ 15% del tempo di esecuzione:

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); 

idee allentati:

• avete considerato la generazione di un lexer statico (Generating the Static Analyzer)
• Hai pensato di usare i punti aspettativa di potenzialmente ridurre la quantità di backtracking (nota: non ho nulla di misurare in quella zona)
• Avete alternative considerate per Position::file e Position::theLine? Copiare le stringhe sembra più pesante del necessario. Preferirei memorizzare const char *. Puoi anche guardare Boost Flyweight
• Il pre-skip è davvero necessario all'interno della direttiva qi::position?
• (Un po 'non gravi:? Avete considerato porting per Spirit X3 sembra promettere potenziali benefici sotto forma di semantica move.)

Spero che questo aiuti.

---

^[1] Quando analizza tutti i casi di test in test/cases/*.eddi 100 volte 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"; 
} 

temporizzato con un semplice

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

Con la md5sum agisce come un controllo di integrità.

^[2] ho creato una richiesta di pull con il refactoring proof-of-concept qui https://github.com/wichtounet/eddic/pull/52