sketch_cms_test.nx source
↩ module page · 137 lines · 4682 B
1// sketch_cms_test.nx -- Count-Min Sketch behavioral test.
2//
3// Tests:
4// 1. Empty CMS returns 0 for any key
5// 2. Single-key insert with count 7 -> estimate >= 7
6// (overestimate-only; may be inflated by collisions)
7// 3. Overestimate-only invariant: stream N items, every query
8// returns >= true count
9// 4. Error bound: estimate <= true + eps*totalCount with very
10// high probability across many keys
11// 5. Merge: counter-wise sum, totalCount adds
12// 6. Typed envelope: NX_ENV_ABS (NOT rel_stddev), conf reflects d
13
14import "syscalls.nx"
15import "sketch_cms.nx"
16import "sketch_types.nx"
17
18func write_i64_le(buf: *u8, value: i64) -> i64 {
19 var i: i64 = 0
20 var v: i64 = value
21 while i < 8 { buf[i] = v & 0xFF; v = v >> 8; i = i + 1 }
22 return 0
23}
24
25func main() -> i64 {
26 // d=5, w=512: eps ~ e/512 ~ 0.0053, delta ~ 0.0067
27 // Memory: 5 * 512 * 8 = 20480 bytes counters + small header
28 let c: *Cms = nx_cms_alloc(5, 512, 0)
29 if c == (0 as *Cms) { return __syscall(93, 5, 0, 0, 0, 0, 0) }
30
31 // ---- empty -> 0 ----
32 let key0: *u8 = sys_mmap(8)
33 write_i64_le(key0, 999999)
34 if nx_cms_estimate(c, key0, 8) != 0 {
35 return __syscall(93, 10, 0, 0, 0, 0, 0)
36 }
37
38 // ---- single insert with count 7 ----
39 write_i64_le(key0, 1)
40 nx_cms_add(c, key0, 8, 7)
41 let est_single: i64 = nx_cms_estimate(c, key0, 8)
42 if est_single < 7 { return __syscall(93, 20, 0, 0, 0, 0, 0) }
43 // Should be tight (no collisions yet on a fresh sketch).
44 if est_single > 7 + 5 {
45 return __syscall(93, 21, 0, 0, 0, 0, 0)
46 }
47
48 // ---- overestimate-only invariant on 200 distinct keys ----
49 let c2: *Cms = nx_cms_alloc(5, 512, 0)
50 let key: *u8 = sys_mmap(8)
51 var i: i64 = 0
52 while i < 200 {
53 write_i64_le(key, 1000 + i)
54 nx_cms_add(c2, key, 8, 1)
55 i = i + 1
56 }
57 // Every inserted key should estimate >= 1 (its true count).
58 i = 0
59 while i < 200 {
60 write_i64_le(key, 1000 + i)
61 let est: i64 = nx_cms_estimate(c2, key, 8)
62 if est < 1 {
63 return __syscall(93, 30, 0, 0, 0, 0, 0)
64 }
65 i = i + 1
66 }
67
68 // ---- error bound: estimate <= true + eps*totalCount ----
69 // For w=512, eps ~ e/512 ~ 0.0053. N=200 -> bound ~ 1.06 (effectively 1-2).
70 // Verify estimate <= 1 + 2 = 3 for at least 95% of keys.
71 var violations: i64 = 0
72 i = 0
73 while i < 200 {
74 write_i64_le(key, 1000 + i)
75 let est: i64 = nx_cms_estimate(c2, key, 8)
76 if est > 3 { violations = violations + 1 }
77 i = i + 1
78 }
79 // Allow up to 5% violations (= 10 out of 200) for the eps bound
80 // to land within slack.
81 if violations > 10 {
82 return __syscall(93, 40, 0, 0, 0, 0, 0)
83 }
84
85 // ---- heavy-hitter detection ----
86 let c3: *Cms = nx_cms_alloc(5, 512, 0)
87 // 100 background items at count 1 each.
88 i = 0
89 while i < 100 {
90 write_i64_le(key, 2000 + i)
91 nx_cms_add(c3, key, 8, 1)
92 i = i + 1
93 }
94 // Heavy hitter at count 500.
95 write_i64_le(key, 99999)
96 nx_cms_add(c3, key, 8, 500)
97 let est_heavy: i64 = nx_cms_estimate(c3, key, 8)
98 if est_heavy < 500 { return __syscall(93, 50, 0, 0, 0, 0, 0) }
99 if est_heavy > 510 { return __syscall(93, 51, 0, 0, 0, 0, 0) }
100
101 // ---- merge ----
102 let a: *Cms = nx_cms_alloc(3, 256, 7)
103 let b: *Cms = nx_cms_alloc(3, 256, 7)
104 write_i64_le(key, 42)
105 nx_cms_add(a, key, 8, 3)
106 nx_cms_add(b, key, 8, 5)
107 let m: *Cms = nx_cms_merge(a, b)
108 if m == (0 as *Cms) { return __syscall(93, 60, 0, 0, 0, 0, 0) }
109 if m.total_count != 8 { return __syscall(93, 61, 0, 0, 0, 0, 0) }
110 let est_merge: i64 = nx_cms_estimate(m, key, 8)
111 if est_merge < 8 { return __syscall(93, 62, 0, 0, 0, 0, 0) }
112
113 // Merge rejects mismatched dimensions.
114 let bad: *Cms = nx_cms_alloc(3, 512, 7) // different w
115 let m_bad: *Cms = nx_cms_merge(a, bad)
116 if m_bad != (0 as *Cms) {
117 return __syscall(93, 63, 0, 0, 0, 0, 0)
118 }
119
120 // ---- typed envelope ----
121 let q: *ApproxI64 = nx_cms_query(c2, key, 8)
122 if q.envelope_kind != NX_ENV_ABS {
123 return __syscall(93, 70, 0, 0, 0, 0, 0)
124 }
125 if q.maturity != NX_MATURITY_REFERENCE_IMPL {
126 return __syscall(93, 71, 0, 0, 0, 0, 0)
127 }
128 if q.adv_safety != NX_ADV_HONEST {
129 return __syscall(93, 72, 0, 0, 0, 0, 0)
130 }
131 // For d=5, conf should be 993_300_000 (= 1 - 1/e^5).
132 if q.conf_ppb != 993300000 {
133 return __syscall(93, 73, 0, 0, 0, 0, 0)
134 }
135
136 return 0
137}