Tiered dispatch algebra

Internals & Design
,
1

In my experience, I have programmed a lot of algebra in the Julia language (created Dendriform.jl, Reduce.jl, Grassmann.jl). Here’s a question:

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 Grassmann are 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 + and * 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 Array and 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 Base.:+ method?

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?

5 Likes
2

As someone who is also suffering from significant compilation times occassionaly, I am definitely interested in this question/proposal and hope that someone knowledgable finds the time to respond.

One question I had with this proposal, is what is actually significant? Is it the number of method definitions in the code, or the number of differently compiled instances? Because even if say Base.:+ has a single entry point for all AbstractArray types, which then call an internal array_plus method, then either

  • you have to force the outer Base.:+ to not specialize on the specific leaf types of the arrays involved, and so it has to resort to dynamic dispatch at run time, coming with some overhead (which might add up if this is the case for many such methods)

  • you let the compiler specialize, but then you end up with as many compiled methods of Base.:+ as if you would just have defined Base.:+ for the all of the specific AbstractArray types as is currently the case

Of course, there is still a difference, as all the array types which you don’t use in a given Julia session do still add to the method table of Base.:+ definitions in the current scheme, whereas they would not in the proposed scheme.

Hence the question, is it the number of defined (but not necessarily compiled) methods which is the relevant parameter, or is it the number of differently compiled/specialized methods?

2 Likes
3

What I found is I can improve the situation by reducing the number of method definitions (not compiled instances). So if I can get as many different compiled instances as possible into a single definition, the better.

It’s better because the compiled binary gets smaller, there is less effort in extending the method tables.

However, that’s a slightly separate issue from tiered dispatch I am talking about in my first post.

4

Well, I guess it’s very much related, as tiered dispatch provides a way to get a lot of many different instances into a single definition, just because that definition then postpones the dispatch to a lower level, and thus provides a branching structure into what is otherwise a long linear list. Very interesting; I would definitely also like to hear the opinion of others.

5

Yes, that can be combined with the tiered dispatch concept, which I am already doing. Being able to combine the concepts makes them slightly seperate.

But that’s just semantics.

Making a branching tree is the point, it’s a faster search. Then, reducing the overall number of definitions also helps further improve the situation (separately).

6

Method tables already do this. My hunch is that you’re running into invalidations.

5 Likes
7

That’s probably correct @mbauman, yet in my proposal the dispatch is specifically customized into a tree based on design decisions. If Julia already uses trees for this purpose, those trees were not specifically designed for a particular algebra… those trees would be determined by generic algorithms, while the trees I propose would specifically be chosen for certain type structures (based on knowledge we have as designers and have control over, as opposed to a generic algorithm).

8

Perhaps this comment belongs more in the aforementioned discussion, but when learning Julia I was surprised and somewhat concerned that the method table is global. Code that doesn’t depend in any way on my module doesn’t seem to have any good reason to be able to see the methods that my module introduces. So it seems like it could be beneficial to somehow give methods a lexical scope, but I’ll admit I haven’t thought through how this would really work.

3 Likes
9

I am not sure what “see” means in this context. But if you don’t use a type, that part of the method table plays no role for your code.

10

Moreover, if some code does somehow end up with a value of some type that it knows nothing about (say it’s passed in from outside), and it in turn passes that value to some other code which calls a function that does have methods for that type (e.g. by shared dependencies or by higher order functions), what do you want it to do?

  1. Throw a no method error
  2. Call the wrong method
  3. Work correctly

The method error and wrong method behaviors are what you get if method tables are not global, which depends on the whether there is an applicable generic fallback method or not. The option which leads to “work correctly” is the one where generic methods have global method tables.

6 Likes
11

@Tamas_Papp “see a method” means consider it as a possible dispatch target.

@StefanKarpinski Yes, it only makes sense for methods for new types to be globally visible.

I guess I was coming at this from a more type-piraty point of view. For example, there have been multiple occasions where I have wanted to extend or modify the behavior of existing methods and types (from Base or external packages) for use within my own code, but without the risk of breaking code that is not mine (including Base). But I am coming to appreciate that the distinction between “my own code” and “everything else” (i.e. @chakravala’s notion of “context”) is perhaps not as clear cut as I had imagined.

1 Like
12

Note that I am not against global method tables, my proposal is only to adjust the situation for specific methods that get overloaded more than usual, such as the methods for +, and I am not talking about eliminating the global method or applying it to all things.

It could all be a stupid idea, but worth considering.

13

A mechanism for “local piracy” does make some sense, but seems complex, hard to make work, and like it may be better to just do what we’ve done and discourage piracy.

2 Likes
14

Let me see if I can rephrase what you’re getting at: You know more about the typical dispatch patterns for code that calls into your modules, so you want to be able to give a hint to inference by defining a prioritized tree structure for inference to search first; of course, to achieve Stefan’s point 3, we should eventually fall back to a full search of the global method table. What you’re proposing is a library developer-driven optimization to inference that nudges it in what you believe is the right direction for looking up the most specific method. Does this sound like a reasonably accurate interpretation?

If so, the issue I see with this is that, to determine the most specific matching method (which supposedly is a method defined in your package), you must take into account methods defined in other packages, because those methods might actually be more specific. So you need to figure out how to guarantee to inference that all other methods are less specific, or else you’re effectively committing a form of type piracy (because your “hints” can steal away dispatches to methods that would otherwise be called). Of course, this isn’t always a bad thing, and can have value as an implementation of this hypothetical local piracy, but it’s important if you want this behavior to become the default.

1 Like