# Sum of tuples are slow

**URL:** <https://discourse.julialang.org/t/sum-of-tuples-are-slow/38541>\
**Category:** Performance\
**Created:** [May 1, 2020, 10:11am UTC](https://discourse.julialang.org/t/sum-of-tuples-are-slow/38541 "2020-05-01T10:11:28Z")\
**Posts on this page:** 13\
**Page:** 1

<div class="post-metadata">

**Author:** ![tfr](https://avatars.discourse-cdn.com/v4/letter/t/6bbea6/32.png) [@tfr](https://discourse.julialang.org/u/tfr)\
**Post date:** [May 1, 2020, 10:11am UTC](https://discourse.julialang.org/t/sum-of-tuples-are-slow/38541/1 "2020-05-01T10:11:28Z")

</div>

I did the following tests

```julia
using BenchmarkTools
a = collect(1: 100)
a_tuple = Tuple(a)
@benchmark sum($a)
@benchmark sum($a_tuple)

```

For the array `a` the output is

```julia
BenchmarkTools.Trial: 
  memory estimate: 0 bytes
  allocs estimate: 0
  --------------
  minimum time: 10.040 ns (0.00% GC)
  median time: 11.175 ns (0.00% GC)
  mean time: 11.428 ns (0.00% GC)
  maximum time: 102.707 ns (0.00% GC)
  --------------
  samples: 10000
  evals/sample: 999

```

For the tuple `a_tuple` the output is

```julia
BenchmarkTools.Trial: 
  memory estimate: 1.63 KiB
  allocs estimate: 4
  --------------
  minimum time: 4.123 μs (0.00% GC)
  median time: 4.310 μs (0.00% GC)
  mean time: 5.077 μs (1.88% GC)
  maximum time: 966.656 μs (98.90% GC)
  --------------
  samples: 10000
  evals/sample: 7

```

Have I done something wrong or tuples are indeed much slower in this example?

---

<div class="post-metadata">

**Author:** ![robsmith11](https://sea2.discourse-cdn.com/julialang/user_avatar/discourse.julialang.org/robsmith11/32/29641_2.png) [@robsmith11](https://discourse.julialang.org/u/robsmith11)\
**Post date:** [May 1, 2020, 12:09pm UTC](https://discourse.julialang.org/t/sum-of-tuples-are-slow/38541/2 "2020-05-01T12:09:49Z")

</div>

Tuples don’t necessarily have elements of the same type, so it appears that the sum function isn’t clever enough to realize it could use a vectorized sum in this case.

Foldl is a bit faster or you just reinterpret to an array when you know the types are all the same:

```julia
memory estimate: 832 bytes                                
allocs estimate: 2
  --------------
  minimum time: 1.001 μs (0.00% GC)                      
median time: 1.159 μs (0.00% GC)                    
  mean time: 1.124 μs (0.40% GC)                      
maximum time: 46.261 μs (97.10% GC)
  --------------                                           
  samples: 10000                                   
 evals/sample: 10

julia> @benchmark reinterpret(Int, [$a_tuple])
BenchmarkTools.Trial:
  memory estimate: 928 bytes
  allocs estimate: 2
  --------------                                            
 minimum time: 54.358 ns (0.00% GC)                     
median time: 67.345 ns (0.00% GC)                  
   mean time: 74.515 ns (7.90% GC)                     
maximum time: 508.725 ns (84.20% GC)
  --------------                                           
  samples: 10000                                 
   evals/sample: 986

```

---

<div class="post-metadata">

**Author:** ![ettersi](https://sea2.discourse-cdn.com/julialang/user_avatar/discourse.julialang.org/ettersi/32/6829_2.png) [@ettersi](https://discourse.julialang.org/u/ettersi)\
**Post date:** [May 1, 2020, 2:34pm UTC](https://discourse.julialang.org/t/sum-of-tuples-are-slow/38541/3 "2020-05-01T14:34:49Z")

</div>

Tuples are blazing fast if their length is \<= 32:

```julia
julia> a = collect(1:32);
       a_tuple = Tuple(a);
       b = Vector{Int}(undef,1);

julia> @benchmark $b[1] = sum($a)
BenchmarkTools.Trial: 
  memory estimate: 0 bytes
  allocs estimate: 0
  --------------
  minimum time: 17.451 ns (0.00% GC)
  median time: 17.508 ns (0.00% GC)
  mean time: 20.399 ns (0.00% GC)
  maximum time: 73.336 ns (0.00% GC)
  --------------
  samples: 10000
  evals/sample: 995

julia> @benchmark $b[1] = sum($a_tuple)
BenchmarkTools.Trial: 
  memory estimate: 0 bytes
  allocs estimate: 0
  --------------
  minimum time: 7.847 ns (0.00% GC)
  median time: 7.981 ns (0.00% GC)
  mean time: 9.270 ns (0.00% GC)
  maximum time: 62.961 ns (0.00% GC)
  --------------
  samples: 10000
  evals/sample: 998

```

(Assigning to `$b[1]` is necessary to prevent the compiler from eliminating the tuple computations altogether.)

---

<div class="post-metadata">

**Author:** ![tfr](https://avatars.discourse-cdn.com/v4/letter/t/6bbea6/32.png) [@tfr](https://discourse.julialang.org/u/tfr)\
**Post date:** [May 1, 2020, 3:05pm UTC](https://discourse.julialang.org/t/sum-of-tuples-are-slow/38541/4 "2020-05-01T15:05:41Z")

</div>

@robsmith11 Well, arrays don’t necessarily have elements of the same type as well. It sounds a bit odd to me that tuples, being less flexible than arrays, are slower.  
@ettersi Indeed I noticed that the time taken by sum() on tuples changed drastically from 20 to 40 elements, but the reason is still a mystery to me.

---

<div class="post-metadata">

**Author:** ![Henrique\_Becker](https://sea2.discourse-cdn.com/julialang/user_avatar/discourse.julialang.org/henrique_becker/32/15443_2.png) [@Henrique\_Becker](https://discourse.julialang.org/u/Henrique_Becker)\
**Post date:** [May 1, 2020, 3:18pm UTC](https://discourse.julialang.org/t/sum-of-tuples-are-slow/38541/5 "2020-05-01T15:18:05Z")

</div>

A mistery to me is why do you have Tuples with more than 32 elements, XD. It is not better to use [StaticArrays.jl](https://github.com/JuliaArrays/StaticArrays.jl) at this points? What is your use case?

---

<div class="post-metadata">

**Author:** ![avik](https://sea2.discourse-cdn.com/julialang/user_avatar/discourse.julialang.org/avik/32/17_2.png) [@avik](https://discourse.julialang.org/u/avik)\
**Post date:** [May 1, 2020, 3:26pm UTC](https://discourse.julialang.org/t/sum-of-tuples-are-slow/38541/6 "2020-05-01T15:26:22Z")

</div>

> [@tfr](#):
>
> Well, arrays don’t necessarily have elements of the same type as well

In general yes, but the complier can infer if a specific array has homegenous elements, and thus can optimise accordingly. So in your case, it know that it’s adding 64 bit integers.

```julia
julia> typeof(collect(1: 100))
Array{Int64,1}

```

However, in this case, that is not the cause of the problem, since it has that information for Tuples as well. It’s just that, as was said previously, Tuples are super optimised for small collections.

```julia
julia> typeof(Tuple(collect(1: 100)))
NTuple{100,Int64}

```

---

<div class="post-metadata">

**Author:** ![tfr](https://avatars.discourse-cdn.com/v4/letter/t/6bbea6/32.png) [@tfr](https://discourse.julialang.org/u/tfr)\
**Post date:** [May 1, 2020, 3:33pm UTC](https://discourse.julialang.org/t/sum-of-tuples-are-slow/38541/7 "2020-05-01T15:33:55Z")

</div>

@Henrique_Becker I have no practical use in mind. I just did this test and I found it odd. As I said previously I used to think that tuples, being less flexible, would be more efficient for this kind of simple operation, but it seems that I am wrong.

Thank you guys for the comments/explanations.

---

<div class="post-metadata">

**Author:** ![DNF](https://sea2.discourse-cdn.com/julialang/user_avatar/discourse.julialang.org/dnf/32/10191_2.png) [@DNF](https://discourse.julialang.org/u/DNF)\
**Post date:** [May 1, 2020, 3:59pm UTC](https://discourse.julialang.org/t/sum-of-tuples-are-slow/38541/8 "2020-05-01T15:59:37Z")

</div>

> [@tfr](#):
>
> would be more efficient for this kind of simple operation, but it seems that I am wrong.

No, as people have said, they _are_ more efficient, but they are intended for _small_ collections.

---

<div class="post-metadata">

**Author:** ![tim.holy](https://sea2.discourse-cdn.com/julialang/user_avatar/discourse.julialang.org/tim.holy/32/52_2.png) [@tim.holy](https://discourse.julialang.org/u/tim.holy)\
**Post date:** [May 1, 2020, 9:09pm UTC](https://discourse.julialang.org/t/sum-of-tuples-are-slow/38541/9 "2020-05-01T21:09:20Z")

</div>

Yep, the small collections is key.

They’re also _more_ flexible in some ways:

```julia
julia> typeof((3.5, "Hi"))
Tuple{Float64,String}

julia> typeof([3.5, "Hi"])
Array{Any,1}

```

Operations with the tuple will be inferrable and thus fast, whereas some operations with the array will be noninferrable and thus slow.

---

<div class="post-metadata">

**Author:** ![ettersi](https://sea2.discourse-cdn.com/julialang/user_avatar/discourse.julialang.org/ettersi/32/6829_2.png) [@ettersi](https://discourse.julialang.org/u/ettersi)\
**Post date:** [May 4, 2020, 2:28am UTC](https://discourse.julialang.org/t/sum-of-tuples-are-slow/38541/10 "2020-05-04T02:28:55Z")

</div>

> [@tfr](#):
>
> Indeed I noticed that the time taken by sum() on tuples changed drastically from 20 to 40 elements, but the reason is still a mystery to me.

There is no inherent reason why `sum(a_tuple)` with `length(a_tuple) > 32` has to be slow. The only reason why it currently is slow is because tuples aren’t intended to be used as long static-sized vectors, and so Julia is not optimised for this case.

---

<div class="post-metadata">

**Author:** ![Oscar\_Smith](https://sea2.discourse-cdn.com/julialang/user_avatar/discourse.julialang.org/oscar_smith/32/25343_2.png) [@Oscar\_Smith](https://discourse.julialang.org/u/Oscar_Smith)\
**Post date:** [May 4, 2020, 4:38am UTC](https://discourse.julialang.org/t/sum-of-tuples-are-slow/38541/11 "2020-05-04T04:38:03Z")

</div>

Specifically, the issue is that optimizing performance here makes the compiler a little crazy. Also, if you don’t have a cutoff, your type system is turing-complete (which is bad – you want inference to terminate).

---

<div class="post-metadata">

**Author:** ![oschulz](https://sea2.discourse-cdn.com/julialang/user_avatar/discourse.julialang.org/oschulz/32/2998_2.png) [@oschulz](https://discourse.julialang.org/u/oschulz)\
**Post date:** [November 17, 2023, 2:23pm UTC](https://discourse.julialang.org/t/sum-of-tuples-are-slow/38541/12 "2023-11-17T14:23:14Z")

</div>

Just ran into the same with `cumsum`:

```julia
julia> using BenchmarkTools

julia> tpl = (rand(1:10, 1)...,); @btime cumsum($tpl);
  2.520 ns (0 allocations: 0 bytes)

julia> tpl = (rand(1:10, 10)...,); @btime cumsum($tpl);
  3.785 ns (0 allocations: 0 bytes)

julia> tpl = (rand(1:10, 32)...,); @btime cumsum($tpl);
  14.795 ns (0 allocations: 0 bytes)

julia> tpl = (rand(1:10, 33)...,); @btime cumsum($tpl);
  3.041 μs (9 allocations: 1.89 KiB)

julia> tpl = (rand(1:10, 64)...,); @btime cumsum($tpl);
  47.400 μs (102 allocations: 28.34 KiB)

julia> tpl = (rand(1:10, 100)...,); @btime cumsum($tpl);
  128.165 μs (245 allocations: 78.97 KiB)

julia> VERSION
v"1.10.0-beta3"

```

The compiler may not be able to optimize as well for larger tuples, but the jump from ns to μs still seems huge. The cost seems to grow non-linearly, too, but not in a simple fashion. I guess cumcum goes through intermediate tuples of different sizes?

---

<div class="post-metadata">

**Author:** ![croberts](https://sea2.discourse-cdn.com/julialang/user_avatar/discourse.julialang.org/croberts/32/9465_2.png) [@croberts](https://discourse.julialang.org/u/croberts)\
**Post date:** [November 17, 2023, 2:45pm UTC](https://discourse.julialang.org/t/sum-of-tuples-are-slow/38541/13 "2023-11-17T14:45:39Z")

</div>

Would there be any value if Julia provided support for persistent arrays in Base (where elements are immutable)? StaticArrays were not intended for and do not work well for large arrays. FunctionalCollections.jl supports a “PersistentVector” type, which does work for longer arrays, but does not seem to facilitate compilation the way that StaticArrays does, and it does not support more general array types than Vector. BTW, how does Julia program its arrays? When I read through the Julia Base code, it looked like arrays were built into Julia rather than being written in Julia. I wonder if that imposes meaningful limitations on packages defining persistent arrays?