Slow performance on Tuple{Type1, Type2}

[timholy]

Here's a fun one that's an issue both here and for JLD. Since this is under "deeper" development, I thought I'd report it here.

The issue is that tuples can lead to a big penalty due to code specialization. This was discovered in the course of JuliaGraphics/Colors.jl@690f56e, where initially I used tuples like (Vector{RGB},Vector{HSV}) to store the expected results of conversion from many pairs of color spaces.

Demo:

using JLD2

vals = [Val{i}() for i = 1:20]
fn = tempname()
file = jldopen(fn, "w")
write(file, "val0", Val{0}())
@time write(file, "vals", vals)

valsa = [Any[vals[i],vals[j]] for i = 1:length(vals), j= 1:length(vals)]
@time write(file, "valsa", valsa)

valst = [(vals[i],vals[j]) for i = 1:length(vals), j = 1:length(vals)]
@time write(file, "valst", valst)

close(file)

Output:

julia> include("jldtest.jl")
  3.534846 seconds (3.09 M allocations: 132.546 MB, 1.48% gc time)
  0.311439 seconds (297.17 k allocations: 12.700 MB, 2.75% gc time)
 64.548822 seconds (45.51 M allocations: 1.928 GB, 1.57% gc time)

and obviously the result is quadratic in length(vals). The second run is fast, demonstrating that it's a codegen issue:

julia> include("jldtest.jl")
  0.000606 seconds (745 allocations: 30.797 KB)
  0.000872 seconds (1.27 k allocations: 70.797 KB)
  0.011489 seconds (11.75 k allocations: 511.844 KB)

This seems to argue for some kind of "late binding of types" design wherever possible?

The serializer has the same issue, but the coefficient is smaller:

julia> serialize(io, Val{0}())

julia> @time serialize(io, vals)
  0.818252 seconds (775.42 k allocations: 31.418 MB, 3.82% gc time)

julia> @time serialize(io, valsa)
  0.124597 seconds (147.32 k allocations: 6.075 MB)

julia> @time serialize(io, valst)
  4.480248 seconds (2.99 M allocations: 118.578 MB, 1.69% gc time)

julia> @time serialize(io, valsa)
  0.001521 seconds (2.42 k allocations: 389.188 KB)

julia> @time serialize(io, valst)
  0.011649 seconds (2.41 k allocations: 301.281 KB)

[simonster]

This is a hard one. If we have a lot of tuples of different types, then we don't want to specialize, but if we have a lot of tuples of the same type, then we do. I can think of a couple possible heuristics:

• Specialize on tuples in leaf-typed slots (or for arrays with leaf eltypes) but not in other cases.
• Specialize on types only after we have saved them n times. Otherwise use an unspecialized code path.

Either of these should solve this particular case. But actually writing the code in a way that allows either a specialized or unspecialized code path to be executed seems kinda hard.

I'd also like to decrease the amount of codegen time for each new type, so that the coefficient is closer to that of serialize, but it's difficult to know what needs to be optimized because we don't have a good way of profiling codegen time.

Ultimately, the problem here extends well beyond JLD. For example:

julia> vals = [Val{i}() for i = 1:5];

julia> @time valst = [(vals[i],vals[j]) for i = 1:length(vals), j = 1:length(vals)];
  0.061875 seconds (13.18 k allocations: 815.614 KB)

julia> @time show(IOBuffer(), valst);
  0.766540 seconds (714.30 k allocations: 36.741 MB, 1.21% gc time)

julia> vals = [Val{i}() for i = 6:35];

julia> @time valst = [(vals[i],vals[j]) for i = 1:length(vals), j = 1:length(vals)];
  2.797126 seconds (411.34 k allocations: 25.280 MB, 0.16% gc time)

julia> @time show(IOBuffer(), valst);
 19.339135 seconds (10.96 M allocations: 602.963 MB, 0.64% gc time)

Ideally Julia itself would be smart enough to interpret code until it's hot enough to deserve compilation (modern JS engines do this), but that's a long ways off.

[timholy]

CCing @carnaval and @vtjnash, not because I'm hoping for a quick fix, but because I think you'll find this one fun.

I hadn't thought of waiting to compile until you've actually run the code via the interpreter; seems like a smarter strategy than trying to forecast two costs (compilation and interpretation) and choosing in advance.

[JonasIsensee]

               _
   _       _ _(_)_     |  Documentation: https://docs.julialang.org
  (_)     | (_) (_)    |
   _ _   _| |_  __ _   |  Type "?" for help, "]?" for Pkg help.
  | | | | | | |/ _` |  |
  | | |_| | | | (_| |  |  Version 1.6.0 (2021-03-24)
 _/ |\__'_|_|_|\__'_|  |  Official https://julialang.org/ release
|__/                   |

julia> include("jldtest.jl")
  5.887887 seconds (10.20 M allocations: 565.706 MiB, 2.23% gc time, 16.08% compilation time)
  0.517091 seconds (1.11 M allocations: 58.193 MiB, 2.11% gc time, 99.70% compilation time)
110.533142 seconds (216.16 M allocations: 12.303 GiB, 3.57% gc time)

julia> include("jldtest.jl")
  0.000898 seconds (1.39 k allocations: 59.016 KiB)
  0.001258 seconds (5.25 k allocations: 202.031 KiB)
  0.013244 seconds (26.71 k allocations: 1.225 MiB)

Ouch, this has gotten significantly worse since then

Update:

   _       _ _(_)_     |  Documentation: https://docs.julialang.org
  (_)     | (_) (_)    |
   _ _   _| |_  __ _   |  Type "?" for help, "]?" for Pkg help.
  | | | | | | |/ _` |  |
  | | |_| | | | (_| |  |  Version 1.10.0 (2023-12-25)
 _/ |\__'_|_|_|\__'_|  |  Official https://julialang.org/ release
|__/                   |

julia> include("jldtest.jl")
Precompiling JLD2
  1 dependency successfully precompiled in 18 seconds. 10 already precompiled.
  1.474348 seconds (2.41 M allocations: 157.608 MiB, 13.24% gc time, 99.76% compilation time)
  0.213206 seconds (358.63 k allocations: 23.462 MiB, 3.82% gc time, 99.71% compilation time)
 43.048239 seconds (100.61 M allocations: 6.450 GiB, 3.16% gc time, 99.84% compilation time)

julia> include("jldtest.jl")
  0.000466 seconds (1.35 k allocations: 54.711 KiB)
  0.000492 seconds (1.26 k allocations: 51.461 KiB)
  0.006597 seconds (27.15 k allocations: 1.185 MiB)