# Generic functions between mutability

**URL:** <https://discourse.julialang.org/t/generic-functions-between-mutability/20983>\
**Category:** General Usage\
**Tags:** question\
**Created:** [February 19, 2019, 7:03pm UTC](https://discourse.julialang.org/t/generic-functions-between-mutability/20983 "2019-02-19T19:03:28Z")\
**Posts on this page:** 7\
**Page:** 1

<div class="post-metadata">

**Author:** ![foobar\_lv2](https://avatars.discourse-cdn.com/v4/letter/f/ee59a6/32.png) [@foobar\_lv2](https://discourse.julialang.org/u/foobar_lv2)\
**Post date:** [February 19, 2019, 7:03pm UTC](https://discourse.julialang.org/t/generic-functions-between-mutability/20983/1 "2019-02-19T19:03:28Z")

</div>

There is often the question of whether to go for `mutable` types, like `Array` or `BigInt`, or for `bitstype`like `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](https://github.com/chethega/BitmapGraphs). 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?

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

---

<div class="post-metadata">

**Author:** ![Tamas\_Papp](https://sea2.discourse-cdn.com/julialang/user_avatar/discourse.julialang.org/tamas_papp/32/25949_2.png) [@Tamas\_Papp](https://discourse.julialang.org/u/Tamas_Papp)\
**Post date:** [February 20, 2019, 9:53am UTC](https://discourse.julialang.org/t/generic-functions-between-mutability/20983/2 "2019-02-20T09:53:25Z")

</div>

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

```julia
nxt .|= ...

```

into an interface like

```julia
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.

---

<div class="post-metadata">

**Author:** ![mauro3](https://sea2.discourse-cdn.com/julialang/user_avatar/discourse.julialang.org/mauro3/32/292_2.png) [@mauro3](https://discourse.julialang.org/u/mauro3)\
**Post date:** [February 20, 2019, 9:55am UTC](https://discourse.julialang.org/t/generic-functions-between-mutability/20983/3 "2019-02-20T09:55:23Z")

</div>

x-ref to Setfield.jl: [Fix some tests and suppress warnings in Julia 0.7 by tkf · Pull Request #31 · jw3126/Setfield.jl · GitHub](https://github.com/jw3126/Setfield.jl/pull/31#issuecomment-396480792), [https://github.com/jw3126/Setfield.jl/issues/32](https://github.com/jw3126/Setfield.jl/issues/32)

---

<div class="post-metadata">

**Author:** ![foobar\_lv2](https://avatars.discourse-cdn.com/v4/letter/f/ee59a6/32.png) [@foobar\_lv2](https://discourse.julialang.org/u/foobar_lv2)\
**Post date:** [February 20, 2019, 3:31pm UTC](https://discourse.julialang.org/t/generic-functions-between-mutability/20983/4 "2019-02-20T15:31:55Z")

</div>

> [@Tamas\_Papp](#):
>
> but couldn’t you abstract the operations […] into an interface like `nxt = calculate_next!(nxt, g, i, visited)`

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

---

<div class="post-metadata">

**Author:** ![tkoolen](https://sea2.discourse-cdn.com/julialang/user_avatar/discourse.julialang.org/tkoolen/32/1603_2.png) [@tkoolen](https://discourse.julialang.org/u/tkoolen)\
**Post date:** [February 20, 2019, 3:50pm UTC](https://discourse.julialang.org/t/generic-functions-between-mutability/20983/5 "2019-02-20T15:50:35Z")

</div>

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:

> <https://github.com/tkoolen/PlanarConvexHulls.jl/blob/master/src/hrep.jl#L21-L76>

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

---

<div class="post-metadata">

**Author:** ![foobar\_lv2](https://avatars.discourse-cdn.com/v4/letter/f/ee59a6/32.png) [@foobar\_lv2](https://discourse.julialang.org/u/foobar_lv2)\
**Post date:** [February 20, 2019, 4:25pm UTC](https://discourse.julialang.org/t/generic-functions-between-mutability/20983/6 "2019-02-20T16:25:32Z")

</div>

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.

---

<div class="post-metadata">

**Author:** ![tkf](https://sea2.discourse-cdn.com/julialang/user_avatar/discourse.julialang.org/tkf/32/17635_2.png) [@tkf](https://discourse.julialang.org/u/tkf)\
**Post date:** [February 21, 2019, 1:30am UTC](https://discourse.julialang.org/t/generic-functions-between-mutability/20983/7 "2019-02-21T01:30:41Z")

</div>

Related: [Make immutable mutable again - or make arrays of structures stack-allocated](https://discourse.julialang.org/t/make-immutable-mutable-again-or-make-arrays-of-structures-stack-allocated/20800)