search

mdaines / grammophone

A tool for analyzing and transforming context-free grammars.
https://mdaines.github.io/grammophone
MIT License
205 stars 23 forks source link

Replaced sorted queue with priority queue. #12

Closed Levalicious closed 3 years ago

Levalicious commented 3 years ago

I've noticed a 40x improvement in performance on Brave v1.26.67 Chromium: 91.0.4472.114 (Official Build) (64-bit.

mdaines commented 3 years ago

Seems plausible :-) I'll take a closer look this weekend. Where does priorityqueue.js come from?

Levalicious commented 3 years ago

It's a small port I made of a C minheap implementation that I use occasionally.

Levalicious commented 3 years ago

The 2nd optimization I tried broke the sentence generation and I hadn't noticed. At some point I might try replacing it with a button that generates a certain number of random sentences, so that it's decoupled from grammar processing & hopefully to optimize it a bit again. The first optimization still works fine though, and the difference is quite noticeable: I managed to parse a version of this c bnf in about 90 seconds.

Edit: I also just realized my benchmarks are moot because they're evaluated under the profiler: Without the profiler, the C bnf evaluates in about 2 seconds.

mdaines commented 3 years ago

The min heap does seem to speed things up, but I think the calculation may need a limit on the size of the queue, or some other way to generate example sentences.

This smaller grammar takes a while to display the results of clicking "analyze", and most of the time is spent in the example sentences calculation:

a1 -> x .
a1 -> a2 x a2 .
a2 -> a3 x a3 .
a3 -> a1 x a1 .

In this case, the maximum queue depth was 15208 and it was sorted 36828 times.

Levalicious commented 3 years ago

Yep, I had some ideas for generating example sentences differently, but I haven't had a chance to tinker with any of them yet. Hopefully I'll get a chance to tinker with it some more over the next few days. Also, there's a decent chance the changes would involve getting rid of the priority queue anyway, so we'll see.

mdaines commented 3 years ago

I've just added a check to limit the depth of the queue: fadd52228273fb53e3472ee0e7ecfd2ed34f1dd0

That seems to address the performance issue with sentence generation. I'm going to leave this open for now to remind myself to implement the heap data structure at some point.

mdaines commented 3 years ago

Thank you for the suggestions and pull request. I'm planning to make some other changes to the example sentences calculation that would conflict with the changes, so I'm closing it.