search

Morgul / rpgdice

A generic RPG dice roller syntax and library.
27 stars 1 forks source link

Exponential performance drop when deeply nesting parse trees (Repeat, Function, Parentheses) #9

Open mrfigg opened 5 years ago

mrfigg commented 5 years ago

So I noticed what seems to be an exponential performance drop while doing another stress test. I remade my fork to illustrate the issue here and made a few optimization tweaks to the side-associative helper functions to (unsuccessfully) try to help alleviate the issue.

When you get to around 6 nested parentheses, ((((((6)))))), it takes about 830ms to parse the expression, at least on my machine. Adding one more for 7 nested parentheses bumps that all the way up to about 5000ms.

When testing in 2.0.0-rc.2 the same performance drop is there, it just takes around 8 nested parentheses before getting to be about 800ms. 9 nested parentheses gets up to around 4100ms.

I don't know how severe you consider this issue to be right now, but it seems like it will only get worse once/if we proceed with adding conditionals, as that would probably add another 5 or 6 peg rules.

I could be too inexperienced with PEG.js to be coming to this conclusion given that I only became aware of it two weeks ago, but this seems to be an issue on their end as your peg file seems to match the format of the examples they give. I'm really not sure what we can do about this one.

Morgul commented 5 years ago

I wonder if it's related to this:

https://github.com/pegjs/pegjs/issues/237

So, for the moment, I'm not that worried, since we have the ability to store a parsed tree, and call it as many times as we want to get unique output values. However, I'll have to make it clear in the documentation that for performance reasons, users will want to cache parsed rolls.

Hmm. Also might need to check Variable, and make sure it updates if the scope changes between eval calls.

Might even consider shipping a built-in cache, if performance is going to be poor enough. Thanks for finding this; we should probably build a small benchmarking util (can even run it between versions and store that off) and come up with as many real-worldish strings as possible to test. If we can handle, say most of the rolls from D&D 5e, 4e, and 3.5e without caching, then we're probably fine.

(I have a half dozen 4e and 3.5e characters stored in sqlite with their roll texts; I can scrape some of that for this. We might have to build the rest by hand. Off the top of my head, I don't remember which class/spell/power has the largest, weirdest ruleset.)