35 Proposed changes to DGS 2

Proposal for dgs performance increase

Can we introduce a concept of nodes which represent many underlying nodes? That would reduce the number of dgs nodes and edges and increase efficiency.

For example, maybe we want a single node to stand for all indep nodes

    { MJigsaw::Pieces[i].Position | i }

We might also want to range over parameters of cache functions.

This is related to indexing DGS nodes in maps. Normally we key on MJigsaw.Pieces[i].Position. We instead want to key on MJigsaw.Pieces.Position. i.e. drop the [i] part.

In the process it would be nice to get maps working as well.

For cache functions, we still need to cache the values on all parameters, but we only key the DGS node on a subset of the parameters. That way there are fewer nodes than values. Possibly we use two maps, or else nested maps.

indeps in models

struct FieldId
{
    OID oid;
    Path path;
};

The path steps through:

• elements of structs
• elements of arrays
• elements of maps

In all three cases we may want to "range over" - i.e. have a node that represents the union over all the nodes.

In such cases application code needs to call an explicit read barrier, then subsequent accesses can directly access the model.

Q. How are we currently supporting visiting into the containing objects?

// 32 bytes on 64 bit platforms
class DGIndepNodeId
{
private:
    const void* m_fieldAddress;
    ptr<const IObject> m_object;  // Can be null
    const char* m_name;
};

// effectively
std::map<DGIndepNodeId, DGIndepNode>

The write barrier involves exactly the key in this map:

void DataSourceWriteBarrier(const void* fieldAddress, ptr<const IObject> obj, const char* name);

(and we could get some performance increase by passing through the address of a struct rather than all the members)

Proposal: Consider that paths allow for a special marker which means "any" at a given position. E.g.

    1.4.*.3.*."frog"

This standards for all paths of the form 1.4.i.3.j."frog" for some i and j. We need the generated code to somehow support getting such paths. E.g.

    obj.x[4][ANY][3].any["frog"].path()

The "fieldAddress" optimisation in its most general form means starting at the left, we proceed through fixed array and struct field members. After that point the data is relocable in memory and therefore we need to record a path from that point onward.

Write barriers

Currently the genop_xxx functions all initialse a FieldParams

struct PseudoFieldId
{
    PseudoOid oid;
    Path path;
};

// When this is generated the oid member is not initialised.
struct FieldParams
{
    ptr<IObject> obj;
    PseudoFieldId fid;
    void* addr;
    const char* name;
};

This is exactly what we need for full generality for the DGS. Furthermore these genop_xxx functions are well suited for caches that need to be updated incrementally. E.g. insertions and deletions in vectors.

The DGS write barriers hook into the genop_xxx functions. E.g.

@api void OCB_BeforeAssignValue(AssignValue_params& params)
{
    if (s_operationCallBacks)
    {
        params.fid.oid.low_ = 0;
        params.fid.oid.high_ = 0;
        s_operationCallBacks->OnBeforeAssignValue(params);
    }
    DataSourceWriteBarrier(params.addr,params.obj,params.name);
}

template <typename T>
inline void genop_Assign(ptr<IObject> obj, const Path& path, T& field, const char* name, const T& val)
{
    AssignValue_params params;
    params.obj = obj;
    params.fid.path = path;
    params.addr = &field;
    params.name = name;
    params.visitPrefsFn = nullptr;
    OCB_BeforeAssignValue(params);
    field = val;
}

So we certainly have access to the path.

API

The front end generates read() functions at all levels - even the main object. So course level DGS is very easy. These read() functions can return a reference as required.

We also allow for paths to have "any" in them. So one can invoke something like:

    // Invoke a read barrier
    obj.x[4].any[3].any["frog"].read()

For the jigsaw it would be:

    jigsawModel.Pieces.any().Position.read()

It just means at the point where we generate operator[] we also generate the any() method.

Clearly this will complicate the generated code. IF we can use templates to help simplify the generated code that might be a good idea.

Tree of indep nodes under an object

First we index off obj.self. If this becomes a bottleneck it can become state recorded in the object (perhaps an object records a pointer to this state).

For a given obj all the indep nodes which current exist under it are recorded in a tree. This tree structure follows the path idea. Nodes are created because of read barriers, not from write barriers. A write barrier causes a search through the tree. The tree might be empty in which case the search can have very low overhead! The tree search makes it possible to call OnChange() on multiple nodes along the path.

During the recurse down the tree, we have an InputArchive on the path. So deserialising the path as we go is very fast and very effective. E.g. the current node of the tree may represent an array so we need to deserialise an array index from the path. That allows us to recursive into the child if any. If there is no child then that just means there are no more indep nodes on which OnChange() needs to be called. If we had already reached the end of the path we can assume the entire array was the target of the operation.

In this tree there are the following kinds of nodes:

• struct nodes
• fixed array nodes
• dynamic array nodes
• map nodes

For the first three we use an xvector<DgiNode*> for the children. NULLs in this xvector means there are no children - so no need to call OnChange() on anything under that child. Navigating the path is fast (deserialise an index from the path and use it to index into the xvector).

A map node uses a std::map< VectorOfByte, DgiNode*>. The VectorOfByte is the serialised form of the key into the map. In this map we don't record NULL DgiNode pointers, instead we don't have a map entry at all.

Obviously the recurse must make use of the reflection information.