use std::collections::{HashMap, VecDeque};
use thiserror::Error;
#[derive(Debug, Error)]
pub enum RenderGraphError {
#[error("Pass '{0}' already exists in the graph")]
DuplicatePass(String),
#[error("Resource '{0}' already exists")]
DuplicateResource(String),
#[error("Pass '{0}' not found")]
PassNotFound(String),
#[error("Resource '{0}' not found")]
ResourceNotFound(String),
#[error("Cycle detected in render graph involving pass '{0}'")]
CycleDetected(String),
#[error("Pass '{dep}' depends on '{pass}' but '{pass}' does not produce resource '{res}'")]
ResourceDependencyMismatch {
pass: String,
dep: String,
res: String,
},
#[error("Resource '{0}' declared as both read and write in pass '{1}'")]
ReadWriteConflict(String, String),
#[error("Resource '{res}' is written by both pass '{first}' and pass '{second}'")]
DuplicateWrite {
res: String,
first: String,
second: String,
},
}
#[derive(Debug, Clone, PartialEq, Eq, Hash)]
pub enum ResourceFormat {
Rgba8,
Rgba16f,
Rgba32f,
Depth32f,
R32f,
Rg16f,
}
impl ResourceFormat {
pub fn bytes_per_pixel(&self) -> usize {
match self {
ResourceFormat::Rgba8 => 4,
ResourceFormat::Rgba16f => 8,
ResourceFormat::Rgba32f => 16,
ResourceFormat::Depth32f => 4,
ResourceFormat::R32f => 4,
ResourceFormat::Rg16f => 4,
}
}
}
#[derive(Debug, Clone)]
pub struct ResourceDesc {
pub name: String,
pub format: ResourceFormat,
pub width: u32,
pub height: u32,
}
impl ResourceDesc {
pub fn new(name: impl Into<String>, format: ResourceFormat, width: u32, height: u32) -> Self {
Self {
name: name.into(),
format,
width,
height,
}
}
pub fn size_bytes(&self) -> usize {
self.width as usize * self.height as usize * self.format.bytes_per_pixel()
}
}
#[derive(Debug, Clone, PartialEq, Eq, Hash)]
pub struct ResourceId(String);
impl ResourceId {
pub fn new(name: impl Into<String>) -> Self {
Self(name.into())
}
pub fn name(&self) -> &str {
&self.0
}
}
#[derive(Debug, Clone, PartialEq)]
pub enum PassType {
Compute,
Rasterize,
Transfer,
Present,
}
#[derive(Debug, Clone)]
pub struct PassDesc {
pub name: String,
pub pass_type: PassType,
pub reads: Vec<ResourceId>,
pub writes: Vec<ResourceId>,
pub estimated_gpu_us: u64,
}
impl PassDesc {
pub fn new(name: impl Into<String>, pass_type: PassType) -> Self {
Self {
name: name.into(),
pass_type,
reads: Vec::new(),
writes: Vec::new(),
estimated_gpu_us: 0,
}
}
pub fn read(mut self, resource: impl Into<String>) -> Self {
self.reads.push(ResourceId::new(resource));
self
}
pub fn write(mut self, resource: impl Into<String>) -> Self {
self.writes.push(ResourceId::new(resource));
self
}
pub fn with_gpu_time(mut self, us: u64) -> Self {
self.estimated_gpu_us = us;
self
}
}
#[derive(Debug, Clone)]
pub struct ResourceLifetime {
pub resource_id: ResourceId,
pub written_by: String,
pub read_by: Vec<String>,
pub can_alias: bool,
}
#[derive(Debug)]
pub struct CompiledRenderGraph {
pub execution_order: Vec<String>,
pub resource_lifetimes: Vec<ResourceLifetime>,
pub peak_memory_bytes: usize,
pub num_passes: usize,
}
impl CompiledRenderGraph {
pub fn parallel_passes(&self, graph: &RenderGraph) -> Vec<Vec<String>> {
let order_index: HashMap<&str, usize> = self
.execution_order
.iter()
.enumerate()
.map(|(i, name)| (name.as_str(), i))
.collect();
let mut resource_writer: HashMap<&str, &str> = HashMap::new();
for pass in &graph.passes {
for w in &pass.writes {
resource_writer.insert(w.name(), pass.name.as_str());
}
}
let mut level: HashMap<&str, usize> = HashMap::new();
for pass_name in &self.execution_order {
let pass = match graph.pass(pass_name) {
Some(p) => p,
None => {
level.insert(pass_name.as_str(), 0);
continue;
}
};
let max_pred_level = pass
.reads
.iter()
.filter_map(|r| resource_writer.get(r.name()))
.filter_map(|writer| level.get(writer))
.copied()
.max()
.unwrap_or(0);
let this_level = if pass
.reads
.iter()
.any(|r| resource_writer.contains_key(r.name()))
{
max_pred_level + 1
} else {
0
};
level.insert(pass_name.as_str(), this_level);
}
let max_level = level.values().copied().max().unwrap_or(0);
let mut batches: Vec<Vec<String>> = vec![Vec::new(); max_level + 1];
for pass_name in &self.execution_order {
let lvl = level.get(pass_name.as_str()).copied().unwrap_or(0);
batches[lvl].push(pass_name.clone());
}
batches.retain(|b| !b.is_empty());
for batch in &mut batches {
batch.sort_by_key(|name| {
order_index
.get(name.as_str())
.copied()
.unwrap_or(usize::MAX)
});
}
batches
}
pub fn format_summary(&self) -> String {
let mut out = String::new();
out.push_str("=== Compiled Render Graph ===\n");
out.push_str(&format!("Passes: {}\n", self.num_passes));
out.push_str(&format!(
"Peak memory: {} bytes ({:.2} MiB)\n",
self.peak_memory_bytes,
self.peak_memory_bytes as f64 / (1024.0 * 1024.0)
));
out.push_str("\nExecution order:\n");
for (i, name) in self.execution_order.iter().enumerate() {
out.push_str(&format!(" {:2}. {}\n", i + 1, name));
}
out.push_str("\nResource lifetimes:\n");
for lt in &self.resource_lifetimes {
let writer = if lt.written_by.is_empty() {
"<external>".to_string()
} else {
lt.written_by.clone()
};
out.push_str(&format!(
" {} | writer: {} | readers: [{}] | alias: {}\n",
lt.resource_id.name(),
writer,
lt.read_by.join(", "),
lt.can_alias
));
}
out
}
pub fn passes_reading(&self, resource: &ResourceId) -> Vec<&str> {
self.resource_lifetimes
.iter()
.find(|lt| <.resource_id == resource)
.map(|lt| lt.read_by.iter().map(|s| s.as_str()).collect())
.unwrap_or_default()
}
}
pub struct RenderGraph {
passes: Vec<PassDesc>,
resources: Vec<ResourceDesc>,
}
impl Default for RenderGraph {
fn default() -> Self {
Self::new()
}
}
impl RenderGraph {
pub fn new() -> Self {
Self {
passes: Vec::new(),
resources: Vec::new(),
}
}
pub fn add_resource(&mut self, desc: ResourceDesc) -> Result<ResourceId, RenderGraphError> {
if self.resources.iter().any(|r| r.name == desc.name) {
return Err(RenderGraphError::DuplicateResource(desc.name));
}
let id = ResourceId::new(&desc.name);
self.resources.push(desc);
Ok(id)
}
pub fn resource(&self, id: &ResourceId) -> Option<&ResourceDesc> {
self.resources.iter().find(|r| r.name == id.0)
}
pub fn add_pass(&mut self, desc: PassDesc) -> Result<(), RenderGraphError> {
if self.passes.iter().any(|p| p.name == desc.name) {
return Err(RenderGraphError::DuplicatePass(desc.name));
}
self.passes.push(desc);
Ok(())
}
pub fn pass(&self, name: &str) -> Option<&PassDesc> {
self.passes.iter().find(|p| p.name == name)
}
pub fn estimated_gpu_time_us(&self) -> u64 {
self.passes.iter().map(|p| p.estimated_gpu_us).sum()
}
pub fn num_passes(&self) -> usize {
self.passes.len()
}
pub fn num_resources(&self) -> usize {
self.resources.len()
}
pub fn compile(&self) -> Result<CompiledRenderGraph, RenderGraphError> {
let n = self.passes.len();
for pass in &self.passes {
for w in &pass.writes {
if pass.reads.contains(w) {
return Err(RenderGraphError::ReadWriteConflict(
w.name().to_owned(),
pass.name.clone(),
));
}
}
}
let mut resource_writer: HashMap<&str, usize> = HashMap::new();
for (idx, pass) in self.passes.iter().enumerate() {
for w in &pass.writes {
if let Some(&first_idx) = resource_writer.get(w.name()) {
return Err(RenderGraphError::DuplicateWrite {
res: w.name().to_owned(),
first: self.passes[first_idx].name.clone(),
second: pass.name.clone(),
});
}
resource_writer.insert(w.name(), idx);
}
}
let mut adj: Vec<Vec<usize>> = vec![Vec::new(); n];
let mut in_degree: Vec<usize> = vec![0; n];
for (b_idx, pass_b) in self.passes.iter().enumerate() {
for r in &pass_b.reads {
if let Some(&a_idx) = resource_writer.get(r.name()) {
if a_idx == b_idx {
continue;
}
if !adj[a_idx].contains(&b_idx) {
adj[a_idx].push(b_idx);
in_degree[b_idx] += 1;
}
}
}
}
let mut queue: VecDeque<usize> = VecDeque::new();
for (i, °) in in_degree.iter().enumerate().take(n) {
if deg == 0 {
queue.push_back(i);
}
}
let mut execution_order: Vec<String> = Vec::with_capacity(n);
while let Some(node) = queue.pop_front() {
execution_order.push(self.passes[node].name.clone());
for &succ in &adj[node] {
in_degree[succ] -= 1;
if in_degree[succ] == 0 {
queue.push_back(succ);
}
}
}
if execution_order.len() < n {
let sorted_set: std::collections::HashSet<&str> =
execution_order.iter().map(|s| s.as_str()).collect();
let cycle_pass = self
.passes
.iter()
.find(|p| !sorted_set.contains(p.name.as_str()))
.map(|p| p.name.clone())
.unwrap_or_else(|| "unknown".to_string());
return Err(RenderGraphError::CycleDetected(cycle_pass));
}
let exec_pos: HashMap<&str, usize> = execution_order
.iter()
.enumerate()
.map(|(i, name)| (name.as_str(), i))
.collect();
let mut resource_lifetimes: Vec<ResourceLifetime> = Vec::new();
for res in &self.resources {
let writer_idx = resource_writer.get(res.name.as_str()).copied();
let written_by = writer_idx
.map(|i| self.passes[i].name.clone())
.unwrap_or_default();
let mut read_by: Vec<String> = Vec::new();
for pass_name in &execution_order {
let pass = match self.pass(pass_name) {
Some(p) => p,
None => continue,
};
if pass.reads.iter().any(|r| r.name() == res.name) {
read_by.push(pass_name.clone());
}
}
let last_reader_pos = read_by
.iter()
.filter_map(|name| exec_pos.get(name.as_str()).copied())
.max();
let can_alias = match (writer_idx, last_reader_pos) {
(Some(_w_idx), Some(last_pos)) => {
let writer_pos = exec_pos
.get(written_by.as_str())
.copied()
.unwrap_or(usize::MAX);
writer_pos <= last_pos
}
_ => true,
};
resource_lifetimes.push(ResourceLifetime {
resource_id: ResourceId::new(&res.name),
written_by,
read_by,
can_alias,
});
}
let peak_memory_bytes: usize = self.resources.iter().map(|r| r.size_bytes()).sum();
Ok(CompiledRenderGraph {
execution_order,
resource_lifetimes,
peak_memory_bytes,
num_passes: n,
})
}
}
pub fn build_standard_3dgs_graph(
width: u32,
height: u32,
num_gaussians: u32,
) -> Result<RenderGraph, RenderGraphError> {
let mut g = RenderGraph::new();
let n = num_gaussians.max(1);
g.add_resource(ResourceDesc::new("tile_counts", ResourceFormat::R32f, n, 1))?;
g.add_resource(ResourceDesc::new("keys", ResourceFormat::R32f, n, 1))?;
g.add_resource(ResourceDesc::new("values", ResourceFormat::R32f, n, 1))?;
g.add_resource(ResourceDesc::new("sorted_keys", ResourceFormat::R32f, n, 1))?;
g.add_resource(ResourceDesc::new(
"sorted_values",
ResourceFormat::R32f,
n,
1,
))?;
g.add_resource(ResourceDesc::new(
"tile_ranges",
ResourceFormat::Rg16f,
width,
height,
))?;
g.add_resource(ResourceDesc::new(
"color",
ResourceFormat::Rgba8,
width,
height,
))?;
g.add_resource(ResourceDesc::new(
"depth",
ResourceFormat::Depth32f,
width,
height,
))?;
g.add_resource(ResourceDesc::new(
"transmittance",
ResourceFormat::R32f,
width,
height,
))?;
g.add_resource(ResourceDesc::new(
"grad_positions",
ResourceFormat::Rgba32f,
n,
1,
))?;
g.add_resource(ResourceDesc::new(
"grad_scales",
ResourceFormat::Rgba32f,
n,
1,
))?;
g.add_resource(ResourceDesc::new(
"grad_colors",
ResourceFormat::Rgba32f,
n,
1,
))?;
g.add_pass(
PassDesc::new("preprocess", PassType::Compute)
.write("tile_counts")
.write("keys")
.write("values")
.with_gpu_time(500),
)?;
g.add_pass(
PassDesc::new("sort", PassType::Compute)
.read("tile_counts")
.read("keys")
.read("values")
.write("sorted_keys")
.write("sorted_values")
.write("tile_ranges")
.with_gpu_time(2000),
)?;
g.add_pass(
PassDesc::new("rasterize_fwd", PassType::Rasterize)
.read("sorted_keys")
.read("sorted_values")
.read("tile_ranges")
.write("color")
.write("depth")
.write("transmittance")
.with_gpu_time(3000),
)?;
g.add_pass(
PassDesc::new("rasterize_bwd", PassType::Compute)
.read("color")
.read("depth")
.read("transmittance")
.write("grad_positions")
.write("grad_scales")
.write("grad_colors")
.with_gpu_time(5000),
)?;
g.add_pass(
PassDesc::new("output", PassType::Present)
.read("color")
.with_gpu_time(100),
)?;
Ok(g)
}
#[cfg(test)]
#[allow(clippy::unwrap_used)]
mod tests {
use super::*;
fn simple_graph() -> RenderGraph {
let mut g = RenderGraph::new();
g.add_resource(ResourceDesc::new("buf_a", ResourceFormat::Rgba8, 512, 512))
.unwrap();
g.add_resource(ResourceDesc::new("buf_b", ResourceFormat::Rgba8, 512, 512))
.unwrap();
g.add_pass(PassDesc::new("pass_a", PassType::Compute).write("buf_a"))
.unwrap();
g.add_pass(
PassDesc::new("pass_b", PassType::Compute)
.read("buf_a")
.write("buf_b"),
)
.unwrap();
g
}
#[test]
fn test_new_starts_empty() {
let g = RenderGraph::new();
assert_eq!(g.num_passes(), 0);
assert_eq!(g.num_resources(), 0);
}
#[test]
fn test_add_resource_returns_id() {
let mut g = RenderGraph::new();
let id = g
.add_resource(ResourceDesc::new("buf", ResourceFormat::Rgba8, 64, 64))
.unwrap();
assert_eq!(id.name(), "buf");
assert_eq!(g.num_resources(), 1);
}
#[test]
fn test_add_resource_duplicate() {
let mut g = RenderGraph::new();
g.add_resource(ResourceDesc::new("buf", ResourceFormat::Rgba8, 64, 64))
.unwrap();
let err = g
.add_resource(ResourceDesc::new("buf", ResourceFormat::Rgba8, 64, 64))
.unwrap_err();
assert!(matches!(err, RenderGraphError::DuplicateResource(_)));
}
#[test]
fn test_add_pass() {
let mut g = RenderGraph::new();
g.add_pass(PassDesc::new("my_pass", PassType::Compute))
.unwrap();
assert_eq!(g.num_passes(), 1);
}
#[test]
fn test_add_pass_duplicate() {
let mut g = RenderGraph::new();
g.add_pass(PassDesc::new("my_pass", PassType::Compute))
.unwrap();
let err = g
.add_pass(PassDesc::new("my_pass", PassType::Compute))
.unwrap_err();
assert!(matches!(err, RenderGraphError::DuplicatePass(_)));
}
#[test]
fn test_compile_simple_chain() {
let g = simple_graph();
let compiled = g.compile().unwrap();
assert_eq!(compiled.execution_order, vec!["pass_a", "pass_b"]);
}
#[test]
fn test_compile_independent_passes() {
let mut g = RenderGraph::new();
g.add_resource(ResourceDesc::new("x", ResourceFormat::R32f, 8, 8))
.unwrap();
g.add_resource(ResourceDesc::new("y", ResourceFormat::R32f, 8, 8))
.unwrap();
g.add_pass(PassDesc::new("pa", PassType::Compute).write("x"))
.unwrap();
g.add_pass(PassDesc::new("pb", PassType::Compute).write("y"))
.unwrap();
let compiled = g.compile().unwrap();
let set: std::collections::HashSet<&str> = compiled
.execution_order
.iter()
.map(|s| s.as_str())
.collect();
assert!(set.contains("pa"));
assert!(set.contains("pb"));
assert_eq!(compiled.num_passes, 2);
}
#[test]
fn test_compile_cycle_detected() {
let mut g = RenderGraph::new();
g.add_resource(ResourceDesc::new("x", ResourceFormat::R32f, 8, 8))
.unwrap();
g.add_resource(ResourceDesc::new("y", ResourceFormat::R32f, 8, 8))
.unwrap();
g.add_pass(PassDesc::new("pa", PassType::Compute).write("x").read("y"))
.unwrap();
g.add_pass(PassDesc::new("pb", PassType::Compute).write("y").read("x"))
.unwrap();
let err = g.compile().unwrap_err();
assert!(matches!(err, RenderGraphError::CycleDetected(_)));
}
#[test]
fn test_compile_empty_graph() {
let g = RenderGraph::new();
let compiled = g.compile().unwrap();
assert!(compiled.execution_order.is_empty());
assert_eq!(compiled.num_passes, 0);
assert_eq!(compiled.peak_memory_bytes, 0);
}
#[test]
fn test_resource_desc_size_bytes() {
let desc = ResourceDesc::new("t", ResourceFormat::Rgba8, 512, 512);
assert_eq!(desc.size_bytes(), 1_048_576);
}
#[test]
fn test_bytes_per_pixel() {
assert_eq!(ResourceFormat::Rgba8.bytes_per_pixel(), 4);
assert_eq!(ResourceFormat::Rgba16f.bytes_per_pixel(), 8);
assert_eq!(ResourceFormat::Rgba32f.bytes_per_pixel(), 16);
assert_eq!(ResourceFormat::Depth32f.bytes_per_pixel(), 4);
assert_eq!(ResourceFormat::R32f.bytes_per_pixel(), 4);
assert_eq!(ResourceFormat::Rg16f.bytes_per_pixel(), 4);
}
#[test]
fn test_estimated_gpu_time_us() {
let mut g = RenderGraph::new();
g.add_pass(PassDesc::new("a", PassType::Compute).with_gpu_time(1000))
.unwrap();
g.add_pass(PassDesc::new("b", PassType::Compute).with_gpu_time(2500))
.unwrap();
assert_eq!(g.estimated_gpu_time_us(), 3500);
}
#[test]
fn test_pass_desc_builder() {
let p = PassDesc::new("p", PassType::Rasterize)
.read("tex_in")
.write("tex_out")
.with_gpu_time(42);
assert_eq!(p.reads.len(), 1);
assert_eq!(p.reads[0].name(), "tex_in");
assert_eq!(p.writes.len(), 1);
assert_eq!(p.writes[0].name(), "tex_out");
assert_eq!(p.estimated_gpu_us, 42);
}
#[test]
fn test_format_summary_non_empty() {
let g = simple_graph();
let compiled = g.compile().unwrap();
let summary = compiled.format_summary();
assert!(!summary.is_empty());
assert!(summary.contains("pass_a"));
assert!(summary.contains("pass_b"));
}
#[test]
fn test_parallel_passes_single_chain() {
let g = simple_graph();
let compiled = g.compile().unwrap();
let batches = compiled.parallel_passes(&g);
assert_eq!(batches.len(), 2);
assert_eq!(batches[0], vec!["pass_a"]);
assert_eq!(batches[1], vec!["pass_b"]);
}
#[test]
fn test_parallel_passes_independent_same_batch() {
let mut g = RenderGraph::new();
g.add_resource(ResourceDesc::new("x", ResourceFormat::R32f, 8, 8))
.unwrap();
g.add_resource(ResourceDesc::new("y", ResourceFormat::R32f, 8, 8))
.unwrap();
g.add_pass(PassDesc::new("pa", PassType::Compute).write("x"))
.unwrap();
g.add_pass(PassDesc::new("pb", PassType::Compute).write("y"))
.unwrap();
let compiled = g.compile().unwrap();
let batches = compiled.parallel_passes(&g);
assert_eq!(batches.len(), 1);
assert_eq!(batches[0].len(), 2);
}
#[test]
fn test_standard_3dgs_graph_compiles() {
let g = build_standard_3dgs_graph(1920, 1080, 100_000).expect("graph construction");
let result = g.compile();
assert!(result.is_ok(), "compile failed: {:?}", result.err());
}
#[test]
fn test_standard_3dgs_graph_five_passes() {
let g = build_standard_3dgs_graph(1920, 1080, 100_000).expect("graph construction");
assert_eq!(g.num_passes(), 5);
}
#[test]
fn test_standard_3dgs_graph_per_gaussian_sizing() {
let g = build_standard_3dgs_graph(1920, 1080, 12_345).expect("graph construction");
let keys = g
.resource(&ResourceId::new("keys"))
.expect("keys resource must exist");
assert_eq!(
keys.width, 12_345,
"per-Gaussian buffers must be sized by num_gaussians"
);
assert_eq!(keys.height, 1);
let color = g
.resource(&ResourceId::new("color"))
.expect("color resource must exist");
assert_eq!(
color.width, 1920,
"per-pixel buffers must still be sized by width/height"
);
assert_eq!(color.height, 1080);
}
#[test]
fn test_compile_rejects_duplicate_write() {
let mut g = RenderGraph::new();
g.add_resource(ResourceDesc::new("shared", ResourceFormat::Rgba8, 64, 64))
.unwrap();
g.add_pass(PassDesc::new("first", PassType::Compute).write("shared"))
.unwrap();
g.add_pass(PassDesc::new("second", PassType::Compute).write("shared"))
.unwrap();
let err = g.compile().unwrap_err();
match err {
RenderGraphError::DuplicateWrite { res, first, second } => {
assert_eq!(res, "shared");
assert_eq!(first, "first");
assert_eq!(second, "second");
}
other => panic!("expected DuplicateWrite, got {other:?}"),
}
}
#[test]
fn test_passes_reading() {
let g = simple_graph();
let compiled = g.compile().unwrap();
let readers = compiled.passes_reading(&ResourceId::new("buf_a"));
assert_eq!(readers, vec!["pass_b"]);
}
#[test]
fn test_num_passes_and_resources() {
let g = simple_graph();
assert_eq!(g.num_passes(), 2);
assert_eq!(g.num_resources(), 2);
}
#[test]
fn test_resource_and_pass_lookups() {
let g = simple_graph();
let id = ResourceId::new("buf_a");
let res = g.resource(&id);
assert!(res.is_some());
assert_eq!(res.unwrap().name, "buf_a");
let pass = g.pass("pass_a");
assert!(pass.is_some());
assert_eq!(pass.unwrap().name, "pass_a");
assert!(g.resource(&ResourceId::new("nonexistent")).is_none());
assert!(g.pass("nonexistent").is_none());
}
#[test]
fn test_resource_id_equality() {
let a = ResourceId::new("buf");
let b = ResourceId::new("buf");
let c = ResourceId::new("other");
assert_eq!(a, b);
assert_ne!(a, c);
}
#[test]
fn test_peak_memory_bytes() {
let g = simple_graph();
let compiled = g.compile().unwrap();
assert_eq!(compiled.peak_memory_bytes, 2 * 512 * 512 * 4);
}
#[test]
fn test_read_write_conflict() {
let mut g = RenderGraph::new();
g.add_resource(ResourceDesc::new("buf", ResourceFormat::R32f, 8, 8))
.unwrap();
g.add_pass(
PassDesc::new("bad_pass", PassType::Compute)
.read("buf")
.write("buf"),
)
.unwrap();
let err = g.compile().unwrap_err();
assert!(matches!(err, RenderGraphError::ReadWriteConflict(_, _)));
}
#[test]
fn test_standard_3dgs_execution_order() {
let g = build_standard_3dgs_graph(800, 600, 50_000).expect("graph construction");
let compiled = g.compile().unwrap();
let order = &compiled.execution_order;
let pos = |name: &str| order.iter().position(|n| n == name).unwrap();
assert!(pos("preprocess") < pos("sort"));
assert!(pos("sort") < pos("rasterize_fwd"));
assert!(pos("rasterize_fwd") < pos("rasterize_bwd"));
assert!(pos("rasterize_fwd") < pos("output"));
}
}