Skip to content

Commit d41311c

Browse files
luisleo526claude
andcommitted
o1w-slabfold: bounded per-write fold for the consumed-table slab (id_pair_slab_fold.hpp), supervisor commit
Executor result of lane core-cr150-o1w-slabfold (Codex gpt-6.1-sol), committed by the supervisor. Design (b): a sorted offset roster and per-bucket transforms kept inside the existing slab index, reusing BrokerStateByteFold, replace the rebuild of the whole sorted fold on every write that publish_fold did in slab mode (about L*N row comparisons and 257*L byte folds per write, about 33 million comparisons per write at the production K_c = 4096; found by the Claude read of merge M1). fold_sorted runs about twice per recorded bar (scheduler hash append, host refresh after bar close), so a lazy rebuild was rejected; the caller trace is in docs/design/consumed-partial-exit-fold.md. Reasoned bound at 4,096 keys: 13 row comparisons, at most 257 rows refolded (1,585,176 byte steps for eight-byte keys), 32 map compositions per write; a new insert may shift O(N) offsets. Reserves 115,200 of the existing 131,072 index bytes; no allocation or file IO on the write path; the 32 KiB static_assert stays. The digest is unchanged (bit-identical to the sorted enumerate/sort/relookup fold; oracle old_sorted_fold). Tests added in tests/test_id_pair_ordered_fold.cpp: slab_work_bound_and_oracle_4096(false/true), slab_work_counters_observe_the_old_byte_loop, slab_fold_layout_fits_every_index_tier, slab_data_refusal_preserves_fold_and_index; the 12-key fixture is intact. NOT VERIFIED: no compile, no test, no measurement ran on this commit. The bounds above are from reading. Lab first: backport only the observation hooks onto ba5bfdc and obtain the expected fail-before "4096-key slab fold exceeds 13 row comparisons/write"; then test_id_pair_ordered_fold, test_id_pair_store_ram, test_adapter_idpair_ram, test_id_pair_store, test_adapter_auxiliary_disk, position-tail rows, preflight, release, debug. Co-Authored-By: Claude Sonnet 5.5 <[email protected]>
1 parent ba5bfdc commit d41311c

4 files changed

Lines changed: 699 additions & 40 deletions

File tree

‎docs/design/consumed-partial-exit-fold.md‎

Lines changed: 167 additions & 10 deletions
Original file line numberDiff line numberDiff line change
@@ -1,4 +1,4 @@
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
2323
loop. String length and signed cycle value use its native byte spelling;
2424
there is no format, domain, endian, count, or version change.
2525

26-
## Ordered structure and work
26+
## Ordered disk structure and work
2727

2828
The auxiliary index is a compressed binary radix tree with buckets of at
2929
most 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
5050
runs maintain the same root, so an unrecorded run's terminal hash also has
5151
the 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
57172
buffers, rehash buffers, headers and scalar frames to 32 KiB. There is no
58173
per-distinct-key resident allocation. The explicit memory-reference fixture
59174
is 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

129285
No existing test assertions or the L18 fixture size/recording are changed.
130286
Required 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
134290
lab 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

139295
The 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`.
143300
The 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

Comments
 (0)