在 Julia 中，从前面还是从后面增长元组的性能更高？

Question

如果我有一个构建元组的递归函数，它在每个函数中通过在元组中附加/添加一个元素来创建一个新元组，是将它朝前还是朝后生长更好？有关系吗？即使它们最终执行相同，它们中的一个在编译器上是否更容易？

以这个愚蠢的函数为例，想象一下我不在乎数字是升序还是降序（因为我总是可以调整调用代码以两种方式工作）：

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)

有什么理由更喜欢t在之前n或之后喷溅吗？谢谢！

编辑：对于更多上下文：我们添加这样的元组是因为我们实际上将它用作不可变的函数跟踪，并且通过附加创建新元组是线程安全的，因此即使我们生成新任务它也能工作：每个任务都会然后让它自己的堆栈跟踪增长，跟踪所有调用者。

我认为更好的选择可能是PersistentVector来自https://github.com/JuliaCollections/FunctionalCollections.jl/blob/master/README.md的不可变内容，但对于最简单的第一遍，我只是使用元组，而我是想知道是否有任何理由更喜欢一种或另一种订单。:) 因为有些人可能有一个增长元组的有效用例，我想我会问。

Answer 1

使用Vectors 而不是Tuples。Tuples 是不可变的，这在实践中意味着它们需要在循环的每一步中重新创建。将元素附加到 的末尾Array。考虑以下示例：

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

现在是基准：

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)

请注意，百分比差异将随着 的增加而增加n。

最后但并非最不重要的。如果可能的话，Vector为结果预先分配而不是不断扩展它。考虑代码：

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

现在是基准测试（又快了 3 倍）：

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