DepGraph.cpp
// DepGraph.cpp
//
// Author David Barrett-Lennard
// (C)opyright Cedanet Pty Ltd 2007
#define NOMINMAX
@import "Ceda/cxObject/Object.h"
@import "Ceda/cxObject/DGNode.h"
@import "Ceda/cxObject/WCSpace.h"
@import "ExampleUtils.h"
#include <assert.h>
#include <map>
#include <algorithm>
/*
Dependency graphs
-----------------
Introduction
------------
The Dependency Graph System (DGS) provides a powerful means for efficiently and correctly
recalculating cached functional dependencies.
A significant part of software development relates to caching the results of time consuming
calculations, and only recalculating caches when the inputs of the calculation have changed.
A common approach is to use the observer pattern, and use notifications as a means to
recalculate caches. However, the problem is more difficult than it might first appear. There
are a number of pitfalls that can easily occur if cache maintenance is not implemented
correctly:
* Inefficiency caused by calculating caches unnecessarily
* Dirty reads - i.e. when a cache is read before it has been recalculated
* Stack overflow caused by a cycle in the dependency graph
* Reentrancy problems with the observer pattern - e.g. while notifying observers, the
subject receives incoming attach or detach calls.
* Deleting a subject while observers are still attached
* Cycles in the graph of attach relations.
The concept of lazy evaluation is very helpful in writing a correct and efficient program. The
basic idea is that caches are only calculated on demand. This avoids dirty reads because
calculation is automatically done in the right order (i.e. as prescribed by the dependency graph).
When changes occur, dependent caches are only marked as dirty, rather than being eagerly
recalculated. This can provide significant efficiency gains, because the inputs may be changed
many times before caches are recalculated. It allows an interface on an object to have lots of
fine grained mutative methods without a concern that dependent caches will be recalculated many
times. In fact objects in the system can accumulate many changes for an extended period before
any recalculation begins.
The basic form of the lazy evaluation approach requires invalidation of caches (i.e. marking caches
as dirty) to propagate eagerly through the dependency graph. In other words, change notifications
do nothing but invalidate caches, and this invalidation must immediately be propagated on to the
dependents in a recursive fashion.
However, in practice it is common for calculations to produce results that don't change despite
changes to the input. For example
* namespace look-up in a dictionary is a "calculation" that often provides the same result
despite the addition or removal of entries to or from the dictionary.
* the max() or min() functions, commonly used for bounding box calculations in GUI layout
management.
* logical or (p || q) is independent of q when p = true.
Therefore the basic form of the lazy evaluation approach can be too eager in its cache invalidation
strategy, leading to a great deal of unnecessary recalculation.
A solution is to introduce the concept of soft versus hard dirty states. When a node is changed
it is marked as hard-dirty, and all dependent nodes are recursively marked as soft-dirty. I.e.
only soft-dirtiness propagates immediately and eagerly through the dependency graph. When a node
that is soft-dirty is read, it first calls the read barrier on all its immediate inputs to see
whether they have really changed. If not then the soft-dirty status can be cleared without a need
to recalculate the cache.
Definitions and terminology
---------------------------
There are two types of nodes in the dependency graph:
* Independent nodes record a value in a variable which can be assigned different values,
but there is no sense in which the recorded value represents a cache of some calculation.
* Dependent nodes cache a calculated value. The calculation may read the values in any number
of "input" nodes.
Note that DGS nodes are finer grained than application objects. By making the dependency graph
explicit we achieve dependency analysis within an application object as well as between application
objects.
The dependency graph is a directed graph. It can be related to a data flow diagram. In the
following example, assume that all edges are directed upwards unless shown otherwise.
n1
/ \
/ \
n2 n3 n8
/ \ \ /
/ \ \ /
n4 n5 n6-->-+
| |
| |
n7----+
In this example, n4, n5 are independent nodes. All the other nodes are dependent nodes.
Nodes n6,n7 are involved in a cycle in the dependency graph. Cycles must be detected and dealt
with appropriately at run time. They do not necessarily represent a design error in the program.
For example, a system may allow end users to type in formulae at the nodes, making it quite easy
for cycles to appear. This "error" must be dealt with at run time. In particular, it must not
lead to a stack overflow!
Definition :
* The in-nodes of a node are the (adjacent) nodes that are directly read when its value is
calculated.
* The out-nodes of a node are the (adjacent) nodes that directly read the node when their
values are calculated.
In the above diagram, the in-nodes of n2 are n4, n5. The out-nodes of n6 are n3, n7, n8.
We say that a node /attaches/ to one of its in-nodes, in order to receive soft or hard invalidation
notifications. Notifications are sent in the direction of the directed links in the dependency
graph.
Requirements
------------
Over time we allow for the following changes
* Nodes can be added and removed
* A node may change is value/calculation (and be hard-invalidated). This can involve
arbitrary changes to the set of in-nodes. A dependent node may become independent and vice
versa.
Note that cycles can appear or disappear because of these changes.
Arbitrary many changes can accumulate before recalculation. All recalculation is dictated by
clients that call read barriers on nodes.
Automatic building of the dependency graph
------------------------------------------
Unlike the observer pattern there is no need to explicitly attach and detach observers to subjects.
Rather, this framework builds the dependency graph automatically by using read barriers on
dependency graph nodes. This removes an error prone task and greatly simplifies the problem of
writing an application.
The read barrier also allows the framework to take on responsibility for working out when to
recalculate a cached value (because it is dirty)
Summary of advantages
---------------------
The Dependency graph system features the following
* Lazy recalculation of dependents
* Short circuiting of recalculation when dependents haven't changed
* Automatic maintenance of the dependency graph
* IObject visiting through the dependency graph
* An elegant syntax
* Cycle detection
Concurrency
-----------
Each CSpace has a separate dependency graph. It is assumed at most one thread accesses the
objects in a given CSpace at a time.
*/
@def TraceVariable(x) = Tracer() << @str(x = ) << x << '\n';
///////////////////////////////////////////////////////////////////////////////////////////////////
/*
Defining dependent variables in an object
-----------------------------------------
The following example shows an object with model variables x1,x2,x3. These can be regarded as
"independent" nodes of the dependency graph.
Within the class definition, two dependent variables y1,y2 are defined. The definition is similar
to a declaration of a member variable, except for the '=' syntax plus the expression used to
calculate the dependent.
Note that dependents can be calculated from model variables as well as other dependents. In this
example the following dependency graph is formed:
y2
/ \
/ \
y1 \
/ \ \
/ \ \
x1 x2 x3
Output
------
p->y1 = 30
p->y2 = 80
*/
namespace DepGraphEx1
{
$struct X isa ceda::IObject :
model
{
int x1;
int x2;
int x3;
}
{
$dep int y1 = x1 + x2;
$dep int y2 = y1 + x3;
};
void Run()
{
ceda::TraceGroup g("DepGraph example 1");
ceda::CSpaceCreator cspace;
ceda::CSpaceTxn txn;
X* p = $new X();
p->x1 = 10;
p->x2 = 20;
p->x3 = 50;
TraceVariable(p->y1)
TraceVariable(p->y2)
}
}
///////////////////////////////////////////////////////////////////////////////////////////////////
/*
Alternative syntax for calculating dependents
---------------------------------------------
Instead of this syntax
$dep int y1 = x1 + x2;
the following alternative syntax can be used
$dep int y1 =
{
y1 = x1 + x2;
}
The code enclosed in braces can be regarded as the body of an anonymous member function of the
containing class, where the dependent variable to be calculated has been passed by reference.
In the following example we use this as an opportunity to trace a message that the dependent is
being recalculated
Output
------
[Calc y1] p->y1 = 30
p->y1 = 30
[Calc y2] p->y2 = 80
p->y2 = 80
Note that y1,y2 are calculated only once, showing that the calculations of y1 and y2 are being
cached.
*/
namespace DepGraphEx2
{
$struct X isa ceda::IObject :
model
{
int x1;
int x2;
int x3;
}
{
$dep int y1 =
{
Tracer() << "[Calc y1]";
y1 = x1 + x2;
};
$dep int y2 =
{
Tracer() << "[Calc y2]";
y2 = y1 + x3;
};
};
void Run()
{
ceda::TraceGroup g("DepGraph example 2");
ceda::CSpaceCreator cspace;
ceda::CSpaceTxn txn;
X* p = $new X();
p->x1 = 10;
p->x2 = 20;
p->x3 = 50;
TraceVariable(p->y1)
TraceVariable(p->y1)
TraceVariable(p->y2)
TraceVariable(p->y2)
}
}
///////////////////////////////////////////////////////////////////////////////////////////////////
/*
It is recommended that objects containing $indeps / $deps or $cache functions be heap allocated.
Otherwise it is necessary to force the DGS nodes to be evicted before the object destructs.
This isn't generally possible for objects containing async $deps or $cache functions.
Output
------
obj.y1 = 30
obj.y2 = 80
*/
namespace DepGraphObjectOnFrame
{
$struct X :
model
{
int x1;
int x2;
int x3;
}
{
$dep int y1 = x1 + x2;
$dep int y2 = y1 + x3;
};
void Run()
{
ceda::TraceGroup g("DepGraph object on the frame example");
ceda::CSpaceCreator cspace;
ceda::CSpaceTxn txn;
X obj;
// This would be needed if X implemented ceda::IObject
//ceda::RegisterNonGcObject(&obj);
obj.x1 = 10;
obj.x2 = 20;
obj.x3 = 50;
TraceVariable(obj.y1)
TraceVariable(obj.y2)
obj.EvictDgsNodes();
}
}
///////////////////////////////////////////////////////////////////////////////////////////////////
/*
This example illustrates another syntax which is available. It involves the definition of $cache
functions for the dependents y1 and y2.
$cache int y1() const
^^^^^
$cache functions always have const qualification.
Currently $cache functions must be inlined within the class definition.
Output:
[Calc y1] p->y1() = 30
p->y1() = 30
[Calc y2] p->y2() = 80
p->y2() = 80
*/
namespace CacheFunctions1
{
$struct X isa ceda::IObject :
model
{
int x1;
int x2;
int x3;
}
{
$cache int y1() const
{
Tracer() << "[Calc y1]";
return x1 + x2;
};
$cache int y2() const
{
Tracer() << "[Calc y2]";
return y1() + x3;
};
};
void Run()
{
ceda::TraceGroup g("CacheFunctions1");
ceda::CSpaceCreator cspace;
{
ceda::CSpaceTxn txn;
X* p = $new X();
p->x1 = 10;
p->x2 = 20;
p->x3 = 50;
TraceVariable(p->y1())
TraceVariable(p->y1())
TraceVariable(p->y2())
TraceVariable(p->y2())
}
}
}
///////////////////////////////////////////////////////////////////////////////////////////////////
/*
$cache functions can have one or more input parameters. In that case the calculated values are
cached in a map keyed by the input parameters in the implementation. The CSpace garbage collector
may occasionally evict map entries (this is done on an LRU basis for all evictable DGS nodes in the
CSpace).
Each map entry represents a separate dependent node in the dependency graph that records in-nodes
and out-nodes. Also like a $dep each map entry performs early quiescence testing (this can be turned
off for all map entries by specifying $cache^).
In this example the following dependency graph is formed:
g()
|
|
f(1) f(2)
/ \
/ \
/ \
b1 b2
Output:
CacheFunctions2
{
Setting b1 = 10 b2 = 20
[Calc f(1) = (a==1) ? a : max(b1,b2)] c->f(1) = 1
[Calc f(2) = (a==1) ? a : max(b1,b2)] c->f(2) = 20
f(1) and f(2) have been cached in a map
c->f(1) = 1
c->f(2) = 20
Setting b1 = 100. This invalidates f(2) but not f(1)
c->f(1) = 1
[Calc f(2) = (a==1) ? a : max(b1,b2)] c->f(2) = 100
[Calc g() = f(2)] c->g() = 100
Setting b2 = 50.
This invalidates f(2) but not g() because of early quiescence test on f(2)
[Calc f(2) = (a==1) ? a : max(b1,b2)] c->g() = 100
}
*/
namespace CacheFunctions2
{
$struct C isa ceda::IObject :
model
{
int b1;
int b2;
}
{
$cache int f(int a) const
{
Tracer() << "[Calc f(" << a << ") = (a==1) ? a : max(b1,b2)]";
return (a == 1) ? a : std::max(b1.read(),b2.read());
};
$cache int g() const
{
Tracer() << "[Calc g() = f(2)]";
return f(2);
}
};
void Run()
{
ceda::TraceGroup g("CacheFunctions2");
ceda::CSpaceCreator cspace;
ceda::CSpaceTxn txn;
C* c = $new C();
Tracer() << "Setting b1 = 10 b2 = 20\n";
c->b1 = 10;
c->b2 = 20;
TraceVariable(c->f(1))
TraceVariable(c->f(2))
Tracer() << "\nf(1) and f(2) have been cached in a map\n";
TraceVariable(c->f(1))
TraceVariable(c->f(2))
Tracer() << "\nSetting b1 = 100. This invalidates f(2) but not f(1)\n";
c->b1 = 100;
TraceVariable(c->f(1))
TraceVariable(c->f(2))
Tracer() << "\n";
TraceVariable(c->g())
Tracer() << "\nSetting b2 = 50.\nThis invalidates f(2) but not g() because of early quiescence test on f(2)\n";
c->b2 = 50;
TraceVariable(c->g())
}
}
///////////////////////////////////////////////////////////////////////////////////////////////////
/*
Invalidation notification
-------------------------
A dependent node is notified when it has been invalidated, because any one of its upstream nodes
has been invalidated or changed. This causes the invalidate-code to be executed. Note that this
is only a soft-dirty notification, because it is possible that the direct inputs to the dependent
have not actually changed value.
It is not permissible to issue any calls to calculate DG nodes from within the invalidate-code. It
should generally limit itself to marking things as dirty, signalling threads etc.
Invariably the invalidate callback is used to implement a self-cleaning dependent. Typically such
a dependent will post a task to recalculate it when it is invalidated. Sometimes we call a
self-cleaning dependent an "agent".
Dependents of type void
-----------------------
Sometimes the functionally dependent state of a node in the depencency graph are the pixels on the
screen (i.e. state in video memory) or state which exists in a third party library such as
wxWidgets.
In such cases it can be appropriate to use a $dep of type void. Although it seems strange to
calculate a variable of type void it just means the calculated state is being recorded elsewhere.
Dependency graph in this example
--------------------------------
y2
/ \
/ \
y1 \
/ \ \
/ \ \
x1 x2 x3
Output
------
Calculate the agent. This will cause y1 and y2 to be calculated
[Calc y1] [Calc y2]
Trace cached values of y1 and y2
y1 = 30
y2 = 80
Setting x1 = 5
This eagerly propagates soft-dirtiness through the DG, invalidating the agent
The framework will lazily recalculate y1,y2
[agent a invalidated] [Calc y1] y1 = 25
[Calc y2] y2 = 75
y1 = 25
y2 = 75
Setting x3 = 100
The framework avoids the recalculation of y1 which only depends on x1,x2
y1 = 25
[Calc y2] y2 = 125
y1 = 25
y2 = 125
Setting x1 = 5
x1 already has the value 5. The framework avoids the recalculation of y1 and y2
[Calc y1] y1 = 25
y2 = 125
Setting x1 = 4, x2 = 21
After recalculating y1 it is found that it hasn't changed. The framework avoids the recalculation of y2
[Calc y1] y1 = 25
y2 = 125
*/
namespace DepGraphEx3
{
$struct X isa ceda::IObject :
model
{
int x1;
int x2;
int x3;
}
{
$dep int y1 =
{
y1 = x1 + x2;
Tracer() << "[Calc y1]";
};
$dep int y2 =
{
y2 = y1 + x3;
Tracer() << "[Calc y2]";
};
$dep void myagent
invalidate
{
Tracer() << "[myagent invalidated]";
}
calc
{
// Pretend we are calculating screen pixel values, and this state is recorded in
// video memory, which is why myagent is of type void.
int screenValue = y2;
};
void Trace()
{
TraceVariable(y1)
TraceVariable(y2)
}
void Run()
{
x1 = 10;
x2 = 20;
x3 = 50;
Tracer() << "\nCalculate the agent. This will cause y1 and y2 to be calculated\n";
{
ceda::TraceIndenter indent(4);
myagent();
}
Tracer() << "\n\nTrace cached values of y1 and y2\n";
{
ceda::TraceIndenter indent(4);
Trace();
}
Tracer() << "\nSetting x1 = 5\n";
Tracer() << "This eagerly propagates soft-dirtiness through the DG, invalidating the agent\n";
Tracer() << "The framework will lazily recalculate y1,y2\n";
{
ceda::TraceIndenter indent(4);
x1 = 5;
Trace();
Trace();
}
Tracer() << "\nSetting x3 = 100\n";
Tracer() << "The framework avoids the recalculation of y1 which only depends on x1,x2\n";
{
ceda::TraceIndenter indent(4);
x3 = 100;
Trace();
Trace();
}
/*
todo: wrong. actually at the moment y1 is recalculated even though x1 didn't change
This is because the ceda framework doesn't check for redundant assignments to
independents.
*/
Tracer() << "\nSetting x1 = 5\n";
Tracer() << "x1 already has the value 5. The framework avoids the recalculation of y1 and y2\n";
{
ceda::TraceIndenter indent(4);
x1 = 5;
Trace();
}
Tracer() << "\nSetting x1 = 4, x2 = 21\n";
Tracer() << "After recalculating y1 it is found that it hasn't changed. The framework avoids the recalculation of y2\n";
{
ceda::TraceIndenter indent(4);
x1 = 4;
x2 = 21;
Trace();
}
}
};
void Run()
{
ceda::TraceGroup g("DepGraph example 3");
ceda::CSpaceCreator cspace;
ceda::CSpaceTxn txn;
X* p = $new X();
p->Run();
}
}
///////////////////////////////////////////////////////////////////////////////////////////////////
/*
Cycles
------
The dependency graph system is able to automatically detect cycles at run time in the functional
dependencies.
When a cycle is detected, a CycleException is thrown.
Dependency graph
----------------
--------->
y1 y2
/ <-------- \
/ \
x1 x3
Output
------
Error : cycle in dependencies
*/
namespace DepGraphCycleEx
{
$struct X isa ceda::IObject :
model
{
int x1;
int x2;
int x3;
}
{
$dep int y1 = x1 + y2;
$dep int y2 = x3 - y1;
};
void Run()
{
ceda::TraceGroup g("DepGraph example 4");
ceda::CSpaceCreator cspace;
ceda::CSpaceTxn txn;
X* p = $new X();
p->x1 = 10;
p->x2 = 20;
p->x3 = 30;
try
{
TraceVariable(p->y2);
}
catch(ceda::CycleException&)
{
Tracer() << "Error : cycle in dependencies\n";
}
}
}
///////////////////////////////////////////////////////////////////////////////////////////////////
/*
Disabling the early quiescence test
-----------------------------------
By default it is assumed that equality comparison is available for dependent cache values. The
DG framework uses this to test whether a recalculated value has changed from its previous value.
This can allow downstream nodes to avoid unnecessary recalculation if the inputs are found
not to have changed.
This leads to the concept of soft versus hard dirtiness. When a data model variable is changed,
soft dirtiness is always propagated immediately (i.e. synchronously) through the downstream nodes.
Later (and asynchronously) when recalculation is performed, cache value testing is used to
determine whether nodes should be marked as hard dirty. "Early quiescence" refers to the case
where a dependent is found not to have changed even though it is marked as soft dirty.
The chances of early quescence actually happening can vary widely. Some functional dependencies
are much more likely to exhibit this phenomenon than others. Some examples that often do are
* namespace lookup
* min and max functions
* boolean operations
Sometimes a cached value is very likely to change when any of its inputs change.
Furthermore it may be expensive to perform the value comparison. Therefore the framework allows
for early quiescence testing to be disabled. This involves placing a caret (^) after $dep.
Dependency graph
----------------
agent
|
sum = L[0] + L[1]
|
L = [x1+x2, x3+x3]
// \\
/ | | \
/ | | \
x1 x2 x3 x4
Output
------
Calculate the agent. This will cause L,sum to be calculated
[Calc L] [Calc sum]
Trace cached values of L,sum
L = [30,300]
sum = 330
Setting x1 = 5
This eagerly propagates soft-dirtiness through the DG, invalidating the agent
The framework will lazily recalculate L,sum
[Calc L] L = [25,300]
[Calc sum] sum = 325
L = [25,300]
sum = 325
Setting x1 = 5
x1 already has the value 5. The framework avoids the recalculation of L,sum
[Calc L] L = [25,300]
[Calc sum] sum = 325
Setting x1 = 4, x2 = 21
Even though L hasn't changed, sum is recalculated
[Calc L] L = [25,300]
[Calc sum] sum = 325
*/
namespace DepGraphDisableQuiescenceCheckEx
{
$struct X isa ceda::IObject :
model
{
int x1;
int x2;
int x3;
int x4;
}
{
// The ^ symbol disables comparison operations used to allow "early quiescence", i.e.
// recalculations will happen even if the result of the calculation is the same as
// previously calculated
$dep^ ceda::xvector<int> L =
{
L.clear();
L.push_back(x1+x2);
L.push_back(x3+x4);
Tracer() << "[Calc L]";
};
$dep int sum =
{
sum = 0;
// We are careful to only invoke the read barrier once, by storing a reference to the
// dependent L. Note that direct use of L would cause many redundant edges in the DG.
const ceda::xvector<int>& L2 = GetL();
for (int i=0 ; i < L2.size() ; ++i)
{
sum += L2[i];
}
Tracer() << "[Calc sum]";
};
$dep void myagent
invalidate {}
calc
{
int v = sum;
};
void Trace()
{
Tracer() << "L = " << GetL() << '\n';
Tracer() << "sum = " << sum << '\n';
}
void Run()
{
x1 = 10;
x2 = 20;
x3 = 100;
x4 = 200;
Tracer() << "\nCalculate the agent. This will cause L,sum to be calculated\n";
{
ceda::TraceIndenter indent(4);
myagent();
}
Tracer() << "\n\nTrace cached values of L,sum\n";
{
ceda::TraceIndenter indent(4);
Trace();
}
Tracer() << "\nSetting x1 = 5\n";
Tracer() << "This eagerly propagates soft-dirtiness through the DG, invalidating the agent\n";
Tracer() << "The framework will lazily recalculate L,sum\n";
{
ceda::TraceIndenter indent(4);
x1 = 5;
Trace();
Trace();
}
/*
todo: wrong. actually at the moment both L and sum are recalculated even though
x1 didn't change
This is because the ceda framework doesn't check for redundant assignments to
independents.
*/
Tracer() << "\nSetting x1 = 5\n";
Tracer() << "x1 already has the value 5. The framework avoids the recalculation of L,sum\n";
{
ceda::TraceIndenter indent(4);
x1 = 5;
Trace();
}
Tracer() << "\nSetting x1 = 4, x2 = 21\n";
Tracer() << "Even though L hasn't changed, sum is recalculated\n";
{
ceda::TraceIndenter indent(4);
x1 = 4;
x2 = 21;
Trace();
}
}
};
void Run()
{
ceda::TraceGroup g("DepGraphDisableQuiescenceCheckEx");
ceda::CSpaceCreator cspace;
ceda::CSpaceTxn txn;
X* p = $new X();
p->Run();
}
}
///////////////////////////////////////////////////////////////////////////////////////////////////
/*
Types can be used in transient models that are not normally associated with persistable
data types.
Dependency Graph
----------------
agent
|
y
// | \\
/ / | \ \
/ | | | \
x p p->x q q->x
Output
------
Calculate the agent. This will cause y = x + p->x + q->x to be calculated
Trace cached value of y (where x=10, p->x=20 q->x = 30 --> y = 60)
y = 60
Set p->x = 100, so y = 140
y = 140
Set x = 5, so y = 135
y = 135
Set p = new X. so p->x = 1 and y = 36
y = 36
Set q = new X. so q->x = 1 and y = 7
y = 7
Sequence of calculations of y
-----------------------------
x p->x q->x y
----------------------------
10 20 30 60
10 100 30 140
5 100 30 135
5 1 30 36
5 1 1 7
*/
namespace DepGraphEx6
{
$interface+ Ix : ceda::IObject
{
ceda::int32 x;
};
$struct X isa Ix :
model
{
ceda::int32 x;
ceda::ptr<Ix> p;
X* q;
$$() : x(1) {}
}
{
// The expression for y actually creates 5 edges in the dependency graph!
// i.e. because of the access to the pointer as well as what is pointed at.
$dep ceda::int32 y = x + p->x + q->x;
$dep void myagent
invalidate {}
calc { ceda::int32 v = y; };
void Trace()
{
TraceVariable(y)
}
void Run()
{
x = 10;
p = $new X;
p->x = 20;
q = $new X;
q->x = 30;
Tracer() << "\nCalculate the agent. This will cause y = x + p->x + q->x to be calculated\n";
{
ceda::TraceIndenter indent(4);
myagent();
}
Tracer() << "\nTrace cached value of y (where x=10, p->x=20 q->x = 30 --> y = 60)\n";
{
ceda::TraceIndenter indent(4);
Trace();
}
Tracer() << "\nSet p->x = 100, so y = 140\n";
{
ceda::TraceIndenter indent(4);
p->x = 100;
Trace();
}
Tracer() << "\nSet x = 5, so y = 135\n";
{
ceda::TraceIndenter indent(4);
x = 5;
Trace();
}
Tracer() << "\nSet p = new X. so p->x = 1 and y = 36\n";
{
ceda::TraceIndenter indent(4);
p = $new X;
Trace();
}
Tracer() << "\nSet q = new X. so q->x = 1 and y = 7\n";
{
ceda::TraceIndenter indent(4);
q = $new X;
Trace();
}
}
};
void Run()
{
ceda::TraceGroup g("DepGraph example 6");
ceda::CSpaceCreator cspace;
ceda::CSpaceTxn txn;
X* p = $new X();
p->Run();
}
}
///////////////////////////////////////////////////////////////////////////////////////////////////
/*
This example shows that independent variables work as expected with nested models. Also this
example shows how the invalidation notification from an agent can be used to set a "dirty agent
flag", to ensure that the agent is only recalculated where necessary.
[todo: really an agent should have access to the distinction between soft/hard dirtiness]
Output
------
Calculate the agent
Calculating DepVar
Set FM.Var1 = 100
Calculating DepVar
Set FM.Var2 = 101
Calculating DepVar
*/
namespace DepGraphEx7
{
$model+ FreestandingModel
{
int32 Var1;
int32 Var2;
};
$struct+ X isa ceda::IObject :
model
{
FreestandingModel FM;
}
{
$dep int32 DepVar =
{
Tracer() << "Calculating DepVar\n";
DepVar = FM.Var1 + FM.Var2;
};
$$() : m_dirty(false) {}
mutable bool m_dirty;
void doRecalcIfDirty()
{
if (m_dirty)
{
myagent();
m_dirty = false;
}
}
$dep void myagent
invalidate {m_dirty = true;}
calc { calcFn(); };
void calcFn() const
{
GetDepVar();
}
void Run()
{
Tracer() << "Calculate the agent\n";
{
ceda::TraceIndenter indent(4);
myagent();
}
Tracer() << "\nSet FM.Var1 = 100\n";
{
ceda::TraceIndenter indent(4);
FM.Var1 = 100;
// This should recalculate, because calculation depends on Var1.
doRecalcIfDirty();
}
Tracer() << "\nSet FM.Var2 = 101\n";
{
ceda::TraceIndenter indent(4);
FM.Var2 = 101;
// This should recalculate, because calculation depends on Var2.
doRecalcIfDirty();
}
}
};
void Run()
{
ceda::TraceGroup g("DepGraph example 7");
ceda::CSpaceCreator cspace;
ceda::CSpaceTxn txn;
X* p = $new X();
p->Run();
}
}
///////////////////////////////////////////////////////////////////////////////////////////////////
/*
Visit callbacks
---------------
Visit callbacks can be declared for $dep nodes.
The visit call back provides a mechanism for allowing IObjects to be visited for the purpose of
the CSpace GC.
$deps in mixins
---------------
This example demonstrates that dependents can be declared in mixins. 'calc' methods for dependents
can reference independent variables in models that feed into the mixin chain.
Dependency graph
----------------
agent
|
y = x+1
|
x
Output
------
myagent()
The calculations are cached
[agent calc]
[y calc]
Read y
This reads the cached valued of y
y = 11
x = 3
This marks y as hard-dirty and propagates soft-dirtiness through the DG, invalidating the agent
No recalculations are performed
[y invalidate]
[agent invalidate]
x = 5
This has no effect because dependents have already been marked as dirty
Read y
y is recalculated and cached
[y calc]
y = 6
Read y
This reads the cached value
y = 6
x = 5
x already has the value 5 - but the DGS doesn't check for that.
y is marked as hard-dirty. The agent is already soft-dirty.
[y invalidate]
Read y
y is hard-dirty so is recalculated and cached
[y calc]
y = 6
myagent()
This reads the cached value of y
[agent calc]
*/
namespace DepGraphEx8
{
$mixin M
{
$dep- int y
visit
{
Tracer() << "[y visit]\n";
}
invalidate
{
Tracer() << "[y invalidate]\n";
}
calc
{
y = this->x + 1;
Tracer() << "[y calc]\n";
};
$dep- void myagent
visit
{
Tracer() << "[agent visit]\n";
}
invalidate
{
Tracer() << "[agent invalidate]\n";
}
calc
{
Tracer() << "[agent calc]\n";
int v = y;
};
};
$struct X isa ceda::IObject :
model
{
int x;
}
mixin
[
M
]
{
void Trace()
{
TraceVariable(y)
}
void Run()
{
x = 10;
Tracer() << "myagent()\n"
" The calculations are cached\n";
{
ceda::TraceIndenter indent(4);
myagent();
}
Tracer() << "\nRead y\n"
" This reads the cached valued of y\n";
{
ceda::TraceIndenter indent(4);
Trace();
}
Tracer() << "\nx = 3\n"
" This marks y as hard-dirty and propagates soft-dirtiness through the DG, invalidating the agent\n"
" No recalculations are performed\n";
{
ceda::TraceIndenter indent(4);
x = 3;
}
Tracer() << "\nx = 5\n"
" This has no effect because dependents have already been marked as dirty\n";
{
ceda::TraceIndenter indent(4);
x = 5;
}
Tracer() << "\nRead y\n"
" y is recalculated and cached\n";
{
ceda::TraceIndenter indent(4);
Trace();
}
Tracer() << "\nRead y\n"
" This reads the cached value\n";
{
ceda::TraceIndenter indent(4);
Trace();
}
Tracer() << "\nx = 5\n"
" x already has the value 5 - but the DGS doesn't check for that.\n"
" y is marked as hard-dirty. The agent is already soft-dirty.\n";
{
ceda::TraceIndenter indent(4);
x = 5;
}
Tracer() << "\nRead y\n"
" y is hard-dirty so is recalculated and cached\n";
{
ceda::TraceIndenter indent(4);
Trace();
}
Tracer() << "\nmyagent()\n"
" This reads the cached value of y\n";
{
ceda::TraceIndenter indent(4);
myagent();
}
}
};
void Run()
{
ceda::TraceGroup g("DepGraph example 8");
ceda::CSpaceCreator cspace;
ceda::CSpaceTxn txn;
X* p = $new X();
p->Run();
}
}
namespace CannotUpdateModelWhenRecalcDependent
{
$struct A isa ceda::IObject :
model
{
int v;
}
{
};
ceda::IObjectVisitor& operator<<(ceda::IObjectVisitor& v, A*) { return v; }
$struct B isa ceda::IObject :
model
{
A* a;
}
{
$dep int y =
{
y = a->v + 1;
// The purpose of this test is to verify that the following line causes a run time
// assertion. It is not permissible to modify a model during the recalculation of
// a dependent node.
a->v = 1;
};
};
void Run()
{
ceda::TraceGroup g("CannotUpdateModelWhenRecalcDependent");
ceda::CSpaceCreator cspace;
ceda::CSpaceTxn txn;
A* a = $new A();
B* b = $new B();
b->a = a;
// Trips cxAssert(!m_currentNodeBeingCalculated) in DGSystem.cpp,
// DGSystem::DataSourceWriteBarrier()
Tracer() << "y = " << b->y << '\n';
}
}
/*
The following example demonstrates how assertions are tripped when inappropriate code
is executed within the invalidate or calc callbacks
*/
namespace DepGraphCallbackRestrictions
{
$struct C1 isa ceda::IObject :
model
{
int x1;
}
{
$dep int y1 = x1;
};
$struct C2 isa ceda::IObject :
model
{
int x2;
}
{
C1* pc1;
$dep int y2
visit
{
Tracer() << "[y2 visit]\n";
}
invalidate
{
Tracer() << "[y2 invalidate]\n";
// Independent nodes must not be accessed from OnInvalidate() handler of a dependent node
// Trips cxAssert(m_callback == ECB_None) in DGSystem::DataSourceReadBarrier()
// int v = x2;
// Independent nodes must not be accessed from OnInvalidate() handler of a dependent node
// Trips cxAssert(m_callback == ECB_None) in DGSystem::DataSourceWriteBarrier
// pc1->x1 = 1;
// OnInvalidate() handler must not result in a call to ReadBarrier().
// Trips cxAssert(system.m_callback == ECB_None) in DGDepNode::ReadBarrier()
// int v = y2;
// Invalidate() must not be called from OnInvalidate() handler of a dependent node
// Trips cxAssert(system.m_callback == ECB_None) in DGDepNode::Invalidate()
// y2.Invalidate();
}
calc
{
y2 = x2 + 1;
Tracer() << "[y2 calc]\n";
// Cannot modify a model while recalculating a node
// Trips cxAssert(!m_currentNodeBeingCalculated) in DGSystem::DataSourceWriteBarrier()
// pc1->x1 = 1;
// Cannot invalidate a dependent node while a dependent is being recalculated
// Trips cxAssert(!system.m_currentNodeBeingCalculated) in DGDepNode::Invalidate()
// pc1->y1.Invalidate();
};
};
void Run()
{
ceda::TraceGroup g("DepGraphCallbackRestrictions");
ceda::CSpaceCreator cspace;
ceda::CSpaceTxn txn;
C1* c1 = $new C1();
C2* c2 = $new C2();
c2->pc1 = c1;
c2->x2 = 5;
Tracer() << "y2 = " << c2->y2 << '\n';
c2->x2 = 10;
Tracer() << "y2 = " << c2->y2 << '\n';
}
}
///////////////////////////////////////////////////////////////////////////////////////////////////
/*
Notes on $indep
---------------
- This can be regarded as an alternative to using a $model, for defining independent variables
for the DGS.
- $indep fields can support a visit handler (just like $dep variables).
- In a similar manner to model fields, read() and write() methods are available on $indep fields
write() returns a mutative reference and is useful for invoking the write barrier, when some
operation other than assignment is appropriate for updating the variable.
read() returns a const reference to the variable and is useful for invoking the read barrier
without the expense of making a copy.
In this example the following dependency graph is formed:
myagent
|
|
y2
/ \
/ \
y1 \
/ \ \
/ \ \
x1 x2 x3
Generated output:
IndepEx
{
y1 = [Calc y1] 30
Set x1 = 1
y1 = [Calc y1] 21
Set x1 = 3
y2 = [Calc y1] [Calc y2] 73
}
*/
namespace IndepEx
{
$struct X isa ceda::IObject
{
$indep int x1;
$indep int x2;
$indep int x3;
$dep int y1 =
{
y1 = x1 + x2;
Tracer() << "[Calc y1]";
};
$dep int y2 =
{
y2 = y1 + x3;
Tracer() << "[Calc y2]";
};
void Run()
{
x1 = 10;
x2 = 20;
x3 = 50;
Tracer() << "y1 = ";
Tracer() << y1;
Tracer() << '\n';
Tracer() << "Set x1 = 1";
x1 = 1;
Tracer() << '\n';
Tracer() << "y1 = ";
Tracer() << y1;
Tracer() << '\n';
Tracer() << "Set x1 = 3";
x1 = 3;
Tracer() << '\n';
Tracer() << "y2 = ";
Tracer() << y2;
Tracer() << '\n';
}
};
void Run()
{
ceda::TraceGroup g("IndepEx");
ceda::CSpaceCreator cspace;
ceda::CSpaceTxn txn;
X* p = $new X();
p->Run();
}
}
/*
Generated output:
ReflectedDeps
{
y1 56 64
y2 112 120
myagent 0 168
Calculate the agent. This will cause y1 and y2 to be calculated
[Calc y1] [Calc y2]
Trace cached values of y1 and y2
y1 = 30
y2 = 80
Setting x1 = 5
This eagerly propagates soft-dirtiness through the DG, invalidating the agent
The framework will lazily recalculate y1,y2
[agent a invalidated] [Calc y1] y1 = 25
[Calc y2] y2 = 75
y1 = 25
y2 = 75
}
*/
namespace ReflectedDeps
{
$struct+ X isa ceda::IObject :
model
{
ceda::int32 x1;
ceda::int32 x2;
ceda::int32 x3;
}
{
private:
// Note that even private $deps are reflected!
$dep ceda::int32 y1 =
{
y1 = x1 + x2;
Tracer() << "[Calc y1]";
};
public:
$dep ceda::int32 y2 =
{
y2 = y1 + x3;
Tracer() << "[Calc y2]";
};
$dep void myagent
invalidate
{
Tracer() << "[agent a invalidated]";
}
calc
{
int v = y2;
};
void Run()
{
const ceda::ReflectedClass& rc = ceda::GetReflectedClass<ReflectedDeps::X>();
for (int i=0 ; i < rc.numDepFields ; ++i)
{
const ceda::ReflectedDepField& rdf = rc.depFields[i];
Tracer() << rdf.name << ' ' << rdf.offset << ' ' << rdf.depNodeOffset << '\n';
}
cxAssert(rc.numDepFields == 3); // 3 because there are two $deps and one $agent
const ceda::ReflectedDepField& rdf_y1 = rc.depFields[0];
const ceda::ReflectedDepField& rdf_y2 = rc.depFields[1];
const ceda::ReflectedDepField& rdf_myagent = rc.depFields[2];
ceda::int32& datamember_y1 = *(ceda::int32*) ((ceda::octet_t*)this + rdf_y1.offset);
ceda::int32& datamember_y2 = *(ceda::int32*) ((ceda::octet_t*)this + rdf_y2.offset);
ceda::DGDepNode& depnode_y1 = *(ceda::DGDepNode*) ((ceda::octet_t*)this + rdf_y1.depNodeOffset);
ceda::DGDepNode& depnode_y2 = *(ceda::DGDepNode*) ((ceda::octet_t*)this + rdf_y2.depNodeOffset);
ceda::DGDepNode& depnode_myagent = *(ceda::DGDepNode*) ((ceda::octet_t*)this + rdf_myagent.depNodeOffset);
x1 = 10;
x2 = 20;
x3 = 50;
Tracer() << "\nCalculate the agent. This will cause y1 and y2 to be calculated\n";
{
ceda::TraceIndenter indent(4);
depnode_myagent.ReadBarrier();
}
Tracer() << "\n\nTrace cached values of y1 and y2\n";
{
ceda::TraceIndenter indent(4);
depnode_y1.ReadBarrier(); Tracer() << "y1 = " << datamember_y1 << '\n';
depnode_y2.ReadBarrier(); Tracer() << "y2 = " << datamember_y2 << '\n';
}
Tracer() << "\nSetting x1 = 5\n";
Tracer() << "This eagerly propagates soft-dirtiness through the DG, invalidating the agent\n";
Tracer() << "The framework will lazily recalculate y1,y2\n";
{
ceda::TraceIndenter indent(4);
x1 = 5;
depnode_y1.ReadBarrier(); Tracer() << "y1 = " << datamember_y1 << '\n';
depnode_y2.ReadBarrier(); Tracer() << "y2 = " << datamember_y2 << '\n';
depnode_y1.ReadBarrier(); Tracer() << "y1 = " << datamember_y1 << '\n';
depnode_y2.ReadBarrier(); Tracer() << "y2 = " << datamember_y2 << '\n';
}
}
};
void Run()
{
ceda::TraceGroup g("ReflectedDeps");
ceda::CSpaceCreator cspace;
ceda::CSpaceTxn txn;
X* p = $new X();
p->Run();
}
}
/*
The following example illustrates one of the subtleties of the DGS. In this case there is a
vector<int> member L, and a cache function f(i) which simply caches the ith element of L.
f must be invoked with valid index values to avoid array bounds check failures.
None of the cache functions have '^' in the declaration:
$cache int f(int i) const
$cache int size() const
$cache int sum() const
Therefore all these functions check whether their output has in fact changed before passing on
hard-dirtiness. This behaviour can be seen in the trace. After L is cleared, sum has only
been marked as soft dirty. Therefore it invokes the read barrier on its inputs to see whether
they have really changed. Importantly, this is done in the order in which the calls were
originally made, and also as soon as one of the inputs has been seen to change the remaining
inputs are not tested.
In this case it means that after L has been cleared, size() is called but not f(0), f(1) or
f(2) so there is no array bounds check failure.
Dependency graph:
sum
/ / \ \
/ / \ \
/ / \ \
size f(0) f(1) f(2)
\ \ / /
\ \ / /
\ \ / /
L
Output:
sum()
size()
f(0)
f(1)
f(2)
sum = 6
size() <-------- size() is called by read barrier of sum (because sum is soft dirty)
Note that f(0), f(1), f(2) are not called even though they are also
inputs of sum() at that time.
sum()
sum = 0
*/
namespace DepGraphCheckForChange
{
$struct X isa ceda::IObject :
model
{
xvector<int> L;
}
{
$cache int f(int i) const
{
Tracer() << "f(" << i << ")\n";
return L.read()[i];
}
$cache int size() const
{
Tracer() << "size()\n";
return (int) L.read().size();
}
$cache int sum() const
{
Tracer() << "sum()\n";
int n = size();
int s = 0;
for (int i=0 ; i < n ; ++i)
{
s += f(i);
}
return s;
}
};
void Run()
{
ceda::TraceGroup g("DepGraphCheckForChange");
ceda::CSpaceCreator cspace;
ceda::CSpaceTxn txn;
X* p = $new X();
p->L.push_back(1);
p->L.push_back(2);
p->L.push_back(3);
Tracer() << "sum = " << p->sum() << '\n' << '\n';
p->L.clear();
Tracer() << "sum = " << p->sum() << '\n';
}
}
///////////////////////////////////////////////////////////////////////////////////////////////////
namespace DepGraph
{
void Run()
{
DepGraphEx1::Run();
DepGraphEx2::Run();
DepGraphObjectOnFrame::Run();
CacheFunctions1::Run();
CacheFunctions2::Run();
DepGraphEx3::Run();
DepGraphCycleEx::Run();
DepGraphDisableQuiescenceCheckEx::Run();
DepGraphEx6::Run();
DepGraphEx7::Run();
DepGraphEx8::Run();
// Used to verify an assertion is tripped
//CannotUpdateModelWhenRecalcDependent::Run();
DepGraphCallbackRestrictions::Run();
IndepEx::Run();
ReflectedDeps::Run();
DepGraphCheckForChange::Run();
}
}