36 Proposed changes to DGS

As currently the case each CSpace has its own DGS.

State:
    CSpace:
        The CSpace DGS has a Transaction Sequence Number (TSN) which is incremented for each writer
        transaction which changes one or more independent variables.  We call this the "CSpace TSN"

    independent variable:
        For each independent variable there is a change count which is assigned the current value of the
        CSpace TSN when the independent variable is updated.

    dependent variable:
        For each dependent variable the following information is recorded:
        -   its last calculated ("cache") value
        -   the set of inputs on which it was last calculated
        -   its change count, which is the value of the CSpace TSN at the time it was last calculated
        -   the maximum of the change counts over all its direct or indirect input independents at the
            time it was last calculated

Write barrier:
    When an independent variable is written a write barrier is invoked:

        Write barriers don't do anything more than update change counts, so they are very fast.

        There is no concept of explicitly propagating either soft or hard dirtiness through a
        dependency graph when writers update independent variables.

Read barrier:
    independent/dependent variable:
        The read barrier is used to record the set of direct inputs of a dependent which is being
        calculated.

    dependent variable:
        if (dep.changeCount == cspace.tsn)
        {
            // The dependent must (still be) clean, so the read barrier has nothing more to do
        }
        else
        {
            -   recursively invoke the read barrier on its recorded inputs.
            -   update the maximum of the change counts over all its direct or indirect independents
            -   if the change count is less than the maximum of the change counts over all its direct or
                indirect independents then
                    -   recalculate the cached value
                    -   set the change count to the current value of the CSpace TSN
        }

Question: how do we support soft versus hard dirty? The idea is to avoid updating the maximum of the change counts over all its direct or indirect independents, when it is found that the cached value didn't actually change. This makes it possible for cached values to made clean without reclaulating them.

$cache functions : this is no different, each key is mapped to a dependent variable. Map entries are created as they are accessed. Glocal LRU Eviction is used to evict cached variables.

Async cache functions

See DGAsyncNode.h.

Both dependent and independent DGS nodes can be asynchronous! Independent means that it doesn't have input dependencies. It can still need to be calculated! The ROT is an example.

There are four kinds of async node, according to whether it is keyed, and whether there's an input:

template <typename FinalClass, typename Self, typename Output>
class DGAsyncIndepNode : public DGIndepNode

template <typename FinalClass, typename Self, typename Key, typename Output>
class DGKeyedAsyncIndepNode : public DGIndepNode

template <typename FinalClass, typename Self, typename Input, typename Output>
class DGAsyncNodeOnInput : public DGDepNode

template <typename FinalClass, typename Self, typename Key, typename Input, typename Output>
class DGKeyedAsyncNodeOnInput : public DGDepNode

There is a bit flag DF_ASYNC_RUNNING to ensure at most one task is posted to calculate an async dependent.

Currently the virtual function

virtual void OnInvalidate() const

is implemented by template classes such as DGAsyncNodeOnInput to post a task to a thread pool which

1. Gets a CSpace lock, reads the inputs, then releases the lock
2. Calculates the output from the input
3. Gets a CSpace lock, swaps in the output, marks outnodes as dirty

When the inputs change the DGS node is automatically invalidated. Instead we have to poll because dirtiness is not propagated.

But polling is done for us automatically! The application polls for changes to the "top level" dependent(s), and these invoke the read barriers on other dependents and so on.

So whenever the read barrier of an async dependent is invoked, we have an opportunity to post a task to clean it.

Proposal

1. Prototype the new DGS in a pure C++ header library cxDgs Support the four kinds of async nodes. Support different implementations of the map for cache maps (e.g. std::map, std::unordered_map, std::array, std::vector, ...) Heavily test in txDgs. Optimise performance. Careful with how the heap is used. Allow colocation of indep/dep variable and associated DGS information. Optimise for case of keyed async indep nodes which can use a pointer embedded in the output to point at a pending async node. (ROT uses this trick, self pointer of ptr points at a pending ROT indep node)
2. Convert all of CEDA over to the new DGS