Generic code over stored/cached value or value computed on-the-fly

General Usage
1

Sorry in advance for a convoluted question. I struggled to come up with a concise example to illustrate what I’m after.

I’m trying to write some code that is generic over whether some values are eagerly computed, or should be recomputed. This choice is “static”. It should be possible to specialize the two cases at compile time.

Concretely, there is a quantity sofar that I want to compute over an iterable of NamedTuples. It’s the presence of a field :sofar that indicates whether the value has been cached. Otherwise, it is computed on the fly by walking the iterable.

Here are some values

sn_bare = [(path_element=0, path_summary=nothing)]
sn_cache = [(path_element=0, path_summary=(sofar=_zero,))]

And here are two functions that compute the presence of sofar

function has_cached_sofar(searchnode)
    tip = last(searchnode)
    return hasfield(typeof(tip.path_summary), :sofar)
end

function has_cached_sofar2(searchnode)
    Ttip = eltype(searchnode)
    return hasfield(Base.fieldtype(Ttip, :path_summary), :sofar)
end

I think it is last that is wreaking havoc on generating concise code. @code_llvm has_cached_sofar2(sn_bare) shows a single ret instruction, whereas @code_llvm has_cached_sofar(sn_bare) has more going on, because it must do something different if searcnode is empty. It’s possible that both have similar performance, but I didn’t check.

The code that I actually care more about is similar to the following

import DataStructures: PriorityQueue, enqueue!, dequeue!

const _zero = 0 # TODO make generic

function sofar(searchnode)
    Ttip = eltype(searchnode)
    if hasfield(Base.fieldtype(Ttip, :path_summary), :sofar)
        return last(searchnode).path_summary.sofar
    end

    # compute `sofar` from path
    s = _zero
    for a in searchnode
        s += a.path_element
    end
    return s
end


function concat(searchnode, path_element′)
    sofar′ = sofar(searchnode) + path_element′

    if has_cached_sofar2(searchnode)
        return (
            vcat(searchnode, [(path_element=path_element′, path_summary=(sofar=sofar′,))]),
            sofar′
        )
    end
    return (
        vcat(searchnode, [(path_element=path_element′, path_summary=nothing)]),
        sofar′
    )
end

function doit(searchnode_0, n)
    pq = PriorityQueue{typeof(searchnode_0), UInt64}()
    enqueue!(pq, searchnode_0 => UInt64(0))
    for _ = 1:n
        searchnode = dequeue!(pq)
        for pe′ = [1, -1]
            (searchnode′, uhp) = concat(searchnode, pe′)
            p = hash(uhp)
            # p = typemax(UInt64) - length(searchnode′)
            enqueue!(pq, searchnode′ => p)
        end
    end
    return dequeue!(pq)
end

sn_bare = [(path_element=0, path_summary=nothing)]
sn_cache = [(path_element=0, path_summary=(sofar=_zero,))]

path1 = getfield.(doit(sn_bare,1000), Ref(:path_element))
path2 = getfield.(doit(sn_cache,1000), Ref(:path_element))
@assert path1 == path2

I want to write doit in a way that is generic to whether the sofar value is stored or recomputed on-the-fly. It is possible to do in terms of a generic concat and sofar functions above. But I have not figured out how to make a good sofar function. @code_llvm sofar(sn_cache) and @code_llvm sofar(sn_bare) show a lot more going on than I had hoped.

So, finally

  1. is there a better way to write sofar?
  2. is there a better pattern to use to be generic in this way?

(In this case, asymptotically, it makes asymptotic sense to run the has-cached-sofar version, instead of recomputing the sum each time (though benchmarking with my horrible sofar function makes this hard to see). In case it helps make more sense of my problem, in my application, sofar is much bigger to store and much slower to compute, so I’m interested in writing the code generically because it’s not so clear which will be more performant.)