# When is a fold over a fixed-length tuple unrolled?

**URL:** <https://discourse.julialang.org/t/when-is-a-fold-over-a-fixed-length-tuple-unrolled/73410>\
**Category:** Performance\
**Created:** [December 21, 2021, 2:44am UTC](https://discourse.julialang.org/t/when-is-a-fold-over-a-fixed-length-tuple-unrolled/73410 "2021-12-21T02:44:39Z")\
**Posts on this page:** 7\
**Page:** 1

<div class="post-metadata">

**Author:** ![matthias314](https://avatars.discourse-cdn.com/v4/letter/m/a88e4f/32.png) [@matthias314](https://discourse.julialang.org/u/matthias314)\
**Post date:** [December 21, 2021, 2:44am UTC](https://discourse.julialang.org/t/when-is-a-fold-over-a-fixed-length-tuple-unrolled/73410/1 "2021-12-21T02:44:39Z")

</div>

`@code_typed` tells me that the statement

```julia
foldl(+, (1,2,3); init = 0)

```

is unrolled into three additions. On the other hand, if I say

```julia
struct A x::Int; y::Int; z::Int end

f(a::A) = foldl((1,2,3); init = UInt(0)) do h, i
    hash(getfield(a, i), h)
end

@code_typed f(A(1,2,3))

```

then I see a call to `Base.afoldl` (also with `@code_llvm` and `@code_native`), so I assume the code is not unrolled into three separate statements. (Also, if I unroll it by hand, then I get a function that runs faster.) My question therefore is: In which cases does such an expansion happen? Does it maybe depend on the size of the functions involved?

---

<div class="post-metadata">

**Author:** ![N5N3](https://sea2.discourse-cdn.com/julialang/user_avatar/discourse.julialang.org/n5n3/32/17663_2.png) [@N5N3](https://discourse.julialang.org/u/N5N3)\
**Post date:** [December 21, 2021, 8:55am UTC](https://discourse.julialang.org/t/when-is-a-fold-over-a-fixed-length-tuple-unrolled/73410/2 "2021-12-21T08:55:52Z")

</div>

If you use `Cthulhu` and decend into `_afold` you’ll find the kernal is unrolled.  
And the benchmark show little difference on my PC:

```julia
f(a::Tuple) = foldl(a; init = UInt(0)) do h, i
    hash(i, h)
end
_f(a::Tuple) = hash(a[3], hash(a[2], hash(a[1], UInt(0))))

AA = Ref((1,2,3))
using BenchmarkTools
@btime f($AA[]) # 5.000 ns (0 allocations: 0 bytes)
@btime _f($AA[]) # 5.100 ns (0 allocations: 0 bytes)

```

---

<div class="post-metadata">

**Author:** ![matthias314](https://avatars.discourse-cdn.com/v4/letter/m/a88e4f/32.png) [@matthias314](https://discourse.julialang.org/u/matthias314)\
**Post date:** [December 21, 2021, 1:59pm UTC](https://discourse.julialang.org/t/when-is-a-fold-over-a-fixed-length-tuple-unrolled/73410/3 "2021-12-21T13:59:12Z")

</div>

Maybe the time difference got lost when I simplified the code. Here is an example where I can see a difference:

```julia
struct A x::Int; y::Int; z::Int end

h1(a::A, h::UInt) = hash(a.z, hash(a.y, hash(a.x, hash(:A, h))))

function h2(x::A, h0::UInt)
    foldl(ntuple(identity, fieldcount(typeof(x)));
            init = hash(:A, h0)) do h, i
        hash(getfield(x, i), h)
    end
end

```

Here are the timings:

```julia
a = A(1,2,3)
@btime h1($a, UInt(0)) # 6.869 ns (0 allocations: 0 bytes)
@btime h2($a, UInt(0)) # 7.994 ns (0 allocations: 0 bytes)

```

Or shouldn’t I use `$a` for timings?

---

<div class="post-metadata">

**Author:** ![N5N3](https://sea2.discourse-cdn.com/julialang/user_avatar/discourse.julialang.org/n5n3/32/17663_2.png) [@N5N3](https://discourse.julialang.org/u/N5N3)\
**Post date:** [December 21, 2021, 3:15pm UTC](https://discourse.julialang.org/t/when-is-a-fold-over-a-fixed-length-tuple-unrolled/73410/4 "2021-12-21T15:15:55Z")

</div>

I can reproduce the Benchmark result on my pc.  
But if we use a for loop to bench:

```julia
a = A.(rand(1:100,100),rand(1:100,100),rand(1:100,100))
b = h1.(a,UInt(0))
@btime $b .= h1.($a,UInt(0)); # 664.780 ns (0 allocations: 0 bytes)
@btime $b .= h2.($a,UInt(0)); # 615.517 ns (0 allocations: 0 bytes)

```

`Cthulhu` shows that the indexed is not propgate in to the kernal as const for `h2`. Let’s try

```julia
function h3(x::A, h0::UInt)
    f(h, ::Val{i}) where {i} = hash(getfield(x, i), h)
    foldl(f, ntuple(Val, fieldcount(A)); init = hash(:A, h0))
end
@btime $b .= h3.($a,UInt(0)); # 579.570 ns (0 allocations: 0 bytes)

```

a little better.  
And the faster version is transforming `a::A` into a `Tuple`

```julia
function h4(a::A, h0::UInt)
    (;x, y, z) = a
    foldl((x, y, z); init = hash(:A, h0)) do h, i
        hash(i, h)
    end
end
@btime $b .= h4.($a,UInt(0)); # 482.653 ns (0 allocations: 0 bytes)

```

Not sure where cause the difference.

---

<div class="post-metadata">

**Author:** ![matthias314](https://avatars.discourse-cdn.com/v4/letter/m/a88e4f/32.png) [@matthias314](https://discourse.julialang.org/u/matthias314)\
**Post date:** [December 21, 2021, 4:55pm UTC](https://discourse.julialang.org/t/when-is-a-fold-over-a-fixed-length-tuple-unrolled/73410/5 "2021-12-21T16:55:39Z")

</div>

Thanks a lot!

> [@N5N3](#):
>
> the faster version is transforming `a::A` into a `Tuple`

The downside of this is that you need to hard-code the number of fields. (Or am I wrong?) `h2` and `h3` work for any type, except that `:A` is hard-coded. I’m thinking of using the code inside a macro that can be called as `@h(A)` and produces the function definition. Then `:A` can be inserted via `QuoteNode`. (In a regular function like `h2`, I could use `Symbol(typeof(x))`, but this is very slow because it first creates a string.)  
Of course, one can use generated functions, fancier macro code and other things to get a macro that does what I want, see [this GitHUb issue](https://github.com/andrewcooke/AutoHashEquals.jl/issues/22). I was trying to figure out how far one can get with folding without sacrificing speed.

---

<div class="post-metadata">

**Author:** ![N5N3](https://sea2.discourse-cdn.com/julialang/user_avatar/discourse.julialang.org/n5n3/32/17663_2.png) [@N5N3](https://discourse.julialang.org/u/N5N3)\
**Post date:** [December 22, 2021, 1:17am UTC](https://discourse.julialang.org/t/when-is-a-fold-over-a-fixed-length-tuple-unrolled/73410/6 "2021-12-22T01:17:26Z")

</div>

Then you might want?

```julia
function h5(a::T, h0::UInt) where {T}
    temp = ntuple(i -> getfield(a, i), fieldcount(A))
    foldl(temp; init = hash(T, h0)) do h, i
        hash(i, h)
    end
end
@btime $b .= h5.($a,UInt(0)); # 482.143 ns (0 allocations: 0 bytes)

```

I replaced `Symbol(A)` with `A`, as every typename has a unique objectid.  
But the benchmark make things more strange. Why there’s performance difference between `h2` and `h5`

---

<div class="post-metadata">

**Author:** ![matthias314](https://avatars.discourse-cdn.com/v4/letter/m/a88e4f/32.png) [@matthias314](https://discourse.julialang.org/u/matthias314)\
**Post date:** [December 22, 2021, 1:35am UTC](https://discourse.julialang.org/t/when-is-a-fold-over-a-fixed-length-tuple-unrolled/73410/7 "2021-12-22T01:35:05Z")

</div>

This is as fast as the hand-coded function `h1`. Great!

EDIT: Hashing a parametric type is slower than hashing a symbol (provided that you have the symbol and don’t need to generate it via `Symbol`).

I agree that it would be good to understand why `h2` is slower than `h5` or, even better, if it were as fast!