Unexpected Allocations with Multiple Dispatch

General Usage Performance
1

I am setting up a multiple dispatch structure and get unexpected allocations when I use more than 3 dispatch types as illustrated in the MWE below:

Consider the following composite types:

for T in (:A, :B, :C)
    @eval begin
        struct $T
            n::Int
        end
    end
end

Now let’s make a general wrapper type:

struct General
    d::DataType
    n::Int
end

With this let’s define a method for creating A through C (3 types using dispatch):

f3(g::General) = f3(g.d, g)
for T in (:A, :B, :C)
    @eval begin
         f3(::Type{$T}, g) = $T(g.n)
    end
end

Before we test this, let’s add one more composite type D and setup a method f4 that dispatched off of 4 types:

struct D 
    n::Int
end

f4(g::General) = f4(g.d, g)
for T in (:A, :B, :C, :D)
    @eval begin
         f4(::Type{$T}, g) = $T(g.n)
    end
end

Ok, now let’s setup let’s compare:

gs = [General(A, i) for i in 1:1000]

function test(f, gs)
    for g in gs
        f(g)
    end
end

test(f3, gs)
test(f4, gs)
@time test(f3, gs)
@time test(f4, gs)

0.000009 seconds
0.000101 seconds (2.00 k allocations: 46.875 KiB)

Hence, the dispatch only using 3 types does not allocate as expected, but once 4 or more types are used it allocates and is an order of magnitude slower.

Could someone kindly provide an explanation and/or a workaround? Thanks!

2

Your General struct is (effectively) type-unstable because, although Julia knows that g.d is a DataType, it doesn’t know what datatype it is. It might be A, B, C, or D, or it might be Any or Int64 or Vector{Dict}. So when you call f4(g.d, g.n) Julia can’t statically resolve which method will be called or what it might return. It’s gotta pessimistically box up the return value and dynamically resolve its type at runtime with a pointer to arbitrarily-sized data. There’s your allocations.

So why doesn’t this happen with f3? Because Julia knows there are only a limited number (3) of methods… so it’s gotta be one of those. If it’s not, it’s an error, so it can just enumerate the possibilities from the method table itself. Instead of a boxed data with arbitrary types, it just puts in three branches, each of which is specialized with hard-coded dispatch to each particular method and specialized (on-stack/in-register) storage for the different return types. With a bit of (automatic) constant propagation you won’t even see those branches.

Add a fourth method to f3 — doesn’t matter what it is — and Julia will give up. It’ll invalidate all the functions it compiled that call f3 and ditch that optimization.

What’s the workaround? One option would be to ensure that the General struct knows — in its type! — what g.d is with a parameter:

struct General{T}
    d::Type{T}
    n::Int
end

Heck, now you don’t really even need that d member at all — the information is in the type parameter itself.

struct General{T}
    n::Int
end
General(::Type{T}, n) where {T} = General{T}(n)
5 Likes
3

Thank you for the explanation. The behavior makes a lot more sense now.

In my real use case, the analogue to General exists because I need to store mixed types in containers where I then do a lot of operations. So this enables concrete typed containers instead of abstract typed ones. Then it seems the tradeoff to the performance increase that comes from this is then reforming the underlying types to access the data that is associated with them which brings up the topic of this post.

Hence, changing General to General{T} would resolve this particular performance degradation, but then my containers would have to be typed abstractly which based on past experience will invoke a larger performance penalty.

I’ll have to find a happy medium. In any case, thank you for explaining what was going on under the hood.

1 Like