Long compilation time for large tuples

[dpsanders]

julia> ntuple(_->1, Val(10000))
Bus error: 10

julia> versioninfo()
Julia Version 1.4.1
Commit 381693d3df* (2020-04-14 17:20 UTC)
Platform Info:
  OS: macOS (x86_64-apple-darwin18.7.0)
  CPU: Intel(R) Core(TM) i9-9880H CPU @ 2.30GHz
  WORD_SIZE: 64
  LIBM: libopenlibm
  LLVM: libLLVM-8.0.1 (ORCJIT, skylake)

[yuyichao]

#14284 and related ones?

[ViralBShah]

Doesn't happen for me on 1.4.2. Takes a really long time and eventually starts printing (a lot).

[dpsanders]

Still happens for me on 1.4.2.

[dpsanders]

I confirm that this seems fixed on master from a few days ago. It takes several minutes before printing, so maybe the issue can be converted into "long compilation times for large homogeneous tuples".

[kleinhenz]

Is there a fundamental issue that makes large homogeneous tuples hard on the compiler or is this something that could plausibly be fixed with some optimization?

[timholy]

With sufficient effort it can be made better, but one reason this happens is pretty straightforward to understand, and once you understand it you'll probably stop trying to use large tuples (which is a form of victory itself):

1. while all Vector{T} are the same type (for a given T) regardless of how many objects are stored in the vector, each NTuple{N,T} is a separate type, requiring separate method specialization for each N,T combination. This is essential for the performance benefits that small tuples bring in many domains.
2. many tuple methods are implemented recursively, e.g., map(f, t::Tuple) = (f(t[1]), map(f, Base.tail(t))...).

The consequence is that for a given f, T combination, you only have to compile one method for map(f, v::Vector{T}) but you have to compile N methods for map(f, t::NTuple{N,T}). When N is 10000 (as it is in the OP), this is a lot of compilation.

A way to fix this is discovered if you search base's code for Any16, and your homework assignment is to go look up the methods that have been written for them and understand how they work. Once you do, you'll see that they solve the problem essentially by turning the tuple temporarily into a Vector.

So, if you're interested in seeing this fixed, almost anyone can pitch in:

• while you're waiting for a method to compile, hit Ctrl-C and see where it breaks. Likely this is a bottleneck in the compilation process, especially if the same method comes up repeatedly when you try this in fresh sessions.
• create an All16 or Any16 variant of the method, test that it works, and submit a PR.

But of course given that the solution is to turn long tuples into Arrays, you should question why you're using tuples in the first place.

[vtjnash]

This is partially a duplicate of the existing issues with handling StackOverflowError in a reliable way (which is not possible in general). But we should be able to fix this one fairly easily, since it is just a bad recursion design in iterate in the compiler which should be fixable with a workqueue:

Internal error: encountered unexpected error in runtime:
StackOverflowError()
renumber_ssa2! at ./compiler/ssair/ir.jl:903
process_node! at ./compiler/ssair/ir.jl:1042
process_newnode! at ./compiler/ssair/ir.jl:1191
iterate at ./compiler/ssair/ir.jl:1291
process_newnode! at ./compiler/ssair/ir.jl:1199
iterate at ./compiler/ssair/ir.jl:1291
process_newnode! at ./compiler/ssair/ir.jl:1199
iterate at ./compiler/ssair/ir.jl:1291
process_newnode! at ./compiler/ssair/ir.jl:1199
iterate at ./compiler/ssair/ir.jl:1291
process_newnode! at ./compiler/ssair/ir.jl:1199
iterate at ./compiler/ssair/ir.jl:1291
process_newnode! at ./compiler/ssair/ir.jl:1199
iterate at ./compiler/ssair/ir.jl:1291
process_newnode! at ./compiler/ssair/ir.jl:1199
iterate at ./compiler/ssair/ir.jl:1291
process_newnode! at ./compiler/ssair/ir.jl:1199
iterate at ./compiler/ssair/ir.jl:1291
process_newnode! at ./compiler/ssair/ir.jl:1199
iterate at ./compiler/ssair/ir.jl:1291
process_newnode! at ./compiler/ssair/ir.jl:1199
iterate at ./compiler/ssair/ir.jl:1291
process_newnode! at ./compiler/ssair/ir.jl:1199
iterate at ./compiler/ssair/ir.jl:1291
process_newnode! at ./compiler/ssair/ir.jl:1199
iterate at ./compiler/ssair/ir.jl:1291
process_newnode! at ./compiler/ssair/ir.jl:1199
iterate at ./compiler/ssair/ir.jl:1291
process_newnode! at ./compiler/ssair/ir.jl:1199
iterate at ./compiler/ssair/ir.jl:1291
process_newnode! at ./compiler/ssair/ir.jl:1199
...
iterate at ./compiler/ssair/ir.jl:1291
process_newnode! at ./compiler/ssair/ir.jl:1199
iterate at ./compiler/ssair/ir.jl:1291
compact! at ./compiler/ssair/ir.jl:1457
compact! at ./compiler/ssair/ir.jl:1455 [inlined]
run_passes at ./compiler/optimize.jl:513
optimize at ./compiler/optimize.jl:505 [inlined]
_typeinf at ./compiler/typeinfer.jl:255
typeinf at ./compiler/typeinfer.jl:209
typeinf_ext at ./compiler/typeinfer.jl:909
typeinf_ext_toplevel at ./compiler/typeinfer.jl:942
typeinf_ext_toplevel at ./compiler/typeinfer.jl:938
jfptr_typeinf_ext_toplevel_16813 at /Users/jameson/julia1/usr/lib/julia/sys.dylib (unknown line)
...

[Seelengrab]

Seems fixed:

[sukera@tower ~]$ julia -q
julia> @time ntuple(_->1, Val(10000));
  0.862546 seconds (503.10 k allocations: 22.667 MiB, 99.99% compilation time)

julia> versioninfo()
Julia Version 1.11.0-DEV.388
Commit 10599b104e1* (2023-09-01 07:08 UTC)
Platform Info:
  OS: Linux (x86_64-pc-linux-gnu)
  CPU: 24 × AMD Ryzen 9 7900X 12-Core Processor
  WORD_SIZE: 64
  LLVM: libLLVM-15.0.7 (ORCJIT, znver3)
  Threads: 34 on 24 virtual cores
Environment:
  JULIA_PKG_USE_CLI_GIT = true

[vtjnash]

That is from total const-prop, but if we block that somewhat, it still mostly works, just slowly:

julia> effect(::Val{0}) = GC.safepoint(); effect(::Val) = 1;

julia> @time ntuple(i->effect(Val(i)), Val(10000));
  9.686226 seconds (4.80 M allocations: 311.764 MiB, 1.25% gc time, 100.00% compilation time)

julia> @time ntuple(i->effect(Val(i)), Val(20000));
 58.135018 seconds (13.19 M allocations: 876.461 MiB, 0.41% gc time, 100.00% compilation time)

[vtjnash]

Fixed by #46843

[Seelengrab]

Nice!