nx_hash_index_test.nx source
↩ module page · 81 lines · 3924 B
1// nx_hash_index_test.nx -- proves the reusable nx_hash_index library on VARIABLE-LENGTH keys (what the
2// real seg_store uses): correctness (every key round-trips, absent keys miss) + O(1) speed vs a linear scan.
3// expect_exit: 0 license_tier: ORIGINAL
4import "nx_hash_index.nx"
5
6func ht_puts(s: *u8) -> i64 { var n: i64=0; while s[n]!=(0 as u8){n=n+1} sys_write(1,s,n); return 0 }
7func ht_num(v: i64) -> i64 { let b: *u8=sys_mmap(28); var m: i64=v; if m<0{m=0-m;sys_write(1,"-" as *u8,1)} let t: *u8=sys_mmap(28); var k: i64=0; if m==0{t[0]=48 as u8;k=1} while m>0{t[k]=(48+(m%10)) as u8;m=m/10;k=k+1} var i: i64=0; while i<k{b[i]=t[k-1-i];i=i+1} sys_write(1,b,k); return 0 }
8
9func main() -> i64 {
10 ht_puts("nx_hash_index test: O(1) hash get on VARIABLE-LENGTH keys (the seg_store case)\n" as *u8)
11 let N: i64=10000
12 // build variable-length keys: key i = "k" + decimal(i) (lengths 2..6)
13 let kbuf: *u8=sys_mmap(N*8+16)
14 let koff: *i64=sys_mmap(N*8)
15 let klen: *i64=sys_mmap(N*8)
16 var w: i64=0
17 var i: i64=0
18 while i<N {
19 koff[i]=w
20 kbuf[w]=107 as u8; w=w+1 // 'k'
21 // decimal of i (no leading zeros -> variable length)
22 let t: *u8=sys_mmap(16)
23 var m: i64=i
24 var d: i64=0
25 if m==0 { t[0]=48 as u8; d=1 }
26 while m>0 { t[d]=(48+(m%10)) as u8; m=m/10; d=d+1 }
27 var j: i64=0
28 while j<d { kbuf[w]=t[d-1-j]; w=w+1; j=j+1 }
29 klen[i]=w-koff[i]
30 i=i+1
31 }
32
33 // build the hash index (16384 buckets > 10000/0.7)
34 let h: *i64=hi_new(16384)
35 i=0
36 while i<N { hi_put(h, ((kbuf as i64)+koff[i]) as *u8, klen[i], i); i=i+1 }
37
38 // correctness: every key round-trips to its value
39 var ok: i64=0
40 i=0
41 while i<N { if hi_get(h, ((kbuf as i64)+koff[i]) as *u8, klen[i])==i { ok=ok+1 } i=i+1 }
42 // negative control: an absent key misses
43 let absent: i64=hi_get(h, "k99999999\x00" as *u8, 9)
44
45 // speed: time N hash gets vs N linear scans (probe a permutation)
46 let th0: i64=sys_now_us()
47 var sink: i64=0
48 i=0
49 while i<N { let tg: i64=(i*7919)%N; let r: i64=hi_get(h, ((kbuf as i64)+koff[tg]) as *u8, klen[tg]); sink=sink+r; i=i+1 }
50 let th1: i64=sys_now_us()
51 var hash_us: i64=th1-th0
52 if hash_us<=0 { hash_us=1 }
53 // linear scan baseline (the naive get): scan all keys comparing
54 let tl0: i64=sys_now_us()
55 var lin_hits: i64=0
56 i=0
57 while i<N {
58 let tg: i64=(i*7919)%N
59 let kp: *u8=((kbuf as i64)+koff[tg]) as *u8
60 let kl: i64=klen[tg]
61 var j: i64=0
62 var go: i64=1
63 while go==1 { if j>=N { go=0 } else { if hi_keq(((kbuf as i64)+koff[j]) as *u8, klen[j], kp, kl)==1 { lin_hits=lin_hits+1; go=0 } else { j=j+1 } } }
64 i=i+1
65 }
66 let tl1: i64=sys_now_us()
67 var lin_us: i64=tl1-tl0
68 if lin_us<=0 { lin_us=1 }
69
70 ht_puts(" hash get = "); ht_num(hash_us*1000/N); ht_puts(" ns/op linear-scan get = "); ht_num(lin_us*1000/N); ht_puts(" ns/op (sink="); ht_num(sink&1); ht_puts(")\n" as *u8)
71
72 var pass: i64=0
73 var ttl: i64=0
74 ttl=ttl+1; ht_puts(" T1 all variable-length keys round-trip (correctness): " as *u8); if ok==N { pass=pass+1; ht_puts("PASS\n" as *u8) } else { ht_puts("FAIL\n" as *u8) }
75 ttl=ttl+1; ht_puts(" T2 absent key misses (neg control): " as *u8); if absent==(0-1) { pass=pass+1; ht_puts("PASS\n" as *u8) } else { ht_puts("FAIL\n" as *u8) }
76 ttl=ttl+1; ht_puts(" T3 hash get is O(1) -- far faster than linear scan: " as *u8); if hash_us*4<lin_us { pass=pass+1; ht_puts("PASS\n" as *u8) } else { ht_puts("FAIL\n" as *u8) }
77
78 ht_puts("NX-HASH-INDEX-TEST passed "); ht_num(pass); ht_puts("/"); ht_num(ttl)
79 if pass==ttl { ht_puts(" verdict=GREEN (reusable sovereign hash index: variable-length keys, correct + O(1) -- ready for seg_store)\n" as *u8); sys_exit(0); return 0 }
80 ht_puts(" verdict=RED\n" as *u8); sys_exit(1); return 1
81}