Work buffers for algorithms?

[gdalle]

See the discussion in #407

[rafaqz]

I like how Base.sort has sort! for in-place methods but also has a scratch keyword for the scratch space that some sorts like radix sort needs. Graphs could do something like that.

https://github.com/JuliaLang/julia/blob/75d5588d46bf7445626837f05e7a284ad85c7d30/base/sort.jl#L1730-L1739

And a helper method make_scratch:

  │    •  Base.Sort.make_scratch

  make_scratch(scratch::Union{Nothing, Vector}, T::Type, len::Integer)

  Returns (s, t) where t is an AbstractVector of type T with length at least len that is backed by the Vector s. If scratch !==
  nothing, then s === scratch.

  This function will allocate a new vector if scratch === nothing, resize! scratch if it is too short, and reinterpret scratch if its   
  eltype is not T.

[thchr]

One API for this could be something like this:

make_scratch(::typeof(algorithm), g::Graph) = (; scratch1 = ..., scratch2 = ...)

For any method depending on scratch space, a signature and implementation approach could then be

function algorithm(g, args...; scratch = make_scratch(algorithm, g))
    scratch1 = scratch.scratch1
    scratch2 = scratch.scratch2
    return algorithm!(g, args..., scratch1, scratch2)
end

If there's cases where "resetting" some of the scratch space after the calculation could be beneficial for reusing the buffers repeatedly, algorithm could potentially take a reset_scratch kwarg (defaulting to false):

function algorithm(g, args...; scratch = make_scratch(algorithm, g), reset_scratch::Bool = false)
    scratch1 = scratch.scratch1
    scratch2 = scratch.scratch2
    result = algorithm!(g, args..., scratch1, scratch2)
    if reset_scratch
        empty!(scratch1)
        zeros!(scratch2)
    end
    return result
end

[nsajko]

The MutableArithmetics package is relevant here. The make_scratch is a variant on buffer_for from Mutable Arithmetics.

• https://github.com/jump-dev/MutableArithmetics.jl

I propose:

• Taking inspiration from the MutableArithmetics design.

• Possibly even implementing the MutableArithmetics interface here (it's not just for arithmetic, despite the name). But that's a separate discussion.