如何改进Julia中嵌套数组的速度？

Question

以下函数nested_arrays(令人惊讶地)生成"深度"的嵌套数组n.但是,当运行甚至很小的n(2,3等等)时,运行和显示输出需要相当长的时间.

julia> nested_arrays(n) = n == 1 ? [1] : [nested_arrays(n - 1)]
nested_arrays (generic function with 1 method)

julia> nested_arrays(1)
1-element Array{Int64,1}:
 1

julia> nested_arrays(2)
1-element Array{Array{Int64,1},1}:
 [1]

julia> nested_arrays(3)
1-element Array{Array{Array{Int64,1},1},1}:
 Array{Int64,1}[[1]]

julia> nested_arrays(10)
1-element Array{Array{Array{Array{Array{Array{Array{Array{Array{Array{Int64,1},1},1},1},1},1},1},1},1},1}:
 Array{Array{Array{Array{Array{Array{Array{Array{Int64,1},1},1},1},1},1},1},1}[Array{Array{Array{Array{Array{Array{Array{Int64,1},1},1},1},1},1},1}[Array{Array{Array{Array{Array{Array{Int64,1},1},1},1},1},1}[Array{Array{Array{Array{Array{Int64,1},1},1},1},1}[Array{Array{Array{Array{Int64,1},1},1},1}[Array{Array{Array{Int64,1},1},1}[Array{Array{Int64,1},1}[Array{Int64,1}[[1]]]]]]]]]

有趣的是,当使用@time宏或;在行的末尾时,结果花费的时间相对较少.相反,在REPL中实际显示结果占用了大部分时间.

这种奇怪的行为没有在例如Python中显示.

In [1]: def nested_lists(n):
   ...:     if n == 1:
   ...:         return [1]
   ...:     return [nested_lists(n - 1)]
   ...: 

In [2]: nested_lists(10)
Out[2]: [[[[[[[[[[1]]]]]]]]]]

In [3]: %time nested_lists(100)
CPU times: user 0 ns, sys: 0 ns, total: 0 ns
Wall time: 37.7 µs
Out[3]: [[[[[[[[[[[[[[[[[[[[[[[[[[[[[[[[[[[[[[[[[[[[[[[[[[[[[[[[[[[[[[[[[[[[[[[[[[[[[[[[[[[[[[[[[[[[[[[[[[[[1]]]]]]]]]]]]]]]]]]]]]]]]]]]]]]]]]]]]]]]]]]]]]]]]]]]]]]]]]]]]]]]]]]]]]]]]]]]]]]]]]]]]]]]]]]]]]]]]]]]]

为什么朱莉娅这个功能这么慢？朱莉娅重新编译display为不同类型的功能T的Array{T, 1}？如果是这样,为什么会这样？

可以提高这段代码的速度,还是应该不在Julia中完成？在实际意义上,我对此的主要关注点是,例如,加载一个复杂的嵌套JSON文件,其中简单地使用n-dimensional数组是不可能的.

Answer 1

是的,这完全是由于编译时间.你可以看到这个@time-ing的display.第二次显示它很快:

julia> nested_arrays(n) = n == 1 ? [1] : [nested_arrays(n - 1)]
nested_arrays (generic function with 1 method)

julia> @time display(nested_arrays(15));
1-element Array{Array{Array{Array{Array{Array{Array{Array{Array{Array{Array{Array{Array{Array{Array{Int64,1},1},1},1},1},1},1},1},1},1},1},1},1},1},1}:
 Array{Array{Array{Array{Array{Array{Array{Array{Array{Array{Array{Array{Array{Int64,1},1},1},1},1},1},1},1},1},1},1},1},1}[Array{Array{Array{Array{Array{Array{Array{Array{Array{Array{Array{Array{Int64,1},1},1},1},1},1},1},1},1},1},1},1}[Array{Array{Array{Array{Array{Array{Array{Array{Array{Array{Array{Int64,1},1},1},1},1},1},1},1},1},1},1}[Array{Array{Array{Array{Array{Array{Array{Array{Array{Array{Int64,1},1},1},1},1},1},1},1},1},1}[Array{Array{Array{Array{Array{Array{Array{Array{Array{Int64,1},1},1},1},1},1},1},1},1}[Array{Array{Array{Array{Array{Array{Array{Array{Int64,1},1},1},1},1},1},1},1}[Array{Array{Array{Array{Array{Array{Array{Int64,1},1},1},1},1},1},1}[Array{Array{Array{Array{Array{Array{Int64,1},1},1},1},1},1}[Array{Array{Array{Array{Array{Int64,1},1},1},1},1}[Array{Array{Array{Array{Int64,1},1},1},1}[Array{Array{Array{Int64,1},1},1}[Array{Array{Int64,1},1}[Array{Int64,1}[[1]]]]]]]]]]]]]]
 11.682721 seconds (8.83 M allocations: 371.698 MB, 1.82% gc time)

