Performance questions regarding C++ target

[Duttenheim]

Hello! I am using ANTLR to parse https://github.com/gscept/GPULang which I've been using for years prior. Until recently I haven't bothered much with thinking about small optimizations, such as memory placement and being able to release the compilers resources in a swift way.

Recently I have been begun replacing the std::vector, std::strings and whatnot with my own containers that manage memory in a smarter way than doing tons of tiny mallocs.

When profiling I noticed that ANTLR does tons of tiny mallocs, and was wondering whether or not anyone considered approaching memory management in ANTLR with a smarter approach? I think it could be a great benefit to the performance, especially for the C++ target where manual memory management is possible.

Another thing that would be amazing would be to fail early if the input text isn't for example UTF8 and then allow for the user to request string_view's into the original text buffer instead of constructing tiny strings everywhere (which is also a malloc hazard). Not sure how plausible that is.

Thanks,
Gustav

[kaby76]

@Duttenheim, You might want to first resolve ambiguity in your grammar, GPULang.g4. I stripped the grammar to essential EBNF (GPULang.g4.txt; using trparse GPULang.g4 | trquery -c strip.xq | trsponge -c), then ran diagnostics over the grammar (trperf .gpul (only those files from GPULang/code/test/shaders/.gpul that parse)). It says that you have a lot of ambiguity in the grammar, e.g., Decision 88 in suffixExpression for accesstest.gpul. No amount of optimizing C++ memory will overcome the huge inefficiency associated with an ambiguous grammar.

[Duttenheim]

I fixed the suffix and prefix to be direct left recursive. I run it with SLL prediction. It still tens of milliseconds to parse relatively small files (not the test ones, they are old).

I know ANTLRs C++ target has a warmup of static initialization which makes the first iteration significantly slower, which I've come to terms with. In fact I have my own warmup of static symbols which adds some small initial cost.

Mallocing all over the place and using shared pointers instead of having a more robust memory strategy will certainly not help. Not only is malloc and free slow, memory fragmentation becomes a real problem very quickly considering there are geometric properties to parse trees.

And while I understand there is an issue with knowing the UTF encoding before hand, it would certainly be more efficient to allow the user to deal with pointer ranges to the original CharStream, by first asserting its utf8/16/32 and work from that assertion.

Instead I'm forced to copy a string that already exists every time I read a token for which I need its text contents.

Thanks,
Gustav

[kaby76]

Yes, your grammar is really slow!

I grabbed the latest copy of your grammar, and it's still pretty ambiguous according to trperf.

For the grammar you just changed in the last couple of hours, the max-k for accesstest.gpul is 186, which means that it takes an enormous lookahead to work out Decision 88. Let's look at that and see what the rule is doing.

We see that Decision=88 is the rectangle at the far left, and we see that there are two transitions out of that. That's not a problem, but what is a problem is that they are both on the same symbol: binaryexpatom! That's not good.

It's a problem because Antlr keeps track of the set of NFA states for either transition with your input. In order to make a decision and continue the parse, it needs to decide which transition to take by reading a ton of lookahead.

The problem is that Antlr does not do left factoring. (Maybe it should, but that's another discussion.) LL parsers really need a grammar that is left factored.

Minus all the tree construction code, the rule currently is this:

suffixExpression:
      binaryexpatom
    
    (
        '(' 
            (
                  logicalOrExpression  (linePreprocessorEntry)? (','   logicalOrExpression  | linePreprocessorEntry)* 
            )? 
        ')'
        
        | '.'   suffixExpression
        
        | '->'   suffixExpression
        
        | '[' (  expression )? ']'
        
    )*
    |   binaryexpatom (  ('++' | '--')  )* 
    
    ;

After left factoring, it will be this:

suffixExpression:
    binaryexpatom
    (
	(
	    '(' ( logicalOrExpression  (linePreprocessorEntry)? (','   logicalOrExpression  | linePreprocessorEntry)* )? ')'
	    | '.'   suffixExpression
	    | '->'   suffixExpression
	    | '[' (  expression )? ']'
	)*
	| ('++' | '--')*
    )
    ;

That reduces the max-k to something more reasonable, 5 tokens for accesstest.gpul. That change alone accounts for a 30% speed up. But, your grammar still contains ambiguity. My suggestion is to work with the stripped down grammar and use that in something like Intellij to fix these problems.

You can preload a warmup to help the initial startup delay. But, the grammar is the issue.

[KvanTTT]

I don't recommend use ANTLR for anything that requires high performance. It's slow even if grammars are optimised. If they are not, ANTLR doesn't provide assistance with performance issues (at least statically).

[jimidle]

I don't recommend use ANTLR for anything that requires high performance. It's slow even if grammars are optimised. If they are not, ANTLR doesn't provide assistance with performance issues (at least statically).

It was written more for functionality, for sure, but there are very few things that need absolutely blinding parsing performance - almost all tools do way more work than the parser. However, performance problems are almost always in the grammar. This is the case here, though I agree with @Duttenheim that memory management will make a huge difference... but after addressing @kaby76 's comments. I did a lot of work on that for the C runtime in ANTLR 3.

All those separate xxxExpression need to be refactored as a single expression with precedence in mind. I don't like embedding code directly in the grammar as it will influence the parsing time, is difficult to read, and difficult to maintain, but that is personal preference really.

It needs:

expression:
     LPAREN expression RPAREN #exprPrec
    | MINUS expression #unaryMinus
    | expression AND expression
    | expression OR expression
    | expression PLUS expression
     

And so on - the problem is almost always the expression rule. Fix that first, then come back to memory management. In C++ it is easy enough to slot in substitutes for allocators, even without source code.

I would also move all that code into a visitor, which allows you to optimize it separately from the parser.

Jim

[KvanTTT]

almost all tools do way more work than the parser

It's true. Typically, lexer/parser takes a negligible small time of the full profile in compilers. For instance, recently I tested manually-written Kotlin parser and figured out that the parsing speed is extremely high, see the following measurements:

Number of tested files (kt, kts): 222833
Number of files with syntax errors: 11676
Number of chars: 605370336
Number of lines: 16228163
Number of parse nodes: 219933416
Parser total time: 44765 ms

It takes only 44 sec to parse more than 222K files, 6M lines of Kotlin code or more than 0.6B chars! But generally the Kotlin compiler is not as fast as we would like it to be, and it's not because of the parser (the parser takes only a couple of percents of the full compiler profile). And it would be even more sad if the parser was slower. I doubt that ANTLR-generated grammars can even parse it an order of magnitude slower.

However, performance problems are almost always in the grammar.

I believe that generator tools should warn about grammar performance problems or even prevent generating slow parsers. Actually, some time ago I started work on such a tool (based on ANTLR grammars), but there are still a lot of things to do to make it robust. But it's a topic for an another discussion.

[Duttenheim]

Hello everyone!

I took what you said to heart and worked on the grammar a bit to make it less ambiguous, and you were totally right that it did improve performance.

Even so, I still find it a little bit disappointing that the parsing is the largest bottleneck in the compilation process. Unless there really are other major issues with the grammar, should I settle with this as it is right now? Would like to hear your thoughts.

Thanks,
Gustav