In Julia, is it more performant to grow a Tuple from the front or the back?

Question

If I have a recursive function that builds up a tuple, where in each function it creates a new tuple by appending/prepending an element to the tuple, is it better to grow it towards the front or towards the back? Does it matter? Is one of them easier on the compiler even if they end up ultimately performing the same?

Take this silly function as an example, and imagine that i don't care whether the numbers are ascending or descending (since I can always adjust the calling code to work either way):

julia> function tuple_one_through_n(n, t=())::Tuple
           if n === 0
               t
           else
               tuple_one_through_n(n-1, (n, t...))
           end
       end
tuple_one_through_n (generic function with 2 methods)

julia> tuple_one_through_n(5)
(1, 2, 3, 4, 5)

Is there any reason to prefer splatting t before n or after? Thanks!

EDIT: For more context: we're appending tuples like this because we're actually using this as an immutable function trace, and creating a new tuple by appending is thread safe, so it works even if we spawn new tasks: each task will then get it's own stack trace growing that traces all the callers.

I think a better option would probably be something like an immutable PersistentVector from https://github.com/JuliaCollections/FunctionalCollections.jl/blob/master/README.md, but for the easiest first pass I was just using tuples, and i was wondering if there was any reason to prefer one order or the other. :) Since some people probably have a valid use case for growing Tuples, I thought I'd ask.

Boom

If you don't care, why not use a set? – Rowenarowland

I do care about the order, i just don't care if it's ascending or descending, since i can easily adjust the code that reads it. Lemme adjust the wording, thanks. – Boom

Isn't this a simple question of benchmarking? What is it that you cannot find out by just using the ordinary timing tools? – Tynan

Okay sorry everyone, this was a dumb question. 😅 I was just curious if there was any difference between prepending and appending to a tuple, but yes obviously this is not a good pattern in general. EDIT: nvm you're apparently not supposed to delete a question that's been answered before... haha – Boom

Answer 1

This will hit dynamic dispatch and be so slow that the answer to the question wouldn't matter. And if the whole thing unrolls then it clearly doesn't matter either since the same expression will be generated.

A tuple seems like the wrong thing to use here (growing it to length n will be O(n^2) in general)

Alphonso

Answer 2

Use Vectors not Tuples. Tuples are immutable what in practice means that they need to be recreated with every step of the loop. Append the element to end of of the Array. Consider the following example:

function array_one_through_n(n, t=Int[])
   if n == 0
       t
   else
      append!(t,n)
      array_one_through_n(n-1, t)
  end
end

And now the benchmarks:

julia> @btime tuple_one_through_n(20);
  495.855 ns (18 allocations: 1.97 KiB)

julia> @btime array_one_through_n(20);
  280.345 ns (5 allocations: 624 bytes)

Note that the percentage difference will increase with the increasing n.

Last, but not least. If only possible preallocate the Vector for the results rather than continuously expanding it. Consider the code:

function array_one_through_n_pre(n, t=Vector{Int}(undef, n))
   if n == 0
       t
   else
      t[n]=n
      array_one_through_n_pre(n-1, t)
  end
end

And now the benchmark (another 3x faster):

julia> @btime array_one_through_n_pre(20);
  73.456 ns (1 allocation: 240 bytes)

Anatolic

In general, yes this is good advice. Thanks! But I cannot actually use vectors in this case, because in fact it's not going to be adding recursively, we're spawning different threads and extending the tuple in the different threads. So we need to be able to branch the list part way and push to it from different threads. That's why we're using tuples like this – Boom

In that case the best bet is to use an Array with a predifined size across the threads an an Atomic{Int} as the index. Than the threads can properly fill in the Array. Perhaps ask a seperate question on how to collect data from Threads into an Array and I can answer this. – Anatolic

Answer 3

Thanks @KristofferCarlsson and @PrzemyslawSzufel for your answers. Yes, splatting into a tuple like this is a bad idea in either direction; I was just being lazy.

Probably the right data structure for something like this is simply a linked list, which works just fine, and supports branching off multiple threads, each sharing the history until the branching, which is exactly what I wanted. I'll just go with that. Thanks!

julia> struct Node
          n::Int
          next::Union{Nothing,Node}
       end

julia> function tuple_one_through_n(n, t=nothing)::Node
           if n === 0
               t
           else
               tuple_one_through_n(n-1, Node(n, t))
           end
       end
tuple_one_through_n (generic function with 2 methods)

julia> using BenchmarkTools

julia> @btime tuple_one_through_n(10)
  87.694 ns (10 allocations: 320 bytes)
Node(1, Node(2, Node(3, Node(4, Node(5, Node(6, Node(7, Node(8, Node(9, Node(10, nothing))))))))))```

Boom