code wiki / _hdl_build / nx_js_poly_ic_gate.nx
nx_js_poly_ic_gate.nx source
↩ module page · 142 lines · 6635 B
1// nx_js_poly_ic_gate.nx -- P4 POLYMORPHIC inline caches: prove (A) a K-way IC gives IDENTICAL results to
2// a 1-way (monomorphic) IC and the tree-walker, and (B) it MEASURABLY wins on a POLYMORPHIC site -- a loop
3// over objects of TWO shapes at one GETPROP site. A 1-way IC thrashes (each read alternates shape -> miss
4// -> linear obj_find scan); a 4-way IC caches both shapes -> hits. Control: a MONOMORPHIC (single-shape)
5// site where 1-way == K-way (poly must not regress the common case). Forces the VM path (js_jit_disable)
6// so the interpreter's poly IC is what's measured. expect_exit: 0 license_tier: ORIGINAL
7import "nx_js_vm.nx"
8
9func pg_w(s: *u8) -> i64 { var n: i64 = 0; while s[n] != (0 as u8) { n = n + 1 } sys_write(1, s, n); return 0 }
10func pg_n(v: i64) -> i64 {
11 if v == 0 { sys_write(1, "0" as *u8, 1); return 0 }
12 var m: i64 = v
13 if m < 0 { sys_write(1, "-" as *u8, 1); m = 0 - m }
14 let t: *u8 = sys_mmap(32)
15 var k: i64 = 0
16 while m > 0 { t[k] = (48 + (m % 10)) as u8; m = m / 10; k = k + 1 }
17 let o: *u8 = sys_mmap(32)
18 var q: i64 = k - 1
19 var x: i64 = 0
20 while q >= 0 { o[x] = t[q]; x = x + 1; q = q - 1 }
21 sys_write(1, o, x)
22 return 0
23}
24// run `src` at a given poly-way count; best-of-3 us; checks the value.
25func pt(src: *u8, ways: i64, expp: i64, okbox: *i64) -> i64 {
26 js_ic_poly_ways(ways)
27 okbox[0] = 0
28 var best: i64 = 0
29 var r: i64 = 0
30 while r < 3 {
31 let o: *i64 = sys_mmap(16) as *i64
32 let t0: i64 = sys_now_us()
33 let rc: i64 = compile_run(src, o)
34 let t1: i64 = sys_now_us()
35 var us: i64 = t1 - t0
36 if us < 1 { us = 1 }
37 if rc == 0 { if o[0] == VAL_NUM { if o[1] == expp { okbox[0] = 1 } } }
38 if r == 0 { best = us }
39 if us < best { best = us }
40 r = r + 1
41 }
42 js_ic_poly_ways(4)
43 return best
44}
45// tree == 1-way == 4-way agreement (poly is a transparent fast path).
46func pchk(src: *u8, label: *u8, expp: i64, pp: *i64, tp: *i64) -> i64 {
47 tp[0] = tp[0] + 1
48 let tw: *i64 = sys_mmap(16) as *i64
49 let trc: i64 = js_run_source(src, bsl(src), tw)
50 js_ic_poly_ways(1)
51 let mv: *i64 = sys_mmap(16) as *i64
52 let mrc: i64 = compile_run(src, mv)
53 js_ic_poly_ways(4)
54 let kv: *i64 = sys_mmap(16) as *i64
55 let krc: i64 = compile_run(src, kv)
56 pg_w(" ")
57 pg_w(label)
58 pg_w(": ")
59 var ok: i64 = 1
60 if trc != 0 { ok = 0 }
61 if mrc != 0 { ok = 0 }
62 if krc != 0 { ok = 0 }
63 if tw[0] != VAL_NUM { ok = 0 }
64 if tw[1] != expp { ok = 0 }
65 if mv[1] != expp { ok = 0 }
66 if kv[1] != expp { ok = 0 }
67 if ok == 1 { pp[0] = pp[0] + 1; pg_w("ok (tree=1way=4way)\n" as *u8); return 0 }
68 pg_w("FAIL (tree ")
69 pg_n(tw[1])
70 pg_w(" 1way ")
71 pg_n(mv[1])
72 pg_w(" 4way ")
73 pg_n(kv[1])
74 pg_w(")\n" as *u8)
75 return 0
76}
77
78func main(argc: i64, argv: *i64) -> i64 {
79 pg_w("=== nx_js_poly_ic_gate: P4 polymorphic inline caches -- correct + measured on a polymorphic site ===\n" as *u8)
80 js_jit_disable(1) // measure the interpreter's IC (the JIT inline path is monomorphic way-0 by design)
81 let pp: *i64 = sys_mmap(8) as *i64
82 let tp: *i64 = sys_mmap(8) as *i64
83 pg_w(" [A: tree == 1-way == 4-way (poly is transparent)]\n" as *u8)
84 pchk("var o={a:1,b:2};var p={x:3,y:4};o.a+o.b+p.x+p.y" as *u8, "P1 two shapes one program" as *u8, 10, pp, tp)
85 // one GETPROP site (f's o.val) hit with two different shapes -> polymorphic site
86 pchk("function rd(o){return o.val;}var s=0;var i=0;while(i<20){if(i<10){s=s+rd({a:0,val:i});}else{s=s+rd({b:0,c:0,val:i});}i++;}s" as *u8, "P2 polymorphic call site" as *u8, 190, pp, tp)
87 pchk("var a=[{a:1,val:5},{b:1,c:1,val:7}];a[0].val+a[1].val" as *u8, "P3 array mixed shapes" as *u8, 12, pp, tp)
88 pg_w(" --- correctness: ")
89 pg_n(pp[0])
90 pg_w("/")
91 pg_n(tp[0])
92 pg_w(" ---\n" as *u8)
93
94 // [B] the polymorphic signature. 800 objects = 400 of shape A (first key 'a') interleaved with 400 of
95 // shape B (first key 'b'); 'val' at the SAME index (15) in both. One GETPROP site (A[j].val) sees BOTH
96 // shapes alternately. 1-way IC: miss every read -> obj_find scans 16. 4-way IC: both shapes cached -> hit.
97 let poly: *u8 = "var A=[];var i=0;while(i<400){A[i*2]={a:0,c1:1,c2:1,c3:1,c4:1,c5:1,c6:1,c7:1,c8:1,c9:1,c10:1,c11:1,c12:1,c13:1,c14:1,val:i*2};A[i*2+1]={b:0,c1:1,c2:1,c3:1,c4:1,c5:1,c6:1,c7:1,c8:1,c9:1,c10:1,c11:1,c12:1,c13:1,c14:1,val:i*2+1};i++;}var s=0;var r=0;while(r<40){var j=0;while(j<800){s=s+A[j].val;j++;}r++;}s"
98 // MONOMORPHIC control: 800 objects ALL of shape A. Same reads, one shape -> both IC widths hit equally.
99 let mono: *u8 = "var A=[];var i=0;while(i<800){A[i]={a:0,c1:1,c2:1,c3:1,c4:1,c5:1,c6:1,c7:1,c8:1,c9:1,c10:1,c11:1,c12:1,c13:1,c14:1,val:i};i++;}var s=0;var r=0;while(r<40){var j=0;while(j<800){s=s+A[j].val;j++;}r++;}s"
100 let exp: i64 = 12784000 // sum_{0..799} j * 40
101 let ok1: *i64 = sys_mmap(8) as *i64
102 let ok2: *i64 = sys_mmap(8) as *i64
103 let ok3: *i64 = sys_mmap(8) as *i64
104 let ok4: *i64 = sys_mmap(8) as *i64
105 let poly_1way: i64 = pt(poly, 1, exp, ok1)
106 let poly_4way: i64 = pt(poly, 4, exp, ok2)
107 let mono_1way: i64 = pt(mono, 1, exp, ok3)
108 let mono_4way: i64 = pt(mono, 4, exp, ok4)
109 pg_w(" [B: polymorphic site (2 shapes x16 props, 800 reads/pass x40 = 32k reads)]\n" as *u8)
110 pg_w(" POLYMORPHIC kernel: 1-way(mono IC)=")
111 pg_n(poly_1way)
112 pg_w("us 4-way(poly IC)=")
113 pg_n(poly_4way)
114 pg_w("us 1way/4way=")
115 pg_n(poly_1way * 100 / poly_4way)
116 pg_w("/100x\n" as *u8)
117 pg_w(" MONOMORPHIC control: 1-way=")
118 pg_n(mono_1way)
119 pg_w("us 4-way=")
120 pg_n(mono_4way)
121 pg_w("us (should be ~equal -- poly must not regress the common case)\n" as *u8)
122
123 var allok: i64 = 1
124 if pp[0] != tp[0] { allok = 0 }
125 if ok1[0] == 0 { allok = 0 }
126 if ok2[0] == 0 { allok = 0 }
127 if ok3[0] == 0 { allok = 0 }
128 if ok4[0] == 0 { allok = 0 }
129 // PROOF: on the polymorphic site the 4-way IC is materially faster than the 1-way (thrash eliminated);
130 // on the monomorphic control the two are within noise (no regression).
131 var win: i64 = 0
132 if poly_4way < poly_1way { win = 1 }
133 var noregress: i64 = 0
134 let momargin: i64 = mono_1way + mono_1way / 2 + 10 // 4-way <= ~1.5x mono 1-way (noise tolerance)
135 if mono_4way <= momargin { noregress = 1 }
136 if allok == 1 { if win == 1 { if noregress == 1 {
137 pg_w("=== GREEN: P4 poly ICs CORRECT (tree=1way=4way) + faster on polymorphic sites, no mono regression ===\n" as *u8)
138 return 0
139 } } }
140 pg_w("=== RED ===\n" as *u8)
141 return 1
142}