search

antlr / antlr4

ANTLR (ANother Tool for Language Recognition) is a powerful parser generator for reading, processing, executing, or translating structured text or binary files.
http://antlr.org
BSD 3-Clause "New" or "Revised" License
17.17k stars 3.28k forks source link

Very Slow Parsing Speed on Swift Target #1920

Closed hanjoes closed 7 years ago

hanjoes commented 7 years ago

Recently I'm using Swift target to parse some real world Swift files (using this grammar). The speed is really slow. It never finish. (Well, it finishes next day when parsing, for e.g., this file).

Some simple debugging shows the performance bottle neck lies in the "adaptivePredict" method in ParserATNSimulator. To be more specific, most of the CPU resource were spent on execATN method in the ATN simulator.

I'm still trying to find the root cause, this issue is used to track this performance issue. Also, suggestions are very welcome!

hanjoes commented 7 years ago

@parrt Looks like the performance of Swift target is acceptable after compiling using release mode. Parsing the same production file that cost ~2400+ seconds under debug mode only took ~470 seconds under release mode. This is slower than the java target ~145 seconds, but performance optimization doesn't seem a top priority anymore to me. What do you think?

image

Also by using the Xcode profiler (screenshot above) it seems to me one possible performance bottleneck will be the "HashMap", "DoubleKeyMap" implementation which is mimicking the Java data structure which is heavily used in the code base.

As of the ATN implementation I'm not very clear how good it is, but if the original author migrated the Java behavior it should not be too bad? The stack trace in the Xcode profiler is comprised mostly of recursive calls to closure_ and closureCheckingStopState. I think the granularity of the profiler limits us to only see the most time-consuming sub-function calls, but it seems most of the time was spent in executing those recursive calls themselves (the self column in the profiler, each call takes 10~150 ms, but probably the culprit is still the HashMap implementation.)

hanjoes commented 7 years ago

BTW, the above is just a tip of an iceberg, the whole stack trace is too big to put in one graph :)

parrt commented 7 years ago

Wow. so debug mode is REALLY slow in Swift, eh? Ok, maybe we should update the doc to indicate this? Yep, the closure and similar is where all of the parsing work occurs.

hanjoes commented 7 years ago

Yeah. I will add it to Swift target doc.

Ideally I expect the performance to be better than Java target, but still need some experimentation to figure out the root cause why it's slower..if I can eventually figure it out.

hanjoes commented 7 years ago

Closing this for now since we've updated swift doc in PR #1979.