Generic functions between mutability

question
#1

There is often the question of whether to go for mutable types, like Array or BigInt, or for bitstypelike SVector or Int. The former demand careful management of temporaries, use of views and inplace operations; these are made much more convenient by dot-syntax. The latter are often significantly faster and automatically allocation-free; at the cost of somewhat inconvenient mutation, occasional use of dynamic dispatch, and limitation to small sizes.

It would be very nice to somehow write generic code that works for both variants. But I don’t know how. Do any of you here have ideas or advice how to do that?

As an example, let’s compute distances from some specified source in an undirected unweighted graph, whose adjacency matrix is stored in a BitMatrix, whose rows have been padded up to a multiple of 64. In the mutable case, that’s all there is to it. In the immutable case (for tiny matrices), the size of rows is part of the type; and we always get a SVector-like copy instead of a view into the row.

Full code is here. The algorithm is simple: In each step, we write out the distance of current vertices, and flag all unvisited neighbors of current vertices for the next step.

Now it would not be a problem to simply write two functions that don’t share any code. But there are many different algorithms one wants to override in the LightGraphs suite; and doubling the entire code seems pretty bad.

In the following, I control the return types of neighbors(g, i), so I could use any hare-brained customized broadcast scheme that writes to pointer_from_objref, in glorious MVector-style. Nor would I be opposed to macros, or occasional code-doubling, but I don’t want to double all the code. Any ideas?

function LightGraphs.gdistances(g::SBMGraph{N}, s) where N
    res = fill(-1, nv(g))
    @inbounds todo = visited = neighbors(g, i)
    nxt = zero(SRow{N})
    dist = 1
    done = false
    while !done
        done = true
        @inbounds for i in todo
            nxt |= neighbors(g, i) & ~visited
            res[i] = dist
            done = false
        end
        done && break
        visited |= nxt
        todo = nxt
        nxt = zero(SRow{N})
        dist += 1
    end
    res[s] = 0
    res
end

function LightGraphs.gdistances(g::BMGraph, s)
    res = fill(-1, nv(g))
    nchunks = size(g.adj_chunks, 1)
    visited = zeros(UInt, nchunks)
    todo = zeros(UInt, nchunks)
    nxt = zeros(UInt, nchunks)
    done = false
    dist = 1
    todo .= outneighbors(g, s).chunks
    visited .= outneighbors(g, s).chunks
    while !done
        done = true
        for i in BitRow(todo) #iterates over indices of set bits
            nxt .|=  outneighbors(g, s).chunks .& (~).(visited)
            res[i] = dist
            done = false
        end
        done && break
        visited .|= nxt
        todo .= nxt
        fill!(nxt, 0)
        dist += 1
    end
    res[s] = 0
    res
end

PS. The mutable implementation should work on the immutable graph type, but that would defy the point: The immutable graph type has the advantage of never allocating, and unrolling all broadcast-loops (which can be a single wide simd instruction, for small N).

#2

Perhaps I am missing something, but couldn’t you abstract the operations like

nxt .|= ...

into an interface like

nxt = calculate_next!(nxt, g, i, visited)

which then either updates nxt, or returns a new one, depending on the type? Similarly for other mutations. The rest of the code could be generic.

1 Like
#3

x-ref to Setfield.jl: https://github.com/jw3126/Setfield.jl/pull/31#issuecomment-396480792, https://github.com/jw3126/Setfield.jl/issues/32

1 Like
#4

But then, I would need to write two methods for calculate_next! and, even worse, write two methods for every single operation in the code. That seems worse than duplicating all code by 2x.

But I could have a macro

julia> macro maybe_inplace(ex)
              ex.head == :(.=) || throw(ArgumentError())
              ex.args[1] isa Symbol || throw(ArgumentError())
              esc( Expr(:(=), ex.args[1], ex) )
              end

julia> @macroexpand @maybe_inplace nxt .= nxt .| neighbors(g,i) .& (~).(visited)
:(nxt = (nxt .= nxt .| neighbors(g, i) .& (~).(visited)))

julia> Meta.lower(Main, quote @maybe_inplace nxt .= nxt .| neighbors(g,i) .& (~).(visited) end)
:($(Expr(:thunk, CodeInfo(
1 ─ %1 = neighbors(g, i)
│   %2 = (Base.broadcasted)(~, visited)
│   %3 = (Base.broadcasted)(&, %1, %2)
│   %4 = (Base.broadcasted)(|, nxt, %3)
│   %5 = (Base.materialize!)(nxt, %4)
│        nxt = %5
└──      return %5
))))

Next, I would need my bitstype to opt out of broadcasting by

Base.Broadcast.materialize!(::MyBits, bc::Base.Broadcast.Broadcasted{Style}) where Style = Base.Broadcast.materialize(bc) and Base.Broadcast.broadcasted(v::MyBits) = Ref(v).

In order to make the mutable variant work, I’d need Base.broadcasted(v::MyMutable) = v.chunks and Base.Broadcast.materialize!(dest::MyMutable, bc::Base.Broadcast.Broadcasted{Style}) where Style = begin Base.Broadcast.copyto!(dest.chunks, Base.Broadcase.instantiate(bc)); dest end.

Users would be warned that implicit allocation like res = a .& b, is not supported for the mutable variant (because that would not apply my wrapper type to the resulting Array{UInt64}). If I wanted to be extra fancy, I’d implement proper broadcasting for my mutable type, that re-applies wrapper.

Unfortunately I am closer to BitSet than AbstractArray, in terms of supported operations, and should not be <:AbstractArray. The two reasons I am not actually implementing the AbstractSet interface is that complement ~ is supported (the width is fixed), and a | b is just nicer than intersect(a, b). In fact, a & ~b is still nicer than setdiff(a, b).

Because applying such a macro to every single line is tedious, I’d instead write one that walks an entire expression and rewrites every sub-expression with head :(.=) and first argument of type Symbol.

That looks like a plan, at least.

1 Like
#5

Maybe this doesn’t apply to your example yet, but Julia has gotten much better at eliding heap allocations, and you can now do stuff like this without allocating:

I.e., if the size of the output is known at compile time, create MArrays, call the mutating version of the method, and convert the MArrays back to SArrays without allocations and while producing efficient code.

3 Likes
#6

So for StaticArrays, I have an operation like res = a + c * b, where c is a scalar and res, a, b are compatible <:AbstractArray.

Then, I’d write res = zero(tmp_type(typeof(a))) to maybe allocate a temporary, and always write res .= a .+ c .* b in my code, with something like tmp_type(::Type{X{T,N}}) where X<:AbstractArray = Array{T,N} and tmp_type(::Type{SArray{S,T,N,L}}) where {S,T,N,L} = MArray{S,T,N,L} and tmp_type(::Type{MArray{S,T,N,L}}) where {S,T,N,L} = MArray{S,T,N,L}?

My hope would be that julia manages to avoid the MArray allocations. But even if they do allocate, that would be outside of loops, so pretty benign.

That also sounds like a good plan. For that, I would read up on how StaticArrays does all its magic.

#7

Related: Make immutable mutable again - or make arrays of structures stack-allocated