7 The dependency graph

The dependency graph consists of nodes and edges. All nodes are instances of subclasses of DGBaseNode.

Single edge of the dependency graph

Consider a single edge of the dependency graph between nodes 'in' and 'out'. This basically means the value associated with node 'out' depends on the value associated with node 'in'

out-nodes

Node 'out' is one of the out-nodes of 'in'.

in-nodes

Node 'in' is one of the in-nodes of 'out'.

DGConnector

A DGConnector is a struct with 6 pointers that represents a single edge of the dependency graph. A DGConnector object instance represents both:

• an element of a double linked list for the out-nodes of node 'in'; and
• an element of a double linked list for the in-nodes of node 'out'

struct DGConnector
{
    const DGBaseNode* m_in;
    DGConnector* m_prevIn;
    DGConnector* m_nextIn;

    const DGDepNode* m_out;
    DGConnector* m_prevOut;
    DGConnector* m_nextOut;
};

This design has the following features:

• A new edge can be added to the dependency graph easily
• An existing edge of the dependency graph can be removed easily
• It is possible to iterate through all the out-nodes of a given node
• It is possible to iterate through all the in-nodes of a given dependent node

DGBaseNode

DGBaseNode is the base class for both the independent and dependent DGS nodes. All DGS nodes can have out-nodes.

class DGBaseNode
{
protected:
    void AttachOutnode(const DGDepNode* node) const;
    void DetachOutnode(DGConnector* c) const;
    bool HaveOutNodes() const { return m_firstOut != nullptr; }

private:
    // Pointer to the first in a linked list of out-nodes.
    mutable DGConnector* m_firstOut;
};

DGDepNode

DGDepNode is a subclass of DGBaseNode and represents a dependent DGS node. A dependent node can have in-nodes.

class DGDepNode : public DGBaseNode
{
public:
    bool HaveInNodes() const { return m_firstIn != nullptr; }
private:
    mutable DGConnector* m_firstIn;
};

Lifetime management of DGConnector instances

DGConnector object instances are always heap allocated. A DGConnector object is created when a new edge between two nodes is created, and deleted when the edge between two nodes is removed.

DGConnector object instances are not automatically deleted when nodes are destroyed. Instead it is assumed the dependency graph edges are removed before the nodes are destroyed. Indeed ~DGBaseNode() asserts there are no out-nodes:

DGBaseNode::~DGBaseNode()
{
    cxAssert(!m_firstOut);
}

and ~DGDepNode() asserts there are no in-nodes:

DGDepNode::~DGDepNode()
{
    cxAssert(!m_firstIn);
}

These assertions should never trip because:

• If a node either has in-nodes or out-nodes then it must exist in an eviction queue (by the way the converse is false - nodes with no in-nodes or out-nodes sometimes exist in an eviction queue!)
• While nodes are in an eviction queue they are not allowed to be deleted. The containing IObjects of DGS nodes in the eviction queues are visited by the CSpace GC to help ensure this.
• When nodes are evicted all their in-nodes and out-nodes are removed
• When the CSpace is closed, all DGS nodes are evicted from all eviction queues before the CSpace destroys the IObjects in the GC extent

TODO

This implementation makes heavy use of the heap to allocate and deallocate DGConnector instances. It will probably benefit from a custom allocator. Note that edges are often removed and recreated, so a memory pool is appropriate.

This code seems like a good candidate to factor out into a non-Xcpp template library.

DetachOutnode

void DGBaseNode::DetachOutnode(DGConnector* c) const
{
    cxAssert(c);
    cxAssert(c->m_in == this);
    cxAssert(c->m_out);
    cxAssert(c->m_out != this);

    // Erase from this node's list of out-nodes
    {
        if (c->m_prevOut)
        {
            cxAssert(c->m_prevOut->m_nextOut == c);
            c->m_prevOut->m_nextOut = c->m_nextOut;
        }
        else
        {
            cxAssert(m_firstOut == c);
            m_firstOut = c->m_nextOut;
        }

        if (c->m_nextOut)
        {
            cxAssert(c->m_nextOut->m_prevOut == c);
            c->m_nextOut->m_prevOut = c->m_prevOut;
        }

        c->m_prevOut = nullptr;
        c->m_nextOut = nullptr;
    }

    // Erase from the other node's list of in-nodes
    {
        if (c->m_prevIn)
        {
            cxAssert(c->m_prevIn->m_nextIn == c);
            c->m_prevIn->m_nextIn = c->m_nextIn;
        }
        else
        {
            cxAssert(c->m_out->m_firstIn == c);
            c->m_out->m_firstIn = c->m_nextIn;
        }

        if (c->m_nextIn)
        {
            cxAssert(c->m_nextIn->m_prevIn == c);
            c->m_nextIn->m_prevIn = c->m_prevIn;
        }

        c->m_prevIn = nullptr;
        c->m_nextIn = nullptr;
    }

    c->m_in = nullptr;
    c->m_out = nullptr;

    delete c;
}

AttachOutnode

Establish the link from this to the given (out) node. AttachOutnode() is called from the read-barrier of a node (whether independent or dependent).

this : the node (either independent or dependent) on which its read-barrier is called.

outNode : the (dependent) node which is currently being calculated.

void DGBaseNode::AttachOutnode(const DGDepNode* outNode) const
{
    cxAssert(outNode);
    cxAssert(outNode != this);

    DGConnector* c = new DGConnector;

    c->m_in = this;
    c->m_out = outNode;

    c->m_prevOut = nullptr;
    c->m_nextOut = m_firstOut;

    if (m_firstOut)
    {
        m_firstOut->m_prevOut = c;
    }
    m_firstOut = c;

    c->m_prevIn = nullptr;
    c->m_nextIn = outNode->m_firstIn;
    if (outNode->m_firstIn)
    {
        outNode->m_firstIn->m_prevIn = c;
    }
    outNode->m_firstIn = c;
}

When are DGS edges created?

Whenever a dependent node is read (so the read barrier is called) and it's dirty then dependency edges are always formed from its inputs. This maximises the caching of calculated values.

When are DGS edges destroyed?

When a dependent node becomes hard-dirty it always detaches from all of its input nodes. This is always the case, and the only time DGS edges are removed.