Jul 23

Mike Lewis posted a marvelous experience report dubbed ‘Optimizing Boost Spirit – Blazing fast AST generation using boost::spirit’. He describes how he took an old compiler for the Epoch programming language (which was based on Spirit.Classic) and tuned it for performance using Spirit.Qi and Spirit.Lex. His results are exceptional, he got roughly a thousand fold speedup compared to the old version. The complete code for his compiler can be downloaded from here.

He writes:

This code illustrates several advanced techniques for parsing large inputs with complex Spirit grammars:

  • Deferred construction and minimal copying of attribute values
  • Lexical analysis for faster backtracking
  • A special directive for using qi::symbols alongside a lexer
  • Linear allocators for faster AST node allocation
  • Intrusive reference counting for even faster AST node allocation/copying
  • Grammar transformations for general optimality
  • Abuse of the &-predicate for skipping expensive productions
  • Dividing grammars into multiple implementation files for minimal recompilation times

Thanks Mike for sharing your work! I’m sure many Spirit developers will find it very enlightening and encouraging to read about your work. Keep up the excellent work!

2 Responses to “How to Optimize Qi”

  1. Gordon says:

    with respect to this, what will be the future of utree? This describes the ‘classical’ approach of generating an ast.

  2. Rob Stewart says:

    There appear to be many good bits of information in that post that should be part of Spirit’s own documentation. Indeed, examples could be constructed to illustrate each of the suggested changes.

    At the least, I think there should be an Optimizing Spirit section in the documentation that notes when using Lex is worthwhile, that explains the costs of attribute copying and the attendant benefit of using shared_ptr and intrusive_ptr, and the benefit of using the raw directive. Whether the “Deferred Construction Wrapper” or “adapttokens” directive are worth describing or even incorporating into Spirit are separate matters. It makes sense to discuss these topics outside the normal line of the documentation because their importance only comes to the fore once a parser works. (I’m sure Hartmut and others with Karma experience can provide information on optimizing the use of that library, too.)

Leave a Reply

preload preload preload