Skip to content

Commit 4d6cd2b

Browse files
luisleo526claude
andcommitted
CR-150 WL-PTAILFIX: maintain the consumed partial-exit table's sorted hash fold incrementally on disk (exact, O(1) per hash)
hash_state used to enumerate every consumed partial-exit key, sort them and look each value up again, per hash: Theta(N^2) disk reads for the 100k scale-out row (test_position_tail_scale_out_100k ran 3 h 35 min without finishing on a box). IdPairStore now (optionally, for the consumed table only) keeps a disk-backed ordered structure over its keys in std::string lexical order. Interior nodes hold the exact byte-recurrence transform of their subtree (257 words, because the FNV step h ^= byte; h *= prime depends on the seed only through h mod 256 and h / 256); leaves hold 16-record buckets recomputed from their records. fold_sorted(sink) emits the same count and then applies the root transform to the incoming hash state, so the digest equals the former sorted enumerate/sort/relookup loop for every state and every incoming seed. The old loop is kept as the reference in tests/test_id_pair_ordered_fold.cpp. No hash format change. Resident memory is a fixed root and buffers (static_assert 32 KiB); disk cost about 139 to 278 bytes per key at 8 to 16 records per bucket plus a journal. The percentage-exit history walk (pine_adapter.cpp) is a separate quadratic path and is unchanged. Authored by the core-cr150-ptailfix lane; committed by the supervisor because the lane's sandbox could not write the worktree's git metadata. Nothing in this commit has been built or run: lab proof pending. Co-Authored-By: Claude Sonnet 5.5 <[email protected]>
1 parent c15d224 commit 4d6cd2b

10 files changed

