# Non-allocating loop over a set of structs

**URL:** <https://discourse.julialang.org/t/non-allocating-loop-over-a-set-of-structs/25643>\
**Category:** Performance\
**Created:** [June 25, 2019, 10:17am UTC](https://discourse.julialang.org/t/non-allocating-loop-over-a-set-of-structs/25643 "2019-06-25T10:17:56Z")\
**Posts on this page:** 14\
**Page:** 1

<div class="post-metadata">

**Author:** ![fedoroff](https://sea2.discourse-cdn.com/julialang/user_avatar/discourse.julialang.org/fedoroff/32/53209_2.png) [@fedoroff](https://discourse.julialang.org/u/fedoroff)\
**Post date:** [June 25, 2019, 10:17am UTC](https://discourse.julialang.org/t/non-allocating-loop-over-a-set-of-structs/25643/1 "2019-06-25T10:17:56Z")

</div>

I have a set of structs and I want to loop over them. The following code shows two possible loops together with a sequential one by one access to structs:

```julia
using BenchmarkTools

struct Sample{T<:AbstractFloat, F<:Function}
    a :: T
    foo :: F
end

function main()
    foo1(x) = x^1
    foo2(x) = x^2
    foo3(x) = x^3
    s1 = Sample(1., foo1)
    s2 = Sample(2., foo2)
    s3 = Sample(3., foo3)

    samples = (s1, s2, s3)

    @btime begin
        b = 0.
        for i=1:length($samples)
            b = b + $samples[i].a * $samples[i].foo(2.)
        end
    end

    @btime begin
        b = 0.
        for s in $samples
            b = b + s.a * s.foo(2.)
        end
    end

    @btime begin
        b = 0.
        b = b + $samples[1].a * $samples[1].foo(2.)
        b = b + $samples[2].a * $samples[2].foo(2.)
        b = b + $samples[3].a * $samples[3].foo(2.)
    end
end

main()

```

The result is

```julia
  310.543 ns (24 allocations: 480 bytes)
  258.344 ns (17 allocations: 304 bytes)
  0.017 ns (0 allocations: 0 bytes)

```

As you can see both loops result in memory allocations (though I surprised why the number of allocations is different). In turn, the sequential calls to structs give no allocations. Can you, please, tell me how to avoid the allocations in the these kind of loops. Thank you.

---

<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:** [June 25, 2019, 11:48am UTC](https://discourse.julialang.org/t/non-allocating-loop-over-a-set-of-structs/25643/2 "2019-06-25T11:48:00Z")

</div>

Something to note is that if you change the structure to:

```julia
struct Sample
    a :: Float64
    foo :: Function
end

```

The memory allocations change to (using version 1.1.1 and @time instead of @btime.):

```julia
  0.000001 seconds (12 allocations: 192 bytes)
  0.000001 seconds (12 allocations: 192 bytes)
  0.000000 seconds

```

And if I use:

```julia
struct Sample{F<:Function}
    a :: Float64
    foo :: F
end

```

The timings become:

```julia
  0.000002 seconds (24 allocations: 480 bytes)
  0.000002 seconds (16 allocations: 288 bytes)
  0.000000 seconds

```

So there appears to be some magic around the Parametric Function type…

---

<div class="post-metadata">

**Author:** ![carstenbauer](https://sea2.discourse-cdn.com/julialang/user_avatar/discourse.julialang.org/carstenbauer/32/4981_2.png) [@carstenbauer](https://discourse.julialang.org/u/carstenbauer)\
**Post date:** [June 25, 2019, 12:03pm UTC](https://discourse.julialang.org/t/non-allocating-loop-over-a-set-of-structs/25643/3 "2019-06-25T12:03:19Z")

</div>

I don’t know what’s going on here, but timings like `0.017 ns (0 allocations: 0 bytes)`, i.e. fractions of a nano second, typically indicate that something’s wrong with the benchmark.

---

<div class="post-metadata">

**Author:** ![foobar\_lv2](https://avatars.discourse-cdn.com/v4/letter/f/ee59a6/32.png) [@foobar\_lv2](https://discourse.julialang.org/u/foobar_lv2)\
**Post date:** [June 25, 2019, 12:14pm UTC](https://discourse.julialang.org/t/non-allocating-loop-over-a-set-of-structs/25643/4 "2019-06-25T12:14:39Z")

</div>

The way you wrote `Sample`, `s1`, `s2` and `s3` will all have different types.

It is not possible to sensibly store more than a handful of these in a collection and retain detailed type information (that is needed for performant code). Hence, you cannot quickly loop over type-heterogeneous collections of samples. This is a fundamental property of julia (but depending on your application, “slow” loops may be fast enough).

However, if you deal with known length tuples you can unroll the loop, i.e.:

```julia
b = b + s1.a + s1.foo(2.0)
b = b + s2.a + s2.foo(2.0)
b = b + s3.a + s3.foo(2.0)

```

Julia is sometimes able to optimize code like the one you wrote into the above, but I recommend against relying on it.

---

<div class="post-metadata">

**Author:** ![fedoroff](https://sea2.discourse-cdn.com/julialang/user_avatar/discourse.julialang.org/fedoroff/32/53209_2.png) [@fedoroff](https://discourse.julialang.org/u/fedoroff)\
**Post date:** [June 25, 2019, 12:29pm UTC](https://discourse.julialang.org/t/non-allocating-loop-over-a-set-of-structs/25643/5 "2019-06-25T12:29:32Z")

</div>

> The way you wrote `Sample` , `s1` , `s2` and `s3` will all have different types.

Does this happens because of the Function field? Can I do something with it, like specify the type of the function’s output?

> However, if you deal with known length tuples you can unroll the loop

The number of elements changes from run to run. Can I do the loop unrolling using some kind of metaprogramming magic?

I still do not understand why the result of the loop is so different from the result of unrolling. I thought that under the hood Julia does exactly the same.

---

<div class="post-metadata">

**Author:** ![kristoffer.carlsson](https://sea2.discourse-cdn.com/julialang/user_avatar/discourse.julialang.org/kristoffer.carlsson/32/22_2.png) [@kristoffer.carlsson](https://discourse.julialang.org/u/kristoffer.carlsson)\
**Post date:** [June 25, 2019, 12:44pm UTC](https://discourse.julialang.org/t/non-allocating-loop-over-a-set-of-structs/25643/6 "2019-06-25T12:44:22Z")

</div>

> [@fedoroff](#):
>
> I still do not understand why the result of the loop is so different from the result of unrolling. I thought that under the hood Julia does exactly the same.

Why did you think a loop and unrolled code would be exactly the same? Unrolling something like `for i in 1:1000000` is clearly not a good idea. A loop, by its definition, is executing the same code multiple times. Since `samples` contains heterogeneous type, “the same code” needs to be something generic that can handle things with different types.

Of course, a loop _can_ be unrolled but it is not obvious for code like this when doing so is beneficial.

---

<div class="post-metadata">

**Author:** ![fedoroff](https://sea2.discourse-cdn.com/julialang/user_avatar/discourse.julialang.org/fedoroff/32/53209_2.png) [@fedoroff](https://discourse.julialang.org/u/fedoroff)\
**Post date:** [June 25, 2019, 12:55pm UTC](https://discourse.julialang.org/t/non-allocating-loop-over-a-set-of-structs/25643/7 "2019-06-25T12:55:17Z")

</div>

Well, makes sense. However, in my case the number of loop cycles will be small (less than ten). Can I manually push the compiler to force it unrolling the loop?

---

<div class="post-metadata">

**Author:** ![kristoffer.carlsson](https://sea2.discourse-cdn.com/julialang/user_avatar/discourse.julialang.org/kristoffer.carlsson/32/22_2.png) [@kristoffer.carlsson](https://discourse.julialang.org/u/kristoffer.carlsson)\
**Post date:** [June 25, 2019, 1:00pm UTC](https://discourse.julialang.org/t/non-allocating-loop-over-a-set-of-structs/25643/8 "2019-06-25T13:00:50Z")

</div>

Yes, you can look at [https://github.com/cstjean/Unrolled.jl](https://github.com/cstjean/Unrolled.jl).

---

<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:** [June 25, 2019, 1:01pm UTC](https://discourse.julialang.org/t/non-allocating-loop-over-a-set-of-structs/25643/9 "2019-06-25T13:01:18Z")

</div>

This sounds premature to me. Looping 10 times I’m not sure the allocations are going to break the bank. I feel it would be better to write the code then determine where the most time is being spent…

---

<div class="post-metadata">

**Author:** ![fedoroff](https://sea2.discourse-cdn.com/julialang/user_avatar/discourse.julialang.org/fedoroff/32/53209_2.png) [@fedoroff](https://discourse.julialang.org/u/fedoroff)\
**Post date:** [June 25, 2019, 1:06pm UTC](https://discourse.julialang.org/t/non-allocating-loop-over-a-set-of-structs/25643/10 "2019-06-25T13:06:15Z")

</div>

This is the bottleneck so far. These small loops appear inside an external loop and are executed many times. Moreover, the whole code is launched on GPU.

---

<div class="post-metadata">

**Author:** ![Per](https://sea2.discourse-cdn.com/julialang/user_avatar/discourse.julialang.org/per/32/10387_2.png) [@Per](https://discourse.julialang.org/u/Per)\
**Post date:** [June 25, 2019, 1:16pm UTC](https://discourse.julialang.org/t/non-allocating-loop-over-a-set-of-structs/25643/11 "2019-06-25T13:16:01Z")

</div>

Recursion can often be used as a way of “unrolling” loops over small `Tuple`s.

```julia
f() = 0
f(s, ss...) = s.a * s.foo(2.) + f(ss...)
@btime f(samples...) # 1 ns, 0 allocations

```

---

<div class="post-metadata">

**Author:** ![fedoroff](https://sea2.discourse-cdn.com/julialang/user_avatar/discourse.julialang.org/fedoroff/32/53209_2.png) [@fedoroff](https://discourse.julialang.org/u/fedoroff)\
**Post date:** [June 25, 2019, 1:30pm UTC](https://discourse.julialang.org/t/non-allocating-loop-over-a-set-of-structs/25643/12 "2019-06-25T13:30:20Z")

</div>

Thank you @kristoffer.carlsson and @Per for your solutions:

```julia
using BenchmarkTools
using Unrolled

struct Sample{T<:AbstractFloat, F<:Function}
    a :: T
    foo :: F
end

@unroll function do_sum(samples)
    b = 0.
    @unroll for s in samples
        b = b + s.a * s.foo(2.)
    end
    return b
end

frec() = 0.
frec(s, ss...) = s.a * s.foo(2.) + frec(ss...)

function main()
    foo1(x) = x^1
    foo2(x) = x^2
    foo3(x) = x^3
    s1 = Sample(1., foo1)
    s2 = Sample(2., foo2)
    s3 = Sample(3., foo3)

    samples = (s1, s2, s3)

    @btime begin
        b = 0.
        for s in $samples
            b = b + s.a * s.foo(2.)
        end
    end

    @btime $do_sum($samples)

    @btime $frec($samples...)
end

main()

```

```julia
  259.890 ns (17 allocations: 304 bytes)
  0.016 ns (0 allocations: 0 bytes)
  1.522 ns (0 allocations: 0 bytes)

```

Though I still have to check how these approaches work inside CUDA kernels. I guess there will be issues with the recursion solution (though it is really elegant and I like it).

---

<div class="post-metadata">

**Author:** ![Per](https://sea2.discourse-cdn.com/julialang/user_avatar/discourse.julialang.org/per/32/10387_2.png) [@Per](https://discourse.julialang.org/u/Per)\
**Post date:** [June 25, 2019, 1:47pm UTC](https://discourse.julialang.org/t/non-allocating-loop-over-a-set-of-structs/25643/13 "2019-06-25T13:47:12Z")

</div>

It is worth noting that the reason why both the `@unroll`ed and the recursive functions are fast is that the types of the three `Sample`s are stored in the `Tuple` type. If any of the `.foo` fields would change, then the `Tuple` type would change and the entire `do_sum` and `frec` functions would need to be recompiled.

---

<div class="post-metadata">

**Author:** ![tkoolen](https://sea2.discourse-cdn.com/julialang/user_avatar/discourse.julialang.org/tkoolen/32/1603_2.png) [@tkoolen](https://discourse.julialang.org/u/tkoolen)\
**Post date:** [June 25, 2019, 3:22pm UTC](https://discourse.julialang.org/t/non-allocating-loop-over-a-set-of-structs/25643/14 "2019-06-25T15:22:42Z")

</div>

It looks like in this case the number of objects is small, so a tuple-based approach is probably best. Just wanted to note that in the case that the number of objects is large, but the number of different types is a lot smaller, you can use a tuple of concretely typed `Vector`s, unroll the loop over the different vectors, but then iterate over each of the vectors as normal. This approach is automated in [TypeSortedCollections.jl](https://github.com/tkoolen/TypeSortedCollections.jl) (I’m the main author). See also [Looping over different types with common behavior - #5 by tkoolen](https://discourse.julialang.org/t/looping-over-different-types-with-common-behavior/12068/5).