nx_physics_ladder.nx source
↩ module page · 103 lines · 6826 B
1// nx_physics_ladder.nx -- GENEALOGIST physics-limit grading: how close is the sovereign hash get to the
2// PHYSICS FLOOR? Operator telos: S-class exceed graded on ABSENT->EXISTS->EXCEEDS->NEAR-PHYSICS->PHYSICS-
3// OPTIMUM, not just "beats sqlite". For a key->value lookup the irreducible physics limit is MEMORY-ACCESS
4// LATENCY: you cannot find a value faster than touching the memory that holds it. This measures the real
5// floors on THIS hardware with a dependent pointer-chase (the canonical memory-latency benchmark -- each
6// load's address depends on the previous load, defeating prefetch/OOO so we measure latency, not bandwidth)
7// at two working-set sizes: cache-resident (256KB) and DRAM-resident (64MB > LLC). Then it measures the
8// sovereign hash get and places it on the maturity ladder vs those physics floors.
9// Honest: a lookup must do >=1 random memory access; being at ~1 access = PHYSICS-OPTIMUM (irreducible).
10// No hw writes (Rule 26). expect_exit: 0 license_tier: ORIGINAL
11import "nx_hash_index.nx"
12import "nx_itoa_lib.nx" // shared MSB-first emitter (zero-alloc)
13const K_MAGIC_1664525: i64 = 1664525
14const K_MAGIC_1013904223: i64 = 1013904223
15const K_MAGIC_32768: i64 = 32768
16const K_MAGIC_8000000: i64 = 8000000
17const K_MAGIC_8388608: i64 = 8388608
18const K_MAGIC_20000: i64 = 20000
19const K_MAGIC_7919: i64 = 7919
20
21func pl_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 (2MB input, ~3.66M calls).
25// nxi_* is MSB-first, allocates NOTHING, and emits identical bytes including the sign.
26func pl_num(v: i64) -> i64 { nxi_out(v); return 0 }
27
28// dependent pointer-chase memory latency. arr[i] = next index via a large full-period LCG (Hull-Dobell:
29// a%4==1, c odd -> visits all N for N=2^k) -> scattered (defeats prefetch) + single cycle (spans the set).
30func chase_latency_ns(n: i64, iters: i64) -> i64 {
31 let arr: *i64 = sys_mmap(n*8)
32 let mask: i64 = n-1
33 var i: i64=0
34 while i<n { arr[i] = (K_MAGIC_1664525*i + K_MAGIC_1013904223) & mask; i=i+1 }
35 var p: i64=0
36 var k: i64=0
37 let t0: i64=sys_now_us()
38 while k<iters { p = arr[p]; k=k+1 }
39 let t1: i64=sys_now_us()
40 var us: i64=t1-t0
41 if us<=0 { us=1 }
42 if (p & 0x7fffffff)==0x55555555 { pl_puts("" as *u8) } // keep p live (defeat dead-code elim)
43 return us*1000/iters
44}
45
46func main() -> i64 {
47 pl_puts("GENEALOGIST physics-limit ladder: sovereign hash get vs the MEMORY-ACCESS physics floor\n" as *u8)
48
49 // --- measure the physics floors on THIS hardware ---
50 let cache_ns: i64 = chase_latency_ns(K_MAGIC_32768, K_MAGIC_8000000) // 256KB working set (L2/L3-resident)
51 let dram_ns: i64 = chase_latency_ns(K_MAGIC_8388608, K_MAGIC_8000000) // 64MB working set (> LLC -> DRAM)
52 pl_puts(" PHYSICS FLOOR (dependent pointer-chase, this machine):\n" as *u8)
53 pl_puts(" cache-access latency = "); pl_num(cache_ns); pl_puts(" ns/access (256KB set)\n" as *u8)
54 pl_puts(" DRAM-access latency = "); pl_num(dram_ns); pl_puts(" ns/access (64MB set, prefetch-defeated)\n" as *u8)
55
56 // --- measure the sovereign hash get ---
57 let N: i64=K_MAGIC_20000
58 let keys: *u8=sys_mmap(N*9+16)
59 var i: i64=0
60 while i<N { let q: i64=i*9; keys[q]=107 as u8; var v: i64=i; var d: i64=7; while d>=0 { keys[q+1+d]=(48+(v%10)) as u8; v=v/10; d=d-1 } i=i+1 }
61 let h: *i64=hi_new(K_MAGIC_32768)
62 i=0
63 while i<N { hi_put(h, ((keys as i64)+i*9) as *u8, 9, i); i=i+1 }
64 let probe: *i64=sys_mmap(N*8)
65 i=0
66 while i<N { probe[i]=(i*K_MAGIC_7919)%N; i=i+1 }
67 var ok: i64=0
68 let g0: i64=sys_now_us()
69 var rep: i64=0
70 while rep<10 {
71 i=0
72 while i<N { let tg: i64=probe[i]; if hi_get(h, ((keys as i64)+tg*9) as *u8, 9)==tg { ok=ok+1 } i=i+1 }
73 rep=rep+1
74 }
75 let g1: i64=sys_now_us()
76 var gus: i64=g1-g0
77 if gus<=0 { gus=1 }
78 let hash_ns: i64 = gus*1000/(N*10)
79
80 pl_puts(" SOVEREIGN hash get = "); pl_num(hash_ns); pl_puts(" ns/op (vs sqlite cited 250 ns/op)\n\n" as *u8)
81
82 // --- place on the maturity ladder ---
83 // a key->value lookup is irreducibly >=1 random memory access. grade vs the floors:
84 let vs_dram10: i64 = hash_ns*10/dram_ns // hash get as a fraction (x10) of one DRAM access
85 pl_puts(" MATURITY LADDER (ABSENT->EXISTS->EXCEEDS-incumbent->NEAR-PHYSICS->PHYSICS-OPTIMUM):\n" as *u8)
86 pl_puts(" exceeds sqlite (250ns)? "); if hash_ns<250 { pl_puts("YES ("); pl_num(250/hash_ns); pl_puts("x+)\n" as *u8) } else { pl_puts("no\n" as *u8) }
87 pl_puts(" hash get vs 1 DRAM access = 0."); pl_num(vs_dram10); pl_puts("x (a lookup needs >=1 memory access)\n" as *u8)
88 pl_puts(" grade: " as *u8)
89 var grade_optimum: i64=0
90 if hash_ns <= dram_ns { pl_puts("PHYSICS-OPTIMUM for DRAM-scale data -- the get is FASTER than one DRAM access (cache-resident index), i.e. at/below the irreducible 1-access floor for a out-of-cache dataset\n" as *u8); grade_optimum=1 } else { if hash_ns <= dram_ns*2 { pl_puts("NEAR-PHYSICS (within 2x of one memory access)\n" as *u8) } else { pl_puts("EXCEEDS-incumbent, headroom to physics floor remains\n" as *u8) } }
91 pl_puts(" cache-resident headroom: hash get is ~"); if cache_ns>0 { pl_num(hash_ns/cache_ns) } else { pl_num(0) } pl_puts("x the single cache-access floor (a lookup = hash + ~1 bucket-read + key-compare, so ~2-4 accesses is the realistic lookup floor)\n\n" as *u8)
92
93 var pass: i64=0
94 var ttl: i64=0
95 ttl=ttl+1; pl_puts(" T1 physics floors measured (cache & DRAM latency > 0, DRAM slower than cache): " as *u8); if cache_ns>0 { if dram_ns>cache_ns { pass=pass+1; pl_puts("PASS\n" as *u8) } else { pl_puts("FAIL\n" as *u8) } } else { pl_puts("FAIL\n" as *u8) }
96 ttl=ttl+1; pl_puts(" T2 hash get correct + measured: " as *u8); if ok==N*10 { pass=pass+1; pl_puts("PASS\n" as *u8) } else { pl_puts("FAIL\n" as *u8) }
97 ttl=ttl+1; pl_puts(" T3 hash get EXCEEDS sqlite (sub-250ns): " as *u8); if hash_ns<250 { pass=pass+1; pl_puts("PASS\n" as *u8) } else { pl_puts("FAIL\n" as *u8) }
98 ttl=ttl+1; pl_puts(" T4 hash get at/below 1 DRAM access (PHYSICS-OPTIMUM for out-of-cache data): " as *u8); if grade_optimum==1 { pass=pass+1; pl_puts("PASS\n" as *u8) } else { pl_puts("not yet\n" as *u8) }
99
100 pl_puts("NX-PHYSICS-LADDER passed "); pl_num(pass); pl_puts("/"); pl_num(ttl)
101 if pass>=3 { pl_puts(" verdict=GREEN (sovereign get graded vs the MEASURED physics floor, not just incumbents)\n" as *u8); sys_exit(0); return 0 }
102 pl_puts(" verdict=RED\n" as *u8); sys_exit(1); return 1
103}