Claim (false): Julia isn't multiple dispatch but overloading

General Usage
15

@dataSurfer, you can check for yourself, no need to rely on rumors:

julia> g(c) = f(@inbounds c[1])
g (generic function with 1 method)

julia> f(::Int) = 1
f (generic function with 1 method)

julia> f(::Bool) = 2
f (generic function with 2 methods)

julia> g(Any[3])
1

julia> g(Any[true])
2

julia> code_typed(g, (Vector{Any},))
1-element Array{Any,1}:
 CodeInfo(
1 ─ %1  = Base.arrayref(false, c, 1)::Any
│   %2  = (isa)(%1, Bool)::Bool
└──       goto #3 if not %2
2 ─       goto #6
3 ─ %5  = (isa)(%1, Int64)::Bool
└──       goto #5 if not %5
4 ─       goto #6
5 ─ %8  = Main.f(%1)::Int64
└──       goto #6
6 ┄ %10 = φ (#2 => 2, #4 => 1, #5 => %8)::Int64
└──       return %10
) => Int64

So, two of the calls are made at compile-time after checking to see if it’s a Bool or an Int. But then notice that third Main.f(%1) call, which is what gets used if the input is neither a Bool nor an Int. That’s the runtime-dispatch version, which you can see in greater detail with

julia> code_llvm(g, (Vector{Any},))

define i64 @julia_g_264(%jl_value_t* nonnull align 16 dereferenceable(40)) {
top:
  %1 = alloca %jl_value_t*
  %gcframe = alloca %jl_value_t*, i32 3, align 16
  %2 = bitcast %jl_value_t** %gcframe to i8*
  call void @llvm.memset.p0i8.i32(i8* align 16 %2, i8 0, i32 24, i1 false)
  %thread_ptr = call i8* asm "movq %fs:0, $0", "=r"()
  %ptls_i8 = getelementptr i8, i8* %thread_ptr, i64 -15720
  %ptls = bitcast i8* %ptls_i8 to %jl_value_t***
  %3 = getelementptr %jl_value_t*, %jl_value_t** %gcframe, i32 0
  %4 = bitcast %jl_value_t** %3 to i64*
  store i64 4, i64* %4
  %5 = getelementptr %jl_value_t**, %jl_value_t*** %ptls, i32 0
  %6 = getelementptr %jl_value_t*, %jl_value_t** %gcframe, i32 1
  %7 = bitcast %jl_value_t** %6 to %jl_value_t***
  %8 = load %jl_value_t**, %jl_value_t*** %5
  store %jl_value_t** %8, %jl_value_t*** %7
  %9 = bitcast %jl_value_t*** %5 to %jl_value_t***
  store %jl_value_t** %gcframe, %jl_value_t*** %9
  %10 = bitcast %jl_value_t* %0 to %jl_value_t***
  %11 = load %jl_value_t**, %jl_value_t*** %10, align 8
  %12 = load %jl_value_t*, %jl_value_t** %11, align 8
  %13 = icmp eq %jl_value_t* %12, null
  br i1 %13, label %fail, label %pass

L5:                                               ; preds = %pass
  %14 = icmp eq %jl_value_t* %28, inttoptr (i64 140386210668768 to %jl_value_t*)
  br i1 %14, label %L10, label %L8

L8:                                               ; preds = %L5
  %15 = getelementptr %jl_value_t*, %jl_value_t** %gcframe, i32 2
  store %jl_value_t* %12, %jl_value_t** %15
  %16 = getelementptr %jl_value_t*, %jl_value_t** %1, i32 0
  store %jl_value_t* %12, %jl_value_t** %16
  %17 = call nonnull %jl_value_t* @jl_apply_generic(%jl_value_t* inttoptr (i64 140386134835232 to %jl_value_t*), %jl_value_t** %1, i32 1)
  %18 = bitcast %jl_value_t* %17 to i64*
  %19 = load i64, i64* %18, align 8
  br label %L10

L10:                                              ; preds = %pass, %L8, %L5
  %value_phi = phi i64 [ %19, %L8 ], [ 2, %pass ], [ 1, %L5 ]
  %20 = getelementptr %jl_value_t*, %jl_value_t** %gcframe, i32 1
  %21 = load %jl_value_t*, %jl_value_t** %20
  %22 = getelementptr %jl_value_t**, %jl_value_t*** %ptls, i32 0
  %23 = bitcast %jl_value_t*** %22 to %jl_value_t**
  store %jl_value_t* %21, %jl_value_t** %23
  ret i64 %value_phi

fail:                                             ; preds = %top
  call void @jl_throw(%jl_value_t* inttoptr (i64 140386213625328 to %jl_value_t*))
  unreachable

pass:                                             ; preds = %top
  %24 = bitcast %jl_value_t* %12 to i64*
  %25 = getelementptr i64, i64* %24, i64 -1
  %26 = load i64, i64* %25
  %27 = and i64 %26, -16
  %28 = inttoptr i64 %27 to %jl_value_t*
  %29 = icmp eq %jl_value_t* %28, inttoptr (i64 140386211212192 to %jl_value_t*)
  br i1 %29, label %L10, label %L5
}

Since you seem to know something about C/C++, you can check the source of jl_apply_generic yourself.

If you add enough methods to f, then Julia gives up on trying to guess and recompiles g to only use runtime dispatch (when it can’t figure out what the element type will be in advance):

julia> f(::Float64) = 3
f (generic function with 3 methods)

julia> f(::String) = 4
f (generic function with 4 methods)

julia> code_typed(g, (Vector{Any},))
1-element Array{Any,1}:
 CodeInfo(
1 ─ %1 = Base.arrayref(false, c, 1)::Any
│   %2 = Main.f(%1)::Any
└──      return %2
) => Any

A key point with this last version is the following: suppose PkgA defines g and those 4 methods of f. It precompiles them and saves them to the *.ji file. Now PkgB uses PkgA and defines a 5th method of f. g will not be recompiled because the limit for trying to be clever has already been exceeded. Nevertheless g will accurately dispatch to the new f method when fed a container with appropriate elements.

Runtime dispatch, Q.E.D.

35 Likes