Lines changed: 1164 additions & 116 deletions
Lines changed: 170 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,170 @@
1+
# Consumed partial-exit ordered fold (WL-PTAILFIX)
2+
3+
`PineExecutionAdapter::hash_state` retains its existing count followed by
4+
`BrokerStateHashSink::s(key)` and `::i(cycle)` in `std::string` lexical order.
5+
The consumed-cycle `IdPairStore` opts into an auxiliary ordered fold; the
6+
ordinary minima stores do not. The table's hash index, record format, exact
7+
key comparison, and first-seen disk iteration remain its lookup authority.
8+
9+
## Exact seed action
10+
11+
For any byte sequence S, let F be its action on a 64-bit incoming sink state.
12+
One byte changes only the low eight bits before multiplication. Consequently,
13+
modulo 2^64:
14+
15+
```
16+
F(256*q + r) = F(r) + q * (F(256) - F(0)), 0 <= r < 256.
17+
```
18+
19+
`BrokerStateByteFold` stores F(0)..F(256), 257 words / 2,056 bytes.
20+
Concatenating X followed by Y replaces each stored X(r) with Y(X(r)). This
21+
uses the incoming seed, including every higher bit, rather than a cached
22+
digest for one seed. Construction calls the real `BrokerStateHashSink` byte
23+
loop. String length and signed cycle value use its native byte spelling;
24+
there is no format, domain, endian, count, or version change.
25+
26+
## Ordered structure and work
27+
28+
The auxiliary index is a compressed binary radix tree with buckets of at
29+
most 16 original table offsets. Only interior branches store transforms.
30+
End-of-key is the nine-bit symbol 0 and byte b is symbol b+1. Comparing these
31+
symbols most-significant-bit first preserves unsigned byte order, including
32+
prefixes, empty strings, NUL, 0x1f, and 0xff. A pivot stores its byte index and
33+
bit mask separately, avoiding a key-length multiplication/overflow limit.
34+
35+
A new key that differs in a compressed prefix inserts a branch above the
36+
existing subtree. A full bucket splits at the first differing symbol of its
37+
least and greatest keys. Replacements and erase/reinsert retain original
38+
table records and bucket offsets; an erased row contributes the identity
39+
map. Ancestors compose the changed child with their unchanged sibling.
40+
41+
For maximum key length L, radix depth D is at most 9*(L+1), independent of
42+
the number of keys. There is no growing RAM stack: the descent path lives in
43+
the disk journal. Each update visits that path and folds at most 16 records
44+
per leaf it reads. A conservative byte-operation bound is
45+
O(257 * 16 * (L+16) * (D+1)), hence O(1) at fixed L. The existing hash-index
46+
lookup and geometric growth retain their expected amortised bound.
47+
48+
Each hash folds the existing eight-byte count and applies the resident root
49+
map: O(1), zero auxiliary file reads/writes and zero allocation. Ordinary
50+
runs maintain the same root, so an unrecorded run's terminal hash also has
51+
the same byte semantics.
52+
53+
## RAM, disk, and addressable population
54+
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
57+
buffers, rehash buffers, headers and scalar frames to 32 KiB. There is no
58+
per-distinct-key resident allocation. The explicit memory-reference fixture
59+
is excluded from that production disk-backend bound.
60+
61+
Let N be distinct keys ever seen, B be bucket count, and J be the deepest
62+
saved path (including its leaf). The fold adds exactly these logical bytes:
63+
64+
```
65+
136*B + 2088*(B-1) + 2096*J for a nonempty tree
66+
```
67+
68+
The ordinary table still uses `40 + key_length` bytes per record, plus its
69+
16-byte index slots at half load (32..64 bytes/key after warmup). At 8..16
70+
records/bucket the fold's node cost is about 139..278 bytes/key, plus the
71+
reusable journal; bucket occupancy is input-dependent. The conservative
72+
degenerate bound is less than 4,320 extra bytes/key including the journal
73+
(B <= N and J <= B). This is a storage tradeoff, not a claim of measured
74+
occupancy. The new 10,000-key binary fixture asserts total table+fold storage
75+
below 700 bytes/key and prints its actual logical bytes for lab readback.
76+
Updates reuse nodes and reuse the journal after the deepest path is warmed.
77+
78+
A single transform file would impose an earlier `off_t` limit than the old
79+
table. `IdPairFoldFile` instead uses fixed arrays of lazily opened segments
80+
covering the old table's entire `(OFF_MAX/64)+1` distinct-key population.
81+
On 64-bit hosts there are three possible leaf segments, 33 branch segments,
82+
and 33 journal segments; normal populations open one of each. Offsets are
83+
computed within a segment, rather than multiplying the total population by
84+
the map size. Disk-byte accounting saturates at UINT64_MAX instead of
85+
refusing a population whose combined files exceed that reporting range.
86+
All segments use `IdPairScratchFile::open` and its existing scratch directory.
87+
88+
## Publication and failures
89+
90+
The files are anonymous per-run scratch, not crash-recovery storage. Before
91+
any published radix node is modified, the complete old path and leaf are
92+
written to the reusable disk journal. A journal failure changes no live
93+
node. A subsequent failure leaves the previous resident root and table
94+
visible. The next mutation restores the old node images before using the
95+
tree; restoration can itself fail and be retried without invalidating
96+
lookup, iteration, or the cached old root.
97+
98+
The table keeps one committed header and, for an append, one index slot as
99+
fixed resident pending writes. Every header/slot read consults those values.
100+
Both are flushed before either overlay is discarded or the next mutation
101+
starts. Thus even a partial in-place table flush leaves the committed values
102+
readable. A new record's strings are staged beyond the old logical end.
103+
After radix IO succeeds, root, pending table writes, logical end and counts
104+
are published without any further throwing work. A failed index growth
105+
still discards only its incomplete replacement file.
106+
107+
Move carries the cached root, pending table writes, all segment descriptors
108+
and any recovery journal. Clear closes them, restores the identity map and
109+
retains the fixture backend choice and scratch-directory configuration.
110+
111+
## Tests and remote verification
112+
113+
`test_id_pair_ordered_fold` adds the following checks:
114+
115+
- The former enumerate/sort/relookup loop is the test-only oracle. It uses
116+
the actual `BrokerStateHashSink`; table contents are independently checked
117+
against a reference map at every mutation.
118+
- Shuffled random binary sets, random replacements, erase/reinsert, prefixes,
119+
empty/NUL/0x1f/high-byte keys, 513/4,097-byte keys, extreme signed values,
120+
unrelated full-width seeds and all 256 low-byte residues.
121+
- Move, reset, first-seen disk iteration, memory-fixture independence,
122+
10-to-10,000-key flat heap, allocation refusal during hashing, actual IO
123+
counts, bounded amortised mutation IO, and disk reuse.
124+
- Short writes at each write boundary for append/index growth, long-key
125+
append, replacement and erase; a second failure during retry; move with
126+
recovery outstanding; equality of all old rows and their fold after faults.
127+
- Fixed segmented-file capacity under a simulated small offset ceiling.
128+
129+
No existing test assertions or the L18 fixture size/recording are changed.
130+
Required remote checks, on the exact candidate tree, are preflight, docs,
131+
full corpus parity, release and debug. In `lab remote` terminology:
132+
133+
```sh
134+
lab remote submit --repo engine --worktree <candidate-checkout> \
135+
--steps preflight,docs,parity,release,debug --host auto --keep-going \
136+
--label core-cr150-ptailfix
137+
```
138+
139+
The C++ targets/CTest names to inspect explicitly are
140+
`test_id_pair_ordered_fold`, `test_id_pair_store`,
141+
`test_adapter_auxiliary_disk`, `test_position_tail_spill`,
142+
`test_position_tail_scale_out`, and `test_position_tail_scale_out_100k`.
143+
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.
148+
149+
## Separate percentage-exit history walk (unchanged)
150+
151+
`PineExecutionAdapter::exit` still walks closed trades in reverse to
152+
the position-start barrier, then continues through `PositionTailSpill` when
153+
the resident walk reaches its base. Every qualifying percentage exit repeats
154+
that walk, including rows whose incarnation no longer qualifies. Its work
155+
is Theta(sum of history lengths), hence Theta(N^2) for an unbroken position.
156+
157+
The 100k feed has 400,004 bars and 100,001 qualifying exit calls. In its FIFO
158+
shape the first exit closes one slice and every subsequent exit closes two.
159+
Before call j+1 there are 2*j-1 closed rows (j>=1). Summing the preceding
160+
histories gives `sum(j=1..100000, 2*j-1) = 10,000,000,000` row visits per
161+
principal execution, or 20,000,000,000 across sink-off and sink-on. This is
162+
a code-derived count, not a timing measurement. The streamed rows have
163+
96-byte IDs plus 30-byte footers, about 1.26 TB of repeated window coverage
164+
for its principal execution, apart from its small resident tail.
165+
166+
That remaining walk can still take hours after hashing is fixed. A future
167+
fix must preserve position-start filtering, direction, live-incarnation
168+
ancestry, FIFO/from_entry selection, the distinct margin-call rule, and the
169+
reverse-order binary64 accumulation used for percentage reservation. A
170+
reassociated sum can change quantities and trades. No such fix is included.

