Oregami
Repositories/oxedyne/fe2o3

oxedyne/fe2o3/fe2o3_austenite/src/timings.rs

17.6 KiB, 102 runs

created by r1870400018:66076, which is this file's identity for as long as the history lasts, whatever it is later renamed to

download · who wrote it · its history

1//! Per-phase wall time of one compilation, for `austenite --eval --timings FILE`.
2//!
3//! The recorder is exclusive: while a phase runs inside another (realisation is called from flow and from
4//! the page furniture, a sink's page from the pass), the time goes to the innermost phase only, so the
5//! phases of a run add up to its wall time and nothing is counted twice. A phase that is never entered
6//! shows as zero entries, which is how a missing record is told from a quick phase. The recorder lives on
7//! the [`Engine`](crate::eval::Engine) as an `Option`: with none, a phase costs one test of the option,
8//! and with one, a clock read at each end of a phase and no allocation per page (a bucket is added once
9//! per fixpoint pass).
10//!
11//! The record also carries the shaped-run cache's counters, which say whether the time in flow was spent
12//! shaping again what had been shaped.
13//!
14//! Realisation is split further. Six sub-phases (rules, regex, show, repack, styles, intro) are opened inside
15//! `Realise` and are exclusive in the same way, so the time of `Realise` outside them is its own. The
16//! `intro` sub-phase is the introspector reads a realised body makes (counters, states, queries, locations);
17//! a read opened inside another, or by flow or the page furniture, is left to whatever holds the clock. A pass's
18//! `realise` cell is the whole of it, the sub-phases and the rest, so a reader of the phase table sees one
19//! realisation total; the `sub` object splits it, with `self` the part outside every sub-phase. Each pass
20//! also counts the realise calls by the mode and the shape of the content realised and by cause, and a few
21//! work counters (elements visited, show rules matched against, elements copied before they are changed).
22//!
23//! Three of the sub-phases (rules, show, styles) are entered once or twice for every element, a million
24//! times in a pass of a long document, and a clock read costs about as much as the work they time. They are
25//! counted in every record but clocked only in a fine record ([`Timings::start_fine`]), whose time is then
26//! the work and the clock together: the record carries the cost of one read, and a reader takes it off
27//! once for each entry. In a coarse record their time stays in `self`.
28//!
29//! A per-page record of the flow's carry state ([`PageRec`]) rides in the same file, one list for each
30//! pass: it is the measurement of how much of a compile a re-run could reuse, and is made only here. Its
31//! cost is the `probe` phase.
32//!
33//! It reads `std::time::Instant`, which the wasm32-unknown-unknown target does not provide, so only a
34//! native run switches it on.
35
36use crate::fonts::ShapeStats;
37
38use oxedyne_fe2o3_core::prelude::*;
39
40use std::collections::BTreeMap;
41use std::collections::HashMap;
42use std::hash::Hash;
43use std::hash::Hasher;
44use std::time::Instant;
45
46// One entry per kind of work the fixpoint does.
47#[derive(Clone, Copy, Debug, PartialEq, Eq)]
48pub enum Phase {
49 // Once a run.
50 Load,
51 Eval,
52 Finish,
53 Write,
54 // Once a pass.
55 Realise,
56 Flow,
57 Place,
58 Decorate,
59 Sink,
60 Settle,
61 Probe,
62 // Inside realisation.
63 Rules,
64 Regex,
65 Show,
66 Repack,
67 Styles,
68 Intro,
69}
70
71impl Phase {
72 pub const COUNT: usize = 17;
73 pub const RUN: [Phase; 4] = [Phase::Load, Phase::Eval, Phase::Finish, Phase::Write];
74 pub const PASS: [Phase; 7] = [Phase::Realise, Phase::Flow, Phase::Place, Phase::Decorate, Phase::Sink, Phase::Settle, Phase::Probe];
75 pub const SUB: [Phase; 6] = [Phase::Rules, Phase::Regex, Phase::Show, Phase::Repack, Phase::Styles, Phase::Intro];
76
77 pub fn name(&self) -> &'static str {
78 match self {
79 Self::Load => "load",
80 Self::Eval => "eval",
81 Self::Finish => "finish",
82 Self::Write => "write",
83 Self::Realise => "realise",
84 Self::Flow => "flow",
85 Self::Place => "place",
86 Self::Decorate => "decorate",
87 Self::Sink => "sink",
88 Self::Settle => "settle",
89 Self::Probe => "probe",
90 Self::Rules => "rules",
91 Self::Regex => "regex",
92 Self::Show => "show",
93 Self::Repack => "repack",
94 Self::Styles => "styles",
95 Self::Intro => "intro",
96 }
97 }
98
99 fn index(&self) -> usize { *self as usize }
100
101 fn per_pass(&self) -> bool { Self::PASS.contains(self) || Self::SUB.contains(self) }
102
103 // Is it entered so often that a clock at each end costs as much as the work?
104 fn fine(&self) -> bool { matches!(self, Self::Rules | Self::Show | Self::Styles) }
105}
106
107// What a pass counts besides time.
108#[derive(Clone, Copy, Debug, PartialEq, Eq)]
109pub enum Counter {
110 Visits, // elements, sequences and styled runs met by the realisation walk
111 Leaves, // elements that no rule transformed and that reached grouping
112 Shown, // elements and labelled sequences put through the show-rule match
113 Recipes, // recipes in force, summed over the elements shown
114 Matched, // recipes whose selector was tried against an element
115 Prepared, // elements located and given their style values
116 Copied, // elements copied whole because a second holder shared them when they were changed
117 Textual, // textual runs searched for a text or regex rule
118 Finished, // groups finished (paragraphs, lists, cites, textual runs)
119}
120
121impl Counter {
122 pub const COUNT: usize = 9;
123 pub const ALL: [Counter; 9] = [
124 Counter::Visits, Counter::Leaves, Counter::Shown, Counter::Recipes, Counter::Matched,
125 Counter::Prepared, Counter::Copied, Counter::Textual, Counter::Finished,
126 ];
127
128 pub fn name(&self) -> &'static str {
129 match self {
130 Self::Visits => "visits",
131 Self::Leaves => "leaves",
132 Self::Shown => "shown",
133 Self::Recipes => "recipes",
134 Self::Matched => "matched",
135 Self::Prepared => "prepared",
136 Self::Copied => "copied",
137 Self::Textual => "textual",
138 Self::Finished => "finished",
139 }
140 }
141}
142
143// Why a realise call was made, judged by whether the same body was realised before.
144#[derive(Clone, Copy, Debug, PartialEq, Eq)]
145pub enum Cause {
146 First, // pass one, a body never realised
147 New, // a later pass, a body no earlier pass realised: an answer has arrived that gives it content
148 Repass, // a body the previous pass realised, realised again for the new pass
149 Again, // a body already realised in this pass, realised once more
150}
151
152impl Cause {
153 pub const ALL: [Cause; 4] = [Cause::First, Cause::New, Cause::Repass, Cause::Again];
154
155 pub fn name(&self) -> &'static str {
156 match self {
157 Self::First => "first",
158 Self::New => "new",
159 Self::Repass => "repass",
160 Self::Again => "again",
161 }
162 }
163}
164
165// The time and the entries of each phase, indexed by `Phase::index`.
166#[derive(Clone, Debug, Default)]
167struct Bucket {
168 ns: [u64; Phase::COUNT],
169 n: [u64; Phase::COUNT],
170 ctr: [u64; Counter::COUNT],
171 calls: BTreeMap<String, [u64; 4]>, // realise calls by mode and shape of the content, then by cause
172}
173
174impl Bucket {
175 // The time of a phase. Realisation is reported whole, with the sub-phases inside it.
176 fn whole(&self, p: Phase) -> u64 {
177 match p {
178 Phase::Realise => self.ns[p.index()] + Phase::SUB.iter().map(|q| self.ns[q.index()]).sum::<u64>(),
179 _ => self.ns[p.index()],
180 }
181 }
182
183 fn cell(&self, p: Phase) -> String {
184 fmt!("\"{}\":{{\"ns\":{},\"n\":{}}}", p.name(), self.whole(p), self.n[p.index()])
185 }
186
187 fn json(&self, phases: &[Phase]) -> String {
188 let cells: Vec<String> = phases.iter().map(|p| self.cell(*p)).collect();
189 fmt!("{{{}}}", cells.join(","))
190 }
191
192 // The pass's own record: its phases, then the realisation's split, counters and calls.
193 fn pass_json(&self) -> String {
194 let cells: Vec<String> = Phase::PASS.iter().map(|p| self.cell(*p)).collect();
195 let mut subs: Vec<String> = Phase::SUB.iter().map(|p|
196 fmt!("\"{}\":{{\"ns\":{},\"n\":{}}}", p.name(), self.ns[p.index()], self.n[p.index()])).collect();
197 subs.push(fmt!("\"self\":{{\"ns\":{},\"n\":{}}}", self.ns[Phase::Realise.index()], self.n[Phase::Realise.index()]));
198 let ctrs: Vec<String> = Counter::ALL.iter().map(|c| fmt!("\"{}\":{}", c.name(), self.ctr[*c as usize])).collect();
199 let calls: Vec<String> = self.calls.iter().map(|(k, v)| {
200 let by: Vec<String> = Cause::ALL.iter().map(|c| fmt!("\"{}\":{}", c.name(), v[*c as usize])).collect();
201 fmt!("\"{}\":{{{}}}", k.replace('\\', "\\\\").replace('"', "\\\""), by.join(","))
202 }).collect();
203 fmt!("{{{},\"sub\":{{{}}},\"counts\":{{{}}},\"calls\":{{{}}}}}",
204 cells.join(","), subs.join(","), ctrs.join(","), calls.join(","))
205 }
206}
207
208/// The carry state a page was laid out from, as one fingerprint for each part of it, so that two compiles
209/// are compared field by field. The counters are the absolute ones (`count`, `pulled`, `base`, `work_idx`
210/// and `abs`), which shift for every later page when an edit adds a line; the rest are unaffected by such
211/// a shift. Source offsets are masked everywhere; locations, places and marks are hashed.
212#[derive(Clone, Debug, Default, PartialEq, Eq)]
213pub struct Entry {
214 pub count: u32, // pages yielded before this one
215 pub paginator: u64, // waiting tags, blank, started, ended, the run's setup, regions and first flag
216 pub level: u64, // the page-level state, the pairs still to come excluded
217 pub pulled: usize, // pairs taken from the root feed
218 pub base: usize, // the index of the first root child held
219 pub pull_rest: u64, // done, paragraph situation, collect config, mode, feed, the memo's length
220 pub children: u64, // the root children collected and not yet placed
221 pub config: u64, // the root flow's configuration
222 pub work_idx: usize, // the first root child not yet processed
223 pub spill: u64, // the breakable block carried over the page break
224 pub floats: u64, // floats queued for a later region, their children relative to `work_idx`
225 pub footnotes: u64,
226 pub foot_spill: u64, // the rest of a footnote that did not fit
227 pub tags: u64,
228 pub skips: u64, // insertions placed, their children relative to `work_idx`
229 pub abs: u64, // the absolute child indices of `floats` and `skips`
230 pub locator: u64, // the place counters
231 pub masked: u32, // source offsets met and masked in the whole entry
232}
233
234impl Entry {
235 // The fields as name and value, in the order the first difference is named.
236 pub fn fields(&self) -> [(&'static str, u64); 17] {
237 [
238 ("count", self.count as u64),
239 ("paginator", self.paginator),
240 ("level", self.level),
241 ("pulled", self.pulled as u64),
242 ("base", self.base as u64),
243 ("pull_rest", self.pull_rest),
244 ("children", self.children),
245 ("config", self.config),
246 ("work_idx", self.work_idx as u64),
247 ("spill", self.spill),
248 ("floats", self.floats),
249 ("footnotes", self.footnotes),
250 ("foot_spill", self.foot_spill),
251 ("tags", self.tags),
252 ("skips", self.skips),
253 ("abs", self.abs),
254 ("locator", self.locator),
255 ]
256 }
257
258 fn json(&self) -> String {
259 let cells: Vec<String> = self.fields().iter().map(|(k, v)| fmt!("\"{}\":\"{:x}\"", k, v)).collect();
260 fmt!("{{{},\"masked\":{}}}", cells.join(","), self.masked)
261 }
262}
263
264/// What one page was made from: its pairs, and the carry state it began in.
265#[derive(Clone, Debug, Default, PartialEq, Eq)]
266pub struct PageRec {
267 pub pairs: usize, // pairs taken from the root feed while the page was made
268 pub input: u64, // those pairs and the page's run setup, source offsets masked
269 pub entry: Entry,
270}
271
272impl PageRec {
273 fn json(&self) -> String {
274 fmt!("{{\"pairs\":{},\"input\":\"{:x}\",\"entry\":{}}}", self.pairs, self.input, self.entry.json())
275 }
276}
277
278#[derive(Debug)]
279pub struct Timings {
280 last: Instant, // the last clock read
281 stack: Vec<Phase>, // the phases open and clocked, outermost first
282 open: Vec<bool>, // every phase open, outermost first: was it clocked?
283 fine: bool, // are the phases entered for every element clocked too?
284 run: Bucket,
285 passes: Vec<Bucket>, // one for each fixpoint pass
286 pages: Vec<Vec<PageRec>>, // the pages of each fixpoint pass, in step with `passes`
287 fed: Vec<u64>, // fingerprints of the pairs taken from the root feed since the last page record
288 idle: u64, // ns spent outside every phase
289 clock: u64, // ns one clock read costs, measured when the recorder starts
290 shape: Option<ShapeStats>, // the shaped-run cache at the end of the run, once the caller has read it
291 seen: HashMap<u64, usize>, // realised bodies by key: the last pass that realised one
292}
293
294impl Timings {
295 /// Starts the recorder with `Load` open, since the clock runs from the moment the compile is asked for.
296 pub fn start() -> Self { Self::begin(false) }
297
298 /// As [`Timings::start`], also clocking the phases entered for every element. That costs a clock read
299 /// at each end of each, which is a large share of a long document's compile time.
300 pub fn start_fine() -> Self { Self::begin(true) }
301
302 fn begin(fine: bool) -> Self {
303 let clock = Self::clock_cost();
304 let mut stack = Vec::with_capacity(64);
305 stack.push(Phase::Load);
306 let mut run = Bucket::default();
307 run.n[Phase::Load.index()] = 1;
308 let mut open = Vec::with_capacity(64);
309 open.push(true);
310 Self {
311 last: Instant::now(), stack, open, fine, run, passes: Vec::with_capacity(Phase::PASS.len()),
312 pages: Vec::new(), fed: Vec::new(), idle: 0, clock, shape: None, seen: HashMap::new(),
313 }
314 }
315
316 fn clock_cost() -> u64 {
317 const READS: u32 = 1_000;
318 let t = Instant::now();
319 for _ in 0..READS {
320 std::hint::black_box(Instant::now());
321 }
322 (t.elapsed().as_nanos() / READS as u128) as u64
323 }
324
325 /// Opens a phase inside whatever is open, the enclosing phase's clock stopping until it ends.
326 pub fn enter(&mut self, p: Phase) {
327 if p == Phase::Intro && !self.intro_here() {
328 // Neither counted nor clocked: a read made inside another read, or outside realisation.
329 self.open.push(false);
330 return;
331 }
332 self.count(p);
333 let clocked = self.fine || !p.fine();
334 self.open.push(clocked);
335 if clocked {
336 self.charge_top();
337 self.stack.push(p);
338 }
339 }
340
341 // Is the innermost phase one that realisation owns, and not an introspector read already? The reads are
342 // opened at several levels of the introspector's own calls, and flow and the page furniture make reads of
343 // their own, whose time belongs to them.
344 fn intro_here(&self) -> bool {
345 matches!(self.stack.last(), Some(Phase::Realise) | Some(Phase::Rules) | Some(Phase::Regex) | Some(Phase::Show)
346 | Some(Phase::Repack) | Some(Phase::Styles))
347 }
348
349 /// Closes the innermost phase.
350 pub fn leave(&mut self) {
351 if self.open.pop() == Some(true) {
352 self.charge_top();
353 self.stack.pop();
354 }
355 }
356
357 /// Begins a fixpoint pass: its phases are counted in a bucket of their own.
358 pub fn begin_pass(&mut self) {
359 self.passes.push(Bucket::default());
360 self.pages.push(Vec::new());
361 }
362
363 /// Notes a pair the root feed handed out.
364 pub fn see(&mut self, fp: u64) { self.fed.push(fp); }
365
366 /// The fingerprints noted since the last call.
367 pub fn take_seen(&mut self) -> Vec<u64> { std::mem::take(&mut self.fed) }
368
369 /// Adds a page's record to the current pass.
370 pub fn page(&mut self, rec: PageRec) {
371 if self.pages.is_empty() {
372 self.pages.push(Vec::new());
373 }
374 let last = self.pages.len() - 1;
375 self.pages[last].push(rec);
376 }
377
378 // Adds the time since the last read to the innermost phase, or to the idle time with none open.
379 fn charge_top(&mut self) {
380 let now = Instant::now();
381 let dt = now.duration_since(self.last).as_nanos() as u64;
382 self.last = now;
383 match self.stack.last().copied() {
384 Some(p) => self.bucket(p).ns[p.index()] += dt,
385 None => self.idle += dt,
386 }
387 }
388
389 fn count(&mut self, p: Phase) {
390 self.bucket(p).n[p.index()] += 1;
391 }
392
393 // The bucket a phase is charged to: the run's, or the current pass's (the first is made if no pass was begun).
394 fn bucket(&mut self, p: Phase) -> &mut Bucket {
395 if p.per_pass() {
396 if self.passes.is_empty() {
397 self.passes.push(Bucket::default());
398 }
399 let last = self.passes.len() - 1;
400 &mut self.passes[last]
401 } else {
402 &mut self.run
403 }
404 }
405
406 pub fn passes(&self) -> usize { self.passes.len() }
407
408 /// Adds `by` to a counter of the current pass.
409 pub fn bump(&mut self, c: Counter, by: u64) {
410 self.bucket(Phase::Realise).ctr[c as usize] += by;
411 }
412
413 /// Records one realise call: under the label of its mode and the shape of its content, and under the
414 /// cause its `key` gives, the key being the hash of where the body is realised (the place, the span, the
415 /// kind of the content). A key not met in any pass is `First` in pass one and `New` after; one met in
416 /// an earlier pass is `Repass`; one already met in this pass is `Again`.
417 pub fn note_call(&mut self, label: String, key: u64) {
418 let pass = self.passes.len().max(1) - 1;
419 let cause = match self.seen.insert(key, pass) {
420 Some(p) if p == pass => Cause::Again,
421 Some(_) => Cause::Repass,
422 None if pass == 0 => Cause::First,
423 None => Cause::New,
424 };
425 self.bucket(Phase::Realise).calls.entry(label).or_insert([0; 4])[cause as usize] += 1;
426 }
427
428 /// The hash that tells one realised body from another, from what places it.
429 pub fn key<H: Hash>(placing: &H) -> u64 {
430 let mut h = std::collections::hash_map::DefaultHasher::new();
431 placing.hash(&mut h);
432 h.finish()
433 }
434
435 /// Keeps the shaped-run cache's counters for the record.
436 pub fn set_shape(&mut self, stats: ShapeStats) { self.shape = Some(stats); }
437
438 fn shape_json(&self) -> String {
439 match &self.shape {
440 Some(s) => fmt!(
441 "{{\"entries\":{},\"bytes\":{},\"budget\":{},\"hits\":{},\"misses\":{},\"evictions\":{}}}",
442 s.entries, s.bytes, s.budget, s.hits, s.misses, s.evictions),
443 None => "null".to_string(),
444 }
445 }
446
447 /// The recorded times as one JSON object, in nanoseconds, with `total` the run's own wall time as the
448 /// caller read it.
449 pub fn json(&self, total: u64) -> String {
450 let passes: Vec<String> = self.passes.iter().map(|b| b.pass_json()).collect();
451 let pages: Vec<String> = self.pages.iter().map(|ps| {
452 let recs: Vec<String> = ps.iter().map(|r| r.json()).collect();
453 fmt!("[{}]", recs.join(","))
454 }).collect();
455 fmt!(
456 "{{\"unit\":\"ns\",\"fine\":{},\"total\":{},\"idle\":{},\"clock\":{},\"passes\":{},\"run\":{},\"pass\":[{}],\"shape\":{},\"pages\":[{}]}}\n",
457 self.fine, total, self.idle, self.clock, self.passes.len(), self.run.json(&Phase::RUN), passes.join(","), self.shape_json(),
458 pages.join(","))
459 }
460}