what is the DFA Cache miss shown by ANTLR4 profiler in IntelliJ?

Question

what is the DFA Cache miss shown by ANTLR4 profiler in IntelliJ?

I can see that the DFA Cache miss has to do with increased parse time. What can I do to reduce it? Any Examples?

Answer 1

(Referencing the Adaptive LL(*) Parsing: The Power of Dynamic Analysis paper)

ALL(*) parsers memoize analysis results, incrementally and dynamically building up a cache of DFA that map lookahead phrases to predicted productions.

Creating a different lookahead DFA for each possible parser call stack is not feasible since the number of stack permutations is exponential in the stack depth. Instead, we take advantage of the fact that most decisions are not stack-sensitive and build lookahead DFA ignoring the parser call stack.

DFA Cache misses are how ANTLR builds up a DFA cache to optimize performance, so they are to be expected during "warm-up", as ANTLR encounters lookaheads for which it can cache a DFA.

I'm pretty sure that 5 DFA cache misses (and the fact that your input is one 266 character line), means that you can't read anything at all into the number of cache misses.

It starts to become a useful metric once you've run a reasonable volume of expected input through the parser. For best performance, it should start to "settle in" and see fewer and fewer situations where it hasn't already cached the DFA.

If, on a large corpus of input you see the cache misses continue to climb, then there is an indication that the complexity of your grammar may be causing issues.

You should probably, first determine if DFA cache hits are truly a performance problem for you (by running a large volume of input through your parser and watching for whether the cache miss rate drops reasonably over time.

If you, then see that it's an issue, you will probably have better luck posting a question more specific to your grammar re: why the rate never settles in. Maybe someone will comment on some common reasons for this (I don't really have any sort of check list).