Compilation as a step to improving execution speed

[rocky]

In thinking about things over the last couple of days, I think the time is right for me to start looking at how we can improve execution time from the lens of working on compilation.

I'd like to back up a little bit first though. Ever since I started working on Mathics (and maybe even a little bit before) translation to Sympy was an interest. However ever since i started working on Mathics there were so many other more pressing needs like:

• getting the code to work on Python 3.x,
• getting documentation PDF to compile regularly,
• getting Continuous Integration under control,
• getting a release out after 5 or so years, and then subsequent releases (and/or docker builds) in a less haphazard function.
• spitting up the code base and starting to make it more modular and separable

Not strictly needed, but nice to have were organizing the docs and starting a guide to the overall organization.

And then most recently what I have largely been about looking over largely looking over what others have been doing, which always feel a little bit like catch up work. A bit of this feels more like chore work rather than things I want to spend my spare time on.

But now, especially since improving performance I realize is a big thing - we can't load Rubi rules for example - now is the time to go back to stuff that I was interested in from the beginning. And I think that by doing that we may also be in a better position to address some of the performance problems outside of compilation. But that may take a bit of explaining in due course.

To start out though, I'll pick up the compilation aspect threads from earlier:

Regarding the second part, the problem with symbolic evaluation is that the same expression can be evaluated to different values in different places. For example:

a=1; {F[a], a=a+1; F[a]} returns {Sin[1], Sin[2]}, not {Sin[1],Sin[1]}.

Yes, looks hard doesn't it? Fortunately minds greater than ours have studied problems like this and have come up with solutions. What we should be doing is understanding this and building upon it.

One misunderstanding is how Constant propagation (and related optimizations) work . The first step that is done in compilers is to rewrite the code in SSA Form. (By the way, Ken Zadeck and Mark Wegman are colleagues/friends).

If you do that here what you'd get is

a0=1; {F[a0], a1=a0+1; F[a1]}

and it is now clear that F[a0] doesn't have to be he same result as F[a1]. (And here, it never is.)

I find this example amusing for another reason though. In our code base the kind of confusion created by writing a = a + 1 is the kind of confusing code I often see in our code base and sometimes remark on.

In fact, this idiom was used in a recent PR, and I had thought to remark on it, but held back because in that situation the type of updated variable (a above) stayed the same. In the PR, we it was a transformation from one Mathics Expression to another.

But in other places we sometimes have a variable of one type, such as a Mathics Integer getting converted to a Python integer and in both places the variable name stays the same.

Personally, I think this is bad coding style for a couple of reasons. The most serious one in my opinion is the confusion it can cause a programmer looking at the code. When that variable appears, which type is it? Is it a Python integer, or a Mathics Integer? A programmer often needs to keep this in mind because it influences what operations can be done on it or how it can be used such as whether it is in the right form as a parameter in a function call.

But in strongly typed languages, you just aren't allowed to do this, possibly for exactly this reason. (It makes it a little harder or more time consuming for an optimizing compiler to figure this out although it can if it were necessary, and here it is not desirable.)

Coming back to the F[a]; a += 1; ... things are trickier when this is inside a loop. But there I'll just say go read how this works in compiler optimization and let's come back to this if needed after looking at that.

Continuing the concerns raised...

Consider this:

F[x_]=a*x; a=1; {F[2], a=2*a;F[2]}

This example is an interesting example to showing subtitles in implementing caching. You can't indefinitely cache expression F[2] here because F[2] contains non-local variables a, and x so when either of these variables changes, the cache for F[2] needs to be invalidated. One of the cool things that compilation has over caching is that compilation gets to look at a bigger context than F[2] in order to decide what to do. It has advantage in this static behavior. It also has disadvantages in not being able to handle certain kinds of dynamic behavior and that can be handling using a cache, assuming those subtleties in cache invalidation are addressed. Sometimes though all the work in detecting cache invalidation swamps the benefit of a cache. And that might be happening in Mathics.

There are a couple of other levels that get mixed in the example above and that we should straighten out, lest it continue to cause confusion which it potentially can be doing here.

There are really two language levels that I see going on in WMA evaluation. There is a kind of symbolic substitution and then at the core there can sometimes be other kinds of evaluation like the kind that is done for common arithmetic functions.

Aside:
I think in theory all arithmetic calculation could be done using symbolic substitution, but in practice it isn't feasible. There was a GNU Make debugger that in fact did arithmetic calculation by turning everything into unary notation since there was no possibility for arithmetic calculation. But Mathematica and Mathics don't do things this horrendous way which would make things even slower, although theoretically simpler.

A good bit of the traditional kinds of compiler optimization that go on would be done after symbolic substitution is done to the extent possible. Mathics evaluation freely intertwines symbolic and non-symbolic execution. And there will always be situations where this has to be done. But to the extent it can be minimized, I suspect we want to do that. Whether or not we compile code. And there are a number of situations that are in this category.

One of the cool things about compiler optimization in contrast to say code generation is that it is optional: if things get too complex you can just leave things alone and do nothing.

As for the example using a user-defined definition of F[], to start out easy, it is fine just to start considering built-in functions and symbols and expand to user-defined definitions later.

Deferring detailed discussion also has the advantage that I expect the two levels of internal representation will be more concrete, so it will be easier to think about and discuss stuff like this.

A topic for some other time: I suspect, although I don't know for sure, that if you compile a function in Mathematica and then change say the definition of Plus later, the compiled function might not include the redefinition afterwards. And whether this is the case, in Mathics it is probably fine to make this be the situation whichever way Mathematica works. The dynamic nature there is for reasonable coherent flexibility, and when it can cause grave confusion and obfuscated code it probably shouldn't be supported or encouraged. I am not saying that specific example falls into this situation, though. But I will repeat that if things get too complicated or convoluted it is fine to skip it initially and come back to it or skip it forever.

This is long, but there is one additional point I'd like to briefly mention one other aspect. I fully expect that in starting out with clear-cut and simple examples where things can be simplified using simple compiler optimization technology, it will guide us into making more explicit this underlying programming language that implicitly exists where what you want is some kind of form that removes all of the substitution and dynamic lookup properties that can be done.

[mmatera]

In thinking about things over the last couple of days, I think the time is right for me to start looking at how we can improve execution time from the lens of working on compilation.

Sounds like a good idea. I think some of the work is already done in the mathics.builtin.compilation module, but in a still too raw stage. Something nice about this is that you can build a framework for doing the compilation without touching the Expression.evaluate() method: you can develop it and at the end, decide if you call it inside the evaluate method, or in some specific apply methods.

I'd like to back up a little bit first though. Ever since I started working on Mathics (and maybe even a little bit before) translation to Sympy was an interest. However ever since i started working on Mathics there were so many other more pressing needs like: ...

This was a terrific good step forward.

... Yes, looks hard doesn't it? Fortunately minds greater than ours have studied problems like this and have come up with solutions. What we should be doing is understanding this and building upon it.

OK, now I understand better what were you talking about. In any case, as I do not have any background in compilers theory, I am not even able to formulate the problems, so I would hardly be able to look for existent solutions for these problems.

A topic for some other time: I suspect, although I don't know for sure, that if you compile a function in Mathematica and then change say the definition of Plus later, the compiled function might not include the redefinition afterwards.

I think you are right: Inside Compile, Plus always has the built-in behavior. I had a reference of a paper in someplace where this kind of detail of the WMA compiler is explained. I can put it here when I find it.