sketch_space_saving_test.nx source

1// sketch_space_saving_test.nx -- SpaceSaving behavioral test. 2// 3// Tests: 4// 1. Empty sketch returns 0 5// 2. Insert <= k unique keys: every estimate is exact (error=0) 6// 3. Evict-when-full: insert k+1th key; smallest-count entry 7// gets replaced; new entry has count = min_count + 1, error 8// = min_count 9// 4. Heavy hitters (frequency > N/k) are NEVER evicted 10// 5. top_k returns descending-count order 11// 6. Lower bound: count - error <= true count 12// 7. Typed envelope: NX_ENV_ABS / conf 1.0 / max_overcount 13 14import "syscalls.nx" 15import "sketch_space_saving.nx" 16import "sketch_types.nx" 17 18func main() -> i64 { 19 let s: *SpaceSaving = nx_ss_alloc(5) 20 if s == (0 as *SpaceSaving) { return __syscall(93, 5, 0, 0, 0, 0, 0) } 21 22 // ---- empty ---- 23 if nx_ss_estimate(s, 42) != 0 { return __syscall(93, 10, 0, 0, 0, 0, 0) } 24 if s.n_tracked != 0 { return __syscall(93, 11, 0, 0, 0, 0, 0) } 25 26 // ---- under-cap inserts ---- 27 nx_ss_add(s, 100, 1) 28 nx_ss_add(s, 200, 1) 29 nx_ss_add(s, 300, 1) 30 if s.n_tracked != 3 { return __syscall(93, 20, 0, 0, 0, 0, 0) } 31 if nx_ss_estimate(s, 100) != 1 { return __syscall(93, 21, 0, 0, 0, 0, 0) } 32 if nx_ss_error(s, 100) != 0 { return __syscall(93, 22, 0, 0, 0, 0, 0) } 33 // re-add 100: should increment, not duplicate 34 nx_ss_add(s, 100, 4) 35 if s.n_tracked != 3 { return __syscall(93, 23, 0, 0, 0, 0, 0) } 36 if nx_ss_estimate(s, 100) != 5 { return __syscall(93, 24, 0, 0, 0, 0, 0) } 37 38 // Fill to capacity: at k=5, add two more. 39 nx_ss_add(s, 400, 1) 40 nx_ss_add(s, 500, 1) 41 if s.n_tracked != 5 { return __syscall(93, 30, 0, 0, 0, 0, 0) } 42 // Current state: 100=5, 200=1, 300=1, 400=1, 500=1; total=9 43 44 // ---- evict-when-full ---- 45 // Adding new key 600 must evict the minimum. Min count = 1 46 // (tied across 200/300/400/500); find_min picks the first 47 // (lowest index = 1, which is key 200). New entry: key=600, 48 // count = 1 + 1 = 2, error = 1. 49 nx_ss_add(s, 600, 1) 50 if s.n_tracked != 5 { return __syscall(93, 40, 0, 0, 0, 0, 0) } 51 // 200 should be gone. 52 if nx_ss_estimate(s, 200) != 0 { return __syscall(93, 41, 0, 0, 0, 0, 0) } 53 // 600 should be present with count=2, error=1. 54 if nx_ss_estimate(s, 600) != 2 { return __syscall(93, 42, 0, 0, 0, 0, 0) } 55 if nx_ss_error(s, 600) != 1 { return __syscall(93, 43, 0, 0, 0, 0, 0) } 56 // Lower bound for 600 is count - error = 1, true count IS 1. 57 if nx_ss_lower_bound(s, 600) != 1 { 58 return __syscall(93, 44, 0, 0, 0, 0, 0) 59 } 60 61 // ---- heavy hitter survives evictions ---- 62 let s2: *SpaceSaving = nx_ss_alloc(3) 63 // Insert key 999 with count 100 first (heavy hitter). 64 nx_ss_add(s2, 999, 100) 65 // Now flood with 10 unique singletons. 66 var i: i64 = 0 67 while i < 10 { 68 nx_ss_add(s2, 1000 + i, 1) 69 i = i + 1 70 } 71 // 999 must still be tracked (heavy hitter). 72 if nx_ss_estimate(s2, 999) == 0 { 73 return __syscall(93, 50, 0, 0, 0, 0, 0) 74 } 75 // Its estimate may have been inflated slightly by collisions, 76 // but its lower bound should be >= 99. 77 if nx_ss_lower_bound(s2, 999) < 99 { 78 return __syscall(93, 51, 0, 0, 0, 0, 0) 79 } 80 81 // ---- top_k ordering ---- 82 let s3: *SpaceSaving = nx_ss_alloc(5) 83 nx_ss_add(s3, 1, 100) 84 nx_ss_add(s3, 2, 50) 85 nx_ss_add(s3, 3, 25) 86 nx_ss_add(s3, 4, 75) 87 let keys_raw: *u8 = sys_mmap(4 * 8) 88 let counts_raw: *u8 = sys_mmap(4 * 8) 89 let keys: *i64 = keys_raw as *i64 90 let counts: *i64 = counts_raw as *i64 91 let n: i64 = nx_ss_top_k(s3, 4, keys, counts) 92 if n != 4 { return __syscall(93, 60, 0, 0, 0, 0, 0) } 93 if keys[0] != 1 { return __syscall(93, 61, 0, 0, 0, 0, 0) } 94 if counts[0] != 100 { return __syscall(93, 62, 0, 0, 0, 0, 0) } 95 if keys[1] != 4 { return __syscall(93, 63, 0, 0, 0, 0, 0) } 96 if counts[1] != 75 { return __syscall(93, 64, 0, 0, 0, 0, 0) } 97 if keys[2] != 2 { return __syscall(93, 65, 0, 0, 0, 0, 0) } 98 if keys[3] != 3 { return __syscall(93, 66, 0, 0, 0, 0, 0) } 99 100 // ---- typed envelope ---- 101 let q: *ApproxI64 = nx_ss_query(s, 100) 102 if q.envelope_kind != NX_ENV_ABS { 103 return __syscall(93, 70, 0, 0, 0, 0, 0) 104 } 105 if q.conf_ppb != 1000000000 { 106 return __syscall(93, 71, 0, 0, 0, 0, 0) 107 } 108 if q.maturity != NX_MATURITY_REFERENCE_IMPL { 109 return __syscall(93, 72, 0, 0, 0, 0, 0) 110 } 111 if q.adv_safety != NX_ADV_HONEST { 112 return __syscall(93, 73, 0, 0, 0, 0, 0) 113 } 114 // max_overcount for s (k=5, total=10) = ceil(10/5) = 2. 115 if q.param_a != 2 { 116 return __syscall(93, 74, 0, 0, 0, 0, 0) 117 } 118 119 return 0 120}