# Performance scaling of broadcasting compared to looping

**URL:** <https://discourse.julialang.org/t/performance-scaling-of-broadcasting-compared-to-looping/92000>\
**Category:** Performance\
**Tags:** question, optimization, loops, broadcasting\
**Created:** [December 22, 2022, 12:36pm UTC](https://discourse.julialang.org/t/performance-scaling-of-broadcasting-compared-to-looping/92000 "2022-12-22T12:36:29Z")\
**Posts on this page:** 20\
**Page:** 1

<div class="post-metadata">

**Author:** ![f.ij](https://avatars.discourse-cdn.com/v4/letter/f/8491ac/32.png) [@f.ij](https://discourse.julialang.org/u/f.ij)\
**Post date:** [December 22, 2022, 12:36pm UTC](https://discourse.julialang.org/t/performance-scaling-of-broadcasting-compared-to-looping/92000/1 "2022-12-22T12:36:29Z")

</div>

I’m writing a simulation where speed is very important. The program consists of a main loop where I need to collect some scalar by multiplying some floats based on connections in an adjacency matrix. As a very simplified example, a large part of the main loop of my simulation comes down to this:

```julia
using BenchmarkTools

const state = rand(1000)
const n_connections = 10

# (connections, weights)
const adj = (sort!(rand(1:1000, n_connections)), rand(n_connections))

function main_algo_loop(state, adj)
    e = 0
    for (loop_idx, connection_idx) in enumerate(adj[1])
        e += state[connection_idx]*adj[2][loop_idx]
    end
    return e
end

function main_algo_broadcast(state, adj)
    return sum((@view state[adj[1]]) .* adj[2])
end

```

If `n_connections = 10` I get

```julia
julia> @btime main_algo_loop($state, $adj)
  19.224 ns (0 allocations: 0 bytes)

julia> @btime main_algo_broadcast($state, $adj)
  31.910 ns (1 allocation: 144 bytes)

```

however, for `n_connections = 100`

```julia
@btime main_algo_loop($state, $adj)
  446.758 ns (0 allocations: 0 bytes)

julia> @btime main_algo_broadcast($state, $adj)
  98.558 ns (1 allocation: 896 bytes)

```

So I can understand that broadcasting can be optimised, which is why it is faster, but why is it quite a bit slower for smaller vectors? Right now, usually in most cases the number of connections are quite low, so looping is faster. However, in some cases I would like to do simulations with higher connectivity so broadcasting would be much faster. I could switch the algorithm when the average number of connections gets high, but this would be a bit cumbersome and is not very elegant. Can I write something that is always optimally fast, no matter what the value of `n_connections` is?

---

<div class="post-metadata">

**Author:** ![stevengj](https://sea2.discourse-cdn.com/julialang/user_avatar/discourse.julialang.org/stevengj/32/71_2.png) [@stevengj](https://discourse.julialang.org/u/stevengj)\
**Post date:** [December 22, 2022, 1:21pm UTC](https://discourse.julialang.org/t/performance-scaling-of-broadcasting-compared-to-looping/92000/2 "2022-12-22T13:21:41Z")

</div>

The problem is not broadcasting (which is implemented internally with loops, after all), it’s allocation.

> [@f.ij](#):
>
> `sum((@view state[adj[1]]) .* adj[2])`

This allocates a new array (for the result of the `.*`) and then sums it, which is quite a bit slower for small arrays than looping in-place for the summation.

(Even if you pre-allocated the output array, you would lose in memory bandwidth simply by having another array to read/write from.)

---

<div class="post-metadata">

**Author:** ![Dan](https://sea2.discourse-cdn.com/julialang/user_avatar/discourse.julialang.org/dan/32/42581_2.png) [@Dan](https://discourse.julialang.org/u/Dan)\
**Post date:** [December 22, 2022, 1:46pm UTC](https://discourse.julialang.org/t/performance-scaling-of-broadcasting-compared-to-looping/92000/3 "2022-12-22T13:46:56Z")

</div>

```julia
main_algo_sum(state, adj) = 
  sum(i -> state[adj[1][i]]*adj[2][i], 1:length(adj[1]))

```

is faster and shorter than the for-loop version (at least on my system).  
You are welcome to report from yours.

Added: Add `@inbounds` for extra speed:

```julia
main_algo_sum(state, adj) = 
  sum(i -> @inbounds( state[adj[1][i]]*adj[2][i] ), 1:length(adj[1]))

```

---

<div class="post-metadata">

**Author:** ![photor](https://sea2.discourse-cdn.com/julialang/user_avatar/discourse.julialang.org/photor/32/14343_2.png) [@photor](https://discourse.julialang.org/u/photor)\
**Post date:** [December 22, 2022, 1:56pm UTC](https://discourse.julialang.org/t/performance-scaling-of-broadcasting-compared-to-looping/92000/4 "2022-12-22T13:56:56Z")

</div>

Why not use the built-in dot function?

---

<div class="post-metadata">

**Author:** ![Dan](https://sea2.discourse-cdn.com/julialang/user_avatar/discourse.julialang.org/dan/32/42581_2.png) [@Dan](https://discourse.julialang.org/u/Dan)\
**Post date:** [December 22, 2022, 2:03pm UTC](https://discourse.julialang.org/t/performance-scaling-of-broadcasting-compared-to-looping/92000/5 "2022-12-22T14:03:37Z")

</div>

Also an option:

```julia
using LinearAlgebra
main_algo_dot(state, adj) = dot(@view(state[adj[1]]), adj[2])

```

Clear. Around 2x slower than `sum(i->` version.

---

<div class="post-metadata">

**Author:** ![f.ij](https://avatars.discourse-cdn.com/v4/letter/f/8491ac/32.png) [@f.ij](https://discourse.julialang.org/u/f.ij)\
**Post date:** [December 22, 2022, 2:11pm UTC](https://discourse.julialang.org/t/performance-scaling-of-broadcasting-compared-to-looping/92000/6 "2022-12-22T14:11:48Z")

</div>

Thanks for the answer. I see, it makes sense that the allocation causes overhead, I didn’t think of that. However, if it’s implemented with loops, I don’t understand what makes it faster for longer arrays. Can you elaborate?

---

<div class="post-metadata">

**Author:** ![f.ij](https://avatars.discourse-cdn.com/v4/letter/f/8491ac/32.png) [@f.ij](https://discourse.julialang.org/u/f.ij)\
**Post date:** [December 22, 2022, 2:22pm UTC](https://discourse.julialang.org/t/performance-scaling-of-broadcasting-compared-to-looping/92000/7 "2022-12-22T14:22:10Z")

</div>

> [@Dan](#):
>
> ```julia
> main_algo_sum(state, adj) = 
> sum(i -> state[adj[1][i]]*adj[2][i], 1:length(adj[1]))
> 
> ```

Interesting, for `n_connections = 10`

```julia
julia> @btime main_algo_sum($state, $adj)
  24.724 ns (0 allocations: 0 bytes)

```

`n_connections = 100`

```julia
@btime main_algo_sum($state, $adj)
  45.248 ns (0 allocations: 0 bytes)

```

However, for `n_connections = 4` (which is the most common for my simulation)

```julia
@btime main_algo_loop($state, $adj)
  6.666 ns (0 allocations: 0 bytes)

@btime main_algo_broadcast($state, $adj)
  41.961 ns (1 allocation: 96 bytes)

@btime main_algo_sum($state, $adj)
  22.818 ns (0 allocations: 0 bytes)

```

So for larger arrays this is blazing fast, which is very useful. However, I still can’t use it for smaller arrays since a speed decrease of almost 4x is too much. So first of all I would like to understand the reason this is slower for smaller arrays, since this time it does not allocate and also why it is so much faster for larger arrays.

Furthermore it would be useful to know if it can be optimized for small arrays.

Edit: This is all on an M1 Max chip btw.

Edit 2: I don’t know what happened, but first of all without macro interploation it’s faster, and now testing it again, its faster in the first place:

```julia
@btime main_algo_sum(state, adj)
  6.417 ns (0 allocations: 0 bytes)

```

(with macro interpolation it would be around 6.7 ns, why?)

So, this is great! It’s faster in all cases. I still would like to understand why it’s faster for large arrays, however.

---

<div class="post-metadata">

**Author:** ![Dan](https://sea2.discourse-cdn.com/julialang/user_avatar/discourse.julialang.org/dan/32/42581_2.png) [@Dan](https://discourse.julialang.org/u/Dan)\
**Post date:** [December 22, 2022, 2:41pm UTC](https://discourse.julialang.org/t/performance-scaling-of-broadcasting-compared-to-looping/92000/8 "2022-12-22T14:41:09Z")

</div>

> [@f.ij](#):
>
> ` 6.417 ns (0 allocations: 0 bytes)`

For very samll time-scales ( \<100 cycles ) measurement might get trickier. Perhaps this should be repeated many times.

Also, if `n_connections = 4` mostly, it might be worth it to special case it with StaticArrays.

---

<div class="post-metadata">

**Author:** ![stevengj](https://sea2.discourse-cdn.com/julialang/user_avatar/discourse.julialang.org/stevengj/32/71_2.png) [@stevengj](https://discourse.julialang.org/u/stevengj)\
**Post date:** [December 22, 2022, 2:49pm UTC](https://discourse.julialang.org/t/performance-scaling-of-broadcasting-compared-to-looping/92000/9 "2022-12-22T14:49:48Z")

</div>

> [@f.ij](#):
>
> However, if it’s implemented with loops, I don’t understand what makes it faster for longer arrays. Can you elaborate?

`sum` has some [tricks in its loops](https://github.com/JuliaLang/julia/blob/master/base/reduce.jl#L253-L275) to squeeze out a bit more performance (as well as using [pairwise summation](https://en.wikipedia.org/wiki/Pairwise_summation) for better accuracy).

---

<div class="post-metadata">

**Author:** ![f.ij](https://avatars.discourse-cdn.com/v4/letter/f/8491ac/32.png) [@f.ij](https://discourse.julialang.org/u/f.ij)\
**Post date:** [December 22, 2022, 2:51pm UTC](https://discourse.julialang.org/t/performance-scaling-of-broadcasting-compared-to-looping/92000/10 "2022-12-22T14:51:29Z")

</div>

That’s good to know. One weird thing I’m having though is that sometimes the `main_algo_sum` will still report 20ns, and after some restarts of the REPL, sometimes will do 6ns, whereas the one with the loop always reports 6ns… Why is this?

---

<div class="post-metadata">

**Author:** ![f.ij](https://avatars.discourse-cdn.com/v4/letter/f/8491ac/32.png) [@f.ij](https://discourse.julialang.org/u/f.ij)\
**Post date:** [December 22, 2022, 3:01pm UTC](https://discourse.julialang.org/t/performance-scaling-of-broadcasting-compared-to-looping/92000/11 "2022-12-22T15:01:56Z")

</div>

I guess I celebrated too soon. For `n_connections = 4`

and

```julia
function loopalgo_sum(state, adj)
    for _ in 1:100
        main_algo_sum(state,adj)
    end
end

function testalgo_loop(state, adj)
    for _ in 1:100
        main_algo_loop(state,adj)
    end
end

```

I get

```julia
julia> @btime loopalgo_sum(state, adj)
  471.939 ns (0 allocations: 0 bytes)

julia> @btime testalgo_loop(state, adj)
  210.510 ns (0 allocations: 0 bytes)

```

So it does seem quite a bit slower still for small arrays, why?

---

<div class="post-metadata">

**Author:** ![Elrod](https://sea2.discourse-cdn.com/julialang/user_avatar/discourse.julialang.org/elrod/32/22461_2.png) [@Elrod](https://discourse.julialang.org/u/Elrod)\
**Post date:** [December 22, 2022, 3:10pm UTC](https://discourse.julialang.org/t/performance-scaling-of-broadcasting-compared-to-looping/92000/12 "2022-12-22T15:10:46Z")

</div>

Without `@inbounds`, the loop won’t SIMD. Short arrays won’t SIMD either.  
It’s faster not to have code paths that aren’t taken.  
Meaning it’s faster not to have `@inbounds`, because the SIMD code that allows the compiler to create isn’t being executed and just gets in the way.

For big arrays, that code does get executed and is faster.

---

<div class="post-metadata">

**Author:** ![f.ij](https://avatars.discourse-cdn.com/v4/letter/f/8491ac/32.png) [@f.ij](https://discourse.julialang.org/u/f.ij)\
**Post date:** [December 22, 2022, 3:40pm UTC](https://discourse.julialang.org/t/performance-scaling-of-broadcasting-compared-to-looping/92000/13 "2022-12-22T15:40:29Z")

</div>

I don’t understand, the code seems slower for any size without @inbounds (from testing). Also, this doesn’t tell me why it’s still slower for small arrays than looping.

So again, is there anyway to get the optimal speed for any size? Or is the only way to switch algorithms for the simulation if the connectivity get higher?

---

<div class="post-metadata">

**Author:** ![Dan](https://sea2.discourse-cdn.com/julialang/user_avatar/discourse.julialang.org/dan/32/42581_2.png) [@Dan](https://discourse.julialang.org/u/Dan)\
**Post date:** [December 22, 2022, 3:57pm UTC](https://discourse.julialang.org/t/performance-scaling-of-broadcasting-compared-to-looping/92000/14 "2022-12-22T15:57:34Z")

</div>

There is nothing wrong with the loop implementation (if it achieves good performance) and there is nothing wrong with switching algos according to parameters (most algos do this internally).

The best way to get good answers is to post another version of the code, with the test, and with parameters which are representative of actual use case. Such running code will get the best ‘treatment’ by the community (much better than asking for optimal speed for any size).

---

<div class="post-metadata">

**Author:** ![Elrod](https://sea2.discourse-cdn.com/julialang/user_avatar/discourse.julialang.org/elrod/32/22461_2.png) [@Elrod](https://discourse.julialang.org/u/Elrod)\
**Post date:** [December 22, 2022, 4:11pm UTC](https://discourse.julialang.org/t/performance-scaling-of-broadcasting-compared-to-looping/92000/15 "2022-12-22T16:11:19Z")

</div>

```julia
julia> @btime main_algo_inbounds_simd($state, $adj10)
  4.916 ns (0 allocations: 0 bytes)
3.611952005832202

julia> @btime main_algo_inbounds($state, $adj10)
  5.541 ns (0 allocations: 0 bytes)
3.611952005832202

julia> @btime main_algo_loop($state, $adj10)
  7.416 ns (0 allocations: 0 bytes)
3.611952005832202

julia> @btime main_algo_turbo($state, $adj10)
  6.166 ns (0 allocations: 0 bytes)
3.611952005832202

julia> @btime main_algo_inbounds_simd($state, $adj100)
  40.573 ns (0 allocations: 0 bytes)
26.671416641549378

julia> @btime main_algo_inbounds($state, $adj100)
  57.774 ns (0 allocations: 0 bytes)
26.67141664154938

julia> @btime main_algo_loop($state, $adj100)
  68.818 ns (0 allocations: 0 bytes)
26.67141664154938

julia> @btime main_algo_turbo($state, $adj100)
  29.146 ns (0 allocations: 0 bytes)
26.671416641549374

```

These are all the original loop, but with different macros. For example:

```julia
julia> function main_algo_inbounds_simd(state, adj)
           e = zero(eltype(state))
           @inbounds @simd for loop_idx in eachindex(adj[1])
               connection_idx = adj[1][loop_idx]
               e += state[connection_idx]*adj[2][loop_idx]
           end
           return e
       end
main_algo_inbounds_simd (generic function with 1 method)

```

There were examples shared before where `@inbounds` made very short loops slower, but that wasn’t the case here.

---

<div class="post-metadata">

**Author:** ![Dan](https://sea2.discourse-cdn.com/julialang/user_avatar/discourse.julialang.org/dan/32/42581_2.png) [@Dan](https://discourse.julialang.org/u/Dan)\
**Post date:** [December 22, 2022, 4:23pm UTC](https://discourse.julialang.org/t/performance-scaling-of-broadcasting-compared-to-looping/92000/16 "2022-12-22T16:23:55Z")

</div>

Oops… sorry @Elrod, I thought this was a post from question writer 🤭.

---

<div class="post-metadata">

**Author:** ![Elrod](https://sea2.discourse-cdn.com/julialang/user_avatar/discourse.julialang.org/elrod/32/22461_2.png) [@Elrod](https://discourse.julialang.org/u/Elrod)\
**Post date:** [December 22, 2022, 4:31pm UTC](https://discourse.julialang.org/t/performance-scaling-of-broadcasting-compared-to-looping/92000/17 "2022-12-22T16:31:34Z")

</div>

The `main_alog_inbounds_simd` is probably a good choice, and is faster than all the non-`@turbo` versions for large sizes.  
Whether `@turbo`’s advantage at large sizes is enough to offset its disadvantage at small sizes plus its extra compile time latency will require knowing more about the distribution.

If we have 80% 10, 20% 100

```julia
julia> adj4 = (sort!(rand(1:1000, 4)), rand(4));

julia> @btime main_algo_inbounds_simd($state, $adj4)
  3.375 ns (0 allocations: 0 bytes)
0.8052880397380788

julia> @btime main_algo_inbounds($state, $adj4)
  3.666 ns (0 allocations: 0 bytes)
0.8052880397380788

julia> @btime main_algo_loop($state, $adj4)
  4.291 ns (0 allocations: 0 bytes)
0.8052880397380788

julia> @btime main_algo_turbo($state, $adj4)
  4.625 ns (0 allocations: 0 bytes)
0.8052880397380788

```

then we have average runtimes in `ns` of

```julia
julia> 0.8 * 3.375 + 0.2 * 40.573 # @inbounds @simd
10.814600000000002

julia> 0.8 * 4.625 + 0.2 * 29.146 # @turbo
9.5292

```

and `@turbo` wins ignoring compile times, thanks to its advantage for larger inputs.

The above was on an M1.

> **On a 9940X, I get**
>
> ```julia
> julia> @btime main_algo_loop($state, $adj4)
> 5.044 ns (0 allocations: 0 bytes)
> 0.8847923117356615
> 
> julia> @btime main_algo_inbounds($state, $adj4)
> 4.089 ns (0 allocations: 0 bytes)
> 0.8847923117356615
> 
> julia> @btime main_algo_inbounds_simd($state, $adj4)
> 4.078 ns (0 allocations: 0 bytes)
> 0.8847923117356615
> 
> julia> @btime main_algo_turbo($state, $adj4)
> 7.801 ns (0 allocations: 0 bytes)
> 0.8847923117356615
> 
> julia> @btime main_algo_loop($state, $adj100)
> 98.579 ns (0 allocations: 0 bytes)
> 24.71532662119185
> 
> julia> @btime main_algo_inbounds($state, $adj100)
> 89.646 ns (0 allocations: 0 bytes)
> 24.71532662119185
> 
> julia> @btime main_algo_inbounds_simd($state, $adj100)
> 32.077 ns (0 allocations: 0 bytes)
> 24.715326621191846
> 
> julia> @btime main_algo_turbo($state, $adj100)
> 30.409 ns (0 allocations: 0 bytes)
> 24.71532662119185
> 
> ```

On this CPU `@inbounds @simd` and `@turbo` are around 3x or more faster than the alternatives for `adj100` and (now shown) 4x or more faster for length 1000.

---

<div class="post-metadata">

**Author:** ![f.ij](https://avatars.discourse-cdn.com/v4/letter/f/8491ac/32.png) [@f.ij](https://discourse.julialang.org/u/f.ij)\
**Post date:** [March 7, 2023, 3:45pm UTC](https://discourse.julialang.org/t/performance-scaling-of-broadcasting-compared-to-looping/92000/18 "2023-03-07T15:45:53Z")

</div>

After a bit of a bit of a hiatus I’m back on this project. I hope people are still interested because I’m a bit stumped.

To give a bit of a better idea of how my program is set up I will sketch an outline:

```julia
struct g
  state::Vector{Int8}
  adj::Vector{Vector{Tuple{Float32,Int32}}}
end

function mainLoop(state, adj, someBoolRef, loopCounterRef, sumfunc)
  while someBoolRef[]
    metropolisalgo(g, adj, sumfunc) 
    loopCounterRef[] += 1
  end
end

function metropolisalgo(state,adj, sumfunc)
  # Do some stuff
  idx = rand(1:length(state))
  
  energy = - state[idx]*sumfunc(state, adj, idx)

  # do more stuff
end

function sumfunc(state, adj, idx)
  # either include @simd or not
  @inbounds for adj_idx in eachindex(adj[idx])
    e += state[adj[idx][adj_idx][1]] * adj[idx][adj_idx][2]
  end
  return e
end

```

I made the energy function an argument to be able to restart the simulation with a different one easily, but before I tried the same by modifying the code by hand. The weird part is the following, if I run the `sumfunc` from the repl, it’s noticeably faster if I include @simd. I’m testing now for a scenario where ever `adj[idx]` has 224 entries. With `@simd` it will take about 120ns, whereas without is will take 180ns to complete. If I actually try to use it in my simulation, I can see absolutely no difference at all in performance. I’m tracking the performance through the loopCounterRef (actually it’s a field to some other struct in my real program, but it shouldn’t matter), and also just by eye. This makes me think the @simd macro is not being used somehow. Anyone any idea why this would be?

---

<div class="post-metadata">

**Author:** ![lrnv](https://sea2.discourse-cdn.com/julialang/user_avatar/discourse.julialang.org/lrnv/32/19373_2.png) [@lrnv](https://discourse.julialang.org/u/lrnv)\
**Post date:** [March 21, 2023, 11:22am UTC](https://discourse.julialang.org/t/performance-scaling-of-broadcasting-compared-to-looping/92000/19 "2023-03-21T11:22:10Z")

</div>

> [@f.ij](#):
>
> ```julia
> using BenchmarkTools
> 
> const state = rand(1000)
> const n_connections = 10
> 
> # (connections, weights)
> const adj = (sort!(rand(1:1000, n_connections)), rand(n_connections))
> 
> function main_algo_loop(state, adj)
> e = 0
> for (loop_idx, connection_idx) in enumerate(adj[1])
> e += state[connection_idx]*adj[2][loop_idx]
> end
> return e
> end
> 
> function main_algo_broadcast(state, adj)
> return sum((@view state[adj[1]]) .* adj[2])
> end
> 
> ```

I am not sure how much this apply to your actual code, but here `e = 0` builds an int and then you add floats since `state = rand(1000)` makes floats. This is type unstable. Try with `e = zero(eltype(state))` instead, you might win big.

---

<div class="post-metadata">

**Author:** ![f.ij](https://avatars.discourse-cdn.com/v4/letter/f/8491ac/32.png) [@f.ij](https://discourse.julialang.org/u/f.ij)\
**Post date:** [March 21, 2023, 11:24am UTC](https://discourse.julialang.org/t/performance-scaling-of-broadcasting-compared-to-looping/92000/21 "2023-03-21T11:24:56Z")

</div>

Yep, I noticed that before and changed it already. Thanks for the help though!