Grammar that parses in milliseconds in Java runtime, takes many seconds in python #1219
Comments
|
This program takes 5 seconds to parse |
|
Hi |
|
Hi Eric, I did look at #1218 (mentioned it as a recent fix), and checked out build where it was fixed. It did effect the performance a bit (20-30%), but still the very long parse times compared to Java are there. The numbers given are on the build from: Jun 23 08:54:27 2016 -0700 |
|
Hi,
Eric Envoyé de mon iPhone
|
|
Hi Eric, Yes, the goal is to parse in Python only. Could you recommend some techniques to optimize the grammar for Python runtime? Thanks! |
|
I don't buy it. ANTLR is supposed to produce RD parsers comparable in efficiency to hand written ones. Python is slow but it's not that flipping slow. Something is not right here. I know I could manually write one that would beat this hands down. I don't think it's the parser, I suspect python's malfunctioning. I happen to have generated code left over from looking at this Q on stackoverflow. My first suspicion is on the fat and mostly constant expressions like this
AFAICS the only variables in there is _la. Machine generated stuff is famous for breaking compilers/interpreters and I think this may be a possibility. 2nd thought is garbage collection. I'd like to know how much GC is being done. My suggestion is yes, this may be an antlr issue indirectly but my primary concern would be python. I suggest you take this up in a python newsgroup and ask for guys with python profiling and python internals experience to have a look. Sorry I can't suggest anything else, very busy ATM. |
|
If you need speed, then you should consider changing targets. You are flogging a dead horse trying to get performance from Python. If you just need it to be a little faster, then buy all means pursue. Jim
|
|
@jimidle: to say that is to say that the python target in ANTLR is functionally unusable, in which case it should be deprecated ASAP to stop other people from going down that blind alley. |
|
Hi, Envoyé de mon iPhone
|
|
As Eric says, getting a target to work perfectly does take time. But even if it is now perfect it will not perform like the other targets. Lots of good uses for Pythonand many tasks are not driven by performance, though I feel that Python will get better in this regard as time goes on. On Mon, Jun 27, 2016 at 12:32 AM +0800, "ericvergnaud" notifications@github.com wrote: Hi, Many people use Python as a wrapper around c++ libraries, so they get the feeling that it's not that slow. Pure Python is 20-30 times slower than Java, not my say, but what benchmarks say. As we've seen recently, there is a possibility that the Python runtimes don't behave like the Java runtime in terms of performance, due to bugs which prevent algorithmic optimizations. Add to that the fact that the current optimizations were tuned for Java and C#, there is also a possibility that they hit slow parts of Python. It will just take time to identify specific patterns that need further Python specific implementations. That said, there are plenty of good use cases for a not so fast Python parser. People who choose Python in the first place are not looking at performance as a key driver. So no reason to deprecate it. Eric Envoyé de mon iPhone
— |
|
Hi Do you have a simple archive to download that would contain everything needed to reproduce that issue ? |
|
Hi! You can grab the whole thing from the git repository: https://github.com/pavelvelikhov/pythonql I'll try a few things over the weekend (e.g. removing all the grammar added to the original Python3 grammar) and I'll add a launcher with a profiler. |
|
Hi! I've taken out all my productions that were in addition to the Python3 grammar, which is on the official ANTLR4 grammar repository. The speed is about the same, so the original Python3 grammar parses very slow as well. |
|
Regarding my prior thought about performance being caused perhaps by giant expressions, I stripped down one and iterated it 1000 times, updating _la in the loop to prevent result caching, and it took under a second so it's not that. I'm even more suspicious now about garbage & GC. |
|
I encountering performance issues with ANTLR's python target also, and I've compared my grammar on cpython and pypy -- both were at least thousand times slower than java counterparts.. It drives me to the conclusion that it's probably still due to the inefficient translated code or the python runtime code. Like one of the previous comments suggested, people in python community interested in speed usually uses C/C++ extensions. Considering that we've already have a C++ antlr target, having an ANTLR python target based on C++ extension is very practical and will be tons lot useful than the current python target! I can get hands on contributing when I get some time later, but right now this might be a good idea to anyone who might be interested in such an idea. |
|
@pavelvelikhov hi! heh, can you check again due to recent fix? #1441 |
|
Hi Terence,
Will try this again soon!
Best regards,
Pavel
… On 11 Dec 2016, at 01:47, Terence Parr ***@***.***> wrote:
@pavelvelikhov <https://github.com/pavelvelikhov> hi! heh, can you check again due to recent fix? #1441 <#1441>
—
You are receiving this because you were mentioned.
Reply to this email directly, view it on GitHub <#1219 (comment)>, or mute the thread <https://github.com/notifications/unsubscribe-auth/AEJ74RLvVFAZQoCtSRDZ5bBlQeAHQTKPks5rGyv-gaJpZM4I9KOU>.
|
|
@pavelvelikhov take a look at the last comment in #1540. I would be interested to know if it's a similar issue. |
|
@pavelvelikhov still an issue? I'd like to know if I can close. |
|
Hi Terrence, checked out an older version of pythonql, still a simple test takes ~7 sec to parse, the same test parses in about 100msec in PLY. |
|
dang. ok, i'm leaving this open. |
|
Is there any progress on this? I'm currently using Antlr4 to parse some SQLite files (my SQLite grammar comes directly from the Anltr4 website), and it takes a few seconds to parse the simplest of files |
|
@ericvergnaud is there any plan to improve the performance of the Python parser? I'm curious why PLY would take 100ms on an example while antlr4 would take 7s, as pointed out by @pavelvelikhov. Such a big difference is difficult to attribute to Python only. You recommended maybe tuning grammars to be more Python friendly. Is there any advice on how to do that? I'm currently using the SQLite grammar that you guys provide on the website and parsing some simple SQLite file with a few tables takes seconds. Thanks. |
|
Hi, |
|
Some simple potential optimisations for SQLite would be as follows:
|
|
I've removed all the fragments and hardcoded the values of the keywords and it seems that it does not have a significant impact on the number of calls to closure_. To give some numbers, with the change the number of calls as reported by cProfile is '955807/13579' while without the change the number of calls is '1016393/13928' (that's a ~6% reduction). Any other advice off the top of your head that might improve the performance of this grammar in Python? As you pointed out the # calls to core methods of the parsing algorithm seems to be the same in both Java and Python. It seems that unless there's a significant improvement of the underlying parsing algorithm (in which case all runtimes would benefit but I assume is unlikely to happen) the Python runtime can't do much. |
|
I wonder if a cython version of the runtime would help much? |
I was wondering the same. I'm not familiar with cython (just learned about it two days ago). If I understood the principle behind it correctly, it works well as long as it's capable of compiling things down to C, so the question is how much of the runtime could end up being compiled as C actually. For what I read it seems that providing type information (with cython syntax) plays a big role there, but how much of that can help things like managing Python objects? For instance, if part of the slowness of the runtime comes from the fact that we're dealing with Python classes, can cython somehow do some magic that turns that into C code? For what I understood from http://docs.cython.org/en/latest/src/tutorial/cdef_classes.html that is not the case unless we have cython syntax in the runtime. |
|
Is anyone able to break down the profiled performance of |
|
@sharwell: I've been looking at the code and the |
|
@SimonSntPeter Any semantic predicate at the beginning of any lexer rule will disable the lexer DFA with overwhelming performance impact. The grammar indicated at the beginning of this topic contains such a predicate here: It's unlikely anything will make much of a difference without relocating that predicate (to somewhere after the first character) or eliminating it (via modes). |
|
@sharwell I didn't know that, and thanks, but the grammar here is an SQLite grammar, kindly bundled to me by @ricardojuanpalmaduran (see #1219 (comment) above), and the only non-antlr stuff it has is some error reporting, not any predicates AFAICS. I just commented that error bit out and it runs the same. |
|
@SimonSntPeter Thanks, that makes sense. The number of calls to adaptivePredict isn't cause for concern. This is an extremely heavily-used method, even in DFA scenarios. Can you break down the 14.4 seconds by which method(s) adaptivePredict calls? |
|
Sure. The calls seem to be, for the 14.9 sec original, where cumtime is cumulative time in that function and all function called, per python profiler: adaptivePredict (5,992 calls, cumtime 14.4 secs) The sequence of calls are what I found tracing through manually. There's also the following but I don't know where they fit in: After that what's not grammar rules is mostly lexer overheads. I'm not familiar with python profiler so if anything looks not credible, shout and I'll double-check it. I'd trust the call count a bit more than the times reported. On UK time so will pick up tomorrow. |
|
NB if you look at @ricardojuanpalmaduran's bundled code, the SQL being parsed is basically 2 things, a create table statement and a create view statement, both of these copied&pasted a dozen times, so once you've parsed one of each the rest should be trivial regarding adaptive stuff ( = lookups straight from the DFA cache?) |
|
Hey everyone. Posting here since it may be useful to people that find this issue thread. @parrt and @thisiscam's comments about using cython inspired me to put together an accelerator module for Antlr. Here is the code-generator tool: https://github.com/amykyta3/speedy-antlr-tool It is still a work in progress, and I hope to fill in more documentation details this weekend. |
|
Is this issue sorted? |
|
@JameelNabbo nope, not as far as i know. |
|
I have a similar behaviour with a query of mine. Unfortunately, I'm not allowed to share my g4-file, but I hope the following explanation will help to pinpoint where the issue is likely to be. Bahaviour Source of the issue https://acheron.cloud/wp-content/uploads/2021/07/antlr_python_graph.png In particular, the function "execATN" in ParserATNSimulation.py was going over-and-over the tokens. Can this information help with the issue why the ANTLR-Python-parser is slower than its Java brother? |
|
Hi. Yep, unfortunately Python is not particularly efficient with recursion and does not allow a great deal of depth. Maybe increase it? https://docs.python.org/3/library/sys.html#sys.setrecursionlimit |
|
Thank you for the suggestion! I will certainly have a look at this. I'm still a bit flabbergasted by the number of tokens Antlr wishes to visit in the function "execATN". I'm wondering why and if the Java-build requires the same number of tokens to be visited. If I have some time the coming weekend, I will have a look at this. |
|
Yep, lookahead can be HUUUUGE. it's the nature of ALL(*). |
|
Thank you for the clarification! That explains the high number. Makes a lot more sense now! |
|
Performance can be improved for Python using constant folding during generation especially for large grammars, see #3698 |
|
Any idea how much it would improve a real grammar if implemented?
BTW perhaps easier than folding constant exprs it would be just to hoist
them into vars evaluated once:
def no_folding_const_refs_test():
return (1 << C1) | (1 << C2) | (1 << C3) | (1 << C4) | (1 << C5) |
(1 << C6) | \
(1 << C7) | (1 << C8) | (1 << C9) | (1 << C10) | (1 << C11) |
(1 << C12) | \
(1 << C13) | (1 << C14) | (1 << C15) | (1 << C16)
instead
var _evaluated_713 = (1 << C1) | (1 << C2) | (1 << C3) | (1 << C4) | (1
<< C5) | (1 << C6) | \
(1 << C7) | (1 << C8) | (1 << C9) | (1 << C10) | (1 << C11) |
(1 << C12) | \
(1 << C13) | (1 << C14) | (1 << C15) | (1 << C16)
...
...
...
def no_folding_const_refs_test(): return _evaluated_713
folding is easy but maybe a bit messy, hoisting should be much easier
with the same effect, I guess. Would it help here?
jan
…On 07/05/2022 14:22, Ivan Kochurkin wrote:
Performance can be improved for Python especially for large grammars,
see #3698 <#3698>
—
Reply to this email directly, view it on GitHub
<#1219 (comment)>,
or unsubscribe
<https://github.com/notifications/unsubscribe-auth/ACNF57MGZCBMGHJAQ3HGXXTVIZVCBANCNFSM4CHUUOKA>.
You are receiving this because you commented.Message ID:
***@***.***>
|
I don't how much but anyway it should. It looks like the code is located in quite hot path. The simplest case: grammar Test;
e: T1 | T2 | T3;
T1: 't1';
T2: 't2';
T3: 't3';The more alternatives rule have the more operations are required. For instance, SQL grammars contain a lot of alternatives.
Vars also should be stored somewhere. Also, vars not so efficient as const literals because Python has no idea about constants.
It looks like any option is unclear for end user because of bitwise operations. In this case the most effective implementation should be choosed (with folded constants). |
|
as below
On 07/05/2022 15:17, Ivan Kochurkin wrote:
Any idea how much it would improve a real grammar if implemented?
I wrote in detail in the reference issue. The simplest case:
grammar Test;
e:T1 |T2 |T3;
T1:'t1';
T2:'t2';
T3:'t3';
The more alternatives rule have the more operations are required.
I mean, unless I missed it, might it be a 5% speedup or 20 X speedup in
a real grammar?
BTW perhaps easier than folding constant exprs it would be just to
hoist them into vars evaluated once:
Vars also should be stored somewhere. Also, vars not so efficient as
const literals because Python has no idea about constants.
Global vars. Stick them at the top. The efficiency is slightly less I
agree but hoisting const exprs into vars is very easy to do, so very
easy to try out I hope.
Nice work though.
jan
…
folding is easy but maybe a bit messy, hoisting should be much
easier with the same effect, I guess. Would it help here?
It looks like any option is unclear for end user because of bitwise
operations. In this case the most effective implementation should be
choosed (with folded constants).
—
Reply to this email directly, view it on GitHub
<#1219 (comment)>,
or unsubscribe
<https://github.com/notifications/unsubscribe-auth/ACNF57JRF22WDSCNP77YQ7LVIZ3PBANCNFSM4CHUUOKA>.
You are receiving this because you commented.Message ID:
***@***.***>
|
I'll check on a real grammar after implementation.
Actually implementation with constant folding is also very easy, may be even easier than vars. |
|
Doesn't the python compiler do any kind of optimization? |
|
oh, what if we started generating cython? |
I haven't checked, but not all users use cpython. Also, not sure cpython optimized such cases because Python as language doesn't have conception of constant, interpreter or compiler just has no idea if a var will be changed. If cypython has constants than the optimization is possible.
I don't know how many changes are required for compatibility with cython and if it's possible to use such library from ordinary Python. Actually I know almost nothing about cython. |
Where we go, there is no compiler… :) The only «compiler» step is the conversion of source code to bytecode, and the bytecode keeps everything, there is almost no optimization possible. In the previously mentioned no_folding_const_literals_test function, CPython 3.10 will optimize it as return 131070. Otherwise, since the interpreter doesn't know what is a constant and what is variable, it cannot optimize away the variable dereferences, and thus the no_folding_const_refs_test has a wooping 128 bytes body (instead of 4), and does for each part LOAD_CONST, LOAD_GLOBAL, BINARY_LSHIFT. LOAD_GLOBAL will have to go through the global dictionnary, thus an «expensive» call. |
|
Yet another potential performance improvemet: #3703 |
|
I see a lot of and in generated PythonQLParser.py by @pavelvelikhov. I believe suggested improvements might improve parser performance (but it looks like author already doesn't use ANTLR). |
|
@KvanTTT Ive put together a post-processing script that attempts optimizing the constant shift operations you pointed out in #3698 I tried it on an existing grammar on one of my projects and EDIT: Added the optimization described in #3703 to the above gist as well |
|
Heres the diff the patch script produces: SystemRDL/systemrdl-compiler@c4d425e Edited above comment - I had initially botched my benchmark. Now am seeing ~2% improvement in overall parse speed after implementing both optimizations |
Not sure because they have constants that can be effectively folded during compilation. Also they have
Not impressive. Maybe it's better for other grammars or input files. Anyway, I consider it's useful optimization since it also reduces the size of generated code and eliminates very long lines that are confusing. |
Have you tried array of literals |
I have a grammar of Python3 (from the antlr4 grammar repository), extended with query language constructs. The grammar file is here: Grammar file
The whole project is here: PythonQL
This tiny program parses in milliseconds with the Java runtime, but takes about 1.5 seconds in python (after the recent fix, before it was over 2 seconds).
Here is a profiler trace just in case (I left only the relevant entries):
I have attached a file that parses for 7 seconds on my Macbook Pro as well.
I'd be happy to reduce this case to a minimal case for debugging, but don't really know where to start.
The grammar doesn't seem to have any problems like ambiguity, etc.
The text was updated successfully, but these errors were encountered: