Understanding the dangers of abusing multiple dispatch

New to Julia
1

Hi, I’d like to understand more about this topic:

The dangers of abusing multiple dispatch
https://docs.julialang.org/en/v1.6-dev/manual/performance-tips/#The-dangers-of-abusing-multiple-dispatch-(aka,-more-on-types-with-values-as-parameters)-1

I don’t understand when we will get combinatorial explosion, quote

For example, you might imagine using it to store information, e.g.

struct Car{Make, Model}
    year::Int
    ...more fields...
end

and then dispatch on objects like Car{:Honda,:Accord}(year, args...) .

This might be worthwhile when either of the following are true:

  • You require CPU-intensive processing on each Car , and it becomes vastly more efficient if you know the Make and Model at compile time and the total number of different Make or Model that will be used is not too large.
  • You have homogenous lists of the same type of Car to process, so that you can store them all in an Array{Car{:Honda,:Accord},N}

When these do not hold, then it’s likely that you’ll get no benefit; worse, the resulting “combinatorial explosion of types” will be counterproductive.

Given Car{Make, Model} I guess we have combinations like:

Car{:Honda, :Civic)
Car{:Honda, :Accord)
Car{:Toyota, :Prius)
Car{:Toyota, :Corolla)

The combination should be Make x Model, which is polynomial (n*m), not exponential (n^m)

I wonder if someone can give a more elaborated example of the combinatorial explosion mentioned in the linked article?

Thanks

2

I think combinatorial explosion is an exaggeration. Technically the number of types is exponential in the number of parameters. The only practical example of this I can think of is if you try use tuples to store non homogeneous lists of objects. Anyway the manual is right that the car example is an anti pattern and will lead to slow code even if I would not call it combinatorial explosion.

3

The combinatorial explosion comes rather from something where each entry is independent, e.g.

Car{:Honda, :3_wheeler, :hatchback, :goodyear, :green, :sunroof}

5 Likes
4

I think there are more issues here beyond just the exponential complexity in the number of parameters.

There’s also the issue that you might have to search through much of the potentially large method space to decide which method is most specific. The make/model example AFAICT doesn’t highlight this issue because there’s no depth to the type hierarchy and no ambiguities I’m seeing. The possibility of ambiguities makes dispatch more expensive than simply looking up methods in a hash table indexed by “types as enums”. And even that’s more expensive than a simple branch on something like make == :Honda.

2 Likes