code wiki / _hdl_build / nx_livemap_fast.nx
nx_livemap_fast.nx
buildroot/runtime/_hdl_build/nx_livemap_fast.nx
about
nx_livemap_fast.nx -- LINEAR live-doc map construction, to replace the quadratic one in ss_open2.
THE PROBLEM (nx_seg_store.nx:1739-1790): for every key in every segment, the current code scans
EVERY NEWER SEGMENT calling ss_idx_find to ask `has a later segment shadowed this key`. That is
O(keys x segments) index probes -- tens of millions on the live 94-segment web shard -- and it is
QUADRATIC IN SEGMENT COUNT, so it degrades every time the crawler commits. It is the measured
cause of the ~8 minute docportal pre-warm and, through that, of tonight's search wedge.
THE INSIGHT: the shadow question is `does any NEWER segment know this key`. Answering it per-key
by rescanning newer segments repeats the same work once per key. Walk the segments ONCE from
NEWEST to OLDEST instead, recording the first (= newest) segment that knows each key. Then a key
in segment s is shadowed iff its recorded newest segment is greater than s. One pass, one probe.
NOTHING HERE IS WIRED INTO PRODUCTION. This file only ADDS functions; ss_open2 is untouched. The
companion gate proves this produces BYTE-IDENTICAL maps to the existing implementation on the real
shard before anyone considers swapping. A faster live-doc map that is subtly different does not
make search quick, it makes search WRONG -- these maps decide which documents are visible at all.
license_tier: ORIGINAL No hw writes (Rule 26).
dependencies 1 imports · 1 importers
imports: nx_seg_store.nx
imported by: nx_livemap_fast_gate.nx
structs
| none |
consts
| 20 | const LMF_MAGIC_16777619: i64 = 16777619 |
| 22 | const LMF_LOAD_NUM: i64 = 2 // table sized 2x key count: open addressing wants <=50% load |
| 23 | const LMF_EMPTY: i64 = 0 - 1 |
functions
| 26 | func lmf_pow2(n: i64) -> i64 called by 1: main |
| 33 | func lmf_total_keys(h: *i64, ns: i64) -> i64 |
| 46 | func lmf_key_eq(h: *i64, seg: i64, eo: i64, kb2: *u8, eo2: i64) -> i64 |
| 60 | func lmf_hash_entry(kb: *u8, eo: i64) -> i64 |
| 75 | func lmf_build(h: *i64, ns: i64, tbl_seg: *i64, tbl_eo: *i64, cap: i64) -> i64 |
| 117 | func lmf_lookup(h: *i64, tbl_seg: *i64, tbl_eo: *i64, cap: i64, kb: *u8, eo: i64) -> i64 |