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).