Improving eddic Boost Spirit parser performances
After the last changes on the data-flow framework, the parsing pass of the eddic compiler became the slowest one. I was sure there was some area of optimizations, so I decided to improve its performances.
In this post, I will present the different techniques I applied and their results.
Static grammar
The first optimization that I tried was to make the grammar static, meaning that we can declare it static and it will be constructed only once and will be allocated on the data segment.It is indeed heavy to build the lexer especially but also the grammar. I would like to thank sehe for this optimization, he found it after I posted a question on Stackoverflow.
The lexer was very easy to make static (only add static keyword :) ), but the parser was a bit more complicated because it needs the lexer iterator to get the current position in the file. This problem has been resolved by saving the iterator into the qi::locals of the rules.
The result of this optimization are amazing. It saved 33% of the time.
Expectation points
Expectation points have the interesting point that they disallow backtracking and so can improve performances in some cases. Moreover, they are always interesting because they make the grammar clearer and the error messages much better.
I tried adding more expectation points to the grammar. Unfortunately, there weren't a lot of them to add. Moreover, it seems that there are some quite weird behavior with them because some times it is impossible to add them (causes compilation failure) and sometimes it just make the code don't work anymore the same way, though I don't understand why.
Anyway, I have been able to add some to the grammar. These changes improve the performance by a bit more than 1%. It is not a lot, but it is still an improvement. Moreover, I'm quite sure that there are more expectation points that can be added to the code. I will take some time again later to try to add more and to understand them better.
Less skips
In my grammar, I've a special parser for getting the current position in the file to add "debug information" to the AST. This special parser was skipping over its content, but it has no content, since it is artificial. Removing it improved the performance by about half a percent.
Improve Position (debug information)
As said before, there is a special parser to get the current position in the file. This information is then stored into an eddic::ast::Position structure. This structure was holding the line number, the column, the file name and the contents of the line. The first two were ints and the last two were std::string. Each time, a copy of the strings were necessary.
I avoided storing the std::string directly by storing only the number of the line as well as the index of the file. Then, the content of the file is stored in the global context and can be accessed if it is necessary to display the line where the error happened.
This change gave an increase of 10% of the parsing performance.
Auto Rules
Rules in Boost Spirit have an overhead due to the cost of the virtual calls that are necessary. In theory, auto rules can improve the efficiency of the rules by removing the cost of virtual calls. Moreover, auto rules should also avoid code bloat when the rules are compiled. The rules can be inlined and better optimized.
I transformed some rules to auto rules to improve performances. Unfortunately, I found that this did not improve the performances. Moreover, transforming some rules to auto rules made the performance worse. I still did let some of the rules as auto rules. I have to say that I was very disappointed by this result, I was really expecting more from this :(
Generated Static Lexer
The first time the lexer is used, it has to generate the Deterministic Finite Automaton (DFA) that is used to identify the different tokens. This process takes time. There is way to avoid this by using the static model of Boost Spirit Lex. With that, the code is generated with the complete DFA and then it doesn't have to be initialized again.
I was not expecting a lot from this because the lexer was already static and so was initialized only once. Indeed, it resulted in less than half a percent improvement.
Conclusion
Even if I've been able to largely reduce the overhead of the parsing by more than 40%, it still has a big overhead. Indeed, it still represents 36 percent of the whole process of compiling a source file. I think it is still too much.
Moreover, an interesting fact is that the optimization I would have thought to be very effective (auto rules especially) did not have the expected effect, but making the grammar static, which I would not have thought of, was very effective.
When profiled, the final version shows that quite some time is spent in destructing the multi_pass, which is quite odd. And it also seems that transforming the string operators to ast::Operator is not very effective, but I do not know how to improve that at this point.
I won't probably work on that again for the version 1.2.4 of eddic, but I will eventually take some time again for the version 1.3.0 to improve it again.
Comments
Comments powered by Disqus