sketch_ams_vs_naive_bench.nx source
↩ module page · 126 lines · 4094 B
1// sketch_ams_vs_naive_bench.nx -- AMS F_2 vs naive exact tracker.
2//
3// CLAIM TO VALIDATE:
4// AMS sketch (Alon-Matias-Szegedy 1996) estimates F_2 = sum_i f_i^2
5// in O(d*s) memory regardless of distinct-item count. Naive exact
6// tracker needs O(distinct_items) memory. Apache DataSketches does
7// NOT ship AMS or any F_2 estimator -- this is greenfield in the
8// summarization-sketch family.
9//
10// WORKLOAD:
11// 1000 distinct items with Zipfian-ish counts.
12//
13// MEASUREMENT AXES:
14// ACCURACY: AMS estimate vs true F_2 (computed naively)
15// AMS bound: rel stddev ~ sqrt(2/s) at conf 0.68.
16// For s=256, rel stddev ~ 0.088, so |AMS - truth|/truth
17// should be <= 2*sigma = 0.176 (95% conf). We allow 25%.
18// MEMORY: AMS bytes vs naive bytes; expect AMS smaller for >100
19// distinct items.
20//
21// HARD-WIN GATE:
22// MEMORY BEATS by >50% AND
23// AMS estimate within ENV envelope band of truth.
24
25import "syscalls.nx"
26import "sketch_ams.nx"
27import "sketch_comparator.nx"
28import "sketch_types.nx"
29
30func iabs_am(x: i64) -> i64 {
31 if x < 0 { return -x }
32 return x
33}
34
35func main() -> i64 {
36 let d: i64 = 5
37 let s: i64 = 256
38 let seed: i64 = 42
39 let n_items: i64 = 1000
40
41 let ams: *AMS = nx_ams_alloc(d, s, seed)
42 if ams == (0 as *AMS) { return __syscall(93, 1, 0, 0, 0, 0, 0) }
43
44 // ---- Naive baseline: parallel arrays (key, count) ----
45 let naive_keys_raw: *u8 = sys_mmap(n_items * 8)
46 let naive_keys: *i64 = naive_keys_raw as *i64
47 let naive_counts_raw: *u8 = sys_mmap(n_items * 8)
48 let naive_counts: *i64 = naive_counts_raw as *i64
49 var i: i64 = 0
50 while i < n_items {
51 naive_keys[i] = i + 1
52 naive_counts[i] = 0
53 i = i + 1
54 }
55
56 // ---- Zipfian-ish stream: item k gets count = (n_items / k) ----
57 // For k=1: count=1000. k=10: count=100. k=100: count=10.
58 // k=1000: count=1. Skew is heavy-tailed.
59 i = 1
60 while i <= n_items {
61 let key: i64 = i
62 let cnt: i64 = n_items / i
63 // Insert cnt times into AMS
64 var j: i64 = 0
65 while j < cnt {
66 nx_ams_add(ams, key, 1)
67 j = j + 1
68 }
69 // Increment naive
70 naive_counts[i - 1] = cnt
71 i = i + 1
72 }
73
74 // ---- Compute true F_2 = sum count^2 ----
75 var true_f2: i64 = 0
76 i = 0
77 while i < n_items {
78 let c: i64 = naive_counts[i]
79 true_f2 = true_f2 + c * c
80 i = i + 1
81 }
82
83 // ---- AMS estimate ----
84 let ams_est: i64 = nx_ams_f2(ams)
85
86 // ---- ACCURACY: AMS within 25% of truth ----
87 let acc_err: i64 = iabs_am(ams_est - true_f2)
88 let acc_bound: i64 = (true_f2 * 25) / 100
89 if acc_err > acc_bound {
90 return __syscall(93, 10, 0, 0, 0, 0, 0)
91 }
92
93 // ---- MEMORY axis: AMS smaller than naive ----
94 let ams_bytes: i64 = d * s * 8 + 32 // counters + header
95 let naive_bytes: i64 = n_items * 16 // (key, count) pairs
96 let mem: *ComparisonResult = nx_cmp_memory(ams_bytes, naive_bytes, 100000)
97
98 if mem.verdict != NX_CMP_VERDICT_BEATS {
99 return __syscall(93, 20, 0, 0, 0, 0, 0)
100 }
101 if mem.delta_ppm < 500000 { // 50% memory reduction expected
102 return __syscall(93, 21, 0, 0, 0, 0, 0)
103 }
104
105 // ---- Sanity: AMS query envelope reports REL_STDDEV correctly ----
106 let q: *ApproxI64 = nx_ams_query_f2(ams)
107 if q.envelope_kind != NX_ENV_REL_STDDEV {
108 return __syscall(93, 30, 0, 0, 0, 0, 0)
109 }
110 if q.maturity != NX_MATURITY_REFERENCE_IMPL {
111 return __syscall(93, 31, 0, 0, 0, 0, 0)
112 }
113 if q.adv_safety != NX_ADV_HONEST {
114 return __syscall(93, 32, 0, 0, 0, 0, 0)
115 }
116
117 // ---- Envelope honesty: empirical err / truth <= 2 * declared rel_stddev ----
118 // declared rel_stddev_ppb = q.param_a; we compute empirical_rel_err_ppb
119 // and assert it is within 2x.
120 let empirical_rel_err_ppb: i64 = (acc_err * 1000000000) / true_f2
121 if empirical_rel_err_ppb > q.param_a * 2 {
122 return __syscall(93, 33, 0, 0, 0, 0, 0)
123 }
124
125 return 0
126}