sketch_lossy_counting_test.nx source
↩ module page · 99 lines · 3278 B
1// sketch_lossy_counting_test.nx -- Manku-Motwani Lossy Counting verification.
2
3import "syscalls.nx"
4import "sketch_lossy_counting.nx"
5import "sketch_types.nx"
6
7func main() -> i64 {
8 // ---- alloc ----
9 let lc: *LossyCounting = nx_lc_alloc(1024, 10000) // eps = 1%
10 if lc == (0 as *LossyCounting) { return __syscall(93, 5, 0, 0, 0, 0, 0) }
11 // Reject epsilon out of range.
12 if nx_lc_alloc(1024, 50) != (0 as *LossyCounting) {
13 return __syscall(93, 6, 0, 0, 0, 0, 0)
14 }
15 if nx_lc_alloc(1024, 1000000) != (0 as *LossyCounting) {
16 return __syscall(93, 7, 0, 0, 0, 0, 0)
17 }
18 // Reject non-power-of-2 capacity.
19 if nx_lc_alloc(100, 10000) != (0 as *LossyCounting) {
20 return __syscall(93, 8, 0, 0, 0, 0, 0)
21 }
22
23 // ---- bucket size derived from epsilon ----
24 // eps=1% -> bucket_size = 100.
25 if lc.bucket_size != 100 {
26 return __syscall(93, 10, 0, 0, 0, 0, 0)
27 }
28
29 // ---- under-cap exact counting ----
30 nx_lc_add(lc, 42)
31 nx_lc_add(lc, 42)
32 nx_lc_add(lc, 42)
33 if nx_lc_estimate(lc, 42) != 3 {
34 return __syscall(93, 20, 0, 0, 0, 0, 0)
35 }
36 // Unknown key returns 0.
37 if nx_lc_estimate(lc, 999) != 0 {
38 return __syscall(93, 21, 0, 0, 0, 0, 0)
39 }
40
41 // ---- heavy hitter survives bucket pruning ----
42 // Item 42 inserted 200 times in a stream where many other items
43 // each appear once. Bucket boundary (every 100 items) prunes
44 // light items but heavy survives.
45 let lc2: *LossyCounting = nx_lc_alloc(1024, 10000)
46 var i: i64 = 0
47 // Stream: alternating heavy (42) and unique (1000+i).
48 while i < 100 {
49 nx_lc_add(lc2, 42)
50 nx_lc_add(lc2, 1000 + i)
51 i = i + 1
52 }
53 // 42 inserted 100 times; many unique items each once.
54 let est_heavy: i64 = nx_lc_estimate(lc2, 42)
55 // Lossy Counting guarantee: estimate >= true_freq - eps*N
56 // true_freq = 100; eps=1%, N=200 -> max undercount = 2.
57 // estimate >= 98.
58 if est_heavy < 98 {
59 return __syscall(93, 30, 0, 0, 0, 0, 0)
60 }
61 // Estimate never exceeds true freq.
62 if est_heavy > 100 {
63 return __syscall(93, 31, 0, 0, 0, 0, 0)
64 }
65
66 // ---- upper bound: stored + error ----
67 let ub: i64 = nx_lc_upper_bound(lc2, 42)
68 // Upper bound must >= true freq (100).
69 if ub < 100 {
70 return __syscall(93, 40, 0, 0, 0, 0, 0)
71 }
72
73 // ---- light items pruned ----
74 // Most unique items should have been pruned away.
75 // n_entries should be much less than 200.
76 if nx_lc_n_entries(lc2) > 50 {
77 return __syscall(93, 50, 0, 0, 0, 0, 0)
78 }
79
80 // ---- typed envelope ----
81 let q: *ApproxI64 = nx_lc_query(lc2, 42)
82 if q.envelope_kind != NX_ENV_ABS {
83 return __syscall(93, 60, 0, 0, 0, 0, 0)
84 }
85 // param_a = max_undercount = eps*N = 0.01*200 = 2.
86 if q.param_a != 2 {
87 return __syscall(93, 61, 0, 0, 0, 0, 0)
88 }
89 if q.conf_ppb != 1000000000 { // deterministic
90 return __syscall(93, 62, 0, 0, 0, 0, 0)
91 }
92
93 // ---- sentinel key (0) rejected ----
94 if nx_lc_add(lc2, 0) != -1 {
95 return __syscall(93, 70, 0, 0, 0, 0, 0)
96 }
97
98 return 0
99}