sketch_kll_vs_reservoir_bench.nx source
↩ module page · 140 lines · 5652 B
1// sketch_kll_vs_reservoir_bench.nx -- MATCHED-MEMORY honest measurement.
2//
3// HONESTY UP FRONT:
4// sketch_kll.nx header asserts "KLL has tighter rank-error at fixed
5// memory" -- but at MATCHED slot count this is FALSE per declared
6// envelopes:
7// KLL k=64 (16 levels × 64 = 1024 slots): declared eps = 0.12
8// Reservoir cap=1024 (flat): declared eps = 0.0425
9// Reservoir wins on rank-error magnitude at matched memory by ~3x.
10//
11// KLL's actual structural advantage is elsewhere:
12// - DETERMINISTIC mergeable (Reservoir is harder to merge)
13// - Streaming O(1) amortized update vs Reservoir's O(1/n) prob
14// - Eviction-free at large N (Reservoir's sample stops growing)
15//
16// This bench MEASURES the empirical rank error of both at matched
17// memory, and asserts what the substrate actually does, not what the
18// docstring claims. If KLL beats Reservoir empirically, KLL's claim
19// stands. If Reservoir wins, the header gets a correction (queued).
20//
21// WORKLOAD:
22// Stream 1..10000, deterministic.
23// Memory: ~8KB for both (KLL k=64, Reservoir cap=1024).
24//
25// MEASUREMENT:
26// Errors at p10/p50/p90 vs truth (1000/5000/9000).
27// Compare via sketch_comparator accuracy axis.
28
29import "syscalls.nx"
30import "sketch_kll.nx"
31import "sketch_reservoir.nx"
32import "sketch_comparator.nx"
33import "sketch_types.nx"
34
35func iabs_kr(x: i64) -> i64 {
36 if x < 0 { return -x }
37 return x
38}
39
40func main() -> i64 {
41 let kll_k: i64 = 64
42 let res_cap: i64 = 1024 // matches 16 levels × 64 = 1024 slot count
43 let seed: i64 = 7
44 let stream_n: i64 = 10000
45
46 let kll: *Kll = nx_kll_alloc(kll_k, seed)
47 let res: *Reservoir = nx_reservoir_alloc(res_cap, seed)
48 if kll == (0 as *Kll) { return __syscall(93, 1, 0, 0, 0, 0, 0) }
49 if res == (0 as *Reservoir) { return __syscall(93, 2, 0, 0, 0, 0, 0) }
50
51 // ---- Stream ----
52 var i: i64 = 1
53 while i <= stream_n {
54 nx_kll_add(kll, i)
55 nx_reservoir_add(res, i)
56 i = i + 1
57 }
58
59 // ---- Query each at p10, p50, p90 ----
60 let kll_p10: i64 = nx_kll_quantile(kll, 100)
61 let kll_p50: i64 = nx_kll_quantile(kll, 500)
62 let kll_p90: i64 = nx_kll_quantile(kll, 900)
63 let res_p10: i64 = nx_reservoir_quantile(res, 100)
64 let res_p50: i64 = nx_reservoir_quantile(res, 500)
65 let res_p90: i64 = nx_reservoir_quantile(res, 900)
66
67 let truth_p10: i64 = 1000
68 let truth_p50: i64 = 5000
69 let truth_p90: i64 = 9000
70
71 // ---- Sum of absolute errors per sketch ----
72 let kll_err: i64 = iabs_kr(kll_p10 - truth_p10) + iabs_kr(kll_p50 - truth_p50) + iabs_kr(kll_p90 - truth_p90)
73 let res_err: i64 = iabs_kr(res_p10 - truth_p10) + iabs_kr(res_p50 - truth_p50) + iabs_kr(res_p90 - truth_p90)
74
75 // ---- Memory parity check ----
76 let kll_bytes: i64 = nx_kll_memory_bytes(kll)
77 let res_bytes: i64 = nx_reservoir_memory_bytes(res)
78 let mem: *ComparisonResult = nx_cmp_memory(kll_bytes, res_bytes, 50000)
79 // Both should be EQUIVALENT (matched within 5%).
80 if mem.verdict == NX_CMP_VERDICT_LOSES {
81 if mem.delta_ppm < -100000 {
82 // KLL uses >10% more memory -- bench unfair
83 return __syscall(93, 5, 0, 0, 0, 0, 0)
84 }
85 }
86
87 // ---- Honest accuracy verdict via "smaller wins" ----
88 // Use nx_cmp_memory which has smaller-wins semantics (positive
89 // delta = our smaller). No truth-reference division-by-zero.
90 let acc: *ComparisonResult = nx_cmp_memory(kll_err, res_err, 50000)
91
92 // ---- The HONEST claim: at matched memory, Reservoir's rank
93 // error is tighter than KLL's. KLL's structural wins (merge,
94 // amortized update) are NOT measured by this bench.
95 // We expect Reservoir to BEAT KLL here (acc verdict = LOSES from
96 // KLL's perspective which we made "ours"). That outcome would
97 // CONFIRM the substrate-honesty audit finding.
98 //
99 // If somehow KLL beats Reservoir at matched memory, we'd promote
100 // KLL's claim back to TRUE -- update header accordingly.
101
102 // ---- Sanity: both errors positive and bounded ----
103 if kll_err <= 0 { return __syscall(93, 10, 0, 0, 0, 0, 0) }
104 if res_err <= 0 { return __syscall(93, 11, 0, 0, 0, 0, 0) }
105
106 // ---- Honest assertion: Reservoir wins on rank error at matched mem ----
107 // From KLL's perspective (kll_err vs res_err), KLL should LOSE.
108 if acc.verdict != NX_CMP_VERDICT_LOSES {
109 // KLL EQUIVALENT or BEATS -- KLL header claim holds. Bench
110 // is happy either way; just want a definitive verdict.
111 if acc.verdict == NX_CMP_VERDICT_INCONCLUSIVE {
112 return __syscall(93, 20, 0, 0, 0, 0, 0)
113 }
114 // BEATS or EQUIVALENT also OK -- updates substrate truth.
115 }
116
117 // ---- Either way: measure-and-document gate passes if the
118 // measurement was made and verdicts are coherent.
119 // Document the winner via a sentinel exit code visible in the
120 // bench output's tail.
121 // Distinct exit codes per winner for honest forensics:
122 // 0 = Reservoir wins by < 2x (expected per envelopes)
123 // 1 = Reservoir wins by >= 2x (Reservoir EXCEED claim)
124 // 2 = EQUIVALENT (within 5% tolerance)
125 // 3 = KLL wins (surprise -- substrate claim empirically holds)
126 if acc.verdict == NX_CMP_VERDICT_LOSES {
127 if res_err <= kll_err / 2 {
128 return __syscall(93, 1, 0, 0, 0, 0, 0)
129 }
130 return 0
131 }
132 if acc.verdict == NX_CMP_VERDICT_EQUIVALENT {
133 return __syscall(93, 2, 0, 0, 0, 0, 0)
134 }
135 if acc.verdict == NX_CMP_VERDICT_BEATS {
136 return __syscall(93, 3, 0, 0, 0, 0, 0)
137 }
138
139 return __syscall(93, 99, 0, 0, 0, 0, 0)
140}