The lazy graph and execution

What happens between writing a + b and a kernel running, traced through the code that does it.

Nothing runs when you write it

An operator builds a Node and returns a Tensor handle to it. No memory is allocated, no kernel is dispatched, nothing is computed. Work happens only when something observes a value — to_host(), item(), a backward pass — or when realize() is called explicitly.

That deferral is a performance mechanism, not an API style. Batching lets many operations share one GPU submission, and on the development hardware a submission costs about 105 µs against 9 µs for a dispatch. Reducing submissions is worth far more than making any single kernel faster.

What a Node holds

A Node is immutable once constructed, with exactly one exception: its realisation state. That exception is two separate fields for two separate events — storage, filled in when the node is bound, and a kFlagComputed bit set when it has been evaluated.

Immutability is not a stylistic preference. It is what makes three things sound:

two Tensors may share a node, so a mutation would be action at a distance;
an optimisation pass may assume a node never changes under it, and can therefore rewrite by building new nodes rather than patching old ones;
lowering to an execution graph is a pure function of the graph, and hence cacheable.

Pass results consequently live in side-tables keyed by position in the topological order, never as new mutable fields.

Why sources are shared_ptr, not raw pointers

The architecture sketch called for std::array<Node*, 4> with nodes arena-allocated, mirroring ggml — where a context owns every node and raw pointers are safe because the context outlives them all.

vkML uses shared_ptr instead, because it has no equivalent arena. Graphs here are built incrementally from Python, node by node, with no natural scope that owns them: a Python-held Tensor must keep its whole producing subgraph alive on its own. Raw pointers would need either an arena tied to some lifetime — there is nothing to tie it to — or manual refcounting, which is what shared_ptr already is.

This cannot create reference cycles: the DAG is built strictly bottom-up, so a node's sources always predate it and can never point back.

ⓘ Note

The cost was measured rather than assumed: ~410 ns/node to build and ~460 ns/node to traverse, against ~1000 ns of actual compute for a modest element-wise operation — under 1% of step time at current graph sizes. An arena is 20–64× faster on both counts but cannot express Python's unpredictable object lifetimes without reintroducing refcounting. The recorded resolution is to lower into a flat arena-backed execution graph later, where planning and execution get the locality and this layer keeps its safety.

The destructor is iterative, and has to be

Default destruction would recurse: destroying a node releases its source shared_ptrs, which destroys those nodes, which release theirs. On a deep graph that is a stack overflow — and a deep graph is not hypothetical, since an unrolled RNN over a long sequence is a chain of order 10⁵ nodes.

Node's destructor therefore tears the source chain down with an explicit worklist. There is a deep-chain case in tests/cpp/test_graph.cpp that segfaults without it. It costs nothing for leaves, because the worklist never allocates unless there is actually a source to release.

Views keep two edges, and collapsing the wrong one is a silent bug

A view node carries two references to what it aliases:

Field	Points at	Why
`view_src`	the root storage owner	Collapsed through chains, so binding is one hop.
`src[0]`	the immediate base	Scheduling and autograd both need the real chain.

Collapsing src[0] as well is a bug forward execution cannot see. The view's own Shape already encodes the whole transformation, so values come out right. Backward then breaks, because a gradient rule reads src[0]->shape to know what shape to produce a gradient in — for W.transpose().broadcast_to(...) it would see W's (out, in) instead of the transposed (in, out) and emit a correctly-valued but transposed gradient. That is exactly how it was found, through a linear-layer forward-and-backward test.

What realize() does, step by step

Traced through src/dispatch/executor.cpp:

Topological order. Roots are walked to a flat schedule. An already-realised node is treated as a leaf and not re-emitted, so nothing runs twice.
One device per graph. Every node must agree; a graph spanning devices raises DeviceError naming both.
Support check, per node. If the backend cannot evaluate an operator, the error says so and names the remedy.
Coverage recording, when enabled.
Bind storage. A view takes its base's storage plus an offset — the topological order guarantees the base was bound first. Anything computed gets a fresh allocation, and is asserted contiguous.
One compute() call with the whole schedule. This is where batching pays: the backend sees the entire graph, not one node at a time.
Mark computed, after compute() returns — the only place that bit is set.

⚠ Warning

There is no automatic fallback. When a backend cannot evaluate an operator, vkML will not split the graph to run it elsewhere. Doing so moves data through host memory at every split — measured at roughly three times the cost of the arithmetic it carries — and would do it silently. The error names the explicit remedy instead:

vkml.tensor(t.numpy(), device=vkml.cpu)

Bound is not the same as computed

These are two separate events with two separate fields, and the split is deliberate. A node is bound when it has memory and computed when that memory has been written. Binding happens during scheduling; the computed bit is set only after compute() returns.

Merging them would make a node that has been allocated but not yet written indistinguishable from one holding a value — which is precisely the state every node is in between step 5 and step 7 above.

Eager mode

set_eager(True), or VKML_EAGER=1, realizes after every operation. A failure then surfaces at the operation that caused it rather than at the next realize — which is the point. It is a debugging aid and it is slower, because every operation becomes its own submission and the batching above is given up entirely.

The flag is an atomic<bool> read with relaxed ordering, initialised once from the environment at first use.