Runtime polymorphism overhead in Julia

Question

I understand that Julia heavily relies on just-in-time static type derivation (essentially all code needs to be thought of as c++ templates). I also get that this means there is no run-time overhead when using a single algorithm on objects of different type as long as those types are known at compile-time.

When it comes to run-time polymorphism I am less clear on how things work. Say we have the following situation:

abstract Shape

type Circle <: Shape
    radius::Float64
end

type Square <: Shape
    width::Float64
end

dist(x::Circle, y::Circle) = ...
dist(x::Circle, y::Square) = ...
dist(x::Square, y::Circle) = ...
dist(x::Square, y::Square) = ...


s = get_shape()
t = get_shape()
a = dist(s,t)

Here, get_shape can return either circles or squares, based on e.g. user input. In c++, dispatch would simply take a virtual table lookup. How does this work in Julia? What is the mechanism behind multiple dispatch? Is it significantly more expensive then virtual table lookup? Is there any benefit from deriving both Square and Circle from the same abstract type, or is this completely irrelevant in the context of run-time dispatching?

EDT: Running @code_warntype on this example gives:

Variables:
  s::Union{Circle,Square}
  t::Union{Circle,Square}

Body:
  begin  # none, line 2:
      s = (Main.get_shape)()::Union{Circle,Square} # none, line 3:
      t = (Main.get_shape)()::Union{Circle,Square} # none, line 4:
      return (Main.dist)(s::Union{Circle,Square},t::Union{Circle,Square})::ASCIIString
  end::ASCIIString

So the compiler is not completely clueless about the type of s and t. Is this knowledge used to expedite dispatching when calling dist?

Answer 1

When you have multiple methods for the same function, julia uses method lookup via type intersection (matching the types of the arguments to the types in the signature) to determine which method to call. If the types can be inferred, then that calculation can be performed when the code is being compiled. By doing the lookup ahead of time, it doesn't have to perform type intersection at run time, and this gives the best performance.

When the types are not predictable, then julia has to figure out which method to dispatch to at runtime. This can sometimes be a bottleneck on the runtime, if the called function is doing a trivial amount of work. (When it's doing a lot of work, the lookup is basically inconsequential for performance).

It's a slightly more complicated problem for julia than OOP languages, because the correct method depends on all the arguments, not just the first.