-
Notifications
You must be signed in to change notification settings - Fork 210
New issue
Have a question about this project? Sign up for a free GitHub account to open an issue and contact its maintainers and the community.
By clicking “Sign up for GitHub”, you agree to our terms of service and privacy statement. We’ll occasionally send you account related emails.
Already on GitHub? Sign in to your account
Multiple macros expansions with bindings results in exponential time complexity #232
Comments
Possibly related to #86 |
If I remove |
Macro like
which creates a new lexical scope doesn't cause the problem |
After some profiling I see it's |
For additional context see #90. Some initial guesses about this slowdown. It probably has something to do with the interaction of definition contexts and marks. There's a short circuit that should be taken in certain cases that might be failing to trigger? |
The fix is a memoization approach for the expensive recursive resolveCtx function. Although I'm not 100% confident that the memoization approach is correct (though intuitively it feels correct to me), at least all the tests pass ... which I take to mean that the memoized resolveCtx is properly generating hygienic code in the known cases. It certainly does that for the example given in issue sweet-js#232 without incurring exponential time.
realized that even originalName needn't be used in the memoization key and only the context is needed. I'm now confident of the correctness of this optimization and am willing to change the name from "Potential fix for issue sweet-js#232" to "Fix for issue sweet-js#232". It is easier to see the correctness of the assumption made by the memoization step in a purely recursive rewrite of resolveCtx, where every recursive step works with either a "deeper" context or a new one. I've put that up at https://gist.github.com/srikumarks/9847260 .
After poking around the resolveCtx function's logic a bit more, I realized that even originalName needn't be used in the memoization key and only the context is needed. I'm now confident of the correctness of this optimization and am willing to change the name from "Potential fix for issue sweet-js#232" to "Fix for issue sweet-js#232". It is easier to see the correctness of the assumption made by the memoization step in a purely recursive rewrite of resolveCtx, where every recursive step works with either a "deeper" context or a new one. I've put that up at https://gist.github.com/srikumarks/9847260 .
I'm mass closing issues due to the release of 1.0 obviating lots of bugs. If you feel this issue is something we still need to address feel free to reopen. |
Using code from
master
branch.Example macro
expands in
1.04s
While
expands in
5.34s
And after adding just a one more
m 11
in
10.26s
:(
The text was updated successfully, but these errors were encountered: