Analyzer: Single-Pass vs. Multi-Pass
I recently wrote about the new lexer and parser in IronJS, giving a 8x performance boost to parsing. Over the past two days I’ve been looking at the AST analyzer IronJS has been using, and how to improve it. The analyzer steps through the AST produced by the parser and figures out things like closures, static types, dynamic scopes, etc. Due to the non-mutable nature of discriminated unions in F# it has been forced to re-build the syntax tree to resolve everything it needs to, since it sometimes required changes to, it has also been a doing several passes over the syntax tree.
I’m glad to announce that with some clever use of reference cells I’ve been able to both eliminate the need to re-build the AST and also, due to having access to the internals of the new TDOP-based parser, manged to make it require only a single pass over the syntax tree, the performance difference is pretty staggering.
As you can see with both the new parser and analyzer it’s a whopping ~13x faster then the old ANTLR based parser and multi-pass analyzer. It’s also ~4x faster then the new parser with the old multi-pass analyzer.