sketch_hllmap_test.nx source
↩ module page · 170 lines · 5095 B
1// sketch_hllmap_test.nx -- HllMap (distinct-per-key) with merge.
2
3import "syscalls.nx"
4import "sketch_hllmap.nx"
5import "sketch_hll.nx"
6import "sketch_types.nx"
7
8func iabs(x: i64) -> i64 {
9 if x < 0 { return -x }
10 return x
11}
12
13func main() -> i64 {
14 // ---- alloc ----
15 let m: *HllMap = nx_hllmap_alloc(64, 8, 42)
16 if m == (0 as *HllMap) { return __syscall(93, 5, 0, 0, 0, 0, 0) }
17 // Reject non-power-of-2.
18 if nx_hllmap_alloc(50, 8, 1) != (0 as *HllMap) {
19 return __syscall(93, 6, 0, 0, 0, 0, 0)
20 }
21 if m.n_entries != 0 { return __syscall(93, 7, 0, 0, 0, 0, 0) }
22
23 // ---- empty estimate -> 0 ----
24 if nx_hllmap_estimate(m, "url-A", 5) != 0 {
25 return __syscall(93, 10, 0, 0, 0, 0, 0)
26 }
27
28 // ---- add unique values per key ----
29 // url-A: 50 distinct IPs. url-B: 200 distinct IPs.
30 let val: *u8 = sys_mmap(8)
31 var i: i64 = 0
32 while i < 50 {
33 val[0] = (i ) & 0xFF
34 val[1] = (i >> 8 ) & 0xFF
35 val[2] = 0xA1
36 val[3] = 0
37 val[4] = 0
38 val[5] = 0
39 val[6] = 0
40 val[7] = 0
41 nx_hllmap_add(m, "url-A", 5, val, 8)
42 i = i + 1
43 }
44 i = 0
45 while i < 200 {
46 val[0] = (i ) & 0xFF
47 val[1] = (i >> 8 ) & 0xFF
48 val[2] = 0xB1
49 val[3] = 0
50 val[4] = 0
51 val[5] = 0
52 val[6] = 0
53 val[7] = 0
54 nx_hllmap_add(m, "url-B", 5, val, 8)
55 i = i + 1
56 }
57 if m.n_entries != 2 { return __syscall(93, 20, 0, 0, 0, 0, 0) }
58 // url-A estimate ~ 50. HLL_8 lg_k=8 -> 6.5% stddev. Allow 40%.
59 let est_a: i64 = nx_hllmap_estimate(m, "url-A", 5)
60 if iabs(est_a - 50) > 20 { return __syscall(93, 21, 0, 0, 0, 0, 0) }
61 // url-B estimate ~ 200.
62 let est_b: i64 = nx_hllmap_estimate(m, "url-B", 5)
63 if iabs(est_b - 200) > 50 { return __syscall(93, 22, 0, 0, 0, 0, 0) }
64 // url-C unknown -> 0.
65 if nx_hllmap_estimate(m, "url-C", 5) != 0 {
66 return __syscall(93, 23, 0, 0, 0, 0, 0)
67 }
68
69 // ---- typed envelope ----
70 let q: *ApproxI64 = nx_hllmap_query(m, "url-A", 5)
71 if q.envelope_kind != NX_ENV_REL_STDDEV {
72 return __syscall(93, 30, 0, 0, 0, 0, 0)
73 }
74 if q.param_a != 65000000 { // lg_k=8 -> 6.5%
75 return __syscall(93, 31, 0, 0, 0, 0, 0)
76 }
77 // Unknown key -> conf 1e9 (exact zero).
78 let q_unknown: *ApproxI64 = nx_hllmap_query(m, "url-C", 5)
79 if q_unknown.value != 0 {
80 return __syscall(93, 32, 0, 0, 0, 0, 0)
81 }
82 if q_unknown.conf_ppb != 1000000000 {
83 return __syscall(93, 33, 0, 0, 0, 0, 0)
84 }
85
86 // ---- merge: two maps with overlapping + disjoint keys ----
87 let m2a: *HllMap = nx_hllmap_alloc(64, 8, 42)
88 let m2b: *HllMap = nx_hllmap_alloc(64, 8, 42)
89 // m2a: url-X 100 distinct, url-Y 50 distinct
90 // m2b: url-X 100 MORE distinct, url-Z 75 distinct
91 i = 0
92 while i < 100 {
93 val[0] = i & 0xFF
94 val[1] = (i >> 8) & 0xFF
95 val[2] = 0xC1
96 val[3] = 0
97 val[4] = 0
98 val[5] = 0
99 val[6] = 0
100 val[7] = 0
101 nx_hllmap_add(m2a, "url-X", 5, val, 8)
102 i = i + 1
103 }
104 i = 0
105 while i < 50 {
106 val[0] = i & 0xFF
107 val[1] = (i >> 8) & 0xFF
108 val[2] = 0xC2
109 val[3] = 0
110 val[4] = 0
111 val[5] = 0
112 val[6] = 0
113 val[7] = 0
114 nx_hllmap_add(m2a, "url-Y", 5, val, 8)
115 i = i + 1
116 }
117 // m2b: distinct overlap for url-X via DIFFERENT byte values.
118 i = 100
119 while i < 200 {
120 val[0] = i & 0xFF
121 val[1] = (i >> 8) & 0xFF
122 val[2] = 0xC1
123 val[3] = 0
124 val[4] = 0
125 val[5] = 0
126 val[6] = 0
127 val[7] = 0
128 nx_hllmap_add(m2b, "url-X", 5, val, 8)
129 i = i + 1
130 }
131 i = 0
132 while i < 75 {
133 val[0] = i & 0xFF
134 val[1] = (i >> 8) & 0xFF
135 val[2] = 0xC3
136 val[3] = 0
137 val[4] = 0
138 val[5] = 0
139 val[6] = 0
140 val[7] = 0
141 nx_hllmap_add(m2b, "url-Z", 5, val, 8)
142 i = i + 1
143 }
144
145 let merged: *HllMap = nx_hllmap_merge(m2a, m2b)
146 if merged == (0 as *HllMap) {
147 return __syscall(93, 40, 0, 0, 0, 0, 0)
148 }
149 // merged should have 3 entries: url-X, url-Y, url-Z.
150 if merged.n_entries != 3 {
151 return __syscall(93, 41, 0, 0, 0, 0, 0)
152 }
153 // url-X had 100 + 100 distinct (disjoint). Estimate ~ 200.
154 let est_x: i64 = nx_hllmap_estimate(merged, "url-X", 5)
155 if iabs(est_x - 200) > 60 {
156 return __syscall(93, 42, 0, 0, 0, 0, 0)
157 }
158 // url-Y had 50 only in m2a; estimate ~ 50.
159 let est_y: i64 = nx_hllmap_estimate(merged, "url-Y", 5)
160 if iabs(est_y - 50) > 25 {
161 return __syscall(93, 43, 0, 0, 0, 0, 0)
162 }
163 // url-Z had 75 only in m2b; estimate ~ 75.
164 let est_z: i64 = nx_hllmap_estimate(merged, "url-Z", 5)
165 if iabs(est_z - 75) > 30 {
166 return __syscall(93, 44, 0, 0, 0, 0, 0)
167 }
168
169 return 0
170}