1- # Consumed partial-exit ordered fold (WL-PTAILFIX)
1+ # Consumed partial-exit ordered fold (WL-PTAILFIX, O1W slab fold )
22
33` PineExecutionAdapter::hash_state ` retains its existing count followed by
44` BrokerStateHashSink::s(key) ` and ` ::i(cycle) ` in ` std::string ` lexical order.
@@ -23,7 +23,7 @@ digest for one seed. Construction calls the real `BrokerStateHashSink` byte
2323loop. String length and signed cycle value use its native byte spelling;
2424there is no format, domain, endian, count, or version change.
2525
26- ## Ordered structure and work
26+ ## Ordered disk structure and work
2727
2828The auxiliary index is a compressed binary radix tree with buckets of at
2929most 16 original table offsets. Only interior branches store transforms.
@@ -50,10 +50,125 @@ map: O(1), zero auxiliary file reads/writes and zero allocation. Ordinary
5050runs maintain the same root, so an unrecorded run's terminal hash also has
5151the same byte semantics.
5252
53+ ## Incremental slab fold
54+
55+ The slab uses design (b), maintained transforms. Deferring the sort until a
56+ hash request would put the work on the per-bar path. The scheduler calls
57+ ` scheduler_record_broker_hash ` once per terminal script dispatch, including
58+ its quiet carried-callback branch
59+ (` src/source/pine_scheduler_native.cpp:639 ` ,
60+ ` src/source/pine_scheduler_native.cpp:725 ` ). With recording enabled this
61+ calls ` broker_state_hash ` (` src/source/pine_strategy_host.cpp:2772 ` ).
62+ ` on_native_bar ` then refreshes the recorded row after the adapter's close
63+ (` src/source/pine_strategy_host.cpp:613 ` ); its ` recording ` guard
64+ (` src/source/pine_strategy_host.cpp:629 ` ) enables
65+ ` capture_script_continuation_hash `
66+ (` src/source/pine_strategy_host.cpp:549 ` ). Thus an ordinary recorded script
67+ bar folds the table twice. Recorded magnifier sub-bars can refresh it too.
68+ Terminal input updates also call ` capture_script_continuation_hash `
69+ (` src/source/pine_strategy_host.cpp:569 ` ). Without recording, that refresh
70+ does not call the broker hash; explicit broker/stream hash queries still do.
71+ Each broker hash reaches ` hash_host_extension `
72+ (` src/engine_state_hash.cpp:123 ` ); the adapter's ` hash_state `
73+ (` src/source/pine_state_hash.cpp:1216 ` ) calls exactly one ` fold_sorted `
74+ (` src/source/pine_state_hash.cpp:508 ` ). A full-table lazy rebuild per dirty
75+ bar is therefore unsuitable.
76+
77+ ` IdPairSlabFold ` (` include/pineforge/detail/id_pair_slab_fold.hpp:21 ` )
78+ maintains a sorted roster of original record offsets, including dead rows,
79+ partitioned into contiguous buckets. A binary search finds the changed row
80+ or the new key's insertion point using the same length-aware byte comparison
81+ as the former selection loop. A new key shifts roster offsets through a
82+ fixed 512-byte buffer. Only the receiving bucket gains a row; later buckets
83+ retain their rows and maps even though their roster positions shift.
84+ An overflowing bucket splits into two contiguous halves. Erase and
85+ resurrection retain the original offset and bucket membership.
86+
87+ Each bucket caches the disk fold's ` BrokerStateByteFold ` for its live rows.
88+ The changed bucket, or the two halves of a split, is refolded using the
89+ unchanged ` s(key), i(value) ` bytes. All bucket maps are then composed in
90+ roster order into the resident root
91+ (` include/pineforge/detail/id_pair_slab_fold.hpp:71 ` ).
92+ These are derived indexes and transforms, with no additional logical hash
93+ leaf: concatenating the contiguous, sorted live subsequences is exactly the
94+ old sorted live sequence. Dead rows contribute identity. The existing
95+ 257-seed composition law therefore proves equality for every state and
96+ every incoming seed, including binary keys and prefixes. ` fold_sorted `
97+ still folds the live count and applies this root in O(1)
98+ (` include/pineforge/detail/id_pair_store.hpp:330 ` ).
99+
100+ ### Fixed budget and publication
101+
102+ The existing consumed index region is exactly 16* Q bytes, with Q a power of
103+ two and Q >= 2* K. Only the folded slab packs its hash slots as offsets;
104+ the full hash is read from the existing record header, and probing still
105+ compares complete keys (` include/pineforge/detail/id_pair_store.hpp:465 ` ).
106+ There is no change to data records, admission maxima, page spans or slab
107+ allocation. The disk and ordinary non-folded slab slot layouts are unchanged.
108+
109+ Configuration (` include/pineforge/detail/id_pair_slab_fold.hpp:35 ` ) chooses
110+ w=4 bytes when the entire admitted data region fits UINT32_MAX; otherwise
111+ w=8. The bucket maximum M is respectively 256 or 1,024. Split halves contain
112+ at least M/2 ever-keys; no key is removed from the roster. Reserving
113+ ceil(K/(M/2)) maps is sufficient, independently of mutation order or erasures.
114+ A map record is 2,064 bytes: count plus the unchanged 2,056-byte transform.
115+ The storage inside the index region is:
116+
117+ ```
118+ w*Q hash offsets + w*K sorted offsets + 2064*ceil(K/(M/2)) bucket bytes
119+ ```
120+
121+ For K <= M no bucket records are needed: the resident root is the sole map.
122+ For K > M, Q is divisible by 256 (w=4) or 1,024 (w=8), so the ceiling term is
123+ at most Q/256 or Q/1024. Total storage is at most 14.0625* Q or 14.015625* Q
124+ bytes, both below the already admitted 16* Q. This also bounds each
125+ configuration arithmetic intermediate; no new capacity limit is introduced.
126+ At the default K=4,096, Q=8,192, w=4, the reserved storage is 115,200 bytes
127+ inside the existing 131,072-byte index region.
128+
129+ The root and scalar layout state stay in the store; the slab update workspace
130+ is 4,632 bytes, below the existing disk workspace allowance. The final store
131+ static assertion still bounds the store plus update workspace and fixed
132+ buffer/frame allowance to 32 KiB
133+ (` include/pineforge/detail/id_pair_store.hpp:825 ` ), excluding the separately
134+ admitted, fixed slab. All slab access copies through ` read_at ` /` write_at ` ;
135+ there are no retained payload pointers, allocations or file operations.
136+
137+ The existing read-only key/data admission still precedes the first write.
138+ After admission, the roster and map writes fit spans that were made readable
139+ at bind; they cannot introduce a capacity refusal. Slab publication uses the
140+ prospective header while folding, then copies the admitted header and slot
141+ (` include/pineforge/detail/id_pair_store.hpp:789 ` ). A refused operation
142+ changes no row, map, slot, count, root, byte or extent. The disk pending-write
143+ and undo protocol remains the one described below. Move carries the roster
144+ layout, bucket count and root with the slab owner. Clear zeros the same
145+ regions and resets the root and bucket count while retaining configuration.
146+
147+ ### Slab work bound
148+
149+ Let N be ever-keys, L the maximum key length, and B the bucket count.
150+ Each write uses at most ceil(log2(N+1)) fold row comparisons. A new key
151+ copies at most w* N roster bytes and at most B map records on a split;
152+ replacements, erase and resurrection move no roster offsets. At most M+1
153+ rows' bytes are folded, even on a split. The remaining fold work is B
154+ compositions of 257 seed actions, with B <= ceil(K/(M/2)). Thus byte folding
155+ is bounded by 257* (M+1)* (16+L), rather than 257* N* (16+L).
156+ The existing hash lookup cost is separate; forced full-hash collisions
157+ still require linear probing and complete-key comparisons.
158+
159+ At K=4,096, L=8, the conservative per-write bounds are 13 fold comparisons,
160+ 1,585,176 real sink byte steps, and 32 map compositions / 8,224 seed actions.
161+ The old full-live selection loop makes N* N + N* (N-1)/2 = 25,163,776 row
162+ comparisons, plus up to 25,264,128 byte steps at eight-byte keys, per write.
163+ These are code-derived bounds, not timings or executed measurements.
164+ No unchanged bucket's key or value bytes are folded during composition.
165+ Even a smaller manifest's single-bucket rebuild is bounded by the fixed M.
166+
53167## RAM, disk, and addressable population
54168
55- ` IdPairStore ` 's final static assertion bounds the complete folded store plus
56- the 8,840-byte update workspace plus an 8,192-byte allowance for fixed reader
169+ For the disk backend, ` IdPairStore ` 's final static assertion bounds the
170+ complete folded store plus the 8,840-byte update workspace and an
171+ 8,192-byte allowance for fixed reader
57172buffers, rehash buffers, headers and scalar frames to 32 KiB. There is no
58173per-distinct-key resident allocation. The explicit memory-reference fixture
59174is excluded from that production disk-backend bound.
@@ -125,6 +240,47 @@ retains the fixture backend choice and scratch-directory configuration.
125240 append, replacement and erase; a second failure during retry; move with
126241 recovery outstanding; equality of all old rows and their fold after faults.
127242- Fixed segmented-file capacity under a simulated small offset ceiling.
243+ - The original 12-key folded slab fixture, including long keys, full hash
244+ collisions, refusal, first-seen iteration, move and clear.
245+ - ` slab_work_counters_observe_the_old_byte_loop `
246+ (` tests/test_id_pair_ordered_fold.cpp:285 ` ) calibrates real comparisons and
247+ all 257 seeds' byte steps on one- and two-row buckets. The observation
248+ sites are shared ` FoldReader::compare ` , ` compare_rows ` and ` append ` ;
249+ they observe the previous slab selection loop as well as the new path.
250+ - ` slab_work_bound_and_oracle_4096 `
251+ (` tests/test_id_pair_ordered_fold.cpp:309 ` ) requires 4,096 distinct live
252+ binary keys before asserting the per-write bounds, with and without
253+ forced full-hash collisions. It measures every insert, replace, erase,
254+ resurrection and mixed mutation; prohibits allocation during mutation and
255+ hashing; checks zero file IO and unchanged allocation identity; and covers
256+ move/clear with multiple cached buckets. Eight independent seeds at each
257+ checkpoint use the old enumerate/sort/relookup oracle on an independently
258+ mutated memory fixture, with a real-table sort/relookup at each completed
259+ phase. Iterated table contents must also equal an independent map.
260+ - ` slab_fold_layout_fits_every_index_tier `
261+ (` tests/test_id_pair_ordered_fold.cpp:481 ` ) checks power-of-two boundaries
262+ through the largest admitted index tier without allocating those slabs,
263+ and checks actual wide-offset copies with high bits set.
264+ - ` slab_data_refusal_preserves_fold_and_index `
265+ (` tests/test_id_pair_ordered_fold.cpp:518 ` ) checks data exhaustion with a
266+ key slot still available. This and the 4,096-key index exhaustion check
267+ compare every region's admitted bytes and extent, including cached maps.
268+
269+ The slab fail-before base is ba5bfdcfb2. With only its frozen headers, the
270+ expected first diagnostic is the missing ` id_pair_slab_fold.hpp ` include;
271+ after providing that standalone header, the missing ` Store::FixtureFoldWork ` .
272+ Neither compiler diagnostic is work-bound evidence. To obtain the intended
273+ runtime RED, retain that base's store algorithm, backport only the
274+ ` FixtureFoldWork ` type/pointer,
275+ fixture setter, comparison counters, and the ` FoldReader ` byte/compose
276+ observation wrappers; overlay the new test source and the standalone slab
277+ header needed to compile its layout/codec checks. Do not wire that header into
278+ the base store or change its ` publish_fold ` , slots or binder. The calibrated
279+ old loop must then fail at
280+ ` 4096-key slab fold exceeds 13 row comparisons/write ` after the full
281+ population assertion. The independently observed byte bound is also exceeded.
282+ No local compiler, build, test, preflight or corpus execution was performed
283+ by this edit-only lane; the supervisor must obtain both RED and GREEN in lab.
128284
129285No existing test assertions or the L18 fixture size/recording are changed.
130286Required remote checks, on the exact candidate tree, are preflight, docs,
@@ -133,18 +289,19 @@ full corpus parity, release and debug. In `lab remote` terminology:
133289``` sh
134290lab remote submit --repo engine --worktree < candidate-checkout> \
135291 --steps preflight,docs,parity,release,debug --host auto --keep-going \
136- --label core-cr150-ptailfix
292+ --label core-cr150-o1w-slabfold
137293```
138294
139295The C++ targets/CTest names to inspect explicitly are
140296` test_id_pair_ordered_fold ` , ` test_id_pair_store ` ,
141- ` test_adapter_auxiliary_disk ` , ` test_position_tail_spill ` ,
297+ ` test_id_pair_store_ram ` , ` test_adapter_idpair_ram ` , ` test_scratch_slab_layout ` ,
298+ ` test_scratch_defaults ` , ` test_adapter_auxiliary_disk ` , ` test_position_tail_spill ` ,
142299` test_position_tail_scale_out ` , and ` test_position_tail_scale_out_100k ` .
143300The full release/debug CTest logs must also show every recorded-hash consumer
144- passing and include the unchanged 100k row's elapsed time. The previous-header
145- fail-before compilation of the new unit remains required; its expected first
146- diagnostic is the additional ` IdPairStore ` template argument, not a recorded
147- run result .
301+ passing and include the unchanged 100k row's elapsed time. The original
302+ WL-PTAILFIX fixture targeted c15d224588, whose ` IdPairStore ` lacked the
303+ ordered-fold template argument. The slab fixture instead uses the
304+ ba5bfdcfb2 fail-before protocol above; neither expectation is a recorded run .
148305
149306## Separate percentage-exit history walk (unchanged)
150307
0 commit comments