More rule tweaks

[rocky]

@TiagoCavalcante Looks good - thanks. But before we merge would you do a benchmark on mathics-benchmarks on this?

I suspect the time difference will be small, but I'd be interested all the same.

[TiagoCavalcante]

The results were very weird.

Before:

10000 iterations of ElementData...
  2.436314 secs for: ElementData["Gold", "AtomicNumber"]     

10000 iterations of NextPrime...
  3.416719 secs for: NextPrime[1, 1]

After:

10000 iterations of ElementData...
  2.569624 secs for: ElementData["Gold", "AtomicNumber"]

10000 iterations of NextPrime...
  3.259799 secs for: NextPrime[1, 1]

Shouldn't _String be faster than _?StringQ?

[rocky]

Shouldn't String be faster than ?StringQ?

Why not write some benchmarks to check this or try to isolate this?

I am guessing that one can write Mathics definitions with the two kinds of type checking.

And also we can change the Python code - maybe add another builtin temporarily testing the alternative way on simple primitives (and then more complex ones...)

I am not surprised though that we are surprised. If we knew this stuff perfectly we probably would be having fewer problems.

[mmatera]

For a short string:

In[2]:= Timing[Do[MatchQ["ww",_String],{10000}]]
Out[2]= {1.67904, Null}

In[3]:= Timing[Do[MatchQ["ww",_?StringQ],{10000}]]
Out[3]= {3.25842, Null}

For the same string stored in a variable:

In[19]:= Timing[Do[MatchQ[s,_String],{10000}]]
Out[19]= {1.70189, Null}

In[20]:= Timing[Do[MatchQ[s,_?StringQ],{10000}]]
Out[20]= {3.39103, Null}

For a plane symbol:

In[7]:= Timing[Do[MatchQ[L,_String],{10000}]]
Out[7]= {1.56889, Null}

In[8]:= Timing[Do[MatchQ[L,_?StringQ],{10000}]]
Out[8]= {3.33777, Null}

For real numbers:

In[12]:= Timing[Do[MatchQ[27.321212,_String],{10000}]]
Out[12]= {1.59748, Null}

In[13]:= Timing[Do[MatchQ[27.321212,_?StringQ],{10000}]]
Out[13]= {3.25175, Null}

For a "complicate" expression

In[25]:= Timing[Do[MatchQ[Sqrt[1+F[G[t]]],_String],{10000}]]
Out[25]= {18.0476, Null}

In[26]:= Timing[Do[MatchQ[Sqrt[1+F[G[t]]],_?StringQ],{10000}]]
Out[26]= {21.1116, Null}

In[27]:= Timing[Do[Sqrt[1+F[G[t]]],{10000}]]
Out[27]= {16.0676, Null}

[mmatera]

This could be also useful:

In[29]:= F[s_String,n_]:=Do[If[MatchQ[s,_String],1,0],{n}]
Out[29]:= None

In[30]:= G[s_,n_]:=Do[If[MatchQ[s,_String],1,0],{n}]
Out[30]:= None

In[31]:= H[s_?StringQ,n_]:=Do[If[MatchQ[s,_String],1,0],{n}]
Out[31]:= None

In[32]:= {Timing[Do[F["sss",0],{10000}]],Timing[Do[G["sss",0],{10000}]],Timing[Do[H["sss",0],{10000}]]}
Out[32]:= {{4.82359, Null}, {4.52345, Null}, {6.85825, Null}}

In[33]:= {Timing[Do[F["sss",1],{10000}]],Timing[Do[G["sss",1],{10000}]],Timing[Do[H["sss",1],{10000}]]}
Out[33]:= {{7.84266, Null}, {7.82672, Null}, {10.1756, Null}}

In[34]:= {Timing[Do[F["sss",10],{10000}]],Timing[Do[G["sss",10],{10000}]],Timing[Do[H["sss",10],{10000}]]}
Out[34]:= {{36.467, Null}, {36.4047, Null}, {43.4621, Null}}

In[35]:= {Timing[Do[F[2,0],{10000}]],Timing[Do[G[2,0],{10000}]],Timing[Do[H[2,0],{10000}]]}
Out[35]:= {{0.694378, Null}, {4.91281, Null}, {1.22358, Null}}

[TiagoCavalcante]

Thanks for the benchmarks @mmatera! I hadn't time to do them, and probably they won't be as complete as yours.

[rocky]

For a short string:

In[2]:= Timing[Do[MatchQ["ww",_String],{10000}]]
Out[2]= {1.67904, Null}

In[3]:= Timing[Do[MatchQ["ww",_?StringQ],{10000}]]
Out[3]= {3.25842, Null}

For the same string stored in a variable:

In[19]:= Timing[Do[MatchQ[s,_String],{10000}]]
Out[19]= {1.70189, Null}

In[20]:= Timing[Do[MatchQ[s,_?StringQ],{10000}]]
Out[20]= {3.39103, Null}

