In my experiences with algebra dispatch in Julia, the combinatorial explosion of types can quickly grow into an issue, and the
Base methods for
+ are already quite overloaded with 100s of methods.
In the past, this has led to a discussion, where the conclusion was to implement tiered dispatch.
Basically, a new local variant of
+ is defined inside a module scope, and then a method can be added to the
Base instance by extending with referral dispatch:
+(x) = x # new local method scope Base.:+(x::MyDispatch) = +(x)
In this example, it’s just a simple example, a new method table is created for dispatching algebra. The new method need not keep the same name, but can.
So, I could define 50 more methods for
+ locally, while only globally extending by 1 method. The single (or few) global method can relay the dispatch into a different scope, while the new scope handles the dispatch of this name for a specific subset of subtypes.
When I first did this with
Reduce it made the package twice as fast as before and the compiled binary got smaller. Now, I am experimenting with dispatch in
Grassmann and found some ways of improving the situation and making the dispatch more snappy.
I already gained 0.5 seconds in load time, just by changing the way I dispatch algebra in
Grassmann. In Julia, a huge amount of effort and time seems to be lost due to the huge method tables of common algebra.
Since all my types in
TensorAlgebra by abstract supertype, it would also be possible for me to try having a simpler dispatch for
Base algebra by redirecting the method table to a different one. This is just an example of one abstract type.
Most of the time, the culprits for sluggish dispatch are the heavily overloaded
* methods, which already have 100s of methods by default.
Might it be possible to increase the performance of algebra dispatch for the entire language, by having tiered dispatch for
Number and so forth?
For example, define an
array_plus method somewhere to handle all
Array algebra dispatch, and then simply redirect the abstract type on the
Julia already comes with hundreds of
+ methods, and by defining my own algebras, the combinatorial explosion of types makes the method count increase very quickly, especially with code generation.
If you want to extend the
+ method for an
Array, then you would not extend the global
Base.:+ but instead a different method, which
Base redirects to for that particular abstract type.
The result of this would be a simplified dispatch with smaller method tables. Then the
Base algebra dispatch could have a smaller method table by default (and when I define more of my own). I think this simple change could potentially make all of Julia snappier.
Hope that makes sense.
So, my proposal or question is: would it make sense to have systematic tiered dispatch algebra for all common algebraic method names, to try to mitigate the combinatorial issue with types?