sketch_reqsketch_vs_kll_bench.nx source
↩ module page · 134 lines · 5292 B
1// sketch_reqsketch_vs_kll_bench.nx -- MATCHED-MEMORY paired measurement.
2//
3// HONESTY UPDATE (matched-memory rerun):
4// Original bench used same k=64 for both; that gave ReqSketch
5// ~3x memory (24 levels × 2*k = 3072 slots vs KLL 16 × k = 1024).
6// This rerun MATCHES TOTAL SLOT COUNT: ReqSketch k=64 (3072 slots)
7// vs KLL k=192 (16 × 192 = 3072 slots). Loser scaled UP, not winner
8// nerfed down -- per substrate-honesty discipline.
9//
10// SHARED WORKLOAD:
11// - Stream: integers 1..1000 in order
12// - Slot budget: 3072 (matched)
13// - Seed: deterministic, identical for both
14// - Query: p99 -- the tail quantile where ReqSketch hra=1 should
15// structurally beat KLL's uniform-eps bound EVEN AT MATCHED MEMORY
16// (the structural-tail-preservation claim of Cormode et al. 2021).
17//
18// GROUND TRUTH:
19// p99 of 1..1000 = 990
20//
21// VERDICT REQUIREMENTS (honest, matched memory):
22// ACCURACY p99 -> BEATS or EQUIVALENT (structural claim survives)
23// ACCURACY p999 -> BEATS (gap should widen at deeper tail)
24// ACCURACY p50 -> NOT BEATS (KLL's uniform bound holds at median)
25// MEMORY -> EQUIVALENT by construction (matched slot count)
26
27import "syscalls.nx"
28import "sketch_reqsketch.nx"
29import "sketch_kll.nx"
30import "sketch_comparator.nx"
31import "sketch_types.nx"
32
33func iabs_b(x: i64) -> i64 {
34 if x < 0 { return -x }
35 return x
36}
37
38func main() -> i64 {
39 let req_k: i64 = 64
40 let kll_k: i64 = 192 // matched: 16 * 192 = 3072 slots = 24 * 2 * 64
41 let seed: i64 = 7
42
43 // ---- Build both sketches on identical stream ----
44 let req: *Req = nx_req_alloc(req_k, 1, seed)
45 let kll: *Kll = nx_kll_alloc(kll_k, seed)
46 var i: i64 = 1
47 while i <= 1000 {
48 nx_req_add(req, i)
49 nx_kll_add(kll, i)
50 i = i + 1
51 }
52
53 // ---- Query p99 from both ----
54 let p99_req: i64 = nx_req_quantile(req, 990)
55 let p99_kll: i64 = nx_kll_quantile(kll, 990)
56 let truth_p99: i64 = 990
57
58 // ---- ACCURACY axis on p99 (tail) ----
59 // Tolerance: 1% of truth = 9900 ppm
60 let acc: *ComparisonResult = nx_cmp_accuracy(p99_req, p99_kll, truth_p99, 9900)
61
62 // ---- MEMORY axis (now matched by construction; both ~3072 slots) ----
63 let req_bytes: i64 = nx_req_memory_bytes(req)
64 let kll_bytes: i64 = nx_kll_memory_bytes(kll)
65 // Tolerance 5% -- both should land in the same band.
66 let mem: *ComparisonResult = nx_cmp_memory(req_bytes, kll_bytes, 50000)
67
68 // ---- TIME axis: declare INCONCLUSIVE (no in-program clock primitive yet) ----
69 let tim_raw: *u8 = sys_mmap(40)
70 let tim: *ComparisonResult = tim_raw as *ComparisonResult
71 tim.verdict = NX_CMP_VERDICT_INCONCLUSIVE
72 tim.delta_ppm = 0
73 tim.conf_ppb = 500000000
74 tim.axis = NX_CMP_AXIS_TIME
75
76 // ---- HARD-WIN GATE on ACCURACY (the headline claim) ----
77 // ReqSketch hra=1 must beat KLL on p99 by at least the
78 // tolerance band (1% of truth = ~10 ranks).
79 if acc.verdict != NX_CMP_VERDICT_BEATS {
80 // Honesty signal: emit raw measurements + fail.
81 // exit codes encode which axis disappointed.
82 return __syscall(93, 10, 0, 0, 0, 0, 0)
83 }
84
85 // ---- ACCURACY delta must be meaningful (>2% improvement) ----
86 if acc.delta_ppm < 20000 {
87 return __syscall(93, 11, 0, 0, 0, 0, 0)
88 }
89
90 // ---- MEMORY axis at matched slot count -- expect EQUIVALENT ----
91 // ReqSketch 24 * 2 * 64 = 3072 slots; KLL 16 * 192 = 3072 slots.
92 // Header bytes differ slightly; tolerance band 5%.
93 if mem.verdict == NX_CMP_VERDICT_LOSES {
94 // ReqSketch using >5% MORE memory at matched k -- needs
95 // disclosure but not a failure. Accept LOSES so long as the
96 // delta_ppm is bounded. Composite below handles the verdict.
97 if mem.delta_ppm < -100000 {
98 // >10% memory asymmetry -- declare bench unfair
99 return __syscall(93, 20, 0, 0, 0, 0, 0)
100 }
101 }
102
103 // ---- Composite verdict at matched memory ----
104 let composite: i64 = nx_cmp_composite(acc, mem, tim)
105 if composite == NX_CMP_VERDICT_INCONCLUSIVE {
106 return __syscall(93, 30, 0, 0, 0, 0, 0)
107 }
108
109 // ---- SECOND TEST: p99.9 (deeper tail) -- ReqSketch's edge widens ----
110 let p999_req: i64 = nx_req_quantile(req, 999)
111 let p999_kll: i64 = nx_kll_quantile(kll, 999)
112 let truth_p999: i64 = 999
113 let acc_999: *ComparisonResult = nx_cmp_accuracy(p999_req, p999_kll, truth_p999, 5000)
114 if acc_999.verdict != NX_CMP_VERDICT_BEATS {
115 return __syscall(93, 40, 0, 0, 0, 0, 0)
116 }
117
118 // ---- THIRD TEST: median (mid-distribution) -- ReqSketch should NOT
119 // win here; this is where KLL's uniform bound is comfortable.
120 // Verify we are HONEST about not winning at the median.
121 let p50_req: i64 = nx_req_quantile(req, 500)
122 let p50_kll: i64 = nx_kll_quantile(kll, 500)
123 let acc_50: *ComparisonResult = nx_cmp_accuracy(p50_req, p50_kll, 500, 50000)
124 if acc_50.verdict == NX_CMP_VERDICT_BEATS {
125 // If we claim to beat KLL at the median too, that would be
126 // suspicious -- KLL is engineered for uniform bound.
127 // Acceptable: EQUIVALENT or LOSES. Reject false EXCEED.
128 if acc_50.delta_ppm > 50000 {
129 return __syscall(93, 50, 0, 0, 0, 0, 0)
130 }
131 }
132
133 return 0
134}