sketch_hll_test.nx source
↩ module page · 96 lines · 3079 B
1// sketch_hll_test.nx -- end-to-end test for the NishiLang HLL port.
2//
3// Streams N distinct keys through nx_hll_add and verifies the
4// estimate is within 3-sigma of the true cardinality, where sigma
5// is 1.04 / sqrt(m). Caller invokes via nxc2 -> qemu-riscv64-static
6// (analogous to bench/fp64_smoke.sh).
7//
8// Per the lossless-language discipline (nishi-engine doc 20):
9// the test ALSO verifies the typed envelope is correct -- the
10// returned ApproxI64 declares NX_ENV_REL_STDDEV with the right
11// stddev_rel_ppb and NX_MATURITY_REFERENCE_IMPL.
12
13import "syscalls.nx"
14import "sketch_hll.nx"
15import "sketch_types.nx"
16
17// Encode an i64 cardinality counter into 8 bytes for hashing. We
18// use the index as the "key" -- each one is unique, so insertion
19// of N indices means cardinality N.
20func write_i64_le(buf: *u8, value: i64) -> i64 {
21 var i: i64 = 0
22 var v: i64 = value
23 while i < 8 {
24 buf[i] = v & 0xFF
25 v = v >> 8
26 i = i + 1
27 }
28 return 0
29}
30
31// Absolute value of i64 (helper since nx_math_int isn't imported here).
32func iabs(x: i64) -> i64 {
33 if x < 0 { return -x }
34 return x
35}
36
37func main() -> i64 {
38 // lgK = 10 -> 1024 registers, stddev_rel ~ 3.25%
39 // For N = 5000 distinct keys we expect estimate in
40 // [N * (1 - 3*sigma), N * (1 + 3*sigma)]
41 // = [N * 0.9025, N * 1.0975]
42 // Allow a generous ±15% cushion since the small-range correction
43 // is approximate and our integer-fixed-point estimator has
44 // some quantization error on top of the algorithm's stderr.
45
46 let h: *Hll = nx_hll_alloc(10, 0)
47 if h == (0 as *Hll) {
48 return __syscall(93, 5, 0, 0, 0, 0, 0) // alloc failed
49 }
50
51 let N: i64 = 5000
52
53 // Insert N distinct integer keys.
54 let key: *u8 = sys_mmap(8)
55 var i: i64 = 0
56 while i < N {
57 write_i64_le(key, i)
58 nx_hll_add(h, key, 8)
59 i = i + 1
60 }
61
62 // Query.
63 let est: i64 = nx_hll_estimate(h)
64
65 // Allow ±15% cushion (3-sigma + integer quantization slack).
66 let lo_bound: i64 = (N * 85) / 100
67 let hi_bound: i64 = (N * 115) / 100
68
69 if est < lo_bound { return __syscall(93, 10, 0, 0, 0, 0, 0) }
70 if est > hi_bound { return __syscall(93, 11, 0, 0, 0, 0, 0) }
71
72 // Verify the typed envelope is correctly populated.
73 let q: *ApproxI64 = nx_hll_query(h)
74 if q.envelope_kind != NX_ENV_REL_STDDEV {
75 return __syscall(93, 20, 0, 0, 0, 0, 0)
76 }
77 if q.maturity != NX_MATURITY_REFERENCE_IMPL {
78 return __syscall(93, 21, 0, 0, 0, 0, 0)
79 }
80 if q.adv_safety != NX_ADV_HONEST {
81 return __syscall(93, 22, 0, 0, 0, 0, 0)
82 }
83 if q.conf_ppb != 682700000 {
84 return __syscall(93, 23, 0, 0, 0, 0, 0)
85 }
86 // For lgK=10, stddev_rel_ppb should be 32_500_000 (= 0.0325).
87 if q.param_a != 32500000 {
88 return __syscall(93, 24, 0, 0, 0, 0, 0)
89 }
90 if q.value != est {
91 return __syscall(93, 25, 0, 0, 0, 0, 0)
92 }
93
94 // All checks passed.
95 return 0
96}