sketch_kll_test.nx source
↩ module page · 110 lines · 3401 B
1// sketch_kll_test.nx -- KLL/MRL compactor-cascade verification.
2
3import "syscalls.nx"
4import "sketch_kll.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 let s: *Kll = nx_kll_alloc(64, 1)
14 if s == (0 as *Kll) { return __syscall(93, 5, 0, 0, 0, 0, 0) }
15
16 // ---- empty ----
17 if nx_kll_quantile(s, 500) != 0 { return __syscall(93, 10, 0, 0, 0, 0, 0) }
18 if s.total_items != 0 { return __syscall(93, 11, 0, 0, 0, 0, 0) }
19
20 // ---- single value ----
21 nx_kll_add(s, 42)
22 if nx_kll_quantile(s, 500) != 42 {
23 return __syscall(93, 20, 0, 0, 0, 0, 0)
24 }
25
26 // ---- stream 1..1000, k=64 ----
27 let s2: *Kll = nx_kll_alloc(64, 7)
28 var i: i64 = 1
29 while i <= 1000 {
30 nx_kll_add(s2, i)
31 i = i + 1
32 }
33 if s2.total_items != 1000 { return __syscall(93, 30, 0, 0, 0, 0, 0) }
34 if nx_kll_levels_used(s2) < 2 {
35 return __syscall(93, 31, 0, 0, 0, 0, 0)
36 }
37 // Median ~ 500. Rank-error ~ 0.12 for k=64 (conservative).
38 // Value error ~ 0.12 * 1000 = 120.
39 let median: i64 = nx_kll_quantile(s2, 500)
40 if iabs(median - 500) > 150 {
41 return __syscall(93, 32, 0, 0, 0, 0, 0)
42 }
43 let p99: i64 = nx_kll_quantile(s2, 990)
44 if iabs(p99 - 990) > 150 {
45 return __syscall(93, 33, 0, 0, 0, 0, 0)
46 }
47 let p10: i64 = nx_kll_quantile(s2, 100)
48 if iabs(p10 - 100) > 150 {
49 return __syscall(93, 34, 0, 0, 0, 0, 0)
50 }
51
52 // ---- rank inverse ----
53 let rank_500: i64 = nx_kll_rank(s2, 500)
54 if iabs(rank_500 - 500) > 150 {
55 return __syscall(93, 40, 0, 0, 0, 0, 0)
56 }
57 if nx_kll_rank(s2, 99999) != 1000 {
58 return __syscall(93, 41, 0, 0, 0, 0, 0)
59 }
60 if nx_kll_rank(s2, -1) != 0 {
61 return __syscall(93, 42, 0, 0, 0, 0, 0)
62 }
63
64 // ---- deterministic reproducibility ----
65 let a: *Kll = nx_kll_alloc(32, 42)
66 let b: *Kll = nx_kll_alloc(32, 42)
67 i = 0
68 while i < 500 {
69 nx_kll_add(a, i * 3 + 11)
70 nx_kll_add(b, i * 3 + 11)
71 i = i + 1
72 }
73 if a.total_items != b.total_items {
74 return __syscall(93, 50, 0, 0, 0, 0, 0)
75 }
76 if a.n_levels != b.n_levels {
77 return __syscall(93, 51, 0, 0, 0, 0, 0)
78 }
79 if nx_kll_quantile(a, 500) != nx_kll_quantile(b, 500) {
80 return __syscall(93, 52, 0, 0, 0, 0, 0)
81 }
82 if nx_kll_quantile(a, 990) != nx_kll_quantile(b, 990) {
83 return __syscall(93, 53, 0, 0, 0, 0, 0)
84 }
85
86 // ---- typed envelope ----
87 let q: *ApproxI64 = nx_kll_query_quantile(s2, 500)
88 if q.envelope_kind != NX_ENV_RANK_ERROR {
89 return __syscall(93, 60, 0, 0, 0, 0, 0)
90 }
91 if q.conf_ppb != 950000000 {
92 return __syscall(93, 61, 0, 0, 0, 0, 0)
93 }
94 if q.maturity != NX_MATURITY_REFERENCE_IMPL {
95 return __syscall(93, 62, 0, 0, 0, 0, 0)
96 }
97 if q.adv_safety != NX_ADV_HONEST {
98 return __syscall(93, 63, 0, 0, 0, 0, 0)
99 }
100 // k=64 -> param_a should be 120_000_000 (0.12).
101 if q.param_a != 120000000 {
102 return __syscall(93, 64, 0, 0, 0, 0, 0)
103 }
104
105 // ---- min / max preserved ----
106 if s2.min_val != 1 { return __syscall(93, 70, 0, 0, 0, 0, 0) }
107 if s2.max_val != 1000 { return __syscall(93, 71, 0, 0, 0, 0, 0) }
108
109 return 0
110}