Can't finish or takes forever with postgres16 grammar

[mingodad]

While testing this project with a fresh clone and build with a postgres16 grammar the nimbleparse takes forever (I've killed it) see attached grammar/lexer/input.

/usr/bin/time ../target/release/nimbleparse postgresql-16-naked.l postgresql-16-naked.y input.txt

This is the output of bison :

/usr/bin/time bison-nb postgresql-16-naked.y
>/usr/bin/time bison-nb postgresql-16-naked.y
postgresql-16-naked.y: warning: 8 shift/reduce conflicts [-Wconflicts-sr]
postgresql-16-naked.y: note: rerun with option '-Wcounterexamples' to generate conflict counterexamples
1.37user 0.02system 0:01.37elapsed 101%CPU (0avgtext+0avgdata 17944maxresident)k
0inputs+4016outputs (0major+10957minor)pagefaults 0swaps

Notice that the 8 shift/reduce conflicts are due to the changes in the grammar to be accepted by nimbleparse that doesn't accept empty rules with %prec that are used in the postgres16 grammar:

...
opt_existing_window_name :
	ColId
	| %empty //%prec Op /*16L*/
	;
...
json_key_uniqueness_constraint_opt :
	WITH /*13N*/ UNIQUE /*11N*/ KEYS /*12N*/
	| WITH /*13N*/ UNIQUE /*11N*/
	| WITHOUT /*13N*/ UNIQUE /*11N*/ KEYS /*12N*/
	| WITHOUT /*13N*/ UNIQUE /*11N*/
	| %empty //%prec KEYS /*12N*/
	;
...

You can also see how https://github.com/BenHanson/parsertl14 handle it and several others with wasm in the browser here https://mingodad.github.io/parsertl-playground/playground/ (select Postgresql parser (be patient) from Examples then click Parse to see a parse tree for the content in Input source).

build master parser -> Time taken : 70ms
parse user grammar -> Time taken : 6ms
start build user grammar -> Time taken : 2ms
build user parser -> Time taken : 1077ms
dump input parser tree -> Time taken : 10ms

postgres16.zip

[ratmice]

I haven't had a chance to actually look through the grammar yet, but this could perhaps be another occurrence of #290
This could perhaps be ruled out by modifying the goto function and checking whether you hit an added branch such as Some(i) if i == usize::from(stidx) + 1 => panic!("goto lacks forward progress!") as discussed in the original #290 report.

[ratmice]

Had a little look at it now I don't think this is another occurrence of that issue I had mentioned above.
That issue happens at parser runtime, while the time appears to be taken by parser build time.

Here at least it eventually finishes due to the shift/reduce conflicts nimbleparse eventually errors (after about 2 min 10 s) printing the statetable. The state table is pretty big at about 500k lines. However if I panic before the state table is printed
here it still takes 2 mins, so the majority of the time does appear to be taken by building the parser, rather than being taken up just printing stuff.

Edit: So at least from what I can observe this is more "takes forever" than a case of it never actually finishing.

[ltratt]

It wouldn't surprise me if there's some low-hanging optimisation fruit here: I didn't put much effort into optimising grammar generation time (I did put some effort into reducing the size of the resulting tables though).

[ratmice]

Indeed I haven't looked at it much myself either, as it has never really been a problem for me...
Looking at the output of CARGO_PROFILE_RELEASE_DEBUG=true cargo flamegraph --bin nimbleparse --ignore-status -- ../postgres16/postgresql-16-naked.{l,y} ../postgres16/input.txt

A lot of the time is being taken up by sparsevec::fits through the StateTable::new -> sparsevec::from -> sparsevec::compress sequence of calls.

It might be that there could be some form of assert or unsafe that could hoist the bounds checking in that function up out of the loop if the optimizer isn't doing so already, such as assert!(target.len() <= v.len() + d) or some such 🤷. But afaict that accounts for like 98% of the time.

[ltratt]

@ratmice Thanks for the analysis! I had a quick look at sparsevec and although I don't remember the algorithm at all (I think @ptersilie implemented this bit), one simple optimisation opportunity which I could do in 20 minutes jumped out at me which I've done in softdevteam/sparsevec#25. On my machine this speeds this example up by over 30x. Warning: only lightly tested!

[ltratt]

A sidenote. Before and after the sparsevec change I notice that nimbleparse borks with:

thread 'main' panicked at nimbleparse/src/diagnostics.rs:308:13:
assertion failed: !r_prod_spans.is_empty()

I think that's a (separate) pretty-printing error that might not be too difficult to fix?

[ratmice]

Yeah, I saw that too, but I have yet to investigate, or form any hypothesis other than maybe a wild guess that somehow a conflict could be occurring with the implicit start rule and thus it doesn't have any span info? But even in that case I would expect it to be a pretty simple fix of removing the assert and doing some special case printing. But other than that I don't have any idea how we could get a production without span.

[ratmice]

Reopening as I believe we still need to bump version numbers etc, before this will take effect in grmtools.

[ltratt]

Because this is a library, if a user runs cargo update locally they'll naturally get the latest sparsevec and get a speed-up without us updating grmtools itself. We could force the latest version of sparsevec in Cargo.toml but I don't think it's worth making a release just to do that.

[mingodad]

I just did cargo update but I'm still getting takes forever !

[ltratt]

Ah, sorry, I wasn't clear: I need to make a sparsevec release and then grmtools users will only need to cargo update (without us making a grmtools release).

[ltratt]

@mingodad sparsevec is now updated, so hopefully you'll see the speed up!