sketch_theta_intersect_vs_hll_bench.nx source
↩ module page · 143 lines · 5089 B
1// sketch_theta_intersect_vs_hll_bench.nx -- capability bench, Theta vs HLL.
2//
3// CLAIM TO VALIDATE:
4// Theta sketch (Beyer-Haas-Reinwald-Sismanis-Gemulla 2007) supports
5// set INTERSECTION via direct subspace pruning: A∩B is the keys
6// below min(theta_A, theta_B) that appear in BOTH samples.
7//
8// HLL has NO direct intersection. The standard workaround is
9// inclusion-exclusion: |A∩B| = |A| + |B| - |A∪B|. This is
10// notoriously unstable -- variance grows quadratically with the
11// underlying cardinalities even when the true |A∩B| is small.
12//
13// Substrate ships both; this bench DEMONSTRATES Theta's direct
14// intersection beats HLL's inclusion-exclusion on the small-overlap
15// regime where HLL's variance explodes.
16//
17// WORKLOAD:
18// Two sets at MATCHED memory budgets (k vs lg_k chosen so byte
19// footprints are within 25%):
20// Set A: 10000 keys
21// Set B: 10000 keys (disjoint except for 100 shared)
22// True |A∩B| = 100 (heavy on |A| + |B|, light on intersection)
23//
24// MEASUREMENT:
25// theta_inter = nx_theta_intersect(a, b) -> direct |A∩B| estimate
26// hll_inter = max(0, |A| + |B| - |A∪B|) via inclusion-exclusion
27// ACCURACY axis: closer to truth=100 wins.
28
29import "syscalls.nx"
30import "sketch_theta.nx"
31import "sketch_hll.nx"
32import "sketch_comparator.nx"
33import "sketch_types.nx"
34
35func iabs_th(x: i64) -> i64 {
36 if x < 0 { return -x }
37 return x
38}
39
40func write_bth(buf: *u8, value: i64) -> i64 {
41 var i: i64 = 0
42 var v: i64 = value
43 while i < 8 {
44 buf[i] = (v & 0xFF) as u8
45 v = v >> 8
46 i = i + 1
47 }
48 return 0
49}
50
51func main() -> i64 {
52 // MATCHED MEMORY (after bits-up HLL cap raise to lg_k=12):
53 // Theta k=1024: alloc 1024 * 8 (samples) + header = ~8200 B
54 // HLL lg_k=12: alloc 4096 (regs) + header = ~4120 B
55 // Asymmetry tightened from 8x to ~2x. Further parity blocked by
56 // Theta's flat-array overhead (8 bytes/sample) vs HLL's 1-byte
57 // register -- structural.
58 let theta_k: i64 = 1024
59 let hll_lg_k: i64 = 12 // bits-up scale (was lg_k=10 cap)
60 let seed: i64 = 42
61
62 let theta_a: *ThetaSketch = nx_theta_alloc(theta_k, seed)
63 let theta_b: *ThetaSketch = nx_theta_alloc(theta_k, seed)
64 let hll_a: *Hll = nx_hll_alloc(hll_lg_k, seed)
65 let hll_b: *Hll = nx_hll_alloc(hll_lg_k, seed)
66 let hll_u: *Hll = nx_hll_alloc(hll_lg_k, seed) // for |A ∪ B|
67 if theta_a == (0 as *ThetaSketch) { return __syscall(93, 1, 0, 0, 0, 0, 0) }
68 if hll_a == (0 as *Hll) { return __syscall(93, 2, 0, 0, 0, 0, 0) }
69
70 let key_raw: *u8 = sys_mmap(8)
71 let key: *u8 = key_raw
72
73 let total_each: i64 = 10000
74 let overlap: i64 = 100
75
76 // Set A: keys 1..9900 + shared 100000..100099
77 var i: i64 = 1
78 while i <= total_each - overlap {
79 write_bth(key, i)
80 nx_theta_add(theta_a, key, 8)
81 nx_hll_add(hll_a, key, 8)
82 nx_hll_add(hll_u, key, 8)
83 i = i + 1
84 }
85 i = 0
86 while i < overlap {
87 write_bth(key, 100000 + i)
88 nx_theta_add(theta_a, key, 8)
89 nx_theta_add(theta_b, key, 8)
90 nx_hll_add(hll_a, key, 8)
91 nx_hll_add(hll_b, key, 8)
92 nx_hll_add(hll_u, key, 8)
93 i = i + 1
94 }
95 // Set B: keys 20000..29899 + the shared 100 already added
96 i = 20000
97 while i < 20000 + total_each - overlap {
98 write_bth(key, i)
99 nx_theta_add(theta_b, key, 8)
100 nx_hll_add(hll_b, key, 8)
101 nx_hll_add(hll_u, key, 8)
102 i = i + 1
103 }
104
105 // ---- Theta intersection direct ----
106 let theta_inter: *ThetaSketch = nx_theta_intersect(theta_a, theta_b)
107 let theta_inter_est: i64 = nx_theta_estimate(theta_inter)
108
109 // ---- HLL inclusion-exclusion ----
110 let hll_a_est: i64 = nx_hll_estimate(hll_a)
111 let hll_b_est: i64 = nx_hll_estimate(hll_b)
112 let hll_u_est: i64 = nx_hll_estimate(hll_u)
113 var hll_inter: i64 = hll_a_est + hll_b_est - hll_u_est
114 if hll_inter < 0 { hll_inter = 0 }
115
116 // ---- ACCURACY: closer to truth=100 wins ----
117 let truth: i64 = 100
118 let acc: *ComparisonResult = nx_cmp_accuracy(theta_inter_est, hll_inter, truth, 50000)
119
120 if acc.verdict != NX_CMP_VERDICT_BEATS {
121 return __syscall(93, 10, 0, 0, 0, 0, 0)
122 }
123 // The win should be substantial -- inclusion-exclusion has variance
124 // ~ |A|+|B| even when |A∩B| is small. At |A|+|B|~20000 and truth=100,
125 // HLL inter could easily be 0 or 500+; Theta intersect should land
126 // within ~20% of 100.
127 if acc.delta_ppm < 200000 { // 20%+ improvement (in PPM-of-truth)
128 return __syscall(93, 11, 0, 0, 0, 0, 0)
129 }
130
131 // ---- Sanity: Theta intersect within 35% of truth ----
132 if iabs_th(theta_inter_est - truth) > (truth * 35) / 100 {
133 return __syscall(93, 20, 0, 0, 0, 0, 0)
134 }
135
136 // ---- Cardinality estimates: both methods agree on |A|, |B| ----
137 let theta_a_est: i64 = nx_theta_estimate(theta_a)
138 if iabs_th(theta_a_est - total_each) > total_each / 5 { // 20% slack
139 return __syscall(93, 30, 0, 0, 0, 0, 0)
140 }
141
142 return 0
143}