code wiki / _hdl_build / nx_livemap_fast.nx

nx_livemap_fast.nx

buildroot/runtime/_hdl_build/nx_livemap_fast.nx

5228 B128 linesdepth 3pulls 3 transitivereach 1 importersview sourcekind library
docsdependenciesstructsconstsfunctions

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

nx_seg_store.nx nx_livemap_fast.nx nx_livemap_fast_gate.nx

imports: nx_seg_store.nx

imported by: nx_livemap_fast_gate.nx

structs

none

consts

20const LMF_MAGIC_16777619: i64 = 16777619
22const LMF_LOAD_NUM: i64 = 2 // table sized 2x key count: open addressing wants <=50% load
23const LMF_EMPTY: i64 = 0 - 1

functions

26func lmf_pow2(n: i64) -> i64
called by 1: main
33func lmf_total_keys(h: *i64, ns: i64) -> i64
called by 1: main calls 1: ss_r32
46func lmf_key_eq(h: *i64, seg: i64, eo: i64, kb2: *u8, eo2: i64) -> i64
called by 2: lmf_buildlmf_lookup calls 1: ss_r32
60func lmf_hash_entry(kb: *u8, eo: i64) -> i64
called by 2: lmf_buildlmf_lookup calls 1: ss_r32
75func lmf_build(h: *i64, ns: i64, tbl_seg: *i64, tbl_eo: *i64, cap: i64) -> i64
called by 1: main calls 3: ss_r32lmf_hash_entrylmf_key_eq
117func lmf_lookup(h: *i64, tbl_seg: *i64, tbl_eo: *i64, cap: i64, kb: *u8, eo: i64) -> i64
called by 1: main calls 2: lmf_hash_entrylmf_key_eq