/* #hutter_run_costs @hutter_metrics @pprog_p8v2_impl_goal_20260804 @pp_wordsv2 What the Hutter runs cost, and the rule that a cost is always reported with its reason ## The rule Anything expensive reports, with its result, BOTH what it cost and WHY -- the shape of the computation that makes it expensive, in the parameters that matter. A wall-clock number on its own is nearly useless: it does not say whether the next size up is twice the cost or a hundred times, and that is the only thing anyone actually wants to know from it. So a cost is reported as a pair: cost shape the complexity in the parameters that vary, e.g. O(SC * W^2 * 256) cost why one clause naming the thing being repeated, e.g. "one full window settled per candidate recorded byte" alongside the measured wall clock. Blocks, TSV columns, a report line -- the medium does not matter, the pairing does. ## What counts as expensive Deliberately a judgement call, not a threshold. The test is whether the cost CHANGES WHAT YOU CAN DO NEXT: - a run you would hesitate to repeat, or that you would not launch without checking first - a step that caps the sample size, so it decides what can be measured at all - anything that costs money or is nondeterministic (the LLM fill) - anything whose growth is worse than linear in the DSS, at any constant, because our whole problem is that the samples are tiny and the target is 10^9 A step that is merely slow but linear and cheap per byte is not expensive by this test; it is just work. A step that is fast today and quadratic is expensive, and says so before it bites. ## The inventory, p8v2 as built Measured on this machine, and the shapes are from #pp_wordsv2's blocks. THE MEMCHAIN SHIFT -- the wall, and it belongs to p3, not to p8v2. shape O(N) byte moves per input byte, so O(M*N), and since every run so far uses N = M, O(M^2) cost measured on the p3 memchain alone, net of the 200 kHz pacing: 0.17 s at N = 2*10^4, 0.51 s at 4*10^4, 1.63 s at 8*10^4 -- ratios of 3.0 and 3.2 per doubling, converging on the 4 that quadratic predicts. Extrapolating, ~2 minutes at 10^6 and ~3 HOURS at 10^7. why #pp_pattern implements the length-N copy chain literally: chain_shift moves every one of the N cells one position toward the tail on every single input byte. It is a shift register, which is what the p3 design says it is. This WAS the single biggest cost in the system and it is not p8v2's. It is why a p8v2 run at 10^6 took about 213 seconds, of which roughly 68 was shifting and the rest the diagnostic settling below; the two are within a factor of two of each other at that size and the shift wins from there up. It is also why the memchain interpreter cannot reach the DSS at all: at 10^9 the shift alone is 10^18 byte moves. Nothing on the compression ladder is measured end-to-end at enwik9 scale by this interpreter, and the p8-opt.c enwik9 validation (#p8_enwik9_validation_report_20260708) was a direct-optimization C program precisely because of this. FIXED 2026-08-05 for the wordsv2 kind: the chain is stored append-only and never shifted, so a step is O(1) and a run is linear. #um_optimizations carries the collapse, its unfolding and the measurements. p1/p3/p4/p7/p8 still shift literally -- their pp_main blocks index mem[] under the shifting convention, so it is not a one-block change for them -- which is why the p7 baseline rows in the generation TSV stop at 10^5 and say so. SETTLING ONE WINDOW -- the primitive everything below is built from. shape O(W^2 * 256) byte operations, about 12 million at W = 128 why a message travels one position per sweep, so the sweep count is the window length; each sweep recomputes every unclamped position's 256-entry LSA vector from three messages This is why W is the single most expensive constant in the design: it enters squared. WHOLE-SAMPLE SETTLING, for the .pos dump and the settled-argmax diagnostics. shape O(M/W) windows, so O(M * W * 256) overall -- linear in M with a large constant cost about 2 seconds per 10^4 bytes, so ~3 minutes at 10^6 and ~30 minutes at 10^7, per variant why every window of the sample is settled once Consequence: this alone caps the prefix ladder. It SHOULD be capped to the first few thousand positions -- the rendering reads 128 -- with the cap reported alongside, so the diagnostics say over how many positions they were computed. DONE 2026-08-05: capped at the first 65536 positions, and reported as "settled argmax correct of " with "dumped " in the .pos header, so a diagnostic computed over a prefix is never printed as though it covered the sample. With the chain collapse this took a 10^6 run from 213.3 s to 24.4 s -- 8.7x, and linear where it was quadratic -- and made a 10^7 rung affordable. D2 / D3 SPARSIFICATION (#omega-p8-settled, #omega-p8-greedy) -- the expensive one. shape O(SC * W^2 * 256), and since SC is itself proportional to M, that is quadratic in M cost 40 seconds at 10^4; therefore about an hour at 10^5 and out of reach at 10^6 why one full window is settled per candidate recorded byte, to ask whether settling would recover it without that byte Consequence: the D axis cannot ride the prefix ladder. Runs above 10^4 are D1 only, and the skipped rows are recorded with this reason rather than dropped. TOKEN LEARNING (#pp_learn's learn_tokens). shape O(65536 * 256) = 16.7 million entries zeroed and scanned per replay round, plus O(M) cost about 50 ms per round, and 16 MB of resident memory why the successor distribution is held densely for every possible k=2 context Not expensive by the test above at k=2. It becomes expensive immediately at k=3, where the dense form is 256 times larger, and that is one of the things that makes pruning real at larger k. THE LLM FILL (the --rewritepl step of #handle_run_ofra). shape one call per block whose NL changed: 15 for a new variant, 1 for a one-axis change off a filled baseline cost seconds per call, real money, and nondeterministic -- it can return nothing (see the wart recorded in #pprog_p8v2_gen1_report_20260804) why the generated program is written from NL every time its NL changes This is the cost that makes the per-block split of the generated program worth having: it is what turns "regenerate the generation" from 165 calls into 25. Worth recording because it happened: on 2026-08-05 the API returned insufficient_quota with no ollama backend running, and the consequence is sharper than "a step is slow". While that holds, NO NL OF ANY GENERATED BLOCK CAN BE CHANGED AT ALL, because changing NL changes the block's staleness key, which misses the cache, which needs a call. Parent-side C, fixtures, scripts and blocks stay editable; the generated program freezes exactly as it is. Credits returned the same day and both fixes above then landed. THE T-LEVEL CLOCK. shape O(M / hz) seconds of pure waiting, hz being the 200 kHz in #stdin_single_byte's header cost 5 s at 10^6, 50 s at 10^7, and it would be 5000 s at 10^9 why pace() holds the input transducer to the clock the fixture pins, which is a design feature (the Hutter-budget rate from #mc_pattern_design), not an accident Was invisible behind the other costs. Now that a 10^6 run is 24 s the clock is a fifth of it, and it rises to the largest single term at 10^7. Nothing to fix -- but when a ladder rung looks slow for its size, this is the first thing to check. COMPILE. shape once per distinct filled program cost under a second why keyed on the checksum of the filled genc, so identical programs across variants link once Not expensive. ## Where this is reported - per run: a cost line on stderr from the compressor, carrying the settling cost actually paid, the dump cap in force, and the shape/why pair for whichever sparsification alternative ran - per generation: cost_shape and cost_why columns in the TSV, beside the wall clock, and an explicit SKIPPED row with its reason wherever the ladder could not be run - here: the shapes themselves, which do not change per run Written 2026-08-05. */