Performance tips

[binarycow]

I notice that in your benchmarks, RCParsing generally allocates a lot more memory than the other alternatives. Additionally, it's generally slower, unless specific optimizations are turned on.

Can you provide some performance tips? What optimizations should we turn on, and when? What are the drawbacks of those optimizations (I assume they have drawbacks, which is why they're off by default?)

[RomeCore]

Yes, RCParsing can be slower due to lexerless approach (where ANTLR uses lexer-based algorithms that grants linear speed) and uses AST mode with lazy value calculation by default (where combinators, such as Parlot and Pidgin and RCParsing token combinators calculates values immediately).

There is optimizations that can be used:

• UseFirstCharacterMatch(): Choice* token patterns and rules will match children based on first character, for example, we have choice of literals "ab" (first: 'a'), "ac" (first: 'a'), "cb" (first: 'c'); when matching "ac", choice rule will first try to match "ab" and fails -> then tries "ac" and matches it, even if it fails, choice will not try to parse "cb"; but when matching "cd", choice rule will directly (based on 'c' first character) try to match "cb" and fails -> that leads to entire choice rule fail; if we try to match "dd", the choice rule will immediately fail without trying anything, because we don't have any choice path for this character. The drawbacks is: maybe high memory usage (it allocates table for lookups, i think its ~35 KB per rule) and bad debug (since it can bypass some rules to parse and they won't report that they failed). This optimization is pretty safe and precize, even if we have Regex in choices, it will be considered non-deterministic and will be tryed anyway. And if we have Optional* parts in choices, the first character sets will calculated correctly (e.g. sequence "ab"?"bc" calculates into -> ['a', 'b']). So, this optimization is very effective and safe, the only disadvantage is worse debug experience and error messages (some expected rules can be missing).

• UseInlining(): Some rules will not call the Parser instance to parse child rules and call the rules directly where it can be considered safe (Parser.ParseRule(RuleId, ...) -> Rule.Parse(...)), which can pass rule skipping and some things (such as stack trace writing). This method is called Inlining because acts a bit similar way as the inlining in programming languages does (just pastes function assembly code into the caller's function assembly code). For example, Choice rule will try to inline all child rules, and Sequence rule will try to inline only first rule. Rule can be inlined if it has not overriden settings. This thing is safe too, but can tamper the stack trace, which impacts on debug. I may improve this optimization later, due to not all rules using it currently.

• UseCaching(): Uses Packrat memoization, which writes rule parsing results in cache and tries to retrieve results from it. Useful when you find out that some rules can be parsed multiple times at one position. It may be not optimization at all, should be used only on complex grammars. In JSON it makes ~2.5x slowdown and high memory usage (~3.0x as i remember), but in Python 3.13 it leads to better memory usage (~2.0x less) and ~2.5x faster parsing speed, but it currently may be incomatible with barrier tokens (if they have 0 length, such as INDENT and DEDENT in Python), this is because cache does not counts the passed barriers count. In my experience, this thing (caching) can save you from millions of errors (seriously) and very slow parsing speed (the entire seconds) if input have syntax errors, i seen it when developing LLT language, you can see it here. Also, when using incremental parsing it also can save from cascade re-parsing (in theory, not tested yet). So, when using simple grammar -> turn it off; when using complex grammar without optimizations -> turn it on. It does not impacts on debug, if you want to know.

• SkipWhitespacesOptimized(): Parser will direclty skip whitespaces (spaces and newline characters) directly before every rule, without using any skip strategies and skip rules. Use when you don't have complex skip rules, such as comments.

• IgnoreErrors(): Does not records parsing errors at all; when parsing fails, you will get just "Unknown parsing error.". That's all. It just slightly impacts on performance, -8% in the JSON grammar.

But remember, you can apply these settings per rule and token, UseFirstCharacterMatch() applies ParserInitFlags.FirstCharacterMatch init flag, UseInlining() -> ParserInitFlags.InlineRules, UseCaching() -> ParserInitFlags.EnableMemoization, just use the builder.Settings.UseInitFlagsOn(flags, e => e is ParserRule && e.Aliases.Contains("your_rule_name")). But for SkipWhitespacesOptimized() it's the global Parser setting, which cannot be applied per rule. And IgnoreErrors() is inheritance setting, this means that you can apply it to "skip" rule that may be a choice of child rules, and they will inherit that setting and they will not record settings too. You can read this article for some more info.

TL;DR:
So, UseFirstCharacterMatch() if you are not care about basic debug, UseInlining() if you are not use stack traces, UseCaching() if your grammar is complex, SkipWhitespacesOptimized() if you are not have comments in your grammar, IgnoreErrors() for just validation or just calculation, without debug.

And the one important thing: Tokens! They are used as parsing primitives, they don't have settings (except for init flags) and they cannot record tons of errors (except for the furthest one). They have intermediate values that are specific for every token type, for Regex it can be Match, for Number it can be int or double, based on configuration, just read this article for more info. The main insight that they not store any AST, they just calculates values immediately, doing minimal allocations. Parlot, Pidgin and other combinators uses similar approach, so comparing RCParsing AST mode to them is not fair at all. Rewriting parser to token combination style can grant x6.0 faster parsing speed and much better memory usage! Also remember that you can mix these two approaches (AST with lazy and powerful transformations and combinators with fastest zero-overhead immediate transformations).

[RomeCore]

I created release where UseCaching() normally works with barrier tokens.