For a plane symbol:

In[7]:= Timing[Do[MatchQ[L,_String],{10000}]]
Out[7]= {1.56889, Null}

In[8]:= Timing[Do[MatchQ[L,_?StringQ],{10000}]]
Out[8]= {3.33777, Null}

For real numbers:

In[12]:= Timing[Do[MatchQ[27.321212,_String],{10000}]]
Out[12]= {1.59748, Null}

In[13]:= Timing[Do[MatchQ[27.321212,_?StringQ],{10000}]]
Out[13]= {3.25175, Null}

For a "complicate" expression

In[25]:= Timing[Do[MatchQ[Sqrt[1+F[G[t]]],_String],{10000}]]
Out[25]= {18.0476, Null}

In[26]:= Timing[Do[MatchQ[Sqrt[1+F[G[t]]],_?StringQ],{10000}]]
Out[26]= {21.1116, Null}

In[27]:= Timing[Do[Sqrt[1+F[G[t]]],{10000}]]
Out[27]= {16.0676, Null}

My take is on this data is that basically the overhead difference is about the same for everything. When you get to expressions though the overhead in function calls swamps differences there are in pattern matching - this is taking 10 times longer and other tests show that this is not in computation time.

So again we need to focus on function calls.

[mmatera]

So again we need to focus on function calls.

The problem here is that, from the WL side, function calls are just pattern matching, and pattern matching is expensive because it involves many Python function calls, which at the time are very expensive. So, anything we can do to reduce the number of Python function calls will improve the performance.

[rocky]

So again we need to focus on function calls.

The problem here is that, from the WL side, function calls are just pattern matching, and pattern matching is expensive because it involves many Python function calls, which at the time are very expensive. So, anything we can do to reduce the number of Python function calls will improve the performance.

It is a problem, but not the only problem and I am concerned about confusing the pattern matching and Mathics function calls.

A Mathics function call involves not just potentially several pattern-match signatures until one that succeeds, (or all signatures exhausted), but there are iteration and recursion checks, and checks to see if there was a rewrite rule instead of a function call, and if so the process repeats. And once a rule matches, there is argument substitution before the call.

I used to think (and still do) that Python method calls were expensive because methods need to constantly be resolved as a result of its OO behavior and ability to change that at run time. However Mathics can be an order of magnitude worse.

One plan of attack at least for built-in functions and then later possibly for compiled functions is to hold on to the found pattern-to-apply-method map for a particular call site and use that avoiding the entire lookup process.

As the trend has now been to do the checking in Python, we will also detect mismatches when there are mistakes.

Take for example this code that is in a recent PR:

Expression(SymbolGreater, x, Integer0).evaluate(evaluation)

which is found in the implementation of built-in NonPositive[]. Furthermore, we know that to compute this expression no rule rewriting goes on. So the apply() method on a class that gets called here will always be the same. (Probably it is _ComparisonOperator#apply). Therefore the evaluation() method can be replaced with another method (in a refactor branch) - I have been calling it evaluate_fast(), that returns the found pattern-to-method mapping in addition to performing the evaluation .

With this, something the code for NonPositive might look like:

class NonPositive(Builtin):
    greater_than_zero_mapping = None

    ...
    def apply... 
        self.greater_than_zero_mapping = Expression(SymbolGreater, x Integer0).evaluate_fast(self.greater_than_zero_mapping, evaluation)

where evaluate_fast() skips what is done in evaluation() and instead calls evaluate_next() which I intend to rename evaluate_one().

[rocky]

The new benchmark:

Mathics git repo /workspaces/mathics-benchmark/Mathics at cfe55d
10000 iterations of ElementData...
  2.515098 secs for: ElementData["Gold", "AtomicNumber"]     

10000 iterations of NextPrime...s of 
  3.650676 secs for: NextPrime[1, 1]                         

Mathics git repo /workspaces/mathics-benchmark/Mathics at cfe55d
10000 iterations of ElementData...
  2.433841 secs for: ElementData["Gold", "AtomicNumber"]     

10000 iterations of NextPrime...
  3.345542 secs for: NextPrime[1, 1]                         

Why are the two sets of SHA's the same?

[TiagoCavalcante]

My mistake, I forgot to checkout to master before running the tests. I'll add this to mathics-benchmark and re-run the tests latter. And run black too.

[TiagoCavalcante]

New benchmarks:

Mathics git repo /workspaces/mathics-benchmark/Mathics at 58dc69
10000 iterations of StringQ...
  2.595370 secs for: ElementData["Gold", "AtomicNumber"]     

10000 iterations of NextPrime...
  3.167263 secs for: NextPrime[1, 1]                         

Mathics git repo /workspaces/mathics-benchmark/Mathics at cfe55d
10000 iterations of ElementData...
  2.429380 secs for: ElementData["Gold", "AtomicNumber"]     

10000 iterations of NextPrime...
  3.201453 secs for: NextPrime[1, 1]