NEW-25 - branch-and-bound on the competitive-min rail (byte-exact, no ratio cost)
Почему это может сжать сильнее
A competitive-min candidate that has already emitted more bytes than the incumbent cannot win, so it can be abandoned mid-construction. Defer the cube/BWT base candidate until the cheap strong backends have established an incumbent, pass that incumbent size down as a bound, and abandon the chunked accumulation as soon as it passes the bound. Emitted bytes are unchanged by construction: the bound only ever decreases, so an abandonment measured against an older larger bound also holds against every later one; and abandonment uses partial > bound (never >=) so a candidate that would exactly tie still runs to completion and still wins the tie under the existing strictly-smaller rule. Abandoning the value-stream competition does not touch the R7 raw-store fallback that actually bounds expansion. Targets the exe/image classes where base is 43-74% of encode wall and never wins.
Результат проверки
замер · CUBR-0087 · 2026-07-30Implemented: base is deferred on the multi-block path until the cheap strong backends establish an incumbent, that size is passed down as a bound, and the chunked accumulation is abandoned as soon as it passes the bound. Emitted bytes unchanged by construction - the bound only decreases, and abandonment uses > never >= so a candidate that would exactly tie still runs to completion and wins the tie under the existing strictly-smaller rule. FIRST IMPLEMENTATION WAS WRONG AND IS RECORDED AS SUCH: the bound was held in a process-global AtomicUsize, which is sound for one encode and wrong for a library - concurrent callers abandoned each other's base, and an encode with no incumbent of its own returned an EMPTY blob. 26 tests failed on chunked/large-file paths. The byte-identity gate PASSED at the same time (3/3 identical) because the CLI runs one encode per process, so it never exercised the failure mode: a gate that exercises one concurrency level cannot clear a change whose failure mode is concurrency. Fixed by threading the bound as an explicit parameter through encode_base_bounded -> encode_chunked_bounded -> encode_blocks_parallel, with usize::MAX expressing no incumbent, run to completion - the case the global version could not represent. GATE AFTER FIX: cargo test --release 305 passed / 6 failed, and those 6 fail IDENTICALLY on a pristine detached worktree at 09ef2bb (fixtures under documentation/ephemeral/research/corpus/ that no checkout has), so they are the environment baseline and not this change. Full-corpus byte identity against a reference build of the same tree with the knobs unset: silesia/ooffice 6152192 -> 1763460 IDENTICAL round-trip PASS; silesia/x-ray 8474240 -> 3637036 IDENTICAL round-trip PASS. Those two are the load-bearing cases - the classes where a type transform wins so base loses the top-level competition and the bound actually fires. samba (21.6 MB) still running; nothing has been run at enwik8 scale (100 MB). [GATE COMPLETE 2026-07-30] Full-corpus byte identity, 3/3, against a reference build of the same tree with the knobs unset: silesia/ooffice 6152192 -> 1763460 IDENTICAL; silesia/x-ray 8474240 -> 3637036 IDENTICAL; silesia/samba 21606400 -> 3138929 IDENTICAL. Round-trip PASS on every one. ooffice and x-ray were run independently on arcana-devs (16 cores) AND dev-ai (64 cores) and both hosts produced the same byte counts and the same verdict - which is worth more than a repeat on one machine, because the abandonment path is racy by design: a different core count schedules the workers differently, so the two runs did not abandon the same blocks at the same moments and still emitted identical bytes. samba adds a 21.6 MB / ~330-block file to exercise the race at depth. STILL NOT PROVEN: nothing has been run at enwik8 scale (100 MB, ~1500 blocks, model 8x larger than anything tested); and the gate proves the CHANGE is inert, not that the codec was correct beforehand. [F17 CORRECTION 2026-07-30] The image/binary asymmetry (mr 80.22x, x-ray 63.91x, sao 26.77x) is NOT outer-rail waste and NEW-25 does NOT address it. Predicted that it would; measured that it does not. x-ray with the NEW-25 build: base 80.296 s / 71.84% share, against 81.656 s / 73.52% unbounded - unchanged, the bound never fires there. TWO ERRORS CORRECTED: (1) base does NOT never win on x-ray, it wins 13 of 14 calls; that property belongs to ooffice (wins 0) and was carried across to x-ray because the two files share a shape. (2) NEW-25 bounds only the TOP-LEVEL base call; the other 13 are nested calls made by transforms and use the unbounded encode_base. The giveaway was in the attribution the whole time - base 81.656 s against med16 81.586 s, within 70 ms, because they are the SAME WORK: med16 encode IS a nested base call. Bounding the winner would be wrong and NEW-25 correctly does not. REAL CAUSE, now identified: the winning path is itself lopsided - med16 -> nested chunked base -> per-block EIGHT-WAY value-stream competition (vs_ctxmix 490 s, vs_geomix 423 s, vs_order2_rans 79 s CPU on a 2 MB file), while decode replays ONE scheme per block and finishes in 2.6 s. Same structural pattern as the CM2 column sweep (encoder races N, decoder replays 1) one level further down. ADDRESSABLE by bounding or gating the INNER per-block competition, the way NEW-26 gates the column sweep - unimplemented and unmeasured. NEW-25 remains measured and true for ooffice, which is genuine outer-rail waste (base wins 0).