by RossBencina | 2026-03-09 00:02:58+00:00
When I first started working with dataflow computation I was fortunate to have a computer scientist point me in the direction of an introductory compiler textbook.

It's worth considering that the dataflow graph (as an abstract mathematical graph), the computation graph (the partial order of function execution required to compute the data), the traversal strategy, the runtime representation of the graph, the runtime data structure for the graph, and the runtime data structures for efficient reactive update are all separate but related aspects.

For instance, push and pull are both directed graphs. They have the same connectivity, but the direction of the arrows is reversed. You can only efficiently traverse edges in the direction that you represent. A dataflow graph has edges pointing from sources to sinks, a data dependency graph has edges pointing from sinks to sources. [Side note: if a computation can produce multiple results the data dependency graph and the computation dependency graph are not exactly the same thing and you need to be clear on the distinction, but I am assuming here single-output nodes]. In a dataflow graph you want to evaluate the changed nodes prior to evaluating the downstream nodes that depend on them. As TFA states, this necessitates a postorder (children first) traversal of the data dependency graph, starting at all terminal sinks, and terminating at sources or already visited nodes. You can use a sense-reversing "visited" flag on each node to avoid a reset pass. As noted in the article this traversal need only be performed when the graph topology changes. But for stable traversal order the topological sort can be cached in an array. Needless to say that arrays are much faster to iterate over than any kind of pointer chasing. [Witness the rise of Entity-Component systems over OO models]. I suspect that there is a cut-over point where it is more efficient to iterate the entire array (perhaps with memoized results, or JIT compilation) than to perform a more surgical "update only what is downstream of the changes" approach. Another approach is to assign all nodes a contiguous integer id, and maintain a dirty node bitmask where bit-indices correspond to node ids. In addition, each source has a bitmask that is 1 for all downstream dependent nodes. When a source changes, bitwise-or source.downstream_dependents bitmask with the global dirty_nodes bitmask. To evaluate (not necessarily immediately), iterate in topological order processing only the dirty nodes. In any case, the point I'm trying to make is that the data structure that is best for building or manipulating the graph could very well be different from the data structure that is best for computing the desired results. There will be trade-offs to be made. For this reason alone it's best to keep the graph-theoretic properties and the implementation data structures separate in your head.

In my view the interesting requirements raised by the article are (1) lazy evaluation (e.g. of expensive or conditionally required data). This might be where control flow graphs of basic blocks enter the story. and, (2) dynamic reconfiguration during node evaluation. Some questions I'd be asking about dynamic reconfiguration are: what happens if you delete a node that has yet to be evaluated? will new subgraphs "patched in" to the existing graph (how exactly?), or are they always disconnected components that can be evaluated after the current graph traversal completes?