sketch_tuple_test.nx source
↩ module page · 166 lines · 5786 B
1// sketch_tuple_test.nx -- Tuple sketch (Theta + scalar) with reducer + merge.
2
3import "syscalls.nx"
4import "sketch_tuple.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: *TupleSketch = nx_tuple_alloc(128, 1, NX_TUPLE_RED_SUM)
15 if t == (0 as *TupleSketch) { return __syscall(93, 5, 0, 0, 0, 0, 0) }
16 if t.n_items != 0 { return __syscall(93, 6, 0, 0, 0, 0, 0) }
17 if nx_tuple_aggregate(t) != 0 { return __syscall(93, 7, 0, 0, 0, 0, 0) }
18 // Reject invalid reducer.
19 if nx_tuple_alloc(128, 1, 99) != (0 as *TupleSketch) {
20 return __syscall(93, 8, 0, 0, 0, 0, 0)
21 }
22
23 // ---- SUM reducer: multiple values per key accumulate ----
24 nx_tuple_add(t, "alice", 5, 100)
25 nx_tuple_add(t, "alice", 5, 50)
26 nx_tuple_add(t, "bob", 3, 200)
27 nx_tuple_add(t, "alice", 5, 25)
28 if t.n_items != 2 { return __syscall(93, 10, 0, 0, 0, 0, 0) }
29 // alice: 100+50+25 = 175. bob: 200. Sum: 375.
30 if nx_tuple_aggregate(t) != 375 {
31 return __syscall(93, 11, 0, 0, 0, 0, 0)
32 }
33 // Cardinality: 2 distinct keys.
34 if nx_tuple_cardinality(t) != 2 {
35 return __syscall(93, 12, 0, 0, 0, 0, 0)
36 }
37
38 // ---- MAX reducer ----
39 let tmax: *TupleSketch = nx_tuple_alloc(128, 1, NX_TUPLE_RED_MAX)
40 nx_tuple_add(tmax, "alice", 5, 50)
41 nx_tuple_add(tmax, "alice", 5, 100)
42 nx_tuple_add(tmax, "alice", 5, 25)
43 nx_tuple_add(tmax, "bob", 3, 300)
44 if tmax.n_items != 2 { return __syscall(93, 20, 0, 0, 0, 0, 0) }
45 // alice: max(50,100,25) = 100. bob: 300. Sum: 400.
46 if nx_tuple_aggregate(tmax) != 400 {
47 return __syscall(93, 21, 0, 0, 0, 0, 0)
48 }
49
50 // ---- MIN reducer ----
51 let tmin: *TupleSketch = nx_tuple_alloc(128, 1, NX_TUPLE_RED_MIN)
52 nx_tuple_add(tmin, "alice", 5, 50)
53 nx_tuple_add(tmin, "alice", 5, 100)
54 nx_tuple_add(tmin, "alice", 5, 25)
55 if tmin.n_items != 1 { return __syscall(93, 30, 0, 0, 0, 0, 0) }
56 // alice: min(50,100,25) = 25.
57 if nx_tuple_aggregate(tmin) != 25 {
58 return __syscall(93, 31, 0, 0, 0, 0, 0)
59 }
60
61 // ---- REPLACE reducer: last write wins ----
62 let trep: *TupleSketch = nx_tuple_alloc(128, 1, NX_TUPLE_RED_REPLACE)
63 nx_tuple_add(trep, "alice", 5, 50)
64 nx_tuple_add(trep, "alice", 5, 100)
65 nx_tuple_add(trep, "alice", 5, 999)
66 if nx_tuple_aggregate(trep) != 999 {
67 return __syscall(93, 40, 0, 0, 0, 0, 0)
68 }
69
70 // ---- streaming past cap: theta tightens ----
71 let t2: *TupleSketch = nx_tuple_alloc(128, 7, NX_TUPLE_RED_SUM)
72 let buf: *u8 = sys_mmap(8)
73 var i: i64 = 0
74 while i < 1000 {
75 buf[0] = i & 0xFF
76 buf[1] = (i >> 8) & 0xFF
77 buf[2] = 0x30
78 buf[3] = 0
79 buf[4] = 0
80 buf[5] = 0
81 buf[6] = 0
82 buf[7] = 0
83 nx_tuple_add(t2, buf, 8, 10) // each key worth $10
84 i = i + 1
85 }
86 if t2.n_items != 128 { return __syscall(93, 50, 0, 0, 0, 0, 0) }
87 if t2.theta == 4294967296 { return __syscall(93, 51, 0, 0, 0, 0, 0) }
88 // True sum: 1000 * 10 = 10_000. Theta-corrected estimate
89 // should be within 35% (1/sqrt(127) margin loose).
90 let est_sum: i64 = nx_tuple_aggregate(t2)
91 if iabs(est_sum - 10000) > 3500 {
92 return __syscall(93, 52, 0, 0, 0, 0, 0)
93 }
94 // Cardinality ~ 1000.
95 let est_card: i64 = nx_tuple_cardinality(t2)
96 if iabs(est_card - 1000) > 350 {
97 return __syscall(93, 53, 0, 0, 0, 0, 0)
98 }
99
100 // ---- merge: identical sketches -> same aggregate ----
101 let m_a: *TupleSketch = nx_tuple_alloc(64, 5, NX_TUPLE_RED_SUM)
102 let m_b: *TupleSketch = nx_tuple_alloc(64, 5, NX_TUPLE_RED_SUM)
103 i = 0
104 while i < 100 {
105 buf[0] = i & 0xFF
106 buf[1] = (i >> 8) & 0xFF
107 buf[2] = 0x40
108 buf[3] = 0
109 buf[4] = 0
110 buf[5] = 0
111 buf[6] = 0
112 buf[7] = 0
113 nx_tuple_add(m_a, buf, 8, 5)
114 nx_tuple_add(m_b, buf, 8, 5)
115 i = i + 1
116 }
117 let merged_ab: *TupleSketch = nx_tuple_merge(m_a, m_b)
118 if merged_ab == (0 as *TupleSketch) {
119 return __syscall(93, 60, 0, 0, 0, 0, 0)
120 }
121 // Identical hashes; reducer=SUM combines 5+5=10 per key. True
122 // sum: 100 * 10 = 1000.
123 let m_agg: i64 = nx_tuple_aggregate(merged_ab)
124 if iabs(m_agg - 1000) > 200 {
125 return __syscall(93, 61, 0, 0, 0, 0, 0)
126 }
127
128 // ---- merge: disjoint sketches -> sum of individual aggregates ----
129 let d_a: *TupleSketch = nx_tuple_alloc(64, 5, NX_TUPLE_RED_SUM)
130 let d_b: *TupleSketch = nx_tuple_alloc(64, 5, NX_TUPLE_RED_SUM)
131 i = 0
132 while i < 50 {
133 buf[0] = i & 0xFF
134 buf[1] = (i >> 8) & 0xFF
135 buf[2] = 0xAA
136 buf[3] = 0
137 buf[4] = 0
138 buf[5] = 0
139 buf[6] = 0
140 buf[7] = 0
141 nx_tuple_add(d_a, buf, 8, 7)
142 buf[2] = 0xBB
143 nx_tuple_add(d_b, buf, 8, 7)
144 i = i + 1
145 }
146 let merged_disj: *TupleSketch = nx_tuple_merge(d_a, d_b)
147 // disjoint: card ~ 100; sum ~ 100*7 = 700.
148 let d_agg: i64 = nx_tuple_aggregate(merged_disj)
149 if iabs(d_agg - 700) > 200 {
150 return __syscall(93, 70, 0, 0, 0, 0, 0)
151 }
152
153 // ---- typed envelope ----
154 let q: *ApproxI64 = nx_tuple_query_aggregate(t2)
155 if q.envelope_kind != NX_ENV_REL_STDDEV {
156 return __syscall(93, 80, 0, 0, 0, 0, 0)
157 }
158 if q.param_a != 62700000 { // 1/sqrt(255) for k=128 -> bucket k<=256
159 return __syscall(93, 81, 0, 0, 0, 0, 0)
160 }
161 if q.conf_ppb != 682700000 {
162 return __syscall(93, 82, 0, 0, 0, 0, 0)
163 }
164
165 return 0
166}