Closed lambda-ai closed 8 years ago
Engelberg
commented
8 years ago Take a look at tips 5-7 here: https://github.com/Engelberg/instaparse/blob/master/docs/Performance.md#performance-tips
Over 90% of the performance questions I get asked can be addressed by using the insta/parses function to test whether the grammar produces multiple interpretations on a given text, and if so, identifying why and removing that ambiguity. So give that a try first and let me know what you find.
lambda-ai
commented
8 years ago Thanks, on a good chunk of that game (a chunk taking a few seconds), a single parse is returned with insta/parses, also with "unhide all". Even "partial true" only returns a singe parse.
I had been looking at the grammar and added for example the negative lookahead in the regex for Col, but that doesn't seem to help. I imagine the only places that create serious work for the parser are the Moves and Move rules, but I don't have a clue why exactly this game is so bad. It has a lot of comments, but nothing specifically harder than other games that parse fine.
I'm probably just overlooking something stupid :)
lambda-ai
commented
8 years ago ok, if I preprocess the games by removing all the comments, the parsing is very fast. I don't really need the comments, so it's fine, but I wonder what's going on: isn't the regex match supposed to be greedy, so just generating a single alternative. Not sure why that's slowing things down so much...
aengelberg
commented
8 years ago First of all, I'm guessing you're using :auto-whitespace :standard as there is no other explicit whitespace parsing in the parser you provided.
For what it's worth, the parser does complete (on my machine) under a second to find just one parse. To find all parses, however, takes a very long time.
=> (time (do (insta/parse chess-grammar input) nil))
"Elapsed time: 293.826642 msecs"
nil
=> (time (do (count (insta/parses chess-grammar input)) nil))
....takes foreverThe problematic line is:
Moves = (Comment* [MoveNumber] Move Comment* | Line)*Specifically, your usage of Comment* twice. Here's why: If a comment were to appear between two moves, there are two ways to parse it, either after the first move, or before the second move. These small choices multiply to many possible combinations for large inputs. It's easy to find one parse, but when you fully iterate the insta/parses lazy seq, the engine has to fully resolve all those choices to guarantee you're getting all the solutions (which ends up being no more after the first one).
There are two potential solutions I see:
Moves = ([MoveNumber] Move | Line | Comment)* so that each comment is parsed in only one possible place.I'm not sure whether this parser counts as "ambiguous", because it has only one possible parse tree, just multiple ways of deriving the subsequences that ultimately get joined together to create said parse tree.
For example, compare the following two parsers on the same input.
(count (insta/parses (insta/parser "S = 'a'* ('b' 'a'*)*") "bbbabbbabbba" :trace true))
(count (insta/parses (insta/parser "S = ('a'* 'b' 'a'*)*") "bbbabbbabbba" :trace true))These parsers parse equivalent inputs, and these expressions both return 1 as there is indeed only one possible parse tree. The second one, however, has an "internal ambiguity" similar to that in Mathias' grammar, with two ways to handle each a. In the trace output of the second one, if I look at what happens after the Successful parse. line, I see three more instances of this line:
Result for ("a"* "b" "a"*)* at index 0 (bbbabbbabb...) => ("b" "b" "b" "a" "b" "b" "b" "a" "b" "b" "b" "a")which means that it's finding more ways to parse the same sequence of tokens, that are presumably getting suppressed at the front-end because they are duplicates. So it's just unnecessary time being spent while yielding the same result.
--Alex
lambda-ai
commented
8 years ago Thanks a lot, Alex! I should have figured that one out myself...
It's easy enough to re-write the grammar so the pre-move comments are only considered in specific places, so for sure my problem is solved.
I'm still wondering about your initial comment about the parse finishing on your machine. I double (&triple-) checked on my machine, which is pretty new. I'm running 1.4.1 on java 8, and it still doesn't finish in a time quick enough to bother waiting. I thought it might have been the lack of hotspot because I was running leiningen without any jvm-opts, but adding the "-server" in the jvm-opts also doesn't make a difference, it seems. Is it maybe an improvement in the development version of instaparse you may be running?
Anyway, problem solved for me.
Thanks again to both of you for the fantastic library and the amazing support!
-Mathias
Hi,
sorry to be posting this as a bug instead of a message on the instaparse group: I'm waiting for acceptance of my membership there.
I'm using your fantastic library to parse chess games in PGN format, and most of the time the parsing is fast enough for my purposes (around 50 ms per game), but for some games it's incredibly slow. The game below runs for minutes without terminating. I don't have a clue how to debug this; taking away part of the input made it faster, but I don't understand at all what's special about the pieces that make it slow... Would be great to get some ideas.
My simple grammar is attached (the inline formatting caused all kinds of trouble) pgngrammer.txt
This is the game causing the pain:
Thanks, -Mathias