sva_engine/
flops.rs

1// Concern: counts what a render costs in operations, per value, off the table's own plan | Non-concern: running any of it (render/) | IO: (&Render) -> Tree, Work
2
3use std::collections::BTreeSet;
4
5use crate::render::Render;
6use crate::render::table::{Kind, Table};
7
8/// `subtree` is what the holder pays for this value; `shared` marks one an earlier row already
9/// paid for, read again at no cost.
10#[derive(Clone, Debug, PartialEq)]
11pub struct Row {
12    pub depth: usize,
13    pub node: String,
14    pub own: u128,
15    pub subtree: u128,
16    pub percent: f64,
17    pub route: &'static str,
18    pub shared: bool,
19}
20
21#[derive(Clone, Debug, PartialEq)]
22pub struct Tree {
23    pub total: u128,
24    pub budget: u128,
25    pub rows: Vec<Row>,
26}
27
28/// What a stream or a render did, counted exactly and alike on every machine: the samples
29/// written, the price, and the waves summed.
30#[derive(Clone, Copy, Debug, Default, PartialEq, Eq)]
31pub struct Work {
32    pub samples: u64,
33    pub priced_flops: u128,
34    pub waves: Option<u128>,
35}
36
37struct Node {
38    at: usize,
39    subtree: u128,
40    own: u128,
41    shared: bool,
42    children: Vec<Node>,
43}
44
45/// A row under this share of the whole folds into its level's `others`, unless it is `shared`.
46const FOLD_PERCENT: u128 = 1;
47
48/// A child this close to its parent restates it, and is skipped where it owns nothing.
49const PASS_THROUGH_PERCENT: u128 = 99;
50
51/// Every value once, however many read it.
52pub fn total(render: &Render) -> u128 {
53    render
54        .table
55        .as_ref()
56        .map_or(0, |table| table.planned.iter().sum())
57}
58
59pub fn tree(render: &Render) -> Tree {
60    tree_at(render, render.root)
61}
62
63pub fn tree_at(render: &Render, node: sva_formula::NodeId) -> Tree {
64    let Some((table, at)) = render
65        .table
66        .as_ref()
67        .and_then(|table| Some((table, table.of(node)?)))
68    else {
69        return Tree {
70            total: 0,
71            budget: render.config.flop_budget,
72            rows: Vec::new(),
73        };
74    };
75    let root = grow(table, at, &mut BTreeSet::new());
76    let total = root.subtree;
77    let mut rows = Vec::new();
78    emit(&root, table, 0, total, &mut rows);
79    Tree {
80        total,
81        budget: render.config.flop_budget,
82        rows,
83    }
84}
85
86/// The root restates the whole, so the refusal names the costliest row under it.
87pub fn dominating(tree: &Tree) -> Option<&Row> {
88    let root = tree.rows.first()?;
89    tree.rows
90        .iter()
91        .skip(1)
92        .max_by_key(|row| row.subtree)
93        .or(Some(root))
94}
95
96fn grow(table: &Table, at: usize, walked: &mut BTreeSet<usize>) -> Node {
97    walked.insert(at);
98    let own = table.planned[at];
99    let mut reads = table.values[at].reads.clone();
100    reads.dedup();
101    let children: Vec<Node> = reads
102        .into_iter()
103        .map(|read| match walked.contains(&read) {
104            true => Node {
105                at: read,
106                subtree: 0,
107                own: 0,
108                shared: true,
109                children: Vec::new(),
110            },
111            false => grow(table, read, walked),
112        })
113        .collect();
114    Node {
115        at,
116        subtree: own + children.iter().map(|c| c.subtree).sum::<u128>(),
117        own,
118        shared: false,
119        children,
120    }
121}
122
123/// The rule its label names, or a program's own where it has none.
124fn route(table: &Table, at: usize) -> &'static str {
125    let named = table.values[at].label.as_ref().map(|l| l.rule().as_str());
126    match &table.values[at].kind {
127        Kind::Rows(_) | Kind::Program(_) if named.is_some() => named.expect("a label"),
128        Kind::Rows(_) => "rows",
129        Kind::Program(_) => "sampled program",
130        Kind::Frames { .. } => "short-time transform",
131        Kind::Istft => "inverse short-time transform",
132        Kind::Spectrum(_) => "inverse spectrum",
133        Kind::Stored { .. } => "stored",
134    }
135}
136
137fn emit(node: &Node, table: &Table, depth: usize, total: u128, rows: &mut Vec<Row>) {
138    rows.push(Row {
139        depth,
140        node: table.values[node.at].name.clone(),
141        own: node.own,
142        subtree: node.subtree,
143        percent: percent(node.subtree, total),
144        route: route(table, node.at),
145        shared: node.shared,
146    });
147    children(node, table, depth + 1, total, rows);
148}
149
150fn children(node: &Node, table: &Table, depth: usize, total: u128, rows: &mut Vec<Row>) {
151    let mut held: Vec<&Node> = node.children.iter().collect();
152    held.sort_by_key(|c| std::cmp::Reverse(c.subtree));
153    let (shown, folded): (Vec<&Node>, Vec<&Node>) = held
154        .into_iter()
155        .partition(|c| c.shared || c.subtree * 100 >= total * FOLD_PERCENT);
156    for child in shown {
157        let restates = child.subtree * 100 >= node.subtree * PASS_THROUGH_PERCENT
158            && child.own * 100 < total * FOLD_PERCENT;
159        match restates && !child.children.is_empty() {
160            true => children(child, table, depth, total, rows),
161            false => emit(child, table, depth, total, rows),
162        }
163    }
164    if !folded.is_empty() {
165        let under: u128 = folded.iter().map(|c| c.subtree).sum();
166        rows.push(Row {
167            depth,
168            node: format!("{} others", folded.len()),
169            own: under,
170            subtree: under,
171            percent: percent(under, total),
172            route: "folded",
173            shared: false,
174        });
175    }
176}
177
178fn percent(part: u128, whole: u128) -> f64 {
179    match whole {
180        0 => 0.0,
181        _ => 100.0 * part as f64 / whole as f64,
182    }
183}
sva_engine/flops.rs

sva_engine/
flops.rs
