draft: optimization

[dolik-rce]

Hello @arithy and @andrewchambers,

Here is my unfinished attempt on adding optimization phase to packcc, as I mentioned in https://github.com/arithy/packcc/issues/46#issuecomment-936353311.

Possible optimizations:

• Inline simple terminal symbols (multi pass) (no quantity, alternation, captures/action/error)
• Join adjacent strings
• Inline terminal symbols (multi pass) (with captures/action/error)
• Join repeated rules to single quantity
• Extract alternation/quantity to separate rules (might or might not help, probably depends on grammar)

Example

A -> B / C B -> "B" C -> D (E / F) D -> B B E -> "E"* F -> "F"

This could be optimized to:

A -> "B" / C C -> "BB" C1 C1 -> "E"* / "F"

Disclaimer

The code is far from perfect, in fact it barely works. I'm also pretty sure that there are some memory leaks and other problems. This is not intended to be merged, only as an inspiration for whoever might want to continue exploring the ways to make packcc to generate faster code.

[arithy]

Thanks as always.

Your PEG optimizing method is very impressive. However, I decided to pass on introducing it now, because I could fixed the performance issue #47 with wholly satisfying result.

[dolik-rce]

Your PEG optimizing method is very impressive.

It would be, if it worked correctly... which it currently doesn't.

Anyway, I have reused the benchmark from this branch to test the improvements in 0ce1963. It seems that it didn't help that much for complicated grammars. Testing on kotlin.peg shows almost identical times:

Commit       Generation      Build           Run
f583711      5702 us (100%)  4710 ms (100%)  5425 us (100%)
0ce1963      5432 us (95%)   4710 ms (100%)  5505 us (101%)

As a side-note: It might be useful, to have some kind of benchmark like this in the repository, so it is possible to track how changes in code affect the performance. It would have to be bit more extensive than what is here, though. Using more grammars and more runs. I can prepare the code and send a PR if you're interested.

[arithy]

I can prepare the code and send a PR if you're interested.

Of course, I'm interested in it. It would be very helpful.

[arithy]

Hello @dolik-rce , Regarding this PR, can PackCC rely on your project pegof for PEG optimization? I keep the role of PackCC as a tool that just generates a parser from a given PEG as is. So, let me close this PR.

[dolik-rce]

Hi @arithy, I should have closed this PR a long time ago, but I have totally forgot about it.

It is a good idea to keep the functionalities (code generation and parser optimization) separate. It's like the unix philosophy - do one thing a do it well.

I'm not sure whether my pet project is a good fit for that :slightly_smiling_face: But it might be a good decision anyway. Either people will start using pegof and make it better, or there might appear some new (possibly better) projects with similar aims in future.