SArray initialization does not terminate

[jonathan-laurent]

The following snippet of code does not terminate:

using StaticArrays
SArray{Tuple{3,3,3},Union{Nothing, Int}}(fill(1, 27)) # does not terminate (after 300s)

Surprisingly, the following statements return as expected:

SArray{Tuple{3,3,3}, Int}(fill(1, 27)) # ok
SArray{Tuple{2,2,2},Union{Nothing, Int}}(fill(1, 8)) # ok

[tkoolen]

Can reproduce on Julia 1.1 and 1.2.

Reduced to:

julia> using StaticArrays

julia> tup = ntuple(i -> 1, 27)
(1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1)

julia> SArray{Tuple{3,3,3},Union{Nothing, Int}, 3, 27}(tup)

[tkoolen]

I think this is because of a compilation time blowup in

julia> for N = 1 : 18
           print(N, ": ");
           @time NTuple{N, Union{Nothing, Int}}(ntuple(i -> 1, N))
       end
1:   0.020819 seconds (85.99 k allocations: 4.413 MiB)
2:   0.003274 seconds (1.85 k allocations: 114.160 KiB)
3:   0.003351 seconds (1.91 k allocations: 117.066 KiB)
4:   0.003340 seconds (2.04 k allocations: 127.379 KiB)
5:   0.003483 seconds (2.33 k allocations: 137.160 KiB)
6:   0.003627 seconds (2.98 k allocations: 167.363 KiB)
7:   0.004058 seconds (4.39 k allocations: 233.645 KiB)
8:   0.004956 seconds (7.47 k allocations: 377.848 KiB)
9:   0.006916 seconds (14.13 k allocations: 690.129 KiB)
10:   0.011221 seconds (28.47 k allocations: 1.362 MiB)
11:   0.033110 seconds (59.81 k allocations: 2.774 MiB)
12:   0.040465 seconds (124.73 k allocations: 5.737 MiB)
13:   0.088323 seconds (264.00 k allocations: 12.113 MiB, 4.12% gc time)
14:   0.178905 seconds (558.92 k allocations: 25.613 MiB, 1.64% gc time)
15:   0.362540 seconds (1.18 M allocations: 54.176 MiB, 1.01% gc time)
16:   0.753271 seconds (2.56 M allocations: 118.117 MiB, 1.08% gc time)
17:   1.587808 seconds (5.38 M allocations: 248.117 MiB, 0.79% gc time)
18:   3.311642 seconds (11.27 M allocations: 520.117 MiB, 0.78% gc time)

[andyferris]

Yeah... we came across this in TypedTables as well I think. Basically too many Unions can cause problems (the product (tuple or struct) of 27 unions includes 2^27 different cases and I'm guessing some parts of the compiler has to deal with this complexity, but if we can handle it somehow I'm open to ideas).

[c42f]

Great sleuthing @tkoolen, I can confirm this is still a problem in the recent-ish version 1.3-DEV I've got here.

I doubt we can work around this in StaticArrays itself so I think we should close this issue in favor of JuliaLang/julia#32673 :-/