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:
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
struct Agent{T}
behaviors::T
end
and we have multiple behaviors like:
function behavior1(x)
x
end
function behavior2(x)
x
end
function behavior3(x)
x
end
Note each behavior function is its own type:
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:
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 behaviors in a vector and stick it in the Agent
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, 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> typeof(Agent([behavior2, behavior3])) == typeof(Agent([behavior1, behavior2]))
true
Variant 2: use Tuple instead of Vector
This puts the information which behaviors an Agent has into the type-domain, so Julia knows which functions to call at compile time:
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 Agents with different behaviors have different types:
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 Agents 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> 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> @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 Agents and perform a lookup in some external structure, f.e.
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, 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.
So we can now do (need to slightly restructure the type):
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.
