BPVM Snack Pack #13 - The DAG Scheduler: Ordering Chaos
Your Blueprint nodes can connect in complex ways, but they must execute in order. The DAG Scheduler turns your web of nodes into a linear execution list.
The content in this post is based on Unreal Engine 5.6.0
BPVM Snack Pack - Quick Blueprint knowledge drops! Part of the Blueprint to Bytecode series.
The Execution Order Problem
Look at your Blueprint graph. Nodes connect every which way. But the CPU can only do one thing at a time.
Who goes first? Who goes next? That’s the scheduler’s job!
What’s a DAG?
DAG = Directed Acyclic Graph
- Directed: Arrows point one way (data flows forward)
- Acyclic: No loops (can’t go in circles)
- Graph: Nodes connected by edges
Your Blueprint IS a DAG (if it compiles)!
The Topological Sort
The scheduler uses topological sorting to order nodes:
1
2
3
4
5
6
7
8
9
10
11
12
13
14
void CreateExecutionSchedule(Nodes, LinearExecutionList)
{
// Topological sort algorithm
while (NodesLeft) {
// Find node with no dependencies
Node = FindNodeWithNoDependencies();
// Add to execution list
LinearExecutionList.Add(Node);
// Remove from graph
RemoveNode(Node);
}
}
It’s like getting dressed - socks before shoes, shirt before tie!
Visual Example
Your Graph:
1
2
3
A → B → D
↓
C → E
After Scheduling:
1
Linear Order: A → B → C → D → E
The scheduler found the only valid order where dependencies are respected!
Detecting Cycles
What if you accidentally create a loop?
1
2
3
4
5
6
7
8
// Circular dependency!
A → B → C → A
// Scheduler detects it:
if (NodesLeft && NoDependencyFreeNodes) {
Error("Cycle detected in graph!");
// Shows you exactly which nodes form the cycle
}
The scheduler prevents infinite loops before they happen!
Data Dependencies
The scheduler tracks two types of connections:
1
2
3
4
5
// Execution pins (white arrows)
BeginPlay → PrintString → SetVariable
// Data pins (colored wires)
GetVariable → Add → SetVariable
Both create dependencies that affect ordering!
Pure Nodes Are Special
Pure nodes (no execution pins) get scheduled by demand:
1
2
3
4
5
6
7
// Your graph
[Exec] → PrintString(GetRandomFloat() + 10)
// Scheduled order
1. GetRandomFloat() // Computed first (needed by Print)
2. Add(result, 10) // Then add
3. PrintString() // Finally print
Pure nodes run just in time when their output is needed!
The Scheduling Algorithm
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
LinearExecutionList = [];
DependencyCount = {};
// Count dependencies for each node
for (Node in Nodes) {
DependencyCount[Node] = CountIncomingEdges(Node);
}
// Process nodes with no dependencies
Queue = GetNodesWithZeroDependencies();
while (!Queue.Empty()) {
Node = Queue.Pop();
LinearExecutionList.Add(Node);
// Reduce dependency count for connected nodes
for (ConnectedNode in Node.Outputs) {
DependencyCount[ConnectedNode]--;
if (DependencyCount[ConnectedNode] == 0) {
Queue.Push(ConnectedNode);
}
}
}
Real-World Scheduling
Complex Graph:
1
2
3
4
BeginPlay → GetActor → IsValid → Branch
↓ ↓
GetLocation [True] SetLocation
[False] PrintError
Scheduled Order:
- BeginPlay
- GetActor
- IsValid
- Branch
- GetLocation (even if not used)
- SetLocation OR PrintError
Everything ready before it’s needed!
Why Linear Matters
The VM can’t handle branches well:
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
// Bad for VM (branching)
if (Condition) {
Path A nodes...
} else {
Path B nodes...
}
// Good for VM (linear with jumps)
CheckCondition
JumpIfFalse Label_B
Path A nodes...
Jump Label_End
Label_B:
Path B nodes...
Label_End:
Linear execution with jumps is faster than true branching!
Scheduling Errors
When scheduling fails:
1
2
3
4
// Error types
"Cycle detected" → You have A→B→A loop
"Orphaned nodes" → Nodes not connected to anything
"Multiple entry points" → Two BeginPlays?
The scheduler catches these at compile time, not runtime!
Quick Takeaway
- The DAG Scheduler turns your web of nodes into a line of operations
- Uses topological sort to respect all dependencies
- Detects cycles before they cause infinite loops
- Pure nodes are scheduled just-in-time
- Creates a LinearExecutionList for the VM
- Makes branching graphs linear with jumps
From Chaos to Order
Your beautiful, sprawling node graph might look like organized chaos, but the DAG Scheduler transforms it into a perfectly ordered list that the VM can execute step-by-step. It’s the unsung hero that makes visual scripting actually work!
Want More Details?
For the complete scheduling algorithm:
Next: How the backend turns statements into bytecode!
🍿 BPVM Snack Pack Series
- ← #12: Statements 101
- #13: The DAG Scheduler ← You are here
- #14: Backend Magic →