nx_hash_index_bench.nx source
↩ module page · 128 lines · 6571 B
1// nx_hash_index_bench.nx -- IN-NISHI read-path exceed: sovereign O(1) hash index vs binary search.
2// Honest finding: the seg_store binary-search get (~502 ns/op, ~15 variable-length key compares) is SLOWER
3// than sqlite's cached B-tree probe (~250 ns, measured once as the cited 3rd-party baseline). The read path
4// was a DEFICIT, not an exceed. The Nishi-ecosystem fix (no shells): an O(1) sovereign hash index -- FNV-1a
5// over the key -> open-addressing linear-probe table -> 1 hash + ~1 compare per get. This organ builds both
6// a sorted index (binary search) and the hash index over the SAME 20000 keys and times 20000 gets each, in
7// one run, fully in-Nishi. sqlite ~250 ns/get = CITED by-design reference (the doctrine: prove vs 3rd-party
8// in the harness; here cited, not shell-run).
9// KAT: both indexes correct (all 20000 gets hit); the hash get is FASTER than binary search (the in-Nishi win);
10// reports hash ns/op vs sqlite's cited 250 ns (the read exceed, if hit). No hw writes (Rule 26).
11// expect_exit: 0 license_tier: ORIGINAL
12import "nx_syscalls.nx"
13import "nx_itoa_lib.nx" // shared MSB-first emitter (zero-alloc)
14const K_MAGIC_20000: i64 = 20000
15const K_MAGIC_7919: i64 = 7919
16
17const TBL: i64 = 32768
18const HMASK: i64 = 32767
19const FNVP: i64 = 1099511628211
20
21func 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 }
22// MIGRATED to the shared emitter (debt 1785563586). The old body mmapped a scratch buffer
23// per call and never freed it. At page granularity that is 4096B leaked PER CALL -- the
24// defect that took 28.5GB of a 36GB host in nx_ts_lumadiff. A BENCH is the worst home for
25// it: its purpose is millions of iterations. nxi_* is MSB-first and allocates NOTHING.
26func h_num(v: i64) -> i64 { nxi_out(v); return 0 }
27func kptr(keys: *u8, i: i64) -> *u8 { return ((keys as i64) + i*9) as *u8 }
28func 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 }
29func 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 }
30// LSD radix sort sidx by 9-byte keys (for the binary-search baseline)
31func radix9(keys: *u8, sidx: *i64, n: i64, tmp: *i64) -> i64 {
32 let cnt: *i64=sys_mmap(256*8) as *i64
33 var pos: i64=8
34 while pos>=0 {
35 var c: i64=0
36 while c<256 { cnt[c]=0; c=c+1 }
37 var i: i64=0
38 while i<n { let kp: *u8=kptr(keys,sidx[i]); let kb: i64=kp[pos] as i64; cnt[kb]=cnt[kb]+1; i=i+1 }
39 var sm: i64=0
40 c=0
41 while c<256 { let tc: i64=cnt[c]; cnt[c]=sm; sm=sm+tc; c=c+1 }
42 i=0
43 while i<n { let kp: *u8=kptr(keys,sidx[i]); let kb: i64=kp[pos] as i64; tmp[cnt[kb]]=sidx[i]; cnt[kb]=cnt[kb]+1; i=i+1 }
44 i=0
45 while i<n { sidx[i]=tmp[i]; i=i+1 }
46 pos=pos-1
47 }
48 return 0
49}
50func bsearch(keys: *u8, sidx: *i64, n: i64, key: *u8) -> i64 {
51 var lo: i64=0
52 var hi: i64=n-1
53 while lo<=hi {
54 let mid: i64=(lo+hi)/2
55 let rec: i64=sidx[mid]
56 let c: i64=kcmp9(key, kptr(keys,rec))
57 if c==0 { return rec }
58 if c<0 { hi=mid-1 } else { lo=mid+1 }
59 }
60 return 0-1
61}
62
63func main() -> i64 {
64 h_puts("IN-NISHI read-path exceed: sovereign O(1) hash index vs binary search (sqlite ~250ns get = cited baseline)\n" as *u8)
65 let N: i64=K_MAGIC_20000
66 let keys: *u8=sys_mmap(N*9+16)
67 var i: i64=0
68 while i<N { let p: i64=i*9; keys[p]=107 as u8; var v: i64=i; var d: i64=7; while d>=0 { keys[p+1+d]=(48+(v%10)) as u8; v=v/10; d=d-1 } i=i+1 }
69 let probe: *i64=sys_mmap(N*8)
70 i=0
71 while i<N { probe[i]=(i*K_MAGIC_7919)%K_MAGIC_20000; i=i+1 }
72
73 // --- binary-search baseline (radix-sorted index) ---
74 let sidx: *i64=sys_mmap(N*8); let tmp: *i64=sys_mmap(N*8)
75 i=0
76 while i<N { sidx[i]=i; i=i+1 }
77 radix9(keys, sidx, N, tmp)
78 var ok_bs: i64=0
79 let tb0: i64=sys_now_us()
80 i=0
81 while i<N { let tg: i64=probe[i]; let f: i64=bsearch(keys, sidx, N, kptr(keys,tg)); if f==tg { ok_bs=ok_bs+1 } i=i+1 }
82 let tb1: i64=sys_now_us()
83 var bs_us: i64=tb1-tb0
84 if bs_us<=0 { bs_us=1 }
85
86 // --- sovereign hash index (FNV-1a + open addressing) ---
87 let table: *i64=sys_mmap(TBL*8)
88 var b2: i64=0
89 while b2<TBL { table[b2]=0-1; b2=b2+1 }
90 i=0
91 while i<N { let h: i64=khash(kptr(keys,i)); var b: i64=h & HMASK; while table[b]!=(0-1) { b=(b+1) & HMASK } table[b]=i; i=i+1 }
92 var ok_h: i64=0
93 var probes: i64=0
94 let th0: i64=sys_now_us()
95 i=0
96 while i<N {
97 let tg: i64=probe[i]
98 let kp: *u8=kptr(keys,tg)
99 let h: i64=khash(kp)
100 var b: i64=h & HMASK
101 var found: i64=0-1
102 var go: i64=1
103 while go==1 { probes=probes+1; if table[b]==(0-1) { go=0 } else { if kcmp9(kp, kptr(keys,table[b]))==0 { found=table[b]; go=0 } else { b=(b+1) & HMASK } } }
104 if found==tg { ok_h=ok_h+1 }
105 i=i+1
106 }
107 let th1: i64=sys_now_us()
108 var hash_us: i64=th1-th0
109 if hash_us<=0 { hash_us=1 }
110
111 let bs_ns: i64=bs_us*1000/N
112 let hash_ns: i64=hash_us*1000/N
113 let avg_probes10: i64=probes*10/N
114
115 h_puts(" binary-search get = "); h_num(bs_ns); h_puts(" ns/op | sovereign HASH get = "); h_num(hash_ns); h_puts(" ns/op (avg "); h_num(avg_probes10/10); h_puts("."); h_num(avg_probes10%10); h_puts(" probes/get)\n" as *u8)
116 h_puts(" cited sqlite get ~ 250 ns/op (by-design reference)\n" as *u8)
117
118 var pass: i64=0
119 var ttl: i64=0
120 ttl=ttl+1; h_puts(" T1 binary-search index correct (all 20000 gets hit): " as *u8); if ok_bs==N { pass=pass+1; h_puts("PASS\n" as *u8) } else { h_puts("FAIL\n" as *u8) }
121 ttl=ttl+1; h_puts(" T2 hash index correct (all 20000 gets hit): " as *u8); if ok_h==N { pass=pass+1; h_puts("PASS\n" as *u8) } else { h_puts("FAIL\n" as *u8) }
122 ttl=ttl+1; h_puts(" T3 hash get FASTER than binary search (in-Nishi win): " as *u8); if hash_ns<bs_ns { pass=pass+1; h_puts("PASS\n" as *u8) } else { h_puts("FAIL\n" as *u8) }
123 ttl=ttl+1; h_puts(" T4 hash get BEATS the cited sqlite 250 ns (read-path exceed): " as *u8); if hash_ns<250 { pass=pass+1; h_puts("PASS -> EXCEEDS\n" as *u8) } else { h_puts("not yet (hash_ns>=250)\n" as *u8) }
124
125 h_puts("NISHIOS-HASH-GET-GATE passed "); h_num(pass); h_puts("/"); h_num(ttl)
126 if pass>=3 { h_puts(" verdict=GREEN (sovereign O(1) hash get beats binary search in-Nishi; vs sqlite reported honestly)\n" as *u8); sys_exit(0); return 0 }
127 h_puts(" verdict=RED\n" as *u8); sys_exit(1); return 1
128}