sketch_reqsketch_test.nx source
↩ module page · 134 lines · 4402 B
1// sketch_reqsketch_test.nx -- ReqSketch verification.
2
3import "syscalls.nx"
4import "sketch_reqsketch.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 + rejection ----
14 let bad_small: *Req = nx_req_alloc(4, 1, 1)
15 if bad_small != (0 as *Req) { return __syscall(93, 1, 0, 0, 0, 0, 0) }
16 let bad_huge: *Req = nx_req_alloc(99999, 1, 1)
17 if bad_huge != (0 as *Req) { return __syscall(93, 2, 0, 0, 0, 0, 0) }
18
19 let s: *Req = nx_req_alloc(64, 1, 1)
20 if s == (0 as *Req) { return __syscall(93, 5, 0, 0, 0, 0, 0) }
21 if s.hra != 1 { return __syscall(93, 6, 0, 0, 0, 0, 0) }
22
23 // ---- empty ----
24 if nx_req_quantile(s, 500) != 0 { return __syscall(93, 10, 0, 0, 0, 0, 0) }
25 if s.total_items != 0 { return __syscall(93, 11, 0, 0, 0, 0, 0) }
26
27 // ---- single value ----
28 nx_req_add(s, 42)
29 if nx_req_quantile(s, 500) != 42 {
30 return __syscall(93, 20, 0, 0, 0, 0, 0)
31 }
32
33 // ---- stream 1..1000, k=64, hra=1 (upper-tail-tight) ----
34 let s2: *Req = nx_req_alloc(64, 1, 7)
35 var i: i64 = 1
36 while i <= 1000 {
37 nx_req_add(s2, i)
38 i = i + 1
39 }
40 if s2.total_items != 1000 { return __syscall(93, 30, 0, 0, 0, 0, 0) }
41 if nx_req_levels_used(s2) < 2 {
42 return __syscall(93, 31, 0, 0, 0, 0, 0)
43 }
44 // Median ~ 500. Median is NOT a tail query so error bound is
45 // looser here than KLL -- we tolerate +- 200.
46 let median: i64 = nx_req_quantile(s2, 500)
47 if iabs(median - 500) > 200 {
48 return __syscall(93, 32, 0, 0, 0, 0, 0)
49 }
50 // p99 = 990: this is the upper tail where hra=1 is tight.
51 // Effective abs error <= eps * min(990, 10) = 0.177 * 10 = ~2,
52 // but the simplified schedule loosens this; tolerate +- 100.
53 let p99: i64 = nx_req_quantile(s2, 990)
54 if iabs(p99 - 990) > 100 {
55 return __syscall(93, 33, 0, 0, 0, 0, 0)
56 }
57 // p10 = 100: lower tail (hra=1 is NOT tight here); tolerate +- 200.
58 let p10: i64 = nx_req_quantile(s2, 100)
59 if iabs(p10 - 100) > 200 {
60 return __syscall(93, 34, 0, 0, 0, 0, 0)
61 }
62
63 // ---- rank inverse ----
64 let rank_500: i64 = nx_req_rank(s2, 500)
65 if iabs(rank_500 - 500) > 200 {
66 return __syscall(93, 40, 0, 0, 0, 0, 0)
67 }
68 if nx_req_rank(s2, 99999) != 1000 {
69 return __syscall(93, 41, 0, 0, 0, 0, 0)
70 }
71 if nx_req_rank(s2, -1) != 0 {
72 return __syscall(93, 42, 0, 0, 0, 0, 0)
73 }
74
75 // ---- deterministic reproducibility ----
76 let a: *Req = nx_req_alloc(32, 1, 42)
77 let b: *Req = nx_req_alloc(32, 1, 42)
78 i = 0
79 while i < 500 {
80 nx_req_add(a, i * 3 + 11)
81 nx_req_add(b, i * 3 + 11)
82 i = i + 1
83 }
84 if a.total_items != b.total_items {
85 return __syscall(93, 50, 0, 0, 0, 0, 0)
86 }
87 if a.n_levels != b.n_levels {
88 return __syscall(93, 51, 0, 0, 0, 0, 0)
89 }
90 if nx_req_quantile(a, 500) != nx_req_quantile(b, 500) {
91 return __syscall(93, 52, 0, 0, 0, 0, 0)
92 }
93 if nx_req_quantile(a, 990) != nx_req_quantile(b, 990) {
94 return __syscall(93, 53, 0, 0, 0, 0, 0)
95 }
96
97 // ---- typed envelope: REL_RANK_ERROR not RANK_ERROR ----
98 let q: *ApproxI64 = nx_req_query_quantile(s2, 990)
99 if q.envelope_kind != NX_ENV_REL_RANK_ERROR {
100 return __syscall(93, 60, 0, 0, 0, 0, 0)
101 }
102 if q.conf_ppb != 950000000 {
103 return __syscall(93, 61, 0, 0, 0, 0, 0)
104 }
105 if q.maturity != NX_MATURITY_REFERENCE_IMPL {
106 return __syscall(93, 62, 0, 0, 0, 0, 0)
107 }
108 if q.adv_safety != NX_ADV_HONEST {
109 return __syscall(93, 63, 0, 0, 0, 0, 0)
110 }
111 // k=64 -> param_a should be 177_000_000 (0.177 rel rank error).
112 if q.param_a != 177000000 {
113 return __syscall(93, 64, 0, 0, 0, 0, 0)
114 }
115
116 // ---- min / max preserved across cascade ----
117 if s2.min_val != 1 { return __syscall(93, 70, 0, 0, 0, 0, 0) }
118 if s2.max_val != 1000 { return __syscall(93, 71, 0, 0, 0, 0, 0) }
119
120 // ---- hra=0 (lower-tail-tight) variant works too ----
121 let lo: *Req = nx_req_alloc(64, 0, 9)
122 if lo.hra != 0 { return __syscall(93, 80, 0, 0, 0, 0, 0) }
123 i = 1
124 while i <= 1000 {
125 nx_req_add(lo, i)
126 i = i + 1
127 }
128 let lo_p10: i64 = nx_req_quantile(lo, 100)
129 if iabs(lo_p10 - 100) > 100 {
130 return __syscall(93, 81, 0, 0, 0, 0, 0)
131 }
132
133 return 0
134}