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

**URL:** <https://discourse.julialang.org/t/generic-code-over-stored-cached-value-or-value-computed-on-the-fly/39743>\
**Category:** General Usage\
**Created:** [May 19, 2020, 7:23am UTC](https://discourse.julialang.org/t/generic-code-over-stored-cached-value-or-value-computed-on-the-fly/39743 "2020-05-19T07:23:58Z")\
**Posts on this page:** 1\
**Page:** 1

<div class="post-metadata">

**Author:** ![goretkin](https://sea2.discourse-cdn.com/julialang/user_avatar/discourse.julialang.org/goretkin/32/167_2.png) [@goretkin](https://discourse.julialang.org/u/goretkin)\
**Post date:** [May 19, 2020, 7:23am UTC](https://discourse.julialang.org/t/generic-code-over-stored-cached-value-or-value-computed-on-the-fly/39743/1 "2020-05-19T07:23:58Z")

</div>

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 `NamedTuple`s. 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

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

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

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