# Function inside struct allocates when referenced

**URL:** <https://discourse.julialang.org/t/function-inside-struct-allocates-when-referenced/105785>\
**Category:** New to Julia\
**Tags:** function\
**Created:** [November 4, 2023, 4:55am UTC](https://discourse.julialang.org/t/function-inside-struct-allocates-when-referenced/105785 "2023-11-04T04:55:37Z")\
**Posts on this page:** 6\
**Page:** 2

<div class="post-metadata">

**Author:** ![abraemer](https://sea2.discourse-cdn.com/julialang/user_avatar/discourse.julialang.org/abraemer/32/51403_2.png) [@abraemer](https://discourse.julialang.org/u/abraemer)\
**Post date:** [November 7, 2023, 10:39am UTC](https://discourse.julialang.org/t/function-inside-struct-allocates-when-referenced/105785/21 "2023-11-07T10:39:56Z")

</div>

I’ll try to explain more in-depth the whole type-stability story with functions and the different options and what my thought process was to get to this statement:

> [@izod2](#):
>
> Finally, it was noted in the comment above:
> 
> > I don’t think it really matters in your case how you store the information of which function to call. There will always be a dynamic dispatch since the compiler can never known which functions there will be.

# Setup

Suppose we have some agents that can show variable behaviors. Let’s parametrize the behaviors to be able to explore different ways of implementing this. So the `Agent` looks something like this

```julia-auto
struct Agent{T}
    behaviors::T
end

```

and we have multiple behaviors like:

```julia-auto
function behavior1(x)
    x
end
function behavior2(x)
    x
end
function behavior3(x)
    x
end

```

Note each behavior function is its own type:

```julia-repl
julia> typeof(behavior1)
typeof(behavior1) (singleton type of function behavior1, subtype of Function)
julia> typeof(behavior1) == typeof(behavior2)
false

```

A way to test for dispatch:

```julia-auto
function testbehaviors(agent)
    for behavior in agent.behaviors
        behavior(agent)
    end
end
function testagents(agents)
    for agent in agents
        testbehaviors(agent)
    end
end

```

# Variant 1: `Vector{Function}`

This is what you originally did. Just put different `behavior`s in a vector and stick it in the `Agent`

```julia-repl
julia> Agent([behavior1, behavior2])
Agent{Vector{Function}}(Function[behavior1, behavior2])
julia> @btime testbehaviors(Agent([behavior1, behavior2]))
  56.770 ns (3 allocations: 96 bytes)

```

This gives allocations, because Julia needs to do a dynamic dispatch, because `Vector{Function}` is a [abstractly typed container](https://docs.julialang.org/en/v1/manual/performance-tips/#man-performance-abstract-container), meaning Julia cannot infer what function to call from its type.

But the upside here is that every `Agent` constructed this way has the same type:

```julia-repl
julia> typeof(Agent([behavior2, behavior3])) == typeof(Agent([behavior1, behavior2]))
true

```

# Variant 2: use `Tuple` instead of `Vector`

This puts the information which `behavior`s an `Agent` has into the type-domain, so Julia knows which functions to call at compile time:

```julia-repl
julia> Agent((behavior1, behavior2))
Agent{Tuple{typeof(behavior1), typeof(behavior2)}}((behavior1, behavior2))
julia> @btime testbehaviors(Agent((behavior1, behavior2)))
  8.600 ns (0 allocations: 0 bytes)

```

However this has the downside, that now `Agent`s with different `behavior`s have different types:

```julia-repl
julia> typeof(Agent((behavior1, behavior2)))
Agent{Tuple{typeof(behavior1), typeof(behavior2)}}
julia> typeof(Agent((behavior3, behavior1)))
Agent{Tuple{typeof(behavior3), typeof(behavior1)}}

```

So if you where to stick these different `Agent`s into a `Vector` then your type-stability is gone again and you have just moved it to a different place. This is part of what my comment alluded to.

```julia-repl
julia> agents = [Agent((behavior1, behavior2)), Agent((behavior3, behavior1)), Agent((behavior2, behavior3))];
julia> @btime testbehaviors.($agents)
  58.179 ns (0 allocations: 0 bytes)

```

Interestingly, this dynamic dispatch does not cause allocations and I am not sure why. However it still is slower than if Julia knowns all the types:

```julia-repl
julia> @btime testagents($(Tuple(agents)))
  40.242 ns (0 allocations: 0 bytes)

```

# Variant 3: Use some external lookup like `Dict`

The next idea was to just store some indices inside the `Agent`s and perform a lookup in some external structure, f.e.

```julia-repl
julia> function testbehaviors_lookup(lookup, agent)
            for behavior in agent.behaviors
                lookup[behavior](agent)
            end
        end
julia> function testagents_lookup(lookup, agents)
            for agent in agents
                testbehaviors_lookup(lookup, agent)
            end
        end

julia> agents_lookup = [Agent([1,2]), Agent([2,3]), Agent([3,1])] # concretely typed container!
3-element Vector{Agent{Vector{Int64}}}: ...

julia> lookupdict = Dict(1=>behavior1, 2=>behavior2, 3=>behavior3);
# is Dict{Int, Function}, so still type-unstable and has (relatively) slow lookup of Dict
julia> lookupvector = [behavior1,behavior2,behavior3];
# still type-unstable, but faster lookup then Dict
julia> lookuptuple = (behavior1,behavior2,behavior3);
# type-stable for indices known at compile time, but still type-unstable in dynamics context

julia> @btime testagents_lookup($lookupdict, $agents_lookup)
  103.832 ns (6 allocations: 96 bytes)
julia> @btime testagents_lookup($lookupvector, $agents_lookup)
  90.372 ns (6 allocations: 96 bytes)
julia> @btime testagents_lookup($lookuptuple, $agents_lookup)
  47.434 ns (0 allocations: 0 bytes)

```

Essentially this just puts the type-instability elsewhere again. This is the second thing, that lead me to my comment.

Actually the last one could be considered sort-of type-stable, since the tuple is very short and thus Julia can perform [union-splitting](https://julialang.org/blog/2018/08/union-splitting/), which essentially turns it into static dispatch. One can verify this using `julia> @code_warntype testbehaviors_lookup(lookuptuple, agents_lookup[1])` which shows no red types and just highlights the union of the 3 `behavior` functions. (compared to a evil, red annotation you get for `@code_warntype testbehaviors_lookup(lookupvector, agents_lookup[1])`)

# Variant 4: Static dispatch

This was proposed by @nsajko . Essentially instead of some dynamic structure like `Vector` or `Tuple`, we could just write out every case. This makes the dispatch explicit and static, so nothing left at runtime but a (unavoidable) branch. Note that this is essentially what Julia did for us automatically in the `Tuple` case above.  
Also note that the idea of @Salmon is also closely related to this static dispatch idea.

This approach is fully type-stable (as long as the `behavior` functions have the same return type) but is not flexible.

# Variant 5: Use `FunctionWrapper`

If all function have the same signature, then ideally we could communicate this to Julia and then Julia could treat the functions just as something like a function pointer which it blindly follows. This functionality is not built-in but provided by [`FunctionWrappers.jl`](https://github.com/yuyichao/FunctionWrappers.jl).  
So we can now do (need to slightly restructure the type):

```julia-repl
julia> import FunctionWrappers: FunctionWrapper
julia> struct Agent2
            behaviors::FunctionWrapper{Agent2, Tuple{Agent2}}
        end
julia> agents_fwrap = [Agent2([behavior1,behavior2]), Agent2([behavior3,behavior1]), Agent2([behavior2,behavior3])]
julia> @btime testagents($agents_fwrap)
  31.057 ns (0 allocations: 0 bytes)

```

This approach seems the fastest and is also the most flexible but relies on an external dependency that uses Julia internals, which can be considered a downside.

---

<div class="post-metadata">

**Author:** ![Benny](https://avatars.discourse-cdn.com/v4/letter/b/49beb7/32.png) [@Benny](https://discourse.julialang.org/u/Benny)\
**Post date:** [November 7, 2023, 2:02pm UTC](https://discourse.julialang.org/t/function-inside-struct-allocates-when-referenced/105785/22 "2023-11-07T14:02:03Z")

</div>

> [@abraemer](#):
>
> If all function have the same signature, then ideally we could communicate this to Julia and then Julia could treat the functions just as something like a function pointer which it blindly follows.

FunctionWrappers is not this blind, it safeguards the types. The call signature restriction parametizes the wrapper with the _intended_ return type and argument types, and the wrapper constructor takes a function as an argument.

1. Taking the function as an argument is almost self-explanatory, we are trying to group function calls together in a language where functions don’t have fixed input types and return types. So, a concrete wrapper type constructor must take any function as an input.

2. Fixing the return type provides type stability of the functions’ output, which is the bare minimum of categorizing functions in statically typed languages. Since there’s no guarantee of type stability of 1 method, let alone several functions, a `convert` step of the return value is added after calling the wrapped function. This accommodates type-unstable methods, but a `convert` with an uninferred input would need a runtime dispatch so it’s best to stick to type-stable methods if you’re going this far to avoid runtime dispatches and allocations.

3. Fixing the argument types provides the rest of the necessary information to dispatch and compile a function call given the wrapped function, and the wrapper stores the compiled code to skip over the typical dispatch mechanism. A `convert` step of the input arguments is also added before calling the wrapped function. (Hypothetically, function calls could be grouped by return type alone so the argument types could be a field instead of parameters of the wrapper type, but it seems a little crazy to micromanage that for every element of an array of call signatures only to probably input the same argument types every iteration.)

So a FunctionWrapper incurs a runtime cost to make sure what goes in and out of the wrapped compiled code is type-safe, though several `convert`s are usually cheaper than a runtime dispatch. EDIT: those `convert`s might be no-ops if the compiler infers the inputs already are the target type. Also the stored compiled code is not updated when the original method is edited, so use `reinit_wrapper` on existing instances or replace them entirely.

I’ve never used it, but there is a package FunctionWranglers.jl that doesn’t incur this cost. Rather than wrapping a function one by one, it takes in entire arrays of functions and uses recursively inlined generated functions to unroll loops over them in a set of higher order functions. Think the if-statements checking the function in Variant 4, but the if-statements check the _index_ so the same function at different indices still get their own branch. I’ve never reached for this because the `map`-like function requires the same input values for each call, indexing the wrangled array isn’t constant time (again, massive unrolled loop), and you can forget about any array mutations after it gets wrangled into recursive immutable `struct` instances. The repository hasn’t been touched for a couple years but I’m guessing it works because the package has no dependencies and I haven’t spotted any internal or unstable features in the short source file.

---

<div class="post-metadata">

**Author:** ![Salmon](https://sea2.discourse-cdn.com/julialang/user_avatar/discourse.julialang.org/salmon/32/22968_2.png) [@Salmon](https://discourse.julialang.org/u/Salmon)\
**Post date:** [November 7, 2023, 2:27pm UTC](https://discourse.julialang.org/t/function-inside-struct-allocates-when-referenced/105785/23 "2023-11-07T14:27:19Z")

</div>

This is actually a great summary. I have thought before that it would probably be a great idea to summarize all approaches into a blog post on the Julia Forem, this is a good start for something like this.

> [@abraemer](#):
>
> ```julia
> julia> Agent([behavior1, behavior2])
> Agent{Vector{Function}}(Function[behavior1, behavior2])
> julia> @btime testbehaviors(Agent([behavior1, behavior2]))
> 56.770 ns (3 allocations: 96 bytes)
> 
> ```
> 
> This gives allocations, because Julia needs to do a dynamic dispatch, because `Vector{Function}` is a [abstractly typed container](https://docs.julialang.org/en/v1/manual/performance-tips/#man-performance-abstract-container), meaning Julia cannot infer what function to call from its type.

By the way this code also counts the allocation of the array in the constructor (although it does not make much of a difference here)

> [@abraemer](#):
>
> This approach seems the fastest and is also the most flexible but relies on an external dependency that uses Julia internals, which can be considered a downside.

Perhaps I misunderstand but are you saying that a FunctionWrapper can be faster than a functor? The way I see it, a functor should be the most performant as it can be fully inlined without need for pointers to functions.

---

<div class="post-metadata">

**Author:** ![Benny](https://avatars.discourse-cdn.com/v4/letter/b/49beb7/32.png) [@Benny](https://discourse.julialang.org/u/Benny)\
**Post date:** [November 7, 2023, 2:36pm UTC](https://discourse.julialang.org/t/function-inside-struct-allocates-when-referenced/105785/24 "2023-11-07T14:36:57Z")

</div>

> [@Salmon](#):
>
> Perhaps I misunderstand but are you saying that a FunctionWrapper can be faster than a functor?

The variants writeup did not consider functors because functors are restricted to the same method table of their 1 type, which the setup rejects: “Note each behavior function is its own type”. You are right to prefer functors over any of those variants if you can.

---

<div class="post-metadata">

**Author:** ![abraemer](https://sea2.discourse-cdn.com/julialang/user_avatar/discourse.julialang.org/abraemer/32/51403_2.png) [@abraemer](https://discourse.julialang.org/u/abraemer)\
**Post date:** [November 7, 2023, 3:22pm UTC](https://discourse.julialang.org/t/function-inside-struct-allocates-when-referenced/105785/25 "2023-11-07T15:22:22Z")

</div>

> [@Benny](#):
>
> The variants writeup did not consider functors because functors are restricted to the same method table of their 1 type, which the setup rejects: “Note each behavior function is its own type”. You are right to prefer functors over any of those variants if you can.

Alternatively, functors could be seen as a variant of what I wrote under “static dispatch”. Consider

```julia
struct MyBehaviors
    index::Int
end
function (behavior::MyBehavior)(x)
    if behavior.index == 1
        behavior1(x)
    elseif behavior.index == 2
        behavior2(x)
    else
        behavior3(x)
    end
end

```

So the functors are, in my view, a bit of generalization of static dispatch because you could pass some additional parameters along but in essence have the same limititations as static dispatch.

@Benny thanks for clarifying `FunctionWrappers.jl` some more! I actually never it myself either 😄

> [@Salmon](#):
>
> This is actually a great summary. I have thought before that it would probably be a great idea to summarize all approaches into a blog post on the Julia Forem, this is a good start for something like this.

Glad you like it! It was actually part of my motivation to put this somewhere where it could be helpful for more people, so the Forem seems like a good idea 🙂  
I’d like to expand it a bit more with explanations (and fix the slight error you found). Tbh, I ran a bit out of time this morning and had to cut things a bit short and couldn’t reread the whole thing again 😅

So please everyone give feedback on how to improve this to make it a good resource for everyone 🙂

---

<div class="post-metadata">

**Author:** ![Salmon](https://sea2.discourse-cdn.com/julialang/user_avatar/discourse.julialang.org/salmon/32/22968_2.png) [@Salmon](https://discourse.julialang.org/u/Salmon)\
**Post date:** [November 7, 2023, 4:41pm UTC](https://discourse.julialang.org/t/function-inside-struct-allocates-when-referenced/105785/26 "2023-11-07T16:41:16Z")

</div>

> [@abraemer](#):
>
> So please everyone give feedback on how to improve this to make it a good resource for everyone 🙂

If you’re interested in more feedback here are some thoughts :).

- I think it really is worth making the example of functors more explicit. Your example mentions it as a special case of completely different functions where one performs a runtime check, but there are also many other cases that people might naively think o using vectors of functions, i.e. polynomials, interpolations, rotation transformations e.t.c. for which functors are perfectly suited. Personally, I think the first question one should ask oneself before using a collection of functions, is if there is any way one could use a functor instead.
- there is a package called [`FunctionWrapperWrappers.jl`](https://github.com/SciML/FunctionWrappersWrappers.jl). I have no idea what it is used for, but if you do, perhaps this is also useful to mention?

Anyway it’s awesome that you do this, I have seen questions about vectors of functions appear quite a few times 🙂 and not so many resources about the solutions

[Previous page](https://discourse.julialang.org/t/function-inside-struct-allocates-when-referenced/105785.md?page=1)