Volunteer to benchmark some patches?

[rocky]

I'd like a volunteer to try these patches and see which ones are beneficial and should be applied.

Apply these using patch -p1 < name-of-patch.diff

I will start with one that isn't so controversial and is a definite win:

diff --git a/mathics/core/expression.py b/mathics/core/expression.py
index de18bad0..8448ef95 100644
--- a/mathics/core/expression.py
+++ b/mathics/core/expression.py
@@ -198,16 +198,13 @@ class Expression(BaseElement, NumericOperators, EvalMixin):
     ):
         self.options = None
         self.pattern_sequence = False
-        if isinstance(head, str):
-            # We should fix or convert to to_expression all nonSymbol uses.
-            head = Symbol(head)
+
+        # assert isinstance(head, Symbol):
 
         self._head = head
 
         # This is useful for finding potential improprer calls
         # for element in elements:
-        #     if not isinstance(element, BaseElement):
-        #          from trepan.api import debug; debug()
         #     assert isinstance(element, BaseElement)
 
         # Note: After we make a pass over all Expression() calls, these lines will get removed

There will be an alternate version of this with the commented out checking enabled. I haven't figured out the best way. It could just be something low-tech like manually uncommenting the code. Or a copy of the file with the uncommented parts.

This one I think is a simple change and a win too:

diff --git a/mathics/core/expression.py b/mathics/core/expression.py
index de18bad0..57567444 100644
--- a/mathics/core/expression.py
+++ b/mathics/core/expression.py
@@ -1213,5 +1214,7 @@ class Expression(BaseElement, NumericOperators, EvalMixin):
                 if result.sameQ(new):
                     new._timestamp_cache(evaluation)
                     return new, False
+                elif result.is_literal:
+                    return result, False
                 else:
                     return result, True

This detects "fixed-point"ednes (or evaluation stopping in lay speak) earlier in the evaluation cycle so and saves an iteration when we have a literal. When not there is an additional test.

Here are two somewhat patches rolled into one change:

diff --git a/mathics/core/symbols.py b/mathics/core/symbols.py
index 14f2d5ed..3090de75 100644
--- a/mathics/core/symbols.py
+++ b/mathics/core/symbols.py
@@ -612,7 +612,7 @@ class PredefinedSymbol(Symbol):
         has the property HoldRest. That kind of thing though is detected
         at the higher level in handling the expression setup for `If`, not here.
         """
-        return False
+        return True

     def is_uncertain_final_definitions(self, definitions) -> bool:
         """
