Efficiency of Multiple Dispatch

General Usage Performance
1

Hi, I have been curious about the working principle of Multiple Dispatch since I started to Julia. So, I would like to know that, is there some kind of conditional statements in lower level of Multiple Dispatch.

For example, there are 2 functions:

function f(::Type1, x, y, z)
       return x*y*z
end

function f(::Type2, x, y, z)
       return x+y+z
end

with inputs:

struct Type1 end
struct Type2 end

T = Type2()
x = 1.0
y = 2.0
z = 3.0

In this case when we call f(T, x, y, z), we get 6

So, during this process is there some kind of conditional statement performed in lower level?

Thank You.

1 Like
2

You’re right that there are conditional statements in this process. In a simplified description, the code undergoes both compilation and evaluation. If the compiler knows what function is being called and the types of the parameters passed to it, the code is “type stable”. Type stable code runs the conditional statements to determine which function to call, multiple dispatch, once during compilation. Then during evaluation, this compiled code can be reused.

This macro shows an early stage of the compilation process, and that the method being called is already known. There’s a lot of extra information that you don’t need to handle directly, but you can see the function f being called with types Type2, Float64, Float64, Float64, and that it uses + in the method body.

julia> @code_warntype f(T, x, y, z)
MethodInstance for f(::Type2, ::Float64, ::Float64, ::Float64)
  from f(::Type2, x, y, z) @ Main REPL[8]:1
Arguments
  #self#::Core.Const(Main.f)
  _::Core.Const(Type2())
  x::Float64
  y::Float64
  z::Float64
Body::Float64
1 ─ %1 = Main.:+::Core.Const(+)
│   %2 = (%1)(x, y, z)::Float64
└──      return %2
3 Likes
3

Thank you for your explanations.

Just to be clear for me, this conditional process only done once even if we have this kind of code:

Typle_Arr = [Type1(), Type2(), Type1()]
x_Arr = [1.0, 2.0, 3.0]
y_Arr = [1.0, 2.0, 3.0]
z_Arr = [1.0, 2.0, 3.0]
holder= [0.0, 0.0, 0.0]
function test!(Typle_Arr, x_Arr, y_Arr, z_Arr, holder)
       for i in eachindex(x_Arr)
               T = Typle_Arr[i]
               x = x_Arr[i]
               y = y_Arr[i]
               z = z_Arr[i]
              holder[i] = f(T, x, y, z)
       end
end

In this code type will change at every iterations, does that mean we will have same conditional statements that are going to perform at every iterations?

4

Very good observation! Since the type of the parameters change over the iterations, type-inference can’t determine the specific method that will be called ahead of time. This is called dynamic dispatch, since the method is determined during evaluation instead of compilation. The condition checking does need to happen each iteration, which is substantially slower than static dispatch from type-stable code. There are some optimizations to improve on limited type information though, but type-stability is the best way to know for certain that dispatch will be static, rather than dynamic. Once the method has been determined, it can still reuse compiled code.

The same macro as before can help identify problems with type-stability. Blue means type-stability, red means type-instability, and yellow means type-instability with some optimizations that make it a bit faster. Your first example was all blue, but this new example has blue, yellow, and red.

@code_warntype test!(Typle_Arr, x_Arr, y_Arr, z_Arr, holder)
2 Likes