sketch_reservoir_test.nx source
↩ module page · 131 lines · 4276 B
1// sketch_reservoir_test.nx -- Vitter reservoir + sample-based
2// quantile verification.
3
4import "syscalls.nx"
5import "sketch_reservoir.nx"
6import "sketch_types.nx"
7
8func iabs(x: i64) -> i64 {
9 if x < 0 { return -x }
10 return x
11}
12
13func main() -> i64 {
14 let r: *Reservoir = nx_reservoir_alloc(100, 1)
15 if r == (0 as *Reservoir) { return __syscall(93, 5, 0, 0, 0, 0, 0) }
16
17 // ---- empty quantile ----
18 if nx_reservoir_quantile(r, 500) != 0 {
19 return __syscall(93, 10, 0, 0, 0, 0, 0)
20 }
21
22 // ---- under-cap: every value retained exactly ----
23 nx_reservoir_add(r, 7)
24 nx_reservoir_add(r, 14)
25 nx_reservoir_add(r, 3)
26 if r.n_items != 3 { return __syscall(93, 20, 0, 0, 0, 0, 0) }
27 if r.total_seen != 3 { return __syscall(93, 21, 0, 0, 0, 0, 0) }
28 // Median of {3, 7, 14} = 7.
29 if nx_reservoir_quantile(r, 500) != 7 {
30 return __syscall(93, 22, 0, 0, 0, 0, 0)
31 }
32
33 // ---- streaming past capacity ----
34 let r2: *Reservoir = nx_reservoir_alloc(200, 42)
35 // Stream values 1..1000. Median should land near 500.
36 var i: i64 = 1
37 while i <= 1000 {
38 nx_reservoir_add(r2, i)
39 i = i + 1
40 }
41 if r2.total_seen != 1000 { return __syscall(93, 30, 0, 0, 0, 0, 0) }
42 if r2.n_items != 200 { return __syscall(93, 31, 0, 0, 0, 0, 0) }
43 // Median should be near 500 within rank-error 0.085 (for cap=200,
44 // closer to 0.10 conservatively). Translates to value error of
45 // 0.10 * 1000 = 100.
46 let median: i64 = nx_reservoir_quantile(r2, 500)
47 if iabs(median - 500) > 100 {
48 return __syscall(93, 32, 0, 0, 0, 0, 0)
49 }
50 // p99 should be near 990.
51 let p99: i64 = nx_reservoir_quantile(r2, 990)
52 if iabs(p99 - 990) > 150 {
53 return __syscall(93, 33, 0, 0, 0, 0, 0)
54 }
55 // p10 should be near 100.
56 let p10: i64 = nx_reservoir_quantile(r2, 100)
57 if iabs(p10 - 100) > 150 {
58 return __syscall(93, 34, 0, 0, 0, 0, 0)
59 }
60
61 // ---- rank-of-value inverse ----
62 let rank_500: i64 = nx_reservoir_rank(r2, 500)
63 if iabs(rank_500 - 500) > 150 {
64 return __syscall(93, 40, 0, 0, 0, 0, 0)
65 }
66 // rank(1500) -- a value above the entire stream -- should be 1000 (100%).
67 if nx_reservoir_rank(r2, 1500) != 1000 {
68 return __syscall(93, 41, 0, 0, 0, 0, 0)
69 }
70 // rank(-1) -- a value below everything -- should be 0.
71 if nx_reservoir_rank(r2, -1) != 0 {
72 return __syscall(93, 42, 0, 0, 0, 0, 0)
73 }
74
75 // ---- deterministic reproducibility ----
76 // Same seed + same input sequence -> bit-identical reservoir.
77 let r3a: *Reservoir = nx_reservoir_alloc(50, 99)
78 let r3b: *Reservoir = nx_reservoir_alloc(50, 99)
79 i = 0
80 while i < 500 {
81 nx_reservoir_add(r3a, i)
82 nx_reservoir_add(r3b, i)
83 i = i + 1
84 }
85 // After identical adds, every items[] index must match.
86 i = 0
87 while i < 50 {
88 if r3a.items[i] != r3b.items[i] {
89 return __syscall(93, 50, 0, 0, 0, 0, 0)
90 }
91 i = i + 1
92 }
93 // Different seeds should produce DIFFERENT reservoirs.
94 let r3c: *Reservoir = nx_reservoir_alloc(50, 7)
95 i = 0
96 while i < 500 {
97 nx_reservoir_add(r3c, i)
98 i = i + 1
99 }
100 // At least one item should differ between r3a and r3c.
101 var any_differ: i64 = 0
102 i = 0
103 while i < 50 {
104 if r3a.items[i] != r3c.items[i] { any_differ = 1 }
105 i = i + 1
106 }
107 if any_differ != 1 {
108 return __syscall(93, 51, 0, 0, 0, 0, 0)
109 }
110
111 // ---- typed envelope ----
112 let q: *ApproxI64 = nx_reservoir_query_quantile(r2, 500)
113 if q.envelope_kind != NX_ENV_RANK_ERROR {
114 return __syscall(93, 60, 0, 0, 0, 0, 0)
115 }
116 if q.conf_ppb != 950000000 {
117 return __syscall(93, 61, 0, 0, 0, 0, 0)
118 }
119 if q.maturity != NX_MATURITY_REFERENCE_IMPL {
120 return __syscall(93, 62, 0, 0, 0, 0, 0)
121 }
122 if q.adv_safety != NX_ADV_HONEST {
123 return __syscall(93, 63, 0, 0, 0, 0, 0)
124 }
125 // For cap=200 (<=256), rank_error_ppb should be 85_000_000.
126 if q.param_a != 85000000 {
127 return __syscall(93, 64, 0, 0, 0, 0, 0)
128 }
129
130 return 0
131}