‎docs/design/cr150-contracts.md‎

Lines changed: 1 addition & 1 deletion
Original file line numberDiff line numberDiff line change
@@ -212,7 +212,7 @@ references; L15a must maintain these anchors and mechanically pin every current
212212
| Adapter projection validation: use the context normalizer; host stages after lending and before projection, using a context built from its store | `normalize_projected_spec` `src/source/pine_adapter.cpp:3009-3015` | 361-363; V1/V2 change 5 |
213213
| Instrument-feed digest and cached/uncached continuation folds | `digest_instrument_feed_views` `src/native_run_spec.cpp:1162-1205`; `native_instrument_feeds_digest` `src/native_execution_consumer.cpp:322-324`; `native_instrument_feeds_digest` `src/native_execution_consumer.cpp:2775-2776`; `native_run_spec_digest` `src/native_execution_consumer.cpp:13634-13639` | 364-365 |
214214
| Staged feed counts in host state and its hash | `installed_symbol_feed` `src/source/pine_strategy_host.cpp:234-244`; `staged_.instrument_feeds` `src/source/pine_state_hash.cpp:294-301` | 366-367 |
215-
| Refresh of symbol-data digest and host hash fold | `refresh_symbol_data_digest` `src/source/pine_security_eval.cpp:1553-1566`; `symbol_data_digest_` `src/source/pine_state_hash.cpp:1191-1197` | 367-368 |
215+
| Refresh of symbol-data digest and host hash fold | `refresh_symbol_data_digest` `src/source/pine_security_eval.cpp:1553-1566`; `symbol_data_digest_` `src/source/pine_state_hash.cpp:1190` | 367-368 |
216216
| Restore/store upkeep and column-setter length check | `held.bars` `src/source/pine_security_eval.cpp:1091-1101`; `data.bars` `src/source/pine_security_eval.cpp:1433-1439` | 369-370 |
217217
| Lower-path preflight/validation | `NativeExecutionConsumer::preflight_intrabar_path` `src/native_execution_consumer.cpp:3230-3305` | 371,1221-1222 |
218218
| Lower-path digest (count first) and continuation hash | `native_intrabar_path_digest` `src/native_run_spec.cpp:891-919`; `native_intrabar_path_digest` `src/native_execution_consumer.cpp:289` | 371,1223-1224 |

0 commit comments

Comments
 (0)