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.

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)

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)