I want my custom type to implement indexed increments A[...] += B, but not assignments A[...] = B.
Currently, syntax like A[1:3] += [1, 2, 3] is parsed A[1:3] = A[1:3] + [1, 2, 3]. This is straightforward, but unoptimal, because we have excessive memory allocation when A[1:3] is called. Another bad consequence of this language design is that we cannot overload the += operator.
My proposal is the following: interpret the aforementioned expression to a call like mutate_setindex!(A, [1, 2, 3], +, 1:3), similar to how setindex! works now. The default implementation will be very simple:
mutate_setindex!(A::Any, B::Any, f::Function, I...) = A[I...] += f(A[I...], B)
#optimization for AbstractArrays
function mutate_setindex!(A::AbstractArray, B::AbstractArray, f::Function, I...)
# Shape check...
@. A[I...] += f(view(A, I...), B)
end
Also now package developers will be able to make their own implementations of mutating operators like +=.
Does Julia really need such a feature?
julia> f(x, y) = x[1:3] += y
f (generic function with 1 method)
julia> g(x,y) = x[1:3] .+= y
g (generic function with 1 method)
julia> h(x,y) = @views x[1:3] .+= y
h (generic function with 1 method)
julia> let x=[1,2,3,], y=[4,5,6];
@time f(x,y)
@time g(x,y)
@time h(x,y)
end;
0.000002 seconds (2 allocations: 160 bytes)
0.000000 seconds (1 allocation: 80 bytes)
0.000000 seconds
Not really. I’m speaking of interface, not performance. For my custom type, I want getindex and setindex! forbidden, but such mutating operations possible.
To be more precise, I want to create an abstraction that allows seamlessly building sparse arrays:
A = SparseMatrixBuilder(3, 3)
A[2, 3] += 4
A[1, 1] -= 1
A[2, 2] = 3 # This throws an error!
print(A[2, 2]) # This is an error, too!
a = to_matrix(A) # This is a 3x3 sparse array:
# -1 â‹… â‹…
# â‹… â‹… 4
# â‹… â‹… â‹…
The reason - using a simple SparseMatrix this way is extremely slow.
In many scenarios, the allocation condenses the elements in a type that allows for optimized operations, and this can outweigh the performance lost to frequent allocations.
This is very likely a breaking change. += would need to give the same results across v1 to not be breaking. You could instead make a macro that transforms this syntax, and it shouldn’t be in base Julia.
It doesn’t make sense to disallow A[2, 2] = 3 but allow A[2, 3] += 4. In both cases you are semantically setting an index of A, the only difference the latter adds the index’s existing value to the input value before setting the index. You can pull this off; your type doesn’t need to implement getindex and setindex! and can instead implement a different index-setting function digging into internal functions. But I fail to see the advantage of cutting yourself off from code using the AbstractArray interface just to impose operations before setting indices. If your issue is with the copy made when the indices are not all scalars, then you should use views, like broadcasting does.
Sparse arrays (mentioned above) have a heavy lookup/indexing cost, making them really benefit.
Dictionaries are another example.
In C++, d[k] += v would only do a single lookup, in Julia it’d do two. Pretty relevant when d is a dictionary or sparse array.
I can’t see why it is a breaking change. It introduces a new level of abstraction - true. But the default implementation I provided just copies the behavior that existed before, so no new errors should be expected from this. However, I agree that one should be careful with optimizations like I proposed.
In my example this is defined by how my SparseMatrixBuilder looks like under the hood.
The fastest way to build a sparse is providing horizontal indices, vertical indices and values of nonzero elements as three separate Vectors. So the implementation looks something like this:
using SparseArrays
struct SparseMatrixBuilder{T}
a::Int
b::Int
is::Vector{Int}
js::Vector{Int}
vs::Vector{T}
SparseMatrixBuilder{T}(a, b) where T = new{T}(a, b, [], [], [])
end
function mutate_setindex!(A::SparseMatrixBuilder, v, ::typeof(+), i, j)
push!(A.is, i)
push!(A.js, j)
push!(A.vs, v)
end
to_matrix(A::SparseMatrixBuilder) = sparse(A.is, A.js, A.vs, A.a, A.b)
Defining getindex in any way is a bad idea in this case.
Also there are other cases where one might want to overload compound assignment so that its semantics has nothing to do with indexing. For example, in some languages the += operator attaches an event listener.
That issue at least mentions that they are avoiding divergences between + and +=. So I think it would be sensible if += lowers to a higher order function that takes +.
The issue mentions a pretty serious issue with += when there is no indexing, but what Elrod said about repeated indexing makes sense. Instead of 1) index array in getindex or materialize! (1 element vs many) 2) do operation 3) index array again in setindex! or materialize! to write result, you could lower to something that does 1) index array and remember the address 2) do operation 3) write result to address.
Thank you for the info! Didn’t know this question was already addressed so long ago
But my initial idea was only about indexed compound assignment - this will not break anything. As for just += without indexing - one can come up with a syntax that will clearly show that A is mutable. Like A[] += B or A[:] += B or A[!] += B (taken from DataFrames.jl).
Also if we stay limited to the features of modern Julia, we can still hack into the broadcast system to make the A[I...] .+= B notation do what we want (by redefining copyto! and dotview for A). Not sure if it’s a good idea though.
Oh we wouldn’t need any extra indication that A is mutable. A[...] = ... does not work for any immutable A. But that linked issue informs that updating operators should not diverge from the original operators, so my point was rather than overloading the updating operators individually, you could have a higher-order mutate_setindex! that takes an operator + as input. This would be quite a hefty addition to the AbstractArray interface, though hopefully it can be mostly implemented in fallbacks, and a significant rewrite of broadcasting.
using SparseArrays
struct SparseMatrixBuilder{T}
a::Int
b::Int
is::Vector{Int}
js::Vector{Int}
vs::Vector{T}
SparseMatrixBuilder{T}(a, b) where T = new{T}(a, b, Int[], Int[], T[])
end
struct SparseMatrixBuilderScalarIndexView{T}
builder::SparseMatrixBuilder{T}
i::Int
j::Int
end
function Base.getindex(builder::SparseMatrixBuilder, i::Int, j::Int)
return SparseMatrixBuilderScalarIndexView(builder, i, j)
end
struct SparseMatrixBuilderNewAddition{T}
builder_view::SparseMatrixBuilderScalarIndexView{T}
v::T
end
function Base.:(+)(builder_view::SparseMatrixBuilderScalarIndexView{T}, v::T) where T
return SparseMatrixBuilderNewAddition(builder_view, v)
end
function Base.:(-)(builder_view::SparseMatrixBuilderScalarIndexView{T}, v::T) where T
return SparseMatrixBuilderNewAddition(builder_view, -v)
end
function Base.setindex!(builder::SparseMatrixBuilder{T}, v::SparseMatrixBuilderNewAddition{T}, i::Int, j::Int) where T
if !(i == v.builder_view.i && j == v.builder_view.j && builder === v.builder_view.builder)
error("good error message")
end
if !(1 <= i <= builder.a && 1 <= j <= builder.b)
throw(BoundsError(builder, (i, j)))
end
push!(builder.is, i)
push!(builder.js, j)
push!(builder.vs, v.v)
return v
end
to_matrix(A::SparseMatrixBuilder) = sparse(A.is, A.js, A.vs, A.a, A.b)
Note that builder[2, 2] works but return a “useless” object – there are no methods for it so will just give MethodError as soon as you try to use it. builder[2, 2] = 3 is a MethodError for example.
