Performance regression after equivalence change #14
Description
We had a performance regression after releasing the equivalence change, so I reverted it (in live-editor, not here). We don't currently have performance tests, but those would help in detecting performance regressions earlier. I'll make a separate issue around adding performance tests.
Here's a specific program that hung the browser after the change (which may be a separate issue of an infinite recursion):
https://www.khanacademy.org/computer-programming/front-line-v6872-gamma/5994354862456832
Here are some thoughts from another dev that looked at the change:
"-I had a look at the code for implementing equivalencies and if I am not mistaken (which is very very possible) the equivalencies are being checked downwards recursively on the tree.
The issue with checking for the equivalencies in that manner is that we end up running the function 2^(# of binary operators) i.e. every equivalent tree would be created in the event of a miss.
I would suggest the alternative approach of passing the structure tree and parse tree into a function which coverts it into a “standard form” parse tree.
e.g. We decide > is the “standard form” for < and >. We scan the tree for < operators and modify the existing parse tree to convert them into > operators.
(We don’t even have to check for > operators, because they are “standard”)
In that manner, the tree gets scanned and change once. In a situation where misses are more common than hits, the performance gains should be considerable.
-For something like (a*b) or (a+b) I would suggest a “standard form” of the lexically smaller element on the left and the lexically larger element on the right (this may require some tweaking to work with $wildcards)"