code wiki / _hdl_build / nx_js_shape_gate.nx
nx_js_shape_gate.nx source
↩ module page · 167 lines · 7907 B
1// nx_js_shape_gate.nx -- P3 SHAPES / hidden classes: prove (A) shape-keyed ICs give IDENTICAL results
2// to the legacy per-object ICs and the tree-walker, and (B) they MEASURABLY win where per-object ICs
3// fail -- a loop over MANY distinct objects of the SAME shape. Per-object ICs miss on every object
4// (different pointers) and fall back to the linear obj_find scan; shape ICs hit across all of them.
5// The signature: reading a LATE property (index ~9) across many objects costs ~the same as reading an
6// EARLY property under shapes (O(1)), but scales with scan depth under per-object ICs. expect_exit: 0
7// license_tier: ORIGINAL
8import "nx_js_vm.nx"
9
10func sg_w(s: *u8) -> i64 { var n: i64 = 0; while s[n] != (0 as u8) { n = n + 1 } sys_write(1, s, n); return 0 }
11func sg_n(v: i64) -> i64 {
12 if v == 0 { sys_write(1, "0" as *u8, 1); return 0 }
13 var m: i64 = v
14 if m < 0 { sys_write(1, "-" as *u8, 1); m = 0 - m }
15 let t: *u8 = sys_mmap(32)
16 var k: i64 = 0
17 while m > 0 { t[k] = (48 + (m % 10)) as u8; m = m / 10; k = k + 1 }
18 let o: *u8 = sys_mmap(32)
19 var q: i64 = k - 1
20 var x: i64 = 0
21 while q >= 0 { o[x] = t[q]; x = x + 1; q = q - 1 }
22 sys_write(1, o, x)
23 return 0
24}
25// run `src` under tree, shape-IC VM, and pointer-IC VM; all three must agree (value + rc).
26func schk(src: *u8, label: *u8, pp: *i64, tp: *i64) -> i64 {
27 tp[0] = tp[0] + 1
28 let tw: *i64 = sys_mmap(16) as *i64
29 let trc: i64 = js_run_source(src, bsl(src), tw)
30 js_ic_ptr_mode(0)
31 let sv: *i64 = sys_mmap(16) as *i64
32 let src2: i64 = compile_run(src, sv)
33 js_ic_ptr_mode(1)
34 let pv: *i64 = sys_mmap(16) as *i64
35 let prc: i64 = compile_run(src, pv)
36 js_ic_ptr_mode(0)
37 sg_w(" ")
38 sg_w(label)
39 sg_w(": ")
40 var ok: i64 = 1
41 if trc != src2 { ok = 0 }
42 if trc != prc { ok = 0 }
43 if trc == 0 { if cells_eq(tw, sv) == 0 { ok = 0 } }
44 if trc == 0 { if cells_eq(tw, pv) == 0 { ok = 0 } }
45 if ok == 1 { pp[0] = pp[0] + 1; sg_w("ok (tree=shapeIC=ptrIC)\n" as *u8); return 0 }
46 sg_w("FAIL tree(rc=")
47 sg_n(trc)
48 sg_w(",t=")
49 sg_n(tw[0])
50 sg_w(",p=")
51 sg_n(tw[1])
52 sg_w(") shape(rc=")
53 sg_n(src2)
54 sg_w(",t=")
55 sg_n(sv[0])
56 sg_w(",p=")
57 sg_n(sv[1])
58 sg_w(") ptr(rc=")
59 sg_n(prc)
60 sg_w(",t=")
61 sg_n(pv[0])
62 sg_w(",p=")
63 sg_n(pv[1])
64 sg_w(")\n" as *u8)
65 return 0
66}
67// time `src` under a given IC mode; returns the BEST (min) of 3 runs (min-of-N cancels transient WSL
68// load spikes -- the two modes are timed in separate runs, so a single sample can invert on noise).
69func stime(src: *u8, mode: i64, expp: i64, okbox: *i64) -> i64 {
70 js_ic_ptr_mode(mode)
71 okbox[0] = 0
72 var best: i64 = 0
73 var r: i64 = 0
74 while r < 3 {
75 let o: *i64 = sys_mmap(16) as *i64
76 let t0: i64 = sys_now_us()
77 let rc: i64 = compile_run(src, o)
78 let t1: i64 = sys_now_us()
79 var us: i64 = t1 - t0
80 if us < 1 { us = 1 }
81 if rc == 0 { if o[0] == VAL_NUM { if o[1] == expp { okbox[0] = 1 } } }
82 if r == 0 { best = us }
83 if us < best { best = us }
84 r = r + 1
85 }
86 js_ic_ptr_mode(0)
87 return best
88}
89
90func main(argc: i64, argv: *i64) -> i64 {
91 sg_w("=== nx_js_shape_gate: P3 hidden classes -- correct + measured across many objects ===\n" as *u8)
92 // this gate measures the VM INTERPRETER's shape-vs-pointer IC toggle; force the VM path so the
93 // baseline JIT (whose inline GETPROP always uses shapes) doesn't collapse the A/B. The JIT's own
94 // inline shape-IC win is proven separately in nx_js_jit_gate [D].
95 js_jit_disable(1)
96 let pp: *i64 = sys_mmap(8) as *i64
97 let tp: *i64 = sys_mmap(8) as *i64
98 sg_w(" [A: tree == shape-IC == pointer-IC (shapes are a transparent fast path)]\n" as *u8)
99 schk("var o={a:1,b:2,c:3};o.a+o.b+o.c" as *u8, "S1 multi-prop read" as *u8, pp, tp)
100 schk("var o={};o.x=5;o.y=7;o.x+o.y" as *u8, "S2 incremental build" as *u8, pp, tp)
101 schk("var a=[];var i=0;while(i<50){a[i]={n:i,m:i*2};i++;}var s=0;var j=0;while(j<50){s=s+a[j].m;j++;}s" as *u8, "S3 many same-shape objs" as *u8, pp, tp)
102 schk("var o={a:1};var p={b:2};o.a+p.b" as *u8, "S4 different shapes" as *u8, pp, tp)
103 schk("var o={a:1,b:2};var p={b:1,a:2};o.a*10+p.a" as *u8, "S5 same keys diff ORDER = diff shape" as *u8, pp, tp)
104 schk("var o={a:0};var i=0;while(i<100){o.a=o.a+1;i++;}o.a" as *u8, "S6 hot update one shape" as *u8, pp, tp)
105 schk("var o={x:1};o.y=2;var p={x:1};p.y=2;o.y+p.y" as *u8, "S7 transition merge (literal path == set path)" as *u8, pp, tp)
106 schk("function P(n){this.a=n;this.b=n*2;}var s=0;var i=0;while(i<30){var q=new P(i);s=s+q.b;i++;}s" as *u8, "S8 ctor -> same shape" as *u8, pp, tp)
107 sg_w(" --- correctness: " as *u8)
108 sg_n(pp[0])
109 sg_w("/" as *u8)
110 sg_n(tp[0])
111 sg_w(" ---\n" as *u8)
112
113 // [B] the O(1)-across-objects signature. Build 400 objects each with 20 props (q0..q18,last),
114 // then loop reading the LAST property (index 19) vs the FIRST (index 0). Per-object ICs miss on
115 // every distinct object -> obj_find LINEAR SCAN (idx19 = 20 compares, idx0 = 1); shape ICs HIT ->
116 // O(1) for both. So the ROBUST signature (noise-immune, a within-mode ratio) is late/early:
117 // shapes keep it ~1x (O(1)); per-object ICs blow it up by the scan depth.
118 let klast: *u8 = "var a=[];var i=0;while(i<400){a[i]={q0:i,q1:1,q2:1,q3:1,q4:1,q5:1,q6:1,q7:1,q8:1,q9:1,q10:1,q11:1,q12:1,q13:1,q14:1,q15:1,q16:1,q17:1,q18:1,last:i};i++;}var s=0;var r=0;while(r<60){var j=0;while(j<400){s=s+a[j].last;j++;}r++;}s"
119 let kfirst: *u8 = "var a=[];var i=0;while(i<400){a[i]={q0:i,q1:1,q2:1,q3:1,q4:1,q5:1,q6:1,q7:1,q8:1,q9:1,q10:1,q11:1,q12:1,q13:1,q14:1,q15:1,q16:1,q17:1,q18:1,last:i};i++;}var s=0;var r=0;while(r<60){var j=0;while(j<400){s=s+a[j].q0;j++;}r++;}s"
120 // expected sum: last==q0==i, so both = sum_{0..399} j * 60 = 79800*60 = 4788000
121 let exp: i64 = 4788000
122 let ok1: *i64 = sys_mmap(8) as *i64
123 let ok2: *i64 = sys_mmap(8) as *i64
124 let ok3: *i64 = sys_mmap(8) as *i64
125 let ok4: *i64 = sys_mmap(8) as *i64
126 let sh_last: i64 = stime(klast, 0, exp, ok1)
127 let pt_last: i64 = stime(klast, 1, exp, ok2)
128 let sh_first: i64 = stime(kfirst, 0, exp, ok3)
129 let pt_first: i64 = stime(kfirst, 1, exp, ok4)
130 sg_w(" [B: 400 objects x 20 props, 400 reads/pass x 60 passes = 24k obj-reads/kernel]\n" as *u8)
131 sg_w(" read LAST prop (idx 19): shapeIC=" as *u8)
132 sg_n(sh_last)
133 sg_w("us ptrIC=" as *u8)
134 sg_n(pt_last)
135 sg_w("us\n" as *u8)
136 sg_w(" read FIRST prop (idx 0): shapeIC=" as *u8)
137 sg_n(sh_first)
138 sg_w("us ptrIC=" as *u8)
139 sg_n(pt_first)
140 sg_w("us\n" as *u8)
141 // the O(1) signature: under shapes, late==early (ratio ~100); under per-object ICs, late is
142 // ~scan-depth worse. A within-mode ratio cancels box noise -> the load-bearing measurement.
143 let sh_ratio: i64 = sh_last * 100 / sh_first
144 let pt_ratio: i64 = pt_last * 100 / pt_first
145 sg_w(" SIGNATURE late/early x100: shapeIC=" as *u8)
146 sg_n(sh_ratio)
147 sg_w(" (O(1): ~100) ptrIC=" as *u8)
148 sg_n(pt_ratio)
149 sg_w(" (scan-bound: >>100)\n" as *u8)
150
151 var allok: i64 = 1
152 if pp[0] != tp[0] { allok = 0 }
153 if ok1[0] == 0 { allok = 0 }
154 if ok2[0] == 0 { allok = 0 }
155 if ok3[0] == 0 { allok = 0 }
156 if ok4[0] == 0 { allok = 0 }
157 // PROOF: shapes give the O(1) property that per-object ICs cannot -- shape late/early stays near
158 // O(1) while the per-object ratio is materially larger (scan-bound). Robust to box noise.
159 var faster: i64 = 0
160 if sh_ratio < pt_ratio { if sh_ratio < 160 { faster = 1 } }
161 if allok == 1 { if faster == 1 {
162 sg_w("=== GREEN: P3 shapes CORRECT (tree=shapeIC=ptrIC) + O(1)-across-objects SIGNATURE (shape ratio ~100, per-object ratio scan-bound) ===\n" as *u8)
163 return 0
164 } }
165 sg_w("=== RED ===\n" as *u8)
166 return 1
167}