# Unexpected Allocations with Multiple Dispatch

**URL:** <https://discourse.julialang.org/t/unexpected-allocations-with-multiple-dispatch/76988>\
**Category:** Performance\
**Created:** [February 23, 2022, 6:53pm UTC](https://discourse.julialang.org/t/unexpected-allocations-with-multiple-dispatch/76988 "2022-02-23T18:53:34Z")\
**Posts on this page:** 3\
**Page:** 1

<div class="post-metadata">

**Author:** ![pulsipher](https://sea2.discourse-cdn.com/julialang/user_avatar/discourse.julialang.org/pulsipher/32/10461_2.png) [@pulsipher](https://discourse.julialang.org/u/pulsipher)\
**Post date:** [February 23, 2022, 6:53pm UTC](https://discourse.julialang.org/t/unexpected-allocations-with-multiple-dispatch/76988/1 "2022-02-23T18:53:34Z")

</div>

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:

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

```

Now let’s make a general wrapper type:

```julia
struct General
    d::DataType
    n::Int
end

```

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

```julia
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:

```julia
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:

```julia
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)

```

```julia
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!

---

<div class="post-metadata">

**Author:** ![mbauman](https://sea2.discourse-cdn.com/julialang/user_avatar/discourse.julialang.org/mbauman/32/31082_2.png) [@mbauman](https://discourse.julialang.org/u/mbauman)\
**Post date:** [February 23, 2022, 7:29pm UTC](https://discourse.julialang.org/t/unexpected-allocations-with-multiple-dispatch/76988/2 "2022-02-23T19:29:25Z")

</div>

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:

```julia
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.

```nohighlight
struct General{T}
    n::Int
end
General(::Type{T}, n) where {T} = General{T}(n)

```

---

<div class="post-metadata">

**Author:** ![pulsipher](https://sea2.discourse-cdn.com/julialang/user_avatar/discourse.julialang.org/pulsipher/32/10461_2.png) [@pulsipher](https://discourse.julialang.org/u/pulsipher)\
**Post date:** [February 23, 2022, 9:53pm UTC](https://discourse.julialang.org/t/unexpected-allocations-with-multiple-dispatch/76988/3 "2022-02-23T21:53:58Z")

</div>

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.