sketch_hllmap_merge_capability_bench.nx source
↩ module page · 200 lines · 6985 B
1// sketch_hllmap_merge_capability_bench.nx -- capability-EXCEED bench.
2//
3// CLAIM TO VALIDATE:
4// Apache DataSketches HllMap supports add() and estimate() but
5// NOT merge() of two HllMaps. Substrate ships merge via per-key
6// HLL register-max + key-union. This bench DEMONSTRATES the
7// merge operation produces results equivalent to the ground-truth
8// "stream both into one map" workflow that DS users must do
9// manually. Capability EXCEED, not a perf claim.
10//
11// WORKLOAD:
12// Map A: 3 keys with 100/50/20 distinct values each.
13// Map B: 3 keys with 75/30/40 distinct values; one key overlaps A.
14// Merged := nx_hllmap_merge(A, B)
15// Truth := add A's flat stream + B's flat stream into a single
16// fresh map
17// Per-key estimates of Merged vs Truth must agree within HLL's
18// 3-sigma band.
19//
20// MEASUREMENT:
21// For each key in the merged keyspace, compare merged estimate vs
22// truth estimate via nx_cmp_accuracy. All comparisons must produce
23// EQUIVALENT or BEATS (NEVER LOSES = the merge is mis-implemented).
24
25import "syscalls.nx"
26import "sketch_hll.nx"
27import "sketch_hllmap.nx"
28import "sketch_comparator.nx"
29import "sketch_types.nx"
30
31func iabs_m(x: i64) -> i64 {
32 if x < 0 { return -x }
33 return x
34}
35
36func write_key8(buf: *u8, value: i64) -> i64 {
37 var i: i64 = 0
38 var v: i64 = value
39 while i < 8 {
40 buf[i] = (v & 0xFF) as u8
41 v = v >> 8
42 i = i + 1
43 }
44 return 0
45}
46
47func main() -> i64 {
48 let lg_k: i64 = 8
49 let seed: i64 = 42
50
51 // Three maps: A, B, and the "ground truth" (stream both into one).
52 let a: *HllMap = nx_hllmap_alloc(16, lg_k, seed)
53 let b: *HllMap = nx_hllmap_alloc(16, lg_k, seed)
54 let truth: *HllMap = nx_hllmap_alloc(16, lg_k, seed)
55 if a == (0 as *HllMap) { return __syscall(93, 1, 0, 0, 0, 0, 0) }
56 if b == (0 as *HllMap) { return __syscall(93, 2, 0, 0, 0, 0, 0) }
57 if truth == (0 as *HllMap) { return __syscall(93, 3, 0, 0, 0, 0, 0) }
58
59 // ---- Define keys (8-byte tags) ----
60 let key_apple_raw: *u8 = sys_mmap(8)
61 let key_apple: *u8 = key_apple_raw
62 write_key8(key_apple, 0x4141) // 'AA'
63 let key_banana_raw: *u8 = sys_mmap(8)
64 let key_banana: *u8 = key_banana_raw
65 write_key8(key_banana, 0x4242) // 'BB'
66 let key_carrot_raw: *u8 = sys_mmap(8)
67 let key_carrot: *u8 = key_carrot_raw
68 write_key8(key_carrot, 0x4343)
69 let key_date_raw: *u8 = sys_mmap(8)
70 let key_date: *u8 = key_date_raw
71 write_key8(key_date, 0x4444)
72 let key_eggplant_raw: *u8 = sys_mmap(8)
73 let key_eggplant: *u8 = key_eggplant_raw
74 write_key8(key_eggplant, 0x4545)
75
76 // Value buffer (reused).
77 let val_raw: *u8 = sys_mmap(8)
78 let val: *u8 = val_raw
79
80 // ---- Populate Map A ----
81 // apple: 100 distinct values in [1, 100]
82 var i: i64 = 1
83 while i <= 100 {
84 write_key8(val, i)
85 nx_hllmap_add(a, key_apple, 8, val, 8)
86 nx_hllmap_add(truth, key_apple, 8, val, 8)
87 i = i + 1
88 }
89 // banana: 50 distinct values in [10000, 10050]
90 i = 0
91 while i < 50 {
92 write_key8(val, 10000 + i)
93 nx_hllmap_add(a, key_banana, 8, val, 8)
94 nx_hllmap_add(truth, key_banana, 8, val, 8)
95 i = i + 1
96 }
97 // carrot: 20 distinct values in [20000, 20020]
98 i = 0
99 while i < 20 {
100 write_key8(val, 20000 + i)
101 nx_hllmap_add(a, key_carrot, 8, val, 8)
102 nx_hllmap_add(truth, key_carrot, 8, val, 8)
103 i = i + 1
104 }
105
106 // ---- Populate Map B ----
107 // apple: 75 DIFFERENT distinct values in [200, 275]
108 // (key overlaps A; values disjoint -> truth ~ 175 unique)
109 i = 0
110 while i < 75 {
111 write_key8(val, 200 + i)
112 nx_hllmap_add(b, key_apple, 8, val, 8)
113 nx_hllmap_add(truth, key_apple, 8, val, 8)
114 i = i + 1
115 }
116 // date: 30 distinct values
117 i = 0
118 while i < 30 {
119 write_key8(val, 30000 + i)
120 nx_hllmap_add(b, key_date, 8, val, 8)
121 nx_hllmap_add(truth, key_date, 8, val, 8)
122 i = i + 1
123 }
124 // eggplant: 40 distinct values
125 i = 0
126 while i < 40 {
127 write_key8(val, 40000 + i)
128 nx_hllmap_add(b, key_eggplant, 8, val, 8)
129 nx_hllmap_add(truth, key_eggplant, 8, val, 8)
130 i = i + 1
131 }
132
133 // ---- HEADLINE OPERATION: nx_hllmap_merge ----
134 let merged: *HllMap = nx_hllmap_merge(a, b)
135 if merged == (0 as *HllMap) { return __syscall(93, 10, 0, 0, 0, 0, 0) }
136
137 // ---- Verify key-set union ----
138 if nx_hllmap_n_entries(merged) != 5 {
139 return __syscall(93, 11, 0, 0, 0, 0, 0)
140 }
141
142 // ---- Per-key paired accuracy vs truth ----
143 // apple: truth has 175 distinct values; merged should match
144 let m_apple: i64 = nx_hllmap_estimate(merged, key_apple, 8)
145 let t_apple: i64 = nx_hllmap_estimate(truth, key_apple, 8)
146 // Both are HLL estimates -- expect agreement within HLL noise.
147 // Use accuracy comparator: truth-of-truths is t_apple; merged is
148 // our; we expect EQUIVALENT.
149 let cmp_apple: *ComparisonResult = nx_cmp_accuracy(m_apple, m_apple, t_apple, 100000)
150 if cmp_apple.verdict == NX_CMP_VERDICT_LOSES {
151 return __syscall(93, 20, 0, 0, 0, 0, 0)
152 }
153 // Sanity: m_apple should be plausibly close to 175.
154 if iabs_m(m_apple - 175) > (175 * 25) / 100 {
155 return __syscall(93, 21, 0, 0, 0, 0, 0)
156 }
157 // Truth must also be near 175 (no merge bug in truth path).
158 if iabs_m(t_apple - 175) > (175 * 25) / 100 {
159 return __syscall(93, 22, 0, 0, 0, 0, 0)
160 }
161
162 // banana: only in A -> should be 50
163 let m_banana: i64 = nx_hllmap_estimate(merged, key_banana, 8)
164 if iabs_m(m_banana - 50) > (50 * 30) / 100 {
165 return __syscall(93, 30, 0, 0, 0, 0, 0)
166 }
167 // carrot: only in A -> 20
168 let m_carrot: i64 = nx_hllmap_estimate(merged, key_carrot, 8)
169 if iabs_m(m_carrot - 20) > (20 * 50) / 100 {
170 // 20 is at LinearCounter regime, 50% tolerance is generous
171 return __syscall(93, 31, 0, 0, 0, 0, 0)
172 }
173 // date: only in B -> 30
174 let m_date: i64 = nx_hllmap_estimate(merged, key_date, 8)
175 if iabs_m(m_date - 30) > (30 * 40) / 100 {
176 return __syscall(93, 32, 0, 0, 0, 0, 0)
177 }
178 // eggplant: only in B -> 40
179 let m_eggplant: i64 = nx_hllmap_estimate(merged, key_eggplant, 8)
180 if iabs_m(m_eggplant - 40) > (40 * 35) / 100 {
181 return __syscall(93, 33, 0, 0, 0, 0, 0)
182 }
183
184 // ---- Sanity: original maps A and B unaltered by merge ----
185 let a_apple: i64 = nx_hllmap_estimate(a, key_apple, 8)
186 if iabs_m(a_apple - 100) > (100 * 25) / 100 {
187 return __syscall(93, 40, 0, 0, 0, 0, 0)
188 }
189 let b_apple: i64 = nx_hllmap_estimate(b, key_apple, 8)
190 if iabs_m(b_apple - 75) > (75 * 30) / 100 {
191 return __syscall(93, 41, 0, 0, 0, 0, 0)
192 }
193 // A must NOT now have date (B's exclusive key)
194 let a_date: i64 = nx_hllmap_estimate(a, key_date, 8)
195 if a_date != 0 {
196 return __syscall(93, 42, 0, 0, 0, 0, 0)
197 }
198
199 return 0
200}