@@ -658,6 +658,7 @@ format_symbols = system_symbols(
 SymbolFalse = PredefinedSymbol("System`False")
 SymbolList = PredefinedSymbol("System`List")
 SymbolTrue = PredefinedSymbol("System`True")
+SymbolNull = PredefinedSymbol("System`Null")

 SymbolAbs = Symbol("Abs")
 SymbolDivide = Symbol("Divide")
@@ -673,7 +674,6 @@ SymbolMathMLForm = Symbol("MathMLForm")
 SymbolMaxPrecision = Symbol("$MaxPrecision")
 SymbolMinPrecision = Symbol("$MinPrecision")
 SymbolN = Symbol("System`N")
-SymbolNull = Symbol("System`Null")
 SymbolNumberForm = Symbol("System`NumberForm")
 SymbolOutputForm = Symbol("OutputForm")
 SymbolPlus = Symbol("Plus")

I think we discussed this before, but I every time I think of it, it feels wrong: why again is a predefined Symbol not a literal value?

Also, strongly suspect Null should be predefined. If you were to remove or changes this in WMA I imagine havoc would rein.

As for the ability to redefine None inside a block, aside from it being a pretty dangerous and stupid thing to do. Probably the way we would implement this would be inside that block to define that as Symbol and not PredefinedSymbol inside that block. And I am not sure if it would have the "System`" part either, but it could as long as what's in the block is Symbol rather than PredefinedSymbol.

Please try these out and put in PRs for the ones you think should go in.

[mmatera]

Also, strongly suspect Null should be predefined. If you were to remove or changes this in WMA I imagine havoc would rein.

In WMA:

In[1]:= Unprotect[Null]                                                         

Out[1]= {Null}

In[2]:= Null="I am not null"                                                    

Out[2]= I am not null

In[3]:= Print["Hi!"]                                                            
Hi!

Out[3]= I am not null

[mmatera]

In any case, I think nobody uses this feature. So, if we gain something significant in performance, let's do it.

[rocky]

Here is how we could accommodate that behavior We have another symbol PredefinedSystem`Null that is set in the Python code as SymbolNull.

If Null gets defined, then this Null will move to System`Null or whatever context has been set.

As for whether we gain something significant performance, that is up to use to check.

[mmatera]

Here is how we could accommodate that behavior We have another symbol PredefinedSystem`Null that is set in the Python code as SymbolNull.

If Null gets defined, then this Null will move to System`Null or whatever context has been set.

Yes, it should work.

As for whether we gain something significant performance, that is up to use to check.

I am up for it. Do you have in mind a particular set of benchmarks to run? Otherwise, I have a couple of ideas in mind.

[rocky]

As for whether we gain something significant performance, that is up to use to check.

I am up for it. Do you have in mind a particular set of benchmarks to run? Otherwise, I have a couple of ideas in mind.

Great! Thanks. I'd be interested in your set of benchmarks.

[mmatera]

For example, for benchmark the advantage of using PredefinedSymbol in Null, I was thinking about something like

Do[F[i]:=i, {i,100}]

F[i]:=i does something and returns Null, so on each step we save at least call to evaluate and a call to evaluate_next.

[mmatera]

For the first patch, the difference can be seen just by looking at how much time requires to run the full doctest suit. A more narrow test would be something like

• a=Fold[F,1,Range[750]];F[x_,y_]:=x+y; a
• Fold[(#1+#2)&,1,Range[750]]

[mmatera]

one more thing: in the first patch, we still are calling the conversion function by default. Do we want to keep that behavior? Otherwise,

        self._elements, self.elements_properties = convert_expression_elements(
            elements, from_python
        )

should be

        self._elements, self.elements_properties = convert_expression_elements(
            elements, lambda x:x
        )

[rocky]

There is a bug in the code in that the elements_properties are not getting set properly. One place is here:

diff --git a/mathics/core/rules.py b/mathics/core/rules.py
index 44433b23..fe551f45 100644
--- a/mathics/core/rules.py
+++ b/mathics/core/rules.py
@@ -81,14 +81,9 @@ class BaseRule(KeyComparable):
         try:
             self.pattern.match(yield_match, expression, {}, evaluation, fully=fully)
         except StopGenerator_BaseRule as exc:
-            # FIXME: figure where these values are not getting set or updated properly.
-            # For now we have to take a pessimistic view
             expr = exc.value
-            # FIXME: expr is sometimes a list - why the changing types
-            if hasattr(expr, "_elements_fully_evaluated"):
-                expr._elements_fully_evaluated = False
-                expr._is_flat = False  # I think this is fully updated
-                expr._is_ordered = False
+            if hasattr(expr, "_build_elements_properties"):
+                expr._build_elements_properties()
             return expr
 
         if return_list:

but the above patch may have problems as well because expr._build_elements_properties() when I was debugging this was not working properly either. I don't recall if I tried something like expr.elements_properties = None which does basically the same thing.

There may be other places where we aren't setting elements_properties correctly as well. The part of the conversion that recomputes the elements_properties works around these bugs.

You can see this bug by running test/test_series.py. Series[F[x, y],{x, b, 2},{y, a, 1}] is coming out with I believe y listed first rather than x listed first.

So if those were fixed we could and should remove the conversion in Expression.

That is ultimately what I am aiming for. I just won't have time to look at this for a little more than a week.

What happens in the middle I care less about.

Again, if you look at the benchmark+futher-improvements branch that the final code with some mess in comments.

[mmatera]

For the branch benchmarking+further-improvements (with pyston):

branch	doctest	test1	test2	test3
benchmark+futher-improvements	1:36.73	0.211	0.009	0.129
benchmark+futher-improvements+patch3	1:29.89	0.161	0.007	0.111

[rocky]

You should double check, but this branch doesn't have patches 2 and 3, but it has a beefed up version of 1.

[mmatera]

Indeed, it has just the first patch + avoid conversion. The other patches do not seem to provide further improvements: the check in the patch2 is already implemented in the line 462 of mathics.core.expression

What I would like to check is if the third patch makes some difference.

[mmatera]

Also, in the first patch, the assert fails if we pass an expression as a Head. For example, in

D[f][x]

D[f] is the head of the expression, and it is not a Symbol.

[rocky]

When you try these examples in benchmark+futher-improvements are you seeing a problem? As far as I can tell, I am not.

But sure, remove the commented out assert statement since that is wrong.

[mmatera]

Here we go with a first cut:

• CPython 3.9

test 1: 'Timing[Fold[F,x,Range[500]];]'
test 2: 'a=Fold[F,0,Range[150]];F[x_,y_]:=x+y; Timing[a]'
test 3: 'Timing[Do[F[i]:=i, {i,1000}]]'

branch	doctest	test1	test2	test3
origin/master	03:07.93	0.634	0.026	0.412
patch1	02:59:82	0.626	0.026	0.384
patch2	03:05:32	0.636	0.026	0.384
patch3	03:09.39	0.621	0.026	0.381

mathics -e 'Timing[Fold[F,x,Range[500]];]'  -e 'a=Fold[F,0,Range[150]];F[x_,y_]:=x+y; Timing[a]' -e 'Timing[Do[F[i]:=i, {i,1000}]]' 

Here are the branches:

https://github.com/mmatera/mathics-core/tree/benchmark_patch1
https://github.com/mmatera/mathics-core/tree/benchmark_patch2
https://github.com/mmatera/mathics-core/tree/benchmark_patch3

[rocky]

Good work! Patch 2 and 3 kind of go together because patch3 is making more things literal and patch 2 will speed things up when there are literals.

I am curious about whether the relational speedup is the same under pyston.

Was this 3.9 run with or without Cython?

[mmatera]

All without Cython. Pyston is the next step.

[mmatera]

Here the same with Pyston 3.8.12 (2.3.4)

branch	doctest	test1	test2	test3
origin/master	02:13.88	0.251	0.012	0.194
patch1	02:15.13	0.251	0.012	0.196
patch2	02:18.86	0.248	0.012	0.193
patch3	02:17.20	0.252	0.012	0.189

[rocky]

How well do patch2 and patch3 in combination work together? (patch2 is not needed)

Where are we with respect to which patches should go into master?

What can we tell people with respect to speedup over 4.0.0? (Or 3.0.0 or 2.0.0 if you like)

Although we get speedups using pyston, it isn't fair to claim pyston's speedups as our own. (Although it is good to mention the kinds of speedups pyston gives.)

However I suspect we get more of a speedup using pyston in the current code over the speedup run over 4.0.0 (and previous), and if that is so, it is okay to claim those additional speedups as our work.

Why do I think we get more improvement using pyston than we would in 4.0.0 and before?

The guess is based on the fact that the we let pyston do its thing more. Here there are two aspects. First is that we us Cython on more files in 4.0.0 and Cython is slower than pyston. Second, the caching stuff is basically a little at odds with letting pyston (and other JITs) do their thing. Third, related to the seconds is all the shared memory stuff is the kind of dynamism that a JIT like pyston can't handle.

However this is a guess, and I'd be interested to know the real situation.

With respect to where we are with the ListExpression/Expression improvements, I'll say that there are sill a small number of places to go over where we are creating Expressions instead of ListExpressions. These are those more subtle places where we would need to use make_expression() because sometimes Expression is needed and sometimes ListExpression.

And there are a couple bugs in keeping elements_properties up[ to date. It is possible that when this is fixed the benchmark+futher-improvements branch may slow down. But the overall speed we gain by the entire approach far outweighs the small slowdown we might have here or in some examples like F(x,x,x,x,x,x,x,x).

So in that respect, it would be nice to have WMA benchmarks that test longer and real WMA code.

[mmatera]

Here are the comparison of the results (with mathics-bench run in gitpod) for 4.0.0 vs the current master (after merging PR #400):

We can say that in some cases, we really gained a lot!

[mmatera]

A few more benchmarks. These are not so good, but tell us that we probably can improve this a lot by adjusting some specific routines (for instance walk_parts) to use the new interface.

[rocky]

Overall, I think we are on the right track.

Because there is a lot that goes up and a bit that goes down, what we give overall effect, and be transparent that some things slow down and in the following releases those will be addressed.

I have said before that this just scratches the surface for speedups we can get for expr.evaluate and the rewrite_apply_eval. I was not expecting this by any means to be close to the complete in terms of what we can get.

But the benchmarks can guide us as to where to focus on to get the biggest benefit.

[rocky]

With respect to Part and keeping properties in sync or not having to recompute them. The properties Flat, Order, and "fully evaluated" are often preserved when you simply remove pieces of a list and not change the order of the elements.

[rocky]

I have been thinking about what's up with the performance now versus when the Expression cache was doing more.

I think what's going on here is that when there are list literals, caching was doing the same thing as the fully_evaluated property. However caching has to go throw a slow path once before it can detect if something is fully evaluated to get it into the cache, whereas with the property it doesn't. And that means we avoid work sooner.

[mmatera]

Here are the benchmarks for the test_combinatorica, that I run over Gitpod:

(NO_CYTHON=1)
CPython 3.8.13 (default, Jun 19 2022, 14:08:28)
using SymPy 1.8, mpmath 1.2.1, numpy 1.23.0

benchmark	master	4.0.0dev	#403 (5f57c63)
'load_combinatorica'	731.83 ms	1087.76 ms	845.01 ms
'test_permutations_1_1'	2797.27 ms	3592.46 ms	3037.38 ms
'test_permutations_groups_1_2'	21283.00 ms	31403.70 ms	21979.92 ms
'test_inversions_and_inversion_vectors_1_3'	1911.86 ms	3192.06 ms	2073.70 ms
'test_special_classes_of_permutations_1_4'	955.95 ms	1926.73 ms	1003.32 ms
'test_combinations_1_5'	1439.34 ms	2000.36 ms	1644.27 ms
'test_2_1_to_2_3'	244.73 ms	293.12 ms	256.03 ms
'test_combinatorica_rest'	285.77 ms	368.91 ms	577.88 ms

At least for combinatorial, it seems that the current master provides significant improvements regarding the last version (20-30%).
What is funny here is that #403 does all worst: In master, the parameter elements_properties is discarded in the constructor, in a way that
we are not taking advantage of the properties previously computed. #403 tries to amend that but still seems to spoil the speedup.

[mmatera]

Benchmarks run in my laptop (the reported values are the best of 3 runs)
Pyston 2.3.4 (3.8.12)
NO_CYTHON=1
using SymPy 1.8, mpmath 1.2.1, numpy 1.21.4

test	master	#403	4.0.0dev
load_combinatorica	207.29 ms	179.93 ms	209.00 ms
test_permutations_1_1	881.47 ms	932.17 ms	1026.00 ms
test_permutations_groups_1_2	7593.88 ms	5801.66 m	7478.00 ms
test_inversions_and_inversion_vectors_1_3	713.37 ms	667.19 ms	655.00 ms
test_special_classes_of_permutations_1_4	404.48 ms	374.42 ms	367.00 ms
test_combinations_1_5	634.20 ms	614.28 ms	677.00 ms
test_2_1_to_2_3	93.29 ms	81.67 ms	85.00 ms
test_combinatorica_rest	129.06 ms	122.90 ms	113.00 ms

Benchmarks run in my laptop (the reported values are the best of 3 runs)
CPythoN (3.9.7)
NO_CYTHON=1
using SymPy 1.10.1, mpmath 1.2.1, numpy 1.20.3

test	master	#403	4.0.0dev
load_combinatorica	519.33 ms	468.56 ms	524.00 ms
test_permutations_1_1	1490.82 ms	1386.70 ms	1687.00 ms
test_permutations_groups_1_2	11475.65 ms	10628.71 ms	13045.00 ms
test_inversions_and_inversion_vectors_1_3	1023.96 ms	962.48 ms	1163.00 ms
test_special_classes_of_permutations_1_4	545.12 ms	502.93 ms	624.00 ms
test_combinations_1_5	777.90 ms	741.12 ms	1028.00 ms
test_2_1_to_2_3	139.38 ms	121.47 ms	184.00 ms
test_combinatorica_rest	163.00 ms	152.12 ms	242.00 ms