sketch_theta_test.nx source
↩ module page · 143 lines · 4797 B
1// sketch_theta_test.nx -- Theta sketch union + intersection + difference.
2
3import "syscalls.nx"
4import "sketch_theta.nx"
5import "sketch_types.nx"
6
7func iabs(x: i64) -> i64 {
8 if x < 0 { return -x }
9 return x
10}
11
12func main() -> i64 {
13 // ---- alloc + empty ----
14 let t: *ThetaSketch = nx_theta_alloc(128, 7)
15 if t == (0 as *ThetaSketch) { return __syscall(93, 5, 0, 0, 0, 0, 0) }
16 if nx_theta_estimate(t) != 0 { return __syscall(93, 10, 0, 0, 0, 0, 0) }
17 // theta initial = HASH_MAX
18 if t.theta != 4294967296 { return __syscall(93, 11, 0, 0, 0, 0, 0) }
19
20 let buf: *u8 = sys_mmap(8)
21
22 // ---- under-cap: exact counting + theta unchanged ----
23 var i: i64 = 0
24 while i < 50 {
25 buf[0] = i & 0xFF
26 buf[1] = (i >> 8) & 0xFF
27 buf[2] = 0x10
28 buf[3] = 0
29 buf[4] = 0
30 buf[5] = 0
31 buf[6] = 0
32 buf[7] = 0
33 nx_theta_add(t, buf, 8)
34 i = i + 1
35 }
36 if t.n_items != 50 { return __syscall(93, 20, 0, 0, 0, 0, 0) }
37 if t.theta != 4294967296 { return __syscall(93, 21, 0, 0, 0, 0, 0) }
38 if nx_theta_estimate(t) != 50 { return __syscall(93, 22, 0, 0, 0, 0, 0) }
39
40 // ---- fill past cap: theta tightens to kth_smallest ----
41 let t2: *ThetaSketch = nx_theta_alloc(128, 7)
42 i = 0
43 while i < 1000 {
44 buf[0] = i & 0xFF
45 buf[1] = (i >> 8) & 0xFF
46 buf[2] = 0x10
47 buf[3] = 0
48 buf[4] = 0
49 buf[5] = 0
50 buf[6] = 0
51 buf[7] = 0
52 nx_theta_add(t2, buf, 8)
53 i = i + 1
54 }
55 if t2.n_items != 128 { return __syscall(93, 30, 0, 0, 0, 0, 0) }
56 if t2.theta == 4294967296 { return __syscall(93, 31, 0, 0, 0, 0, 0) }
57 if t2.theta != t2.values[127] { return __syscall(93, 32, 0, 0, 0, 0, 0) }
58 let est2: i64 = nx_theta_estimate(t2)
59 // 1/sqrt(127) = 8.9%; allow 35% margin.
60 if iabs(est2 - 1000) > 350 { return __syscall(93, 33, 0, 0, 0, 0, 0) }
61
62 // ---- intersection: identical sketches -> same as input ----
63 let t3a: *ThetaSketch = nx_theta_alloc(64, 5)
64 let t3b: *ThetaSketch = nx_theta_alloc(64, 5)
65 i = 0
66 while i < 500 {
67 buf[0] = i & 0xFF
68 buf[1] = (i >> 8) & 0xFF
69 buf[2] = 0x20
70 buf[3] = 0
71 buf[4] = 0
72 buf[5] = 0
73 buf[6] = 0
74 buf[7] = 0
75 nx_theta_add(t3a, buf, 8)
76 nx_theta_add(t3b, buf, 8)
77 i = i + 1
78 }
79 let inter_aa: *ThetaSketch = nx_theta_intersect(t3a, t3b)
80 if inter_aa.n_items != t3a.n_items { return __syscall(93, 40, 0, 0, 0, 0, 0) }
81 i = 0
82 while i < inter_aa.n_items {
83 if inter_aa.values[i] != t3a.values[i] {
84 return __syscall(93, 41, 0, 0, 0, 0, 0)
85 }
86 i = i + 1
87 }
88 // Cardinality of A ∩ A == cardinality of A.
89 let est_inter: i64 = nx_theta_estimate(inter_aa)
90 let est_a: i64 = nx_theta_estimate(t3a)
91 if iabs(est_inter - est_a) > 100 { return __syscall(93, 42, 0, 0, 0, 0, 0) }
92
93 // ---- intersection: disjoint inputs -> empty ----
94 let t4a: *ThetaSketch = nx_theta_alloc(64, 5)
95 let t4b: *ThetaSketch = nx_theta_alloc(64, 5)
96 i = 0
97 while i < 200 {
98 buf[0] = i & 0xFF
99 buf[1] = (i >> 8) & 0xFF
100 buf[2] = 0xAA // disjoint hash space
101 buf[3] = 0
102 buf[4] = 0
103 buf[5] = 0
104 buf[6] = 0
105 buf[7] = 0
106 nx_theta_add(t4a, buf, 8)
107 buf[2] = 0xBB
108 nx_theta_add(t4b, buf, 8)
109 i = i + 1
110 }
111 let inter_disj: *ThetaSketch = nx_theta_intersect(t4a, t4b)
112 // Should be empty or near-empty (small chance of hash collision).
113 if inter_disj.n_items > 4 { return __syscall(93, 50, 0, 0, 0, 0, 0) }
114
115 // ---- difference: A \ A -> empty ----
116 let diff_aa: *ThetaSketch = nx_theta_difference(t3a, t3b)
117 if diff_aa.n_items != 0 { return __syscall(93, 60, 0, 0, 0, 0, 0) }
118
119 // ---- difference: A \ empty -> A ----
120 let empty: *ThetaSketch = nx_theta_alloc(64, 5)
121 let diff_aE: *ThetaSketch = nx_theta_difference(t3a, empty)
122 if diff_aE.n_items != t3a.n_items { return __syscall(93, 61, 0, 0, 0, 0, 0) }
123 i = 0
124 while i < diff_aE.n_items {
125 if diff_aE.values[i] != t3a.values[i] {
126 return __syscall(93, 62, 0, 0, 0, 0, 0)
127 }
128 i = i + 1
129 }
130
131 // ---- typed envelope ----
132 let q: *ApproxI64 = nx_theta_query(t2)
133 if q.envelope_kind != NX_ENV_REL_STDDEV {
134 return __syscall(93, 70, 0, 0, 0, 0, 0)
135 }
136 // k=128 -> bucket 256: stddev = 1/sqrt(255) ppb
137 if q.param_a != 62700000 {
138 return __syscall(93, 71, 0, 0, 0, 0, 0)
139 }
140 if q.conf_ppb != 682700000 { return __syscall(93, 72, 0, 0, 0, 0, 0) }
141
142 return 0
143}