# Speed of dispatch with heterogeneous functions and types

**URL:** <https://discourse.julialang.org/t/speed-of-dispatch-with-heterogeneous-functions-and-types/26282>\
**Category:** Performance\
**Created:** [July 12, 2019, 10:30am UTC](https://discourse.julialang.org/t/speed-of-dispatch-with-heterogeneous-functions-and-types/26282 "2019-07-12T10:30:16Z")\
**Posts on this page:** 11\
**Page:** 1

<div class="post-metadata">

**Author:** ![mhinsch](https://sea2.discourse-cdn.com/julialang/user_avatar/discourse.julialang.org/mhinsch/32/26676_2.png) [@mhinsch](https://discourse.julialang.org/u/mhinsch)\
**Post date:** [July 12, 2019, 10:30am UTC](https://discourse.julialang.org/t/speed-of-dispatch-with-heterogeneous-functions-and-types/26282/1 "2019-07-12T10:30:16Z")

</div>

I am planning to implement a continuous-time version of a discrete-time agent-based simulation (see [https://github.com/mhinsch/RRGraphs](https://github.com/mhinsch/RRGraphs)). That means there will be some sort of central scheduler that handles dispatch of actions with, both, the type of the objects and the functions to be dispatched varying dynamically. In the light of [this](https://discourse.julialang.org/t/update-on-single-dispatch-benchmark-comparison-to-c/7283), I thought it would make sense to invest some time to find the fastest method.

Here is some test code I wrote: [https://gist.github.com/mhinsch/773b4d34012090c6c551e32ff3f2f576](https://gist.github.com/mhinsch/773b4d34012090c6c551e32ff3f2f576). Basically there are two types of agents and two types of actions where the combination of the two is determined at run-time. I expect actions to be not entirely trivial, therefore the random numbers in `step*`. Part of the consideration also has to be the time it takes to line up agents and actions to be consumed by the scheduler which is why I am benchmarking the entire process not just the scheduling itself.

The results (Julia 1.1) are interesting, I think, and somewhat unexpected (for me):

```julia
static dispatch:
  4.800 ms (49 allocations: 4.00 MiB)
generic function, command array:
  6.521 ms (34 allocations: 4.00 MiB)
generic function:
  8.255 ms (89454 allocations: 5.37 MiB)
plain closures:
  19.733 ms (189371 allocations: 4.89 MiB)
typed closures:
  7.245 ms (189291 allocations: 4.89 MiB)
manual type check:
  6.290 ms (34 allocations: 4.00 MiB)
array of functors:
  8.842 ms (189463 allocations: 4.89 MiB)
FunctionWrapper with functor:
  11.308 ms (300017 allocations: 9.63 MiB)
FunctionWrapper with closure:
  6.596 ms (300017 allocations: 9.63 MiB)

```

To sum it up, from what I have read (and tested) before I would have expected for generic function calls to perform a lot worse and FunctionWrappers with functors a lot better.

In any case, any suggestions on how to improve the code or even entirely different solutions for the problem will be gratefully received 🙂

---

<div class="post-metadata">

**Author:** ![Raf](https://sea2.discourse-cdn.com/julialang/user_avatar/discourse.julialang.org/raf/32/3383_2.png) [@Raf](https://discourse.julialang.org/u/Raf)\
**Post date:** [July 12, 2019, 11:40am UTC](https://discourse.julialang.org/t/speed-of-dispatch-with-heterogeneous-functions-and-types/26282/2 "2019-07-12T11:40:04Z")

</div>

An MWE would help. Its an interesting question but that’s too much code.

---

<div class="post-metadata">

**Author:** ![pixel27](https://sea2.discourse-cdn.com/julialang/user_avatar/discourse.julialang.org/pixel27/32/8902_2.png) [@pixel27](https://discourse.julialang.org/u/pixel27)\
**Post date:** [July 12, 2019, 11:44am UTC](https://discourse.julialang.org/t/speed-of-dispatch-with-heterogeneous-functions-and-types/26282/3 "2019-07-12T11:44:28Z")

</div>

My first worry is the code that is populating the agents/action structures. Is that **part** of scheduling or not…If it’s not I’m worried that your “dispatch” numbers are being overshadowed by the initialization. So breaking the population of the arrays into a different function would probably give you better results.

If it _is_ part you can change `sched_gen`’s first two lines to:

```julia
    agents = Array{Agent}(undef, n)
    action = Array{Int}(undef, n)

```

You will probably get better results just because multiple allocations to populate the arrays turn into exactly 2 allocations. It appears all the tests except `sched_static` can benefit from this type of change, only in `sched_static` you can’t predict how large the arrays need to be.

---

<div class="post-metadata">

**Author:** ![mhinsch](https://sea2.discourse-cdn.com/julialang/user_avatar/discourse.julialang.org/mhinsch/32/26676_2.png) [@mhinsch](https://discourse.julialang.org/u/mhinsch)\
**Post date:** [July 12, 2019, 11:44am UTC](https://discourse.julialang.org/t/speed-of-dispatch-with-heterogeneous-functions-and-types/26282/4 "2019-07-12T11:44:51Z")

</div>

> [@Raf](#):
>
> An MWE would help. Its an interesting question but that’s too much code.

Well, the point of the exercise is to test various methods against each other. I can’t make each of them more minimal than they already are.

---

<div class="post-metadata">

**Author:** ![mhinsch](https://sea2.discourse-cdn.com/julialang/user_avatar/discourse.julialang.org/mhinsch/32/26676_2.png) [@mhinsch](https://discourse.julialang.org/u/mhinsch)\
**Post date:** [July 12, 2019, 11:48am UTC](https://discourse.julialang.org/t/speed-of-dispatch-with-heterogeneous-functions-and-types/26282/5 "2019-07-12T11:48:00Z")

</div>

> [@pixel27](#):
>
> My first worry is the code that is populating the agents/action structures. Is that **part** of scheduling or not…If it’s not I’m worried that your “dispatch” numbers are being overshadowed by the initialization. So breaking the population of the arrays into a different function would probably give you better results.
> 
> If it _is_ part you can change `sched_gen`’s first two lines to:
> 
> ```julia
> agents = Array{Agent}(undef, n)
> action = Array{Int}(undef, n)
> 
> ```
> 
> You will probably get better results just because multiple allocations to populate the arrays turn into exactly 2 allocations. It appears all the tests except `sched_static` can benefit from this type of change, only `sched_static` you can’t predict how large the arrays need to be.

That’s a good point, but in practice the array of actions/agents will grow and shrink dynamically as a result of what’s going on in the simulation (which therefore has to be part of the benchmark), so filling them like I did seems like a reasonable approximation to what’s going to happen in real life.

Edit: More specifically, the amount of allocation needed to hold the necessary structures (i.e. actions + objects) is part of the problem.

---

<div class="post-metadata">

**Author:** ![pixel27](https://sea2.discourse-cdn.com/julialang/user_avatar/discourse.julialang.org/pixel27/32/8902_2.png) [@pixel27](https://discourse.julialang.org/u/pixel27)\
**Post date:** [July 12, 2019, 12:05pm UTC](https://discourse.julialang.org/t/speed-of-dispatch-with-heterogeneous-functions-and-types/26282/6 "2019-07-12T12:05:12Z")

</div>

Far enough.

Looking at the numbers for this:

```julia
function pop_static(a1, a2, n)
	agents1 = Agent1[]
	agents2 = Agent2[]
	action = Int[]

	for i in 1:n
		if rand(1:2) == 1
			push!(agents1, rand(a1))
			push!(action, rand(1:2))
		else
			push!(agents2, rand(a2))
			push!(action, rand(1:2))
		end
	end

	(agents1, agents2, action)
end

function sched_static(agents1, agents2, action)
	i = 1
	for a in agents1
		action[i] == 1 ? step1(a) : step2(a)
		i += 1
	end
	for a in agents2
		action[i] == 1 ? step1(a) : step2(a)
		i += 1
	end
end

const ns = 100_000

agents1, agents2, action = pop_static(arr1, arr2, 1)
sched_static(agents1, agents2, action)

reset()

println("Initialize:")
agents1, agents2, action = @btime pop_static(arr1, arr2, ns)
println("Dispatch:")
@btime sched_static(agents1, agents2, action)

```

I get:

```julia
Initialize:
  4.367 ms (50 allocations: 4.00 MiB)
Dispatch:
  1.211 ms (0 allocations: 0 bytes)

```

So from an optimization standpoint there is more room to optimize populating the data structures than dispatching the calls…So that is what I would focus on first…

---

<div class="post-metadata">

**Author:** ![mhinsch](https://sea2.discourse-cdn.com/julialang/user_avatar/discourse.julialang.org/mhinsch/32/26676_2.png) [@mhinsch](https://discourse.julialang.org/u/mhinsch)\
**Post date:** [July 12, 2019, 12:11pm UTC](https://discourse.julialang.org/t/speed-of-dispatch-with-heterogeneous-functions-and-types/26282/7 "2019-07-12T12:11:22Z")

</div>

> [@pixel27](#):
>
> I get:
> 
> ```julia
> Initialize:
> 4.367 ms (50 allocations: 4.00 MiB)
> Dispatch:
> 1.211 ms (0 allocations: 0 bytes)
> 
> ```
> 
> So from an optimization standpoint there is more room to optimize populating the data structures than dispatching the calls…So that is what I would focus on first…

Hmm, you have a point there. I’ll have to think about what that implies for the project…

---

<div class="post-metadata">

**Author:** ![pixel27](https://sea2.discourse-cdn.com/julialang/user_avatar/discourse.julialang.org/pixel27/32/8902_2.png) [@pixel27](https://discourse.julialang.org/u/pixel27)\
**Post date:** [July 12, 2019, 12:16pm UTC](https://discourse.julialang.org/t/speed-of-dispatch-with-heterogeneous-functions-and-types/26282/8 "2019-07-12T12:16:03Z")

</div>

Just an FYI, I was curious how much “overhead” the rand method was adding to the dispatch process so changing:

```julia
@noinline step1(a :: Agent1) = a.x += 1

@noinline step1(a :: Agent2) = a.y -= 2

@noinline step2(a :: Agent1) = a.x += 3

@noinline step2(a :: Agent2) = a.y -= 4

```

The dispatching time dropped by about 700ms which is also a sizeable chunk of the dispatch time…

Well about by 700ms when I did the “sched\_gen” flow as two pieces…when I did that to the sched\_static flow the dispatch time hit 615us…

---

<div class="post-metadata">

**Author:** ![mhinsch](https://sea2.discourse-cdn.com/julialang/user_avatar/discourse.julialang.org/mhinsch/32/26676_2.png) [@mhinsch](https://discourse.julialang.org/u/mhinsch)\
**Post date:** [July 12, 2019, 12:23pm UTC](https://discourse.julialang.org/t/speed-of-dispatch-with-heterogeneous-functions-and-types/26282/9 "2019-07-12T12:23:41Z")

</div>

> [@pixel27](#):
>
> Just an FYI, I was curious how much “overhead” the rand method was adding to the dispatch process so changing:
> 
> ```julia
> @noinline step1(a :: Agent1) = a.x += 1
> 
> @noinline step1(a :: Agent2) = a.y -= 2
> 
> @noinline step2(a :: Agent1) = a.x += 3
> 
> @noinline step2(a :: Agent2) = a.y -= 4
> 
> ```
> 
> The dispatching time dropped by about 700ms which is also a sizeable chunk of the dispatch time…

Yes, that’s expected. My idea was to add a bit of minimal “load” to the step functions so that speed differences can be judged in a somewhat realistic scenario. E.g. a difference of 700ms doesn’t matter if the whole process (allocation + dispatch + simulation) takes 10s anyway. The comparison of my results to those of cdsousa’s tests (linked in my OP) shows that this makes a certain amount of sense. That said, I think you are right in that a more microscopic approach, identifying the exact costs of all parts of the algorithm, might be more helpful. That requires, though, that I think a bit more about what actually is going to be needed…

---

<div class="post-metadata">

**Author:** ![Raf](https://sea2.discourse-cdn.com/julialang/user_avatar/discourse.julialang.org/raf/32/3383_2.png) [@Raf](https://discourse.julialang.org/u/Raf)\
**Post date:** [July 13, 2019, 5:53am UTC](https://discourse.julialang.org/t/speed-of-dispatch-with-heterogeneous-functions-and-types/26282/10 "2019-07-13T05:53:30Z")

</div>

This is kind of what I was getting at. Your examples have a lot of code difference so its hard to say where slowdowns come from, or really comment on the relative merits of the strategies without getting out a profiler and comparing line by line.

---

<div class="post-metadata">

**Author:** ![smldis](https://sea2.discourse-cdn.com/julialang/user_avatar/discourse.julialang.org/smldis/32/1735_2.png) [@smldis](https://discourse.julialang.org/u/smldis)\
**Post date:** [July 16, 2019, 10:57am UTC](https://discourse.julialang.org/t/speed-of-dispatch-with-heterogeneous-functions-and-types/26282/11 "2019-07-16T10:57:51Z")

</div>

> [@mhinsch](#):
>
> That’s a good point, but in practice the array of actions/agents will grow and shrink dynamically as a result of what’s going on in the simulation (which therefore has to be part of the benchmark), so filling them like I did seems like a reasonable approximation to what’s going to happen in real life.

It would be better to benchmark separately the initialization and the actions. Paricularly, with respect dynamic dispatch, there are caches that help to speed it up. Therefore, you should also try to benchmark what happens when methods are not in cache (by having much more agents and actions)