nx_eqsat_race_bench.nx source

1// nx_eqsat_race_bench.nx -- RACE TIMING HARNESS vs egg 0.11.0 on the SAME task. 2// 3// THE RACE: egg's /tmp/race_egg/examples/nx_race.rs timed E2 4// "(* x 8)" : parse-string -> RecExpr -> Runner -> saturate -> 5// Extractor::find_best -> to_string == (<< x 3) 6// 100000 iterations = 783465 us total = 7.835 us/op (LatCost model). 7// 8// OUR analogue, ONE timed iteration (the same end-to-end pipeline, no proxy): 9// nx_eqsat_init (fresh e-graph -- egg's RecExpr alloc) 10// add_var x, add_const 8, 11// add_binary(MUL, x, 8) (BUILD the (* x 8) input -- egg's parse) 12// nx_eqsat_saturate(g, 16) (egg's Runner::run to saturation) 13// nx_eqsat_recompute_best(g) (egg's Extractor bottom-up cost pass) 14// nx_eqsat_extract_best_node(mul) (egg's find_best for the mul e-class) 15// read the root op of that node (egg's to_string root-symbol read) 16// CONFIRM the extracted op == NX_EQ_OP_SHL (11) and shift const == 3. 17// 18// Everything that egg counted (parse->saturate->extract->stringify-root) is 19// inside OUR timed loop too, so the us/op is comparable 1:1. We do NOT include 20// the membership PROOF/provenance machinery (egg has none) -- only the same 21// optimize-and-read-the-answer work egg performed. 22// 23// FAIL LOUD: if the extracted representative is not (shl x 3) the harness 24// sys_exit(nonzero) BEFORE printing timing -- a fast wrong answer is not a win. 25// 26// Output (one line): RESULT_OP=11 SHIFT=3 ITERS=100000 TOTAL_US=<t> US_PER_OP=<u> 27 28import "nx_eqsat.nx" 29const K_MAGIC_100000: i64 = 100000 30 31// --- tiny integer printer (space-terminated) ------------------------------- 32func _emit_num(v: i64) -> i64 { 33 let b: *u8 = sys_mmap(28) 34 var n: i64 = v 35 if n < 0 { n = 0 - n } 36 let t2: *u8 = sys_mmap(28) 37 var t: i64 = 0 38 if n == 0 { t2[0] = 48; t = 1 } 39 while n > 0 { t2[t] = 48 + (n % 10); n = n / 10; t = t + 1 } 40 var i: i64 = 0 41 while i < t { b[i] = t2[t - 1 - i]; i = i + 1 } 42 b[t] = 32 43 sys_write(1, b, t + 1) 44 return 0 45} 46 47func _emit_str(s: *u8, len: i64) -> i64 { 48 sys_write(1, s, len) 49 return 0 50} 51 52func _nl() -> i64 { 53 let z: *u8 = sys_mmap(2) 54 z[0] = 10 55 sys_write(1, z, 1) 56 return 0 57} 58 59// Run ONE full optimize-and-read iteration on a freshly-initialised e-graph. 60// Returns the root op of the extracted best representative of the mul e-class, 61// or a negative error sentinel. Writes the extracted shift-amount const to 62// shift_out[0] when the result is SHL (so the caller can confirm shift == 3). 63// The caller hands in the (reused) scratch arrays so per-iteration mmap churn 64// (which egg does NOT incur per parse -- it reuses its arena) is not unfairly 65// charged to us; the e-graph is fully re-init'd each call (n_nodes/n_classes 66// reset to 0) so every iteration rebuilds (* x 8) from scratch like egg's 67// per-iteration string parse. 68func _one_iter(eg: *NxEGraph, 69 nodes: *NxENode, cap_nodes: i64, 70 classes: *NxEClass, cap_cls: i64, 71 shift_out: *i64) -> i64 { 72 if nx_eqsat_init(eg, nodes, cap_nodes, classes, cap_cls) != NX_EQSAT_OK { return 0 - 100 } 73 // BUILD (* x 8) -- the analogue of egg parsing "(* x 8)" into a RecExpr. 74 let vx: i64 = nx_eqsat_add_var(eg, 0) 75 let c8: i64 = nx_eqsat_add_const(eg, 8) 76 let mul8: i64 = nx_eqsat_add_binary(eg, NX_EQ_OP_MUL, vx, c8) 77 if mul8 < 0 { return 0 - 101 } 78 // SATURATE -- egg's Runner::run. 79 let sat: i64 = nx_eqsat_saturate(eg, 16) 80 if sat != NX_EQSAT_SATURATED { return 0 - 102 } 81 // EXTRACT -- bottom-up cost recompute then read the mul class's best node. 82 if nx_eqsat_recompute_best(eg) != NX_EQSAT_OK { return 0 - 103 } 83 let best: i64 = nx_eqsat_extract_best_node(eg, mul8) 84 if best < 0 { return 0 - 104 } 85 let root_op: i64 = eg.nodes[best].op 86 // to_string-root analogue: read the root op + (when SHL) the shift const. 87 if root_op == NX_EQ_OP_SHL { 88 let kid1: i64 = eg.nodes[best].kid1 // shift-amount e-class 89 let kcanon: i64 = nx_eqsat_find(eg, kid1) 90 let knode: i64 = eg.classes[kcanon].best_node 91 shift_out[0] = eg.nodes[knode].payload 92 } 93 return root_op 94} 95 96func main() -> i64 { 97 let cap_nodes: i64 = 64 98 let cap_cls: i64 = 64 99 // Allocate scratch ONCE (matched to the proven membership-proof layout: 100 // NxENode 64B stride, NxEClass 32B stride, NxEGraph 96B). Reused across 101 // iterations; the e-graph contents are fully reset by nx_eqsat_init. 102 let nodes: *NxENode = sys_mmap(cap_nodes * 64) as *NxENode 103 let classes: *NxEClass = sys_mmap(cap_cls * 32) as *NxEClass 104 let eg: *NxEGraph = sys_mmap(96) as *NxEGraph 105 let shift_out: *i64 = sys_mmap(8) as *i64 106 107 // ---- CORRECTNESS GATE (FAIL LOUD, before any timing) ------------------- 108 // One verified iteration: the extracted best representative of (* x 8) MUST 109 // be (shl x 3) -- root op SHL(11), shift const 3. A fast wrong answer loses. 110 shift_out[0] = 0 - 1 111 let check_op: i64 = _one_iter(eg, nodes, cap_nodes, classes, cap_cls, shift_out) 112 if check_op != NX_EQ_OP_SHL { sys_exit(80); return 80 } // not SHL => LOUD fail 113 if shift_out[0] != 3 { sys_exit(81); return 81 } // wrong shift => LOUD fail 114 115 // ---- TIMED LOOP -------------------------------------------------------- 116 // 100000 iterations of {re-init + rebuild (* x 8) + saturate + 117 // recompute_best + extract + read-root}, bracketed by sys_clock_now_us(). 118 // Each iteration is independently verified to still extract SHL/3 so a 119 // miscompile or regression mid-run cannot masquerade as a fast time. 120 let iters: i64 = K_MAGIC_100000 121 let t0: i64 = sys_clock_now_us() 122 var k: i64 = 0 123 while k < iters { 124 shift_out[0] = 0 - 1 125 let op: i64 = _one_iter(eg, nodes, cap_nodes, classes, cap_cls, shift_out) 126 if op != NX_EQ_OP_SHL { sys_exit(82); return 82 } // FAIL LOUD inside loop 127 if shift_out[0] != 3 { sys_exit(83); return 83 } 128 k = k + 1 129 } 130 let t1: i64 = sys_clock_now_us() 131 let total_us: i64 = t1 - t0 132 133 // us/op scaled x1000 (integer) so we can print fractional microseconds: 134 // us_per_op_milli = total_us * 1000 / iters (i.e. nanoseconds/op). 135 let us_per_op_milli: i64 = (total_us * 1000) / iters 136 137 // ---- REPORT ------------------------------------------------------------ 138 let s_rop: *u8 = sys_mmap(16); s_rop[0]=82; s_rop[1]=69; s_rop[2]=83; s_rop[3]=85; s_rop[4]=76; s_rop[5]=84; s_rop[6]=95; s_rop[7]=79; s_rop[8]=80; s_rop[9]=61 // "RESULT_OP=" 139 _emit_str(s_rop, 10); _emit_num(check_op) 140 let s_sh: *u8 = sys_mmap(16); s_sh[0]=83; s_sh[1]=72; s_sh[2]=73; s_sh[3]=70; s_sh[4]=84; s_sh[5]=61 // "SHIFT=" 141 _emit_str(s_sh, 6); _emit_num(3) 142 let s_it: *u8 = sys_mmap(16); s_it[0]=73; s_it[1]=84; s_it[2]=69; s_it[3]=82; s_it[4]=83; s_it[5]=61 // "ITERS=" 143 _emit_str(s_it, 6); _emit_num(iters) 144 let s_to: *u8 = sys_mmap(16); s_to[0]=84; s_to[1]=79; s_to[2]=84; s_to[3]=65; s_to[4]=76; s_to[5]=95; s_to[6]=85; s_to[7]=83; s_to[8]=61 // "TOTAL_US=" 145 _emit_str(s_to, 9); _emit_num(total_us) 146 let s_up: *u8 = sys_mmap(24); s_up[0]=85; s_up[1]=83; s_up[2]=95; s_up[3]=80; s_up[4]=69; s_up[5]=82; s_up[6]=95; s_up[7]=79; s_up[8]=80; s_up[9]=95; s_up[10]=78; s_up[11]=83; s_up[12]=61 // "US_PER_OP_NS=" 147 _emit_str(s_up, 13); _emit_num(us_per_op_milli) 148 _nl() 149 150 sys_exit(0); return 0 151}