nx_livemap_fast.nx source

1// nx_livemap_fast.nx -- LINEAR live-doc map construction, to replace the quadratic one in ss_open2. 2// 3// THE PROBLEM (nx_seg_store.nx:1739-1790): for every key in every segment, the current code scans 4// EVERY NEWER SEGMENT calling ss_idx_find to ask `has a later segment shadowed this key`. That is 5// O(keys x segments) index probes -- tens of millions on the live 94-segment web shard -- and it is 6// QUADRATIC IN SEGMENT COUNT, so it degrades every time the crawler commits. It is the measured 7// cause of the ~8 minute docportal pre-warm and, through that, of tonight's search wedge. 8// 9// THE INSIGHT: the shadow question is `does any NEWER segment know this key`. Answering it per-key 10// by rescanning newer segments repeats the same work once per key. Walk the segments ONCE from 11// NEWEST to OLDEST instead, recording the first (= newest) segment that knows each key. Then a key 12// in segment s is shadowed iff its recorded newest segment is greater than s. One pass, one probe. 13// 14// NOTHING HERE IS WIRED INTO PRODUCTION. This file only ADDS functions; ss_open2 is untouched. The 15// companion gate proves this produces BYTE-IDENTICAL maps to the existing implementation on the real 16// shard before anyone considers swapping. A faster live-doc map that is subtly different does not 17// make search quick, it makes search WRONG -- these maps decide which documents are visible at all. 18// license_tier: ORIGINAL No hw writes (Rule 26). 19import "nx_seg_store.nx" 20const LMF_MAGIC_16777619: i64 = 16777619 21 22const LMF_LOAD_NUM: i64 = 2 // table sized 2x key count: open addressing wants <=50% load 23const LMF_EMPTY: i64 = 0 - 1 24 25// Round up to a power of two so the probe can mask instead of divide. 26func lmf_pow2(n: i64) -> i64 { 27 var p: i64 = 16 28 while p < n { p = p * 2 } 29 return p 30} 31 32// Total key-index entries across all segments -- sizes the table in one cheap pass. 33func lmf_total_keys(h: *i64, ns: i64) -> i64 { 34 var t: i64 = 0 35 var s: i64 = 0 36 while s < ns { 37 let kb: *u8 = h[1 + 8 * s] as *u8 38 let ksz: i64 = h[2 + 8 * s] 39 if ksz >= 8 { t = t + ss_r32(kb, 4) } 40 s = s + 1 41 } 42 return t 43} 44 45// Compare a key stored in segment `seg` at entry offset `eo` against a candidate byte range. 46func lmf_key_eq(h: *i64, seg: i64, eo: i64, kb2: *u8, eo2: i64) -> i64 { 47 let kb: *u8 = h[1 + 8 * seg] as *u8 48 let kl: i64 = ss_r32(kb, eo + 1) 49 let kl2: i64 = ss_r32(kb2, eo2 + 1) 50 if kl != kl2 { return 0 } 51 var i: i64 = 0 52 while i < kl { 53 if kb[eo + 5 + i] != kb2[eo2 + 5 + i] { return 0 } 54 i = i + 1 55 } 56 return 1 57} 58 59// FNV over the key bytes of one index entry. 60func lmf_hash_entry(kb: *u8, eo: i64) -> i64 { 61 let kl: i64 = ss_r32(kb, eo + 1) 62 var hsh: i64 = 0x811c9dc5 63 var i: i64 = 0 64 while i < kl { 65 hsh = hsh ^ (kb[eo + 5 + i] as i64) 66 hsh = (hsh * LMF_MAGIC_16777619) & 0xffffffff 67 i = i + 1 68 } 69 return hsh 70} 71 72// Build key -> NEWEST segment that knows it. tbl_seg/tbl_eo are parallel arrays of size cap. 73// Walking newest-first and refusing to overwrite an occupied slot means the FIRST writer wins, 74// which is by construction the newest segment. No comparison of segment numbers is needed. 75func lmf_build(h: *i64, ns: i64, tbl_seg: *i64, tbl_eo: *i64, cap: i64) -> i64 { 76 var i: i64 = 0 77 while i < cap { tbl_seg[i] = LMF_EMPTY; i = i + 1 } 78 let mask: i64 = cap - 1 79 var inserted: i64 = 0 80 var s: i64 = ns - 1 81 while s >= 0 { 82 let kb: *u8 = h[1 + 8 * s] as *u8 83 let ksz: i64 = h[2 + 8 * s] 84 if ksz >= 8 { 85 let m: i64 = ss_r32(kb, 4) 86 var e: i64 = 0 87 while e < m { 88 let eo: i64 = 8 + 4 * m + ss_r32(kb, 8 + 4 * e) 89 let kl: i64 = ss_r32(kb, eo + 1) 90 if kl < 500 { 91 var slot: i64 = lmf_hash_entry(kb, eo) & mask 92 var placed: i64 = 0 93 while placed == 0 { 94 if tbl_seg[slot] == LMF_EMPTY { 95 tbl_seg[slot] = s 96 tbl_eo[slot] = eo 97 inserted = inserted + 1 98 placed = 1 99 } else { 100 if lmf_key_eq(h, tbl_seg[slot], tbl_eo[slot], kb, eo) == 1 { 101 placed = 1 // already recorded by a NEWER segment: keep it 102 } else { 103 slot = (slot + 1) & mask 104 } 105 } 106 } 107 } 108 e = e + 1 109 } 110 } 111 s = s - 1 112 } 113 return inserted 114} 115 116// Newest segment known to contain the key at (kb, eo); -1 if absent. 117func lmf_lookup(h: *i64, tbl_seg: *i64, tbl_eo: *i64, cap: i64, kb: *u8, eo: i64) -> i64 { 118 let mask: i64 = cap - 1 119 var slot: i64 = lmf_hash_entry(kb, eo) & mask 120 var guard: i64 = 0 121 while guard < cap { 122 if tbl_seg[slot] == LMF_EMPTY { return 0 - 1 } 123 if lmf_key_eq(h, tbl_seg[slot], tbl_eo[slot], kb, eo) == 1 { return tbl_seg[slot] } 124 slot = (slot + 1) & mask 125 guard = guard + 1 126 } 127 return 0 - 1 128}