using SparseArrays makes vcat'ing adjoint vectors memory hog, regression in Julia 1.10 beta

[jaakkor2]

using SparseArrays
a=[rand(2) for i=1:30000];
vcat(a'...)

EDIT: using SparseArrays that gets loaded by using Statistics

gives

ERROR: StackOverflowError:
Stacktrace:
 [1] _cat_size_shape(::Tuple{…}, ::Tuple{…}, ::LinearAlgebra.Adjoint{…}, ::LinearAlgebra.Adjoint{…}, ::Vararg{…}) (repeats 15353 times)
   @ Base .\abstractarray.jl:1748
 [2] cat_size_shape(::Tuple{…}, ::LinearAlgebra.Adjoint{…}, ::LinearAlgebra.Adjoint{…}, ::Vararg{…})
   @ Base .\abstractarray.jl:1746
 [3] _cat_t(::Val{1}, ::Type{Float64}, ::LinearAlgebra.Adjoint{Float64, Vector{Float64}}, ::Vararg{LinearAlgebra.Adjoint{Float64, Vector{…}}})
   @ Base .\abstractarray.jl:1787
 [4] _cat(::Val{1}, ::LinearAlgebra.Adjoint{Float64, Vector{Float64}}, ::Vararg{LinearAlgebra.Adjoint{Float64, Vector{Float64}}})
   @ SparseArrays C:\Users\jaakkor2\.julia\juliaup\julia-1.10.0-beta2+0.x64.w64.mingw32\share\julia\stdlib\v1.10\SparseArrays\src\sparsevector.jl:1221
 [5] cat(::LinearAlgebra.Adjoint{Float64, Vector{Float64}}, ::Vararg{LinearAlgebra.Adjoint{Float64, Vector{Float64}}}; dims::Val{1})
   @ Base .\abstractarray.jl:1981
 [6] vcat(::LinearAlgebra.Adjoint{…}, ::LinearAlgebra.Adjoint{…}, ::LinearAlgebra.Adjoint{…}, ::Vararg{…})
   @ SparseArrays C:\Users\jaakkor2\.julia\juliaup\julia-1.10.0-beta2+0.x64.w64.mingw32\share\julia\stdlib\v1.10\SparseArrays\src\sparsevector.jl:1233
Some type information was truncated. Use `show(err)` to see complete types.

The example works on Julia 1.9.

On Julia 1.10 both collect(hcat(a...)') and stack(a, dims=1) work ok, latter requires Julia ≥ 1.9.

julia> versioninfo()
Julia Version 1.10.0-beta2
Commit a468aa198d (2023-08-17 06:27 UTC)
Build Info:
  Official https://julialang.org/ release
Platform Info:
  OS: Windows (x86_64-w64-mingw32)
  CPU: 20 × 13th Gen Intel(R) Core(TM) i7-1370P
  WORD_SIZE: 64
  LIBM: libopenlibm
  LLVM: libLLVM-15.0.7 (ORCJIT, goldmont)
  Threads: 1 on 20 virtual cores

Julia from juliaup, started with julia +beta --startup-file=no

[brenhinkeller]

Can reproduce, and also that performance is fine on both versions without the using Statistics.

The stack overflow on splatting seems potentially serious enough to consider a bug as well as a performance regression. I'll add to the 1.10 milestone given that, but others feel free to undo..

[jishnub]

The issue is perhaps SparseArrays and not Statistics. The latter loads SparseArrays and introduces the offending method

[jakobnissen]

This is a duplicate of a larger problem, namely that

• Julia can't handle splatting lots of elements, and
• There is no mechanism to warn users trying to do this or throw an error. Instead, you just run into various internal buggy behaviour like stack overflows in internal functions, or the compiler taking forever.

May be considered a duplicate of #50473, #30796 and several other issues

Honestly I don't think doing regression whack-a-mole on basically unsupported behaviour is a good long-term strategy. Something like what is suggested by @StefanKarpinski in #50473 (comment) is the only real fix (or, alternatively, combing through Julia internals to guarantee handling of large splats, but I think this will be too hard)

[jishnub]

The large number of elements leading to a stack overflow is a red herring, as there's a performance regression in vcat that's evident even with a smaller number of terms:

julia> using SparseArrays

julia> a=[rand(2) for i=1:30];

julia> @btime vcat($a'...);
  5.382 μs (125 allocations: 4.25 KiB) # v1.9.2
  81.229 μs (1449 allocations: 35.75 KiB) # v1.10.0-beta2

[jaakkor2]

Note that BenchmarkTools pulls in Statistics that pulls in SparseArrays.

[KristofferC]

This is a duplicate of a larger problem, namely that

The issue here seems to be more the type piracy in SparseArrays.

[JeffBezanson]

Bisect points to 8fd5f27 (as far as the behavior change)

sparsevector.jl:1229 is the method called now. Could maybe be fixed by making anysparse iterative instead of recursive?

[JeffBezanson]

This patch to SparseArrays mostly fixes it:

diff --git a/src/sparsevector.jl b/src/sparsevector.jl
index 7e66bc0..12c3fe6 100644
--- a/src/sparsevector.jl
+++ b/src/sparsevector.jl
@@ -1229,13 +1229,13 @@ function hcat(X1::_SparseConcatGroup, X::_SparseConcatGroup...)
     if anysparse(X1) || anysparse(X...)
         X1, X = _sparse(X1), map(_makesparse, X)
     end
-    return cat(X1, X..., dims=Val(2))
+    return Base.typed_hcat(Base.promote_eltype(X1, X...), X1, X...)
 end
 function vcat(X1::_SparseConcatGroup, X::_SparseConcatGroup...)
     if anysparse(X1) || anysparse(X...)
         X1, X = _sparse(X1), map(_makesparse, X)
     end
-    return cat(X1, X..., dims=Val(1))
+    return Base.typed_vcat(Base.promote_eltype(X1, X...), X1, X...)
 end

On the benchmark above, I get:
1.9: 3.5us
1.10: 49us
this patch: 7.3us

Not all the way there unfortunately.