sketch_ddsketch_test.nx source
↩ module page · 147 lines · 4899 B
1// sketch_ddsketch_test.nx -- DDSketch multiplicative-error quantile verification.
2
3import "syscalls.nx"
4import "sketch_ddsketch.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 ----
14 let d: *DDSketch = nx_dd_alloc(64)
15 if d == (0 as *DDSketch) { return __syscall(93, 5, 0, 0, 0, 0, 0) }
16 // Reject BPO < 16.
17 if nx_dd_alloc(8) != (0 as *DDSketch) {
18 return __syscall(93, 6, 0, 0, 0, 0, 0)
19 }
20 if nx_dd_alloc(2000) != (0 as *DDSketch) {
21 return __syscall(93, 7, 0, 0, 0, 0, 0)
22 }
23
24 // ---- empty ----
25 if nx_dd_quantile(d, 500) != 0 {
26 return __syscall(93, 10, 0, 0, 0, 0, 0)
27 }
28
29 // ---- single ----
30 nx_dd_add(d, 100)
31 let p50: i64 = nx_dd_quantile(d, 500)
32 // Single value: bucket containing 100 returns its representative.
33 // BPO=64, octave=6 (since bitlen(100)=7), so bucket = 6*64 + (100-64)*64/64 = 384+36 = 420.
34 // value_at_bucket(420) = (64 * (64 + 36)) / 64 = 100. Exact.
35 if p50 != 100 {
36 return __syscall(93, 11, 0, 0, 0, 0, 0)
37 }
38
39 // ---- streaming 1..1000: quantile within ±1.56% ----
40 let d2: *DDSketch = nx_dd_alloc(64)
41 var i: i64 = 1
42 while i <= 1000 {
43 nx_dd_add(d2, i)
44 i = i + 1
45 }
46 if nx_dd_total(d2) != 1000 { return __syscall(93, 20, 0, 0, 0, 0, 0) }
47 // p50 ~ 500: within 1.56% = 8 absolute.
48 let q50: i64 = nx_dd_quantile(d2, 500)
49 if iabs(q50 - 500) > (500 * 16) / 1000 + 2 { // 1.6% margin + slack
50 return __syscall(93, 21, 0, 0, 0, 0, 0)
51 }
52 // p99 ~ 990: tail-tight via multiplicative error.
53 let q99: i64 = nx_dd_quantile(d2, 990)
54 // multiplicative error * 990 = 1.56% * 990 = 15.4. Allow 30 margin.
55 if iabs(q99 - 990) > 30 {
56 return __syscall(93, 22, 0, 0, 0, 0, 0)
57 }
58 // p1 ~ 10: also multiplicative. Allow margin.
59 let q01: i64 = nx_dd_quantile(d2, 10)
60 // Very small values have very wide BUCKETS in absolute terms... wait,
61 // multiplicative error means ABSOLUTE error scales with value. At
62 // value=10, 1.56% = 0.156 -> rounds to 0 or 1 bucket either way.
63 // Sample size 10 in stream of 1000 -> rank 1% ~ 10. Allow ±5.
64 if iabs(q01 - 10) > 5 {
65 return __syscall(93, 23, 0, 0, 0, 0, 0)
66 }
67
68 // ---- TAIL-TIGHT MULTIPLICATIVE: log-distributed data ----
69 // Latency-like values: many small + few large. Test that p99 of
70 // {1 * 990 times, 10000} returns value near 10000 within 1.56%.
71 let d3: *DDSketch = nx_dd_alloc(128) // tighter error
72 i = 0
73 while i < 990 {
74 nx_dd_add(d3, 1)
75 i = i + 1
76 }
77 i = 0
78 while i < 10 {
79 nx_dd_add(d3, 10000)
80 i = i + 1
81 }
82 // p99.5 should fall in the 10000 bucket.
83 let q995: i64 = nx_dd_quantile(d3, 995)
84 // 1/128 = 0.78% error -> abs error at 10000 = 78.
85 if iabs(q995 - 10000) > 100 {
86 return __syscall(93, 30, 0, 0, 0, 0, 0)
87 }
88 // p50: should fall in the 1 bucket -> value ~ 1.
89 let q50_log: i64 = nx_dd_quantile(d3, 500)
90 if iabs(q50_log - 1) > 1 {
91 return __syscall(93, 31, 0, 0, 0, 0, 0)
92 }
93
94 // ---- zero and negative ----
95 let d4: *DDSketch = nx_dd_alloc(64)
96 nx_dd_add(d4, 0)
97 nx_dd_add(d4, -5)
98 nx_dd_add(d4, 100)
99 if d4.zero_count != 1 { return __syscall(93, 40, 0, 0, 0, 0, 0) }
100 if d4.neg_count != 1 { return __syscall(93, 41, 0, 0, 0, 0, 0) }
101
102 // ---- typed envelope ----
103 let q: *ApproxI64 = nx_dd_query_quantile(d2, 500)
104 if q.envelope_kind != NX_ENV_REL_STDDEV {
105 return __syscall(93, 50, 0, 0, 0, 0, 0)
106 }
107 // BPO=64 -> 1/64 ppb = 15_625_000.
108 if q.param_a != 15625000 {
109 return __syscall(93, 51, 0, 0, 0, 0, 0)
110 }
111 if q.conf_ppb != 1000000000 { // deterministic
112 return __syscall(93, 52, 0, 0, 0, 0, 0)
113 }
114
115 // ---- merge ----
116 let m_a: *DDSketch = nx_dd_alloc(64)
117 let m_b: *DDSketch = nx_dd_alloc(64)
118 i = 1
119 while i <= 500 {
120 nx_dd_add(m_a, i)
121 i = i + 1
122 }
123 i = 501
124 while i <= 1000 {
125 nx_dd_add(m_b, i)
126 i = i + 1
127 }
128 let merged: *DDSketch = nx_dd_merge(m_a, m_b)
129 if merged == (0 as *DDSketch) {
130 return __syscall(93, 60, 0, 0, 0, 0, 0)
131 }
132 if nx_dd_total(merged) != 1000 {
133 return __syscall(93, 61, 0, 0, 0, 0, 0)
134 }
135 let m_q50: i64 = nx_dd_quantile(merged, 500)
136 // Same data as d2 (above), so same quantile.
137 if iabs(m_q50 - q50) > 5 {
138 return __syscall(93, 62, 0, 0, 0, 0, 0)
139 }
140 // Mismatched BPO -> NULL.
141 let m_c: *DDSketch = nx_dd_alloc(128)
142 if nx_dd_merge(m_a, m_c) != (0 as *DDSketch) {
143 return __syscall(93, 63, 0, 0, 0, 0, 0)
144 }
145
146 return 0
147}