Visualizer parseTree perf severely degrades with larger grammars/examples

[jbalogh]

First of all, the visualizer tool is amazing. I love it.

I'm working on a moderately-sized SQL grammar (248 lines, 109 rules so far). The visualizer is fantastic for small examples but there's a noticeable lag clicking on a 98-character input. A 900-character input never finishes and I eventually have to kill the tab.

According to the profiler the time is spent in parseTree.js in initializeWidths and updateInputWidths, measureInput, and measureChildren. I think the text measurements are forcing a ton of reflows which grind the browser to a halt, and updateInputWidths is called at least once per element here, making this O(n^2).

[pdubroy]

Thanks for filing this. That code has been slated for a rewrite for a long time now, and this finally pushed me into doing it :-)

I think you're right that the reflows are causing n squared run time. The problem isn't the line you pointed to (the line you pointed to doesn't actually get executed during the main layout pass, because duration is set to 0) -- but still.

Anyways, I've got a fix in the works...just need to iron out a few kinks. Should be able to land it sometime this week hopefully.

[pdubroy]

I've just pushed some changes to master that should significantly improve things. Can you give it a try and see if you see any improvement?

While investigating this, I also discovered some major performance problems in Chrome. Something about the visualizer causes "Update layer tree" to take upwards of 1s when just scrolling around a medium-sized parse tree. Safari doesn't seem to have the same problems.

[jbalogh]

This definitely seems faster! Thanks! I'm still seeing hangs when I have an example that doesn't parse, which is presumably generating a ton of nodes that were explored and backtracked and need to be rendered in the tree. Hitting explain parse is also a good way to cause a hang.

I'm attaching my current grammar as a text file since github won't allow .ohm uploads. I'm also attaching my version of visualizer/index.html where I've been putting all of my examples. There's examples that don't parse at the bottom. My grammar is probably bad for a number of reasons, but it should serve as a good example of a pathological usecase from an inexperienced user.

visualizer.index.html.txt sql.ohm.txt

[pdubroy]

Hi Jeff,

Thanks for letting me know -- and thanks for sending your grammar! That's interesting to see. We haven't consider the case sensitivity problem before.

Are you using Chrome? I think something must have recently changed in Chrome that is severely impacting our performance. I tried your grammar in Safari with the input select * from users where userId = 'dubroy';, and it only takes about 1 second to render with "Explain parse" turned on. (I'd like it to be better than that, but that's at least not terrible, IMO.)

I investigated on the weekend, and it seems that something about our layout causes Chrome to put every single node in the tree into a separate compositing layer. I've been working on a rewrite that I hope will fix the problem, but in the meantime I'd suggest using Safari.

[pdubroy]

BTW, I just added support for case-insensitive keywords, using a new built-in caseInsensitive rule. If you give it a try in your SQL grammar, let me know how it works out!

[jbalogh]

caseInsensitive is fantastic! Clicking around my examples feels much more responsive (even on Chrome) which is understandable since the trees are smaller. You're missing an implementation of _isNullable though. All the other _isNullables are in pexprs-isNullable.js so I'm not sure if you want to put it in there or inline in CaseInsensitiveTerminal.js.

I failed to note in the beginning that I most often see perf degradation when my grammar doesn't match. This is also understandable since the parse tree is going to get really big, but the reason I'm poking at a failed match with the editor is to understand where it went wrong. :)

In any case the slowness of the parse trees is making me really good at minimizing my test cases.