oxedyne/fe2o3/fe2o3_austenite/tools/bench/replay_ratio.mjs
12.1 KiB, 1 run
created by r1870400018:68329, 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 | #!/usr/bin/env node |
| 2 | // U1 RATIO: how much of a document's page-by-page carry state a small edit leaves unchanged. |
| 3 | // |
| 4 | // The native binary compiles the document with `--eval --timings`, whose `pages` array holds, for each page |
| 5 | // of each fixpoint pass, a fingerprint of what the page was made from: the pairs it took from the flow and the |
| 6 | // flow's carry state as it entered the page (src/timings.rs `PageRec`, src/flow/carry.rs). This driver compiles |
| 7 | // a document, edits it, compiles it again and compares the last pass's records page by page. A page whose |
| 8 | // record is equal before and after is one a page ledger could replay rather than lay out again. |
| 9 | // |
| 10 | // Edit sites are the EDITTOK markers of gen_synthetic.py, or, for a document without them, the first word of |
| 11 | // each plain body paragraph. The sites used are those at 0, 1/N, 2/N ... of the list (N = --positions), and |
| 12 | // each gets two one-letter edits (a letter typed onto the end of the site's word, from the unedited text). |
| 13 | // Two further edits, at the third site, insert a clause of about two lines (`clause`) and one of about sixteen |
| 14 | // (`clause+`), so the paragraph gains lines and the second moves every later page break. |
| 15 | // |
| 16 | // Two equalities are reported for every edit. The raw one compares the pairs, the input fingerprint and every |
| 17 | // entry field. The masked one leaves out the absolute counters (`count`, `pulled`, `base`, `work_idx`, `abs`), |
| 18 | // which shift for every later page when an edit adds a line. A page is "edited" when its raw record is the first |
| 19 | // to differ. The resync distance is the number of pages from the edited page to the start of the run of equal |
| 20 | // pages that lasts to the end of the document; `null` when the last page differs. The keyed figure is the share of |
| 21 | // the edited run's pages whose record, counters left out, occurs on any page of the unedited run: what a ledger |
| 22 | // keyed by content, not by page number, could reuse. |
| 23 | // |
| 24 | // Usage: replay_ratio.mjs <austenite-binary> <doc.typ> [--work=DIR] [--json=FILE] [--positions=N] |
| 25 | // Prints the per-edit table and a summary to stdout; --json writes everything. Run it under |
| 26 | // `systemd-run --user --scope -p MemoryMax=3G`; each compile is a child of this process. |
| 27 | import fs from 'node:fs'; |
| 28 | import path from 'node:path'; |
| 29 | import { spawnSync } from 'node:child_process'; |
| 30 | import { median } from './lib/stats.mjs'; |
| 31 | |
| 32 | const ORDER = ['count', 'paginator', 'level', 'pulled', 'base', 'pull_rest', 'children', 'config', 'work_idx', |
| 33 | 'spill', 'floats', 'footnotes', 'foot_spill', 'tags', 'skips', 'abs', 'locator']; |
| 34 | const COUNTERS = new Set(['count', 'pulled', 'base', 'work_idx', 'abs']); |
| 35 | const CLAUSE = ' and, to take the matter a little further than a first reading allows, the same may be said of ' |
| 36 | + 'the other things that were set beside it, which is why the whole of it was kept in view as long as it was'; |
| 37 | const CLAUSE_LONG = CLAUSE.repeat(8); // about sixteen lines, enough to move every later page break |
| 38 | |
| 39 | function parseArgs(argv) { |
| 40 | const out = { positions: 5, work: null, json: null, rest: [] }; |
| 41 | for (const a of argv.slice(2)) { |
| 42 | const m = a.match(/^--([^=]+)=(.*)$/); |
| 43 | if (!m) { out.rest.push(a); continue; } |
| 44 | out[m[1]] = /^\d+$/.test(m[2]) ? Number(m[2]) : m[2]; |
| 45 | } |
| 46 | return out; |
| 47 | } |
| 48 | |
| 49 | // Where a letter may be typed: the end of an EDITTOK marker (a space follows each, so EDITTOK1 never |
| 50 | // matches the start of EDITTOK10), else the end of the first word of a plain body paragraph. |
| 51 | function sitesOf(text) { |
| 52 | const marks = [...text.matchAll(/EDITTOK(\d+) /g)]; |
| 53 | if (marks.length) return marks.map((m) => ({ at: m.index + m[0].length - 1, name: m[0].slice(0, -1) })); |
| 54 | return [...text.matchAll(/(?:^|\n\n)([A-Za-z]{4,})(?= )/g)].map((m) => ({ at: m.index + m[0].length, name: m[1] })); |
| 55 | } |
| 56 | |
| 57 | function compile(bin, text, work, tag) { |
| 58 | const src = path.join(work, `${tag}.typ`); |
| 59 | const json = path.join(work, `${tag}.json`); |
| 60 | const out = path.join(work, `out_${tag}`); |
| 61 | fs.writeFileSync(src, text); |
| 62 | const t0 = process.hrtime.bigint(); |
| 63 | const r = spawnSync(bin, ['--eval', '--timings', json, src, out], { encoding: 'utf8', maxBuffer: 1 << 26, timeout: 900000 }); |
| 64 | const wall_s = Number(process.hrtime.bigint() - t0) / 1e9; |
| 65 | fs.rmSync(out, { recursive: true, force: true }); |
| 66 | if (r.status !== 0 || !fs.existsSync(json)) { |
| 67 | throw new Error(`compile ${tag} failed: status ${r.status} ${r.signal || ''} ${(r.stderr || '').slice(0, 400)}`); |
| 68 | } |
| 69 | const d = JSON.parse(fs.readFileSync(json, 'utf8')); |
| 70 | fs.rmSync(json, { force: true }); |
| 71 | fs.rmSync(src, { force: true }); |
| 72 | const pages = d.pages[d.pages.length - 1]; |
| 73 | const probe = d.pass[d.pass.length - 1].probe; |
| 74 | return { pages, probe_ns: probe.ns, probe_n: probe.n, probe_ns_page: probe.ns / pages.length, wall_s, total_ns: d.total }; |
| 75 | } |
| 76 | |
| 77 | // Are two page records equal, and if not, in which field first? `input` covers the pairs and their count. |
| 78 | function same(a, b, masked) { |
| 79 | if (!a || !b) return { eq: false, field: 'missing' }; |
| 80 | if (a.pairs !== b.pairs || a.input !== b.input) return { eq: false, field: 'input' }; |
| 81 | for (const f of ORDER) { |
| 82 | if (masked && COUNTERS.has(f)) continue; |
| 83 | if (a.entry[f] !== b.entry[f]) return { eq: false, field: f }; |
| 84 | } |
| 85 | return { eq: true, field: null }; |
| 86 | } |
| 87 | |
| 88 | // A record without its absolute counters, as a key: the same content at another page number has the same key. |
| 89 | function key(r) { |
| 90 | return `${r.pairs}:${r.input}:${ORDER.filter((f) => !COUNTERS.has(f)).map((f) => r.entry[f]).join(':')}`; |
| 91 | } |
| 92 | |
| 93 | // The start of the run of equal pages that lasts to the end, minus the edited page; null if the last differs. |
| 94 | function resync(eq, e) { |
| 95 | const n = eq.length; |
| 96 | if (!n || !eq[n - 1]) return null; |
| 97 | let r = n - 1; |
| 98 | while (r > 0 && eq[r - 1]) r--; |
| 99 | return Math.max(r, e + 1) - e; |
| 100 | } |
| 101 | |
| 102 | function analyse(base, ed) { |
| 103 | const n = Math.max(base.length, ed.length); |
| 104 | const raw = [], msk = []; |
| 105 | for (let i = 0; i < n; i++) { |
| 106 | raw.push(same(base[i], ed[i], false)); |
| 107 | msk.push(same(base[i], ed[i], true)); |
| 108 | } |
| 109 | const reqs = raw.map((x) => x.eq), meqs = msk.map((x) => x.eq); |
| 110 | let e = reqs.indexOf(false); |
| 111 | const count = (a, from = 0) => a.slice(from).filter(Boolean).length; |
| 112 | const res = { pages: n, pages_base: base.length, pages_edit: ed.length, edited: e < 0 ? null : e }; |
| 113 | res.raw_equal = count(reqs) / n; |
| 114 | res.masked_equal = count(meqs) / n; |
| 115 | if (e < 0) e = n; // nothing differs |
| 116 | // Content-keyed reuse: edited-run pages whose record (counters left out) occurs anywhere in the base run. |
| 117 | const keys = new Set(base.map(key)); |
| 118 | res.keyed_equal = ed.filter((r) => keys.has(key(r))).length / n; |
| 119 | res.raw_after = n > e + 1 ? count(reqs, e + 1) / (n - e - 1) : null; |
| 120 | res.masked_after = n > e + 1 ? count(meqs, e + 1) / (n - e - 1) : null; |
| 121 | res.resync_raw = resync(reqs, e); |
| 122 | res.resync_masked = resync(meqs, e); |
| 123 | // Pages after the edited one that differ under the masked equality: those whose pairs changed, and |
| 124 | // those whose pairs are equal while the carry state is not (the failures a ledger would care about). |
| 125 | const input = {}, entry = {}; |
| 126 | let first_entry = null, first_input = null; |
| 127 | for (let i = e + 1; i < n; i++) { |
| 128 | if (msk[i].eq) continue; |
| 129 | const f = msk[i].field; |
| 130 | if (f === 'input' || f === 'missing') { |
| 131 | input[f] = (input[f] || 0) + 1; |
| 132 | if (first_input === null) first_input = i; |
| 133 | } else { |
| 134 | entry[f] = (entry[f] || 0) + 1; |
| 135 | if (first_entry === null) first_entry = { page: i, field: f }; |
| 136 | } |
| 137 | } |
| 138 | res.diff_input = input; |
| 139 | res.diff_entry = entry; |
| 140 | res.first_entry_diff = first_entry; |
| 141 | // The line shift: how far the last page's absolute child counter moved. |
| 142 | const k = Math.min(base.length, ed.length) - 1; |
| 143 | res.shift = k >= 0 ? parseInt(ed[k].entry.work_idx, 16) - parseInt(base[k].entry.work_idx, 16) : null; |
| 144 | return res; |
| 145 | } |
| 146 | |
| 147 | const pct = (x) => (x === null ? ' - ' : (100 * x).toFixed(1).padStart(5)); |
| 148 | |
| 149 | function main() { |
| 150 | const args = parseArgs(process.argv); |
| 151 | const [bin, doc] = args.rest; |
| 152 | if (!bin || !doc) { |
| 153 | process.stderr.write('usage: replay_ratio.mjs <austenite-binary> <doc.typ> [--work=DIR] [--json=FILE] [--positions=N]\n'); |
| 154 | process.exit(2); |
| 155 | } |
| 156 | const work = args.work || fs.mkdtempSync(path.join(process.env.HOME, '.cache', 'replay_ratio_')); |
| 157 | fs.mkdirSync(work, { recursive: true }); |
| 158 | const text = fs.readFileSync(doc, 'utf8'); |
| 159 | const sites = sitesOf(text); |
| 160 | if (!sites.length) { |
| 161 | process.stderr.write('replay_ratio: no edit sites found\n'); |
| 162 | process.exit(1); |
| 163 | } |
| 164 | const picks = []; |
| 165 | for (let i = 0; i < args.positions; i++) picks.push(sites[Math.min(Math.floor((i / args.positions) * sites.length), sites.length - 1)]); |
| 166 | |
| 167 | const base = compile(bin, text, work, 'base'); |
| 168 | // The control: the unedited text again must give an identical record for every page. |
| 169 | const ctl = analyse(base.pages, compile(bin, text, work, 'ctl').pages); |
| 170 | const probes = [base.probe_ns_page]; |
| 171 | const edits = []; |
| 172 | const run = (kind, pos, site, insert, letter) => { |
| 173 | const ed = compile(bin, text.slice(0, site.at) + insert + text.slice(site.at), work, 'ed'); |
| 174 | probes.push(ed.probe_ns_page); |
| 175 | const a = analyse(base.pages, ed.pages); |
| 176 | edits.push({ kind, pos, site: site.name, letter, ...a, probe_ns_page: ed.probe_ns_page, wall_s: ed.wall_s }); |
| 177 | process.stderr.write(`${kind} pos ${pos} ${site.name} ${letter || ''}: raw ${pct(a.raw_equal)} masked ${pct(a.masked_equal)} resync ${a.resync_raw}/${a.resync_masked}\n`); |
| 178 | }; |
| 179 | for (let p = 0; p < picks.length; p++) { |
| 180 | for (const letter of ['q', 'z']) run('letter', p, picks[p], letter, letter); |
| 181 | } |
| 182 | run('clause', 2, picks[Math.min(2, picks.length - 1)], CLAUSE, null); |
| 183 | run('clause+', 2, picks[Math.min(2, picks.length - 1)], CLAUSE_LONG, null); |
| 184 | |
| 185 | const letters = edits.filter((x) => x.kind === 'letter'); |
| 186 | const mean = (xs) => (xs.length ? xs.reduce((s, x) => s + x, 0) / xs.length : null); |
| 187 | const dist = (xs) => { |
| 188 | const ok = xs.filter((x) => x !== null); |
| 189 | return { median: median(ok), worst: ok.length ? Math.max(...ok) : null, none: xs.length - ok.length, n: xs.length }; |
| 190 | }; |
| 191 | const hist = (key) => { |
| 192 | const h = {}; |
| 193 | for (const x of letters) for (const [k, v] of Object.entries(x[key])) h[k] = (h[k] || 0) + v; |
| 194 | return h; |
| 195 | }; |
| 196 | const summary = { |
| 197 | doc: path.basename(doc), pages: base.pages.length, sites: sites.length, |
| 198 | control_raw_equal: ctl.raw_equal, |
| 199 | letter_raw_equal: mean(letters.map((x) => x.raw_equal)), |
| 200 | letter_masked_equal: mean(letters.map((x) => x.masked_equal)), |
| 201 | letter_raw_after: mean(letters.map((x) => x.raw_after).filter((x) => x !== null)), |
| 202 | letter_masked_after: mean(letters.map((x) => x.masked_after).filter((x) => x !== null)), |
| 203 | letter_resync_raw: dist(letters.map((x) => x.resync_raw)), |
| 204 | letter_resync_masked: dist(letters.map((x) => x.resync_masked)), |
| 205 | letter_diff_input: hist('diff_input'), |
| 206 | letter_diff_entry: hist('diff_entry'), |
| 207 | clause: edits.filter((x) => x.kind.startsWith('clause')), |
| 208 | letter_keyed_equal: mean(letters.map((x) => x.keyed_equal)), |
| 209 | probe_ns_page_median: median(probes), |
| 210 | probe_ns_page_max: Math.max(...probes), |
| 211 | compile_wall_s: base.wall_s, |
| 212 | }; |
| 213 | |
| 214 | const lines = [`${summary.doc}: ${summary.pages} pages, ${summary.sites} sites; control raw ${pct(ctl.raw_equal)}%`]; |
| 215 | lines.push('kind pos site raw% msk% key% rawA% mskA% edp rsyR rsyM shift pgs entry-diff fields (masked, after edited)'); |
| 216 | for (const x of edits) { |
| 217 | lines.push(`${x.kind.padEnd(7)} ${String(x.pos).padStart(3)} ${x.site.padEnd(12)} ${pct(x.raw_equal)} ${pct(x.masked_equal)} ${pct(x.keyed_equal)} ${pct(x.raw_after)} ${pct(x.masked_after)} ` |
| 218 | + `${String(x.edited).padStart(4)} ${String(x.resync_raw).padStart(5)} ${String(x.resync_masked).padStart(4)} ${String(x.shift).padStart(5)} ${String(x.pages_edit - x.pages_base).padStart(3)} ` |
| 219 | + `${JSON.stringify(x.diff_entry)} in:${JSON.stringify(x.diff_input)}`); |
| 220 | } |
| 221 | lines.push(`one-letter mean: raw ${pct(summary.letter_raw_equal)}% masked ${pct(summary.letter_masked_equal)}% (after edited page: raw ${pct(summary.letter_raw_after)}% masked ${pct(summary.letter_masked_after)}%)`); |
| 222 | lines.push(`content-keyed reuse (one-letter mean): ${pct(summary.letter_keyed_equal)}%`); |
| 223 | lines.push(`resync raw ${JSON.stringify(summary.letter_resync_raw)} masked ${JSON.stringify(summary.letter_resync_masked)}`); |
| 224 | lines.push(`probe ns/page median ${Math.round(summary.probe_ns_page_median)} max ${Math.round(summary.probe_ns_page_max)} (dev build); compile ${summary.compile_wall_s.toFixed(1)} s`); |
| 225 | process.stdout.write(lines.join('\n') + '\n'); |
| 226 | if (args.json) fs.writeFileSync(args.json, JSON.stringify({ summary, edits, control: ctl }, null, 1) + '\n'); |
| 227 | } |
| 228 | |
| 229 | main(); |