|
| 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. |
0 commit comments