Wie Benchmark Boost Spirit Parser?

Question

Ich arbeite an einem Compiler und möchte seine Leistungen verbessern. Ich habe festgestellt, dass etwa 50% der Zeit damit verbracht wird, die Quelldateien zu analysieren. Da die Quelldatei ziemlich klein ist und ich danach eine ganze Reihe von Transformationen mache, scheint es für mich perfekt zu sein.

Mein Parser ist ein Boost Spirit Parser mit einem Lexer (mit lexer :: pos_iterator) und ich habe eine mittlere Grammatik. Ich analysiere die Quelle in einen AST.

Mein Problem ist, dass ich keine Ahnung habe, was die meiste Zeit beim Parsen kostet: Kopien von AST-Knoten, Lexer, Parser-Regeln oder Speicher.

Ich denke nicht, dass es I/O-Problem ist, da ich an einer SSD arbeite und dass ich die Datei vollständig am Anfang lese und dann nur die Speicherversion benutze.

Ich habe versucht, Profiler, aber die Methoden, die Zeit in Anspruch nimmt einige Methoden-Boost mit Namen Hunderte von Zeichen lang sein und ich weiß nicht genau, was sie tun ...

So ist es eine bevorzugte Art und Weise unter Verwendung von einen Boost Spirit Parser und seine Grammatik zu benchmarken? Oder gibt es einige Regeln, mit denen die Effizienz an bestimmten Punkten überprüft werden kann?

Dank

Quellen für Interessenten:

• Parser
• GrammarGrammarGrammar
• Lexer

Answer 1

ich die Dinge einen schnellen Scan gegeben haben.

Mein Profiler sagte mir schnell, dass das Konstruieren der Grammatik und (vor allem) des Lexer-Objekts einige Ressourcen in Anspruch nahmen.

der Tat nur eine einzige Zeile in SpiritParser.cpp Ändern gespeichert 40% der Ausführungszeit (~ 28s bis ~ 17s):

lexer::Lexer lexer; 

in

static const lexer::Lexer lexer; 

Jetzt

• mak Wenn die Grammatik statisch ist, bedeutet das, sie staatenlos zu machen. Ich habe dies geschehen durch

  • position_begin in qi::_a Bewegen (mit qi::locals) und

  • es als vererbte Attribute zu den entsprechenden Zeiten vorbei

    • die EDDIGrammar und ValueGrammar Grammatiken, z.B.

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

    • sowie die einzelnen Regeln aus, die ValueGrammarextern) verwendet werden.

  Dies hatte eine Reihe von suboptimalen Nebenwirkungen:

  • Regel Debuggen kommentiert, weil die lexer::pos_iterator_type Überlastung keine Standardausgabe hat Streaming

  • der qi::position(position_begin) Ausdruck ‚gefälscht wurde 'mit einem ziemlich aufwendigen Ersatz:

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

    Das scheint nicht ideal. (Idealerweise möchte man qi::position durch eine modifizierte benutzerdefinierte Parser-Richtlinie ersetzen, die weiß, wie begin_position von Qi zu bekommen bekommen :: Einheimischen (?) So gäbe es keine Notwendigkeit, einen Parser Ausdruck aufzurufen lazily?)

Sowieso implementing these further changes² weitere ~ 15% der Ausführungszeit abrasiert:

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

lose Ideen:

• Haben Sie darüber nachgedacht, eine statische Lexer zu erzeugen (Generating the Static Analyzer)
• Haben Sie Erwartung Punkte mit in Betracht gezogen, um potenziell die Menge der Rückzieher zu reduzieren (Anmerkung: Ich messe nichts in diesem Bereich)
• Sie haben überlegte Alternativen für Position::file und Position::theLine? Das Kopieren der Strings scheint schwerer als nötig zu sein. Ich würde lieber const char * speichern. Sie könnten sich auch Boost Flyweight ansehen
• Ist der Vorabsprung wirklich in Ihrer qi::position Richtlinie erforderlich?
• (etwas nicht ernst: Sie haben zu Spirit X3 Portierung betrachtet Es scheint in der Form von bewegen Semantik potenziellen Vorteile versprechen.)

Hoffnung, das hilft.

---

^[1] Wenn alle Testfälle in test/cases/*.eddi 100 mal Parsen 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 mit einem einfachen

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

Mit dem md5sum als Plausibilitätsprüfung handeln.

^[2] habe ich eine Pull-Anforderung mit den Proof-of-Concept-Refactorings hier https://github.com/wichtounet/eddic/pull/52