Change of behavior/regression between julia 1.7 and 1.8

[lucasondel]

Hello,

I've observed some inconsistencies between julia 1.7 and 1.8 with the SparseArrays module:

1. Concatenation of sparse vectors:

julia> VERSION
v"1.7.2"
julia> using SparseArrays
julia> x = sparsevec([1], [3])
1-element SparseVector{Int64, Int64} with 1 stored entry:
  [1]  =  3
julia> vcat(x, zero(eltype(x)))
2-element SparseVector{Int64, Int64} with 1 stored entry:  # <- a sparse vector is returned as expected
  [1]  =  3

julia> VERSION
v"1.8.0"
julia> using SparseArrays
julia> x = sparsevec([1], [3])
1-element SparseVector{Int64, Int64} with 1 stored entry:
  [1]  =  3
julia> vcat(x, zero(eltype(x)))
2×1 SparseMatrixCSC{Int64, Int64} with 1 stored entry: # <- a sparse matrix CSC is returned
 3
 ⋅

2. Failure to use sum with types not supporting integer multiplication:

julia> VERSION
v"1.7.2"
julia> using SparseArrays
julia> using Semirings
julia> K = LogSemiring{Float64} # This type cannot be multiplied with an integer
LogSemiring{Float64}
julia> sum(sparse([2], [3], K[one(K)], 10, 10))
0.0

julia> VERSION
v"1.8.0"
julia> using SparseArrays
julia> using Semirings
julia> K = LogSemiring{Float64} # This type cannot be multiplied with an integer
LogSemiring{Float64}
julia> sum(sparse([2], [3], K[one(K)], 10, 10))
ERROR: promotion of types LogSemiring{Float64} and Int64 failed to change any arguments
Stacktrace:
  [1] error(::String, ::String, ::String)
    @ Base ./error.jl:44
  [2] sametype_error(input::Tuple{LogSemiring{Float64}, Int64})
    @ Base ./promotion.jl:383
  [3] not_sametype(x::Tuple{LogSemiring{Float64}, Int64}, y::Tuple{LogSemiring{Float64}, Int64})
    @ Base ./promotion.jl:377
  [4] promote
    @ ./promotion.jl:360 [inlined]
  [5] *(x::LogSemiring{Float64}, y::Int64)
    @ Base ./promotion.jl:389
  [6] _mapreducezeros
    @ ~/Julia/julia-1.8.0/share/julia/stdlib/v1.8/SparseArrays/src/sparsematrix.jl:1918 [inlined]
  [7] _mapreduce
    @ ~/Julia/julia-1.8.0/share/julia/stdlib/v1.8/SparseArrays/src/sparsematrix.jl:1913 [inlined]
  [8] _mapreduce_dim
    @ ./reducedim.jl:365 [inlined]
  [9] #mapreduce#764
    @ ./reducedim.jl:357 [inlined]
 [10] mapreduce
    @ ./reducedim.jl:357 [inlined]
 [11] #_sum#774
    @ ./reducedim.jl:999 [inlined]
 [12] _sum
    @ ./reducedim.jl:999 [inlined]
 [13] #_sum#773
    @ ./reducedim.jl:998 [inlined]
 [14] _sum
    @ ./reducedim.jl:998 [inlined]
 [15] #sum#771
    @ ./reducedim.jl:994 [inlined]
 [16] sum(a::SparseMatrixCSC{LogSemiring{Float64}, Int64})
    @ Base ./reducedim.jl:994
 [17] top-level scope
    @ REPL[11]:1

[MartinKocour]

+1

[rayegun]

@dkarrasch I haven't looked closely at the concatenation code, it looks like in 1.7 we went through the abstractarray.jl code path, while in 1.8 we go through the machinery in sparsevector.jl. This likely occurred here: f341c79 when Linalg and SA were fully split?

[dkarrasch]

Concatenation is always so much fun!!! This is on v1.6.7:

julia> vcat(x, zero(eltype(x)))
2-element SparseVector{Int64, Int64} with 1 stored entry:
  [1]  =  3

julia> vcat(zero(eltype(x)), x)
2-element Vector{Int64}:
 0
 3

[dkarrasch]

As for the second issue, the offending line is this one:

SparseArrays.jl/src/sparsematrix.jl

Lines 1918 to 1919 in aa51c9b

	_mapreducezeros(f, op::Union{typeof(Base.add_sum),typeof(+)}, ::Type{T}, nzeros::Integer, v0) where {T} =
	nzeros == 0 ? op(zero(v0), v0) : op(f(zero(T))*nzeros, v0)

In the sparse context, this is a very reasonable optimization. If you follow the call track, you see that it used to work only because the reduction was using generic, iterator-based code that is supposed to be slow for sparse matrices. In particular, it used to work only because it was tediously adding up all the zeros (or the values of f applied to zeros). I don't think that we will want to revert that optimization. So you may want to consider actually defining the multiplication via repeated addition, for instance, like

Base.:*(x::LogSemiring{T}, n::Integer) where T = begin
    z = zero(x)
    iszero(n) && return z
    if n > 0
        for _ in 1:n
            z += x
        end
    else
        for _ in 1:n
            z -= x
        end
    end
    return z
end

Note, this is not cheating, because this is what has been done inside sum in the generic case anyway.

[lucasondel]

I see... Then, we'll patch Semirings to support this. Thanks for the details.

[dkarrasch]

Closed by #253.