julia> @time display(nested_arrays(15));
1-element Array{Array{Array{Array{Array{Array{Array{Array{Array{Array{Array{Array{Array{Array{Array{Int64,1},1},1},1},1},1},1},1},1},1},1},1},1},1},1}:
 Array{Array{Array{Array{Array{Array{Array{Array{Array{Array{Array{Array{Array{Int64,1},1},1},1},1},1},1},1},1},1},1},1},1}[Array{Array{Array{Array{Array{Array{Array{Array{Array{Array{Array{Array{Int64,1},1},1},1},1},1},1},1},1},1},1},1}[Array{Array{Array{Array{Array{Array{Array{Array{Array{Array{Array{Int64,1},1},1},1},1},1},1},1},1},1},1}[Array{Array{Array{Array{Array{Array{Array{Array{Array{Array{Int64,1},1},1},1},1},1},1},1},1},1}[Array{Array{Array{Array{Array{Array{Array{Array{Array{Int64,1},1},1},1},1},1},1},1},1}[Array{Array{Array{Array{Array{Array{Array{Array{Int64,1},1},1},1},1},1},1},1}[Array{Array{Array{Array{Array{Array{Array{Int64,1},1},1},1},1},1},1}[Array{Array{Array{Array{Array{Array{Int64,1},1},1},1},1},1}[Array{Array{Array{Array{Array{Int64,1},1},1},1},1}[Array{Array{Array{Array{Int64,1},1},1},1}[Array{Array{Array{Int64,1},1},1}[Array{Array{Int64,1},1}[Array{Int64,1}[[1]]]]]]]]]]]]]]
  0.001688 seconds (2.38 k allocations: 102.766 KB)

那为什么这么慢？这里的显示递归遍历所有数组,并将它们嵌套在彼此内部.这是递归调用show14种不同的类型 - 一种是14个嵌套数组,然后是13个嵌套数组的元素,然后是12个元素......依此类推!这些show方法中的每一个都被独立编译.为特定元素类型编译专用方法是Julia如何生成非常高效代码的关键部分.这意味着它能够专门化每个元素上完成的每个操作,而无需任何运行时类型检查或调度.不幸的是,在这种情况下,它会妨碍.

你可以使用Any[]数组解决这个问题; 在JSON文件的上下文中,这非常有意义,因为你不知道它是否包含字符串或数组或数字等.这要快得多,因为它只需要为Any[]数组编译一次show方法,然后它递归地使用它.

# new session
julia> nested_arrays(n) = n == 1 ? Any[1] : Any[nested_arrays(n - 1)]
nested_arrays (generic function with 1 method)

julia> @time display(nested_arrays(15));
1-element Array{Any,1}:
 Any[Any[Any[Any[Any[Any[Any[Any[Any[Any[Any[Any[Any[Any[1]]]]]]]]]]]]]]
  1.571632 seconds (767.12 k allocations: 32.472 MB, 1.04% gc time)

julia> @time display(nested_arrays(15));
1-element Array{Any,1}:
 Any[Any[Any[Any[Any[Any[Any[Any[Any[Any[Any[Any[Any[Any[1]]]]]]]]]]]]]]
  0.000606 seconds (839 allocations: 30.859 KB)

julia> @time display(nested_arrays(100));
1-element Array{Any,1}:
 Any[Any[Any[Any[Any[Any[Any[Any[Any[Any[Any[Any[Any[Any[Any[Any[Any[Any[Any[Any[Any[Any[Any[Any[Any[Any[Any[Any[Any[Any[Any[Any[Any[Any[Any[Any[Any[Any[Any[Any[Any[Any[Any[Any[Any[Any[Any[Any[Any[Any[Any[Any[Any[Any[Any[Any[Any[Any[Any[Any[Any[Any[Any[Any[Any[Any[Any[Any[Any[Any[Any[Any[Any[Any[Any[Any[Any[Any[Any[Any[Any[Any[Any[Any[Any[Any[Any[Any[Any[Any[Any[Any[Any[Any[Any[Any[Any[Any[Any[1]]]]]]]]]]]]]]]]]]]]]]]]]]]]]]]]]]]]]]]]]]]]]]]]]]]]]]]]]]]]]]]]]]]]]]]]]]]]]]]]]]]]]]]]]]]]]]]]]]]
  0.002523 seconds (17.76 k allocations: 579.297 KB)