nx_hash_index_bench.nx
buildroot/runtime/nx_hash_index_bench.nx
about
nx_hash_index_bench.nx -- IN-NISHI read-path exceed: sovereign O(1) hash index vs binary search.
Honest finding: the seg_store binary-search get (~502 ns/op, ~15 variable-length key compares) is SLOWER
than sqlite's cached B-tree probe (~250 ns, measured once as the cited 3rd-party baseline). The read path
was a DEFICIT, not an exceed. The Nishi-ecosystem fix (no shells): an O(1) sovereign hash index -- FNV-1a
over the key -> open-addressing linear-probe table -> 1 hash + ~1 compare per get. This organ builds both
a sorted index (binary search) and the hash index over the SAME 20000 keys and times 20000 gets each, in
one run, fully in-Nishi. sqlite ~250 ns/get = CITED by-design reference (the doctrine: prove vs 3rd-party
in the harness; here cited, not shell-run).
KAT: both indexes correct (all 20000 gets hit); the hash get is FASTER than binary search (the in-Nishi win);
reports hash ns/op vs sqlite's cited 250 ns (the read exceed, if hit). No hw writes (Rule 26).
expect_exit: 0 license_tier: ORIGINAL
dependencies 2 imports · 0 importers
imports: nx_syscalls.nxnx_itoa_lib.nx
imported by: nobody (leaf or entry point)
call flow from main pre-order; caps 40 nodes / depth 6 declared; ↻ = already shown
structs
| none |
consts
| 14 | const K_MAGIC_20000: i64 = 20000 |
| 15 | const K_MAGIC_7919: i64 = 7919 |
| 17 | const TBL: i64 = 32768 |
| 18 | const HMASK: i64 = 32767 |
| 19 | const FNVP: i64 = 1099511628211 |
functions
| 21 | func h_puts(s: *u8) -> i64 { var n: i64=0; while s[n]!=(0 as u8){n=n+1} sys_write(1,s,n); return 0 } |
| 26 | func h_num(v: i64) -> i64 { nxi_out(v); return 0 } |
| 27 | func kptr(keys: *u8, i: i64) -> *u8 { return ((keys as i64) + i*9) as *u8 } |
| 28 | func kcmp9(a: *u8, b: *u8) -> i64 { var i: i64=0; while i<9 { let x: i64=a[i] as i64; let y: i64=b[i] as i64; if x<y { return 0-1 } if x>y { return 1 } i=i+1 } return 0 } |
| 29 | func khash(k: *u8) -> i64 { var h: i64=0; var i: i64=0; while i<9 { h=(h ^ (k[i] as i64)) * FNVP; i=i+1 } return h } called by 1: main |
| 31 | func radix9(keys: *u8, sidx: *i64, n: i64, tmp: *i64) -> i64 |
| 50 | func bsearch(keys: *u8, sidx: *i64, n: i64, key: *u8) -> i64 |
| 63 | func main() -> i64 |