Find Methods Can Be Innefficient

[piacenti]

I recently started parsing and processing files that need to be done as fast as possible and noticed while profiling some slowness while navigating the context tree. I noticed that the find methods use a solver which will loop over a list of defined types every time they are called. While not a problem most times, it becomes a problem when doing those operations many many times and it gets worse as the grammar gets more and more parser rules. I suggest that those solver.getType methods look up the types by index rather than by name, so the generated code would be O(1) rather than O(n) like it is today. A map of string to types would also possibly work but would likely be slower since map hash for strings require iterating through it so it won't really be O(1)

[lppedd]

Thanks! I'll take a look tomorrow.

[lppedd]

As a general rule, we want to match the Java runtime, but if performance is critical I'm ok to change it, keeping the same semantics.

[lppedd]

I suppose you mean the following call stack, right?
Taking as example the generated MiniCalcParser, we have:

LineContext.findStatement()
  ParserRuleContext.getRuleContext()
    ParserRuleContext.getChild()

getChild loops over an array of children

public var children: MutableList<ParseTree>? = null

[lppedd]

Btw, which version are you using?

[piacenti]

The Java version just uses the class directly so it doesn't do a lookup for it. I checked to see if suffered from the same problem. The difference comes from supporting others platforms like JS.

I'm actually using a fork since some projects I use this don't allow usage of jitpack. I've fixed this problem as well as others in my fork but also removed some stuff I don't use, like the entire native support. I also added some functionality not officially supported by antlr4 like fragment parser rules. I generally have picked up the main updates coming from this repo though.

Looks like the project is back on maven Central so I might at some point merge changes between both and contribute back. For now this issue is just an FYI.

[lppedd]

This repository has changed quite a lot in the past month. It's now completely on par with the Java target and runtime, plus Kotlin-specific enhancements. You'll find many breaking changes at the type level.

If you feel like some of the things you added might benefit everyone, just open a PR.

[piacenti]

Awesome, thanks. I will take a look

[piacenti]

this looks to be fixed in latest version

[lppedd]

Thanks! I will soon get #162 fixed too.