Mathics3
Expressions with undefined variables are slow
Expressions with undefined variables are 16x slower than the equivalents defined variables.
In[1]:= x=1
Out[1]= 1
In[2]:= Print[Timing[x+1+1.4+2]]; Print[Timing[y+1+1.4+2]]; Print[Timing[1+1.4+2+x]]; Print[Timing[1+1.4+2+y]]
{0.000742186, 5.4}
{0.0123144, 4.4 + y}
{0.000772454, 5.4}
{0.0121675, 4.4 + y}
Out[2]= None
One way to fix it is to have a hash table (python dict) with the numeric variables (in the future we can expand it to have a hash table for each type of value).
If the variable isn't there and we are expecting a numeric value we stop searching for the variable in other hash tables (currently we just have the huge definitions).
To we have an order of magnitude of the performance improvement here is the time with a hardcoded y:
In[1]:= Timing[1+1.4+2+y]
Out[1]= {0.00349792, 4.4 + y}
And by hardcoded I mean:
- items = items.numerify(evaluation).get_sequence()
+ items = [Integer(1), Real(1.4), Integer(2), Symbol("y")]
The hardcoded sum is almost 3.5x (71%) faster.
I have been thinking about this and for a good improvement there should be added 2 more hash tables: the numbers one and a hash table for only delayed rules (:=).
I'm in favor of trying something simple in code in a branch as a feasibility study to get a more detailed picture of how this would work and have something more concrete to discuss.
I think of this sort of like how an artist or cartoonist might do a rough sketch before working on the finished painting or cartoon.
@TiagoCavalcante , do you have a clue about why it takes so much time to add undefined symbols? I think that before adding more caching and hash-tables, we need to understand better why the evaluator has this behavior.
@mmatera I think it is because it needs to check all the definitions, one way to verify this is evaluate that without adding builtins.
@mmatera I think it is because it needs to check all the definitions, one way to verify this is evaluate that without adding builtins.
Thanks @TiagoCavalcante ! I would like to see us do more of this kind of activity where we think of ways to verify hypotheses before spending a lot of time implementing them. This kind of test I think is easy to do.
@rocky @mmatera just including the folders numbers and arithfns to include as @rocky suggested gave an improvement of only 4%, while removing arithfns too, gave an improvement of 96%, so there's a lot of slowness there.
@TiagoCavalcante , could you check how much the size of the dictionaries in the definitions object changes when you add/remove arithfns?
This happens because after the first application, the expression changes, to a new Plus[...] expression. Then, as the expression has changed (the return value is not None), the evaluator tries to reevaluate the expression. It would be different if apply would result in a number. Maybe this is why to add a+b with a and b undefined costs more than to evaluate it with a=2; b=3..
I think it would be possible, but not desirable. A better approach would be to accelerate the pattern matching for special symbols like Plus, Times, Power, or List, or just cache the last pattern that matched.