sketch_misra_gries_test.nx source

1// sketch_misra_gries_test.nx -- MG heavy hitters (under-estimate variant). 2 3import "syscalls.nx" 4import "sketch_misra_gries.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 + empty ---- 14 let mg: *MisraGries = nx_mg_alloc(6) // K=6, capacity=5 slots 15 if mg == (0 as *MisraGries) { return __syscall(93, 5, 0, 0, 0, 0, 0) } 16 if mg.n_tracked != 0 { return __syscall(93, 6, 0, 0, 0, 0, 0) } 17 if nx_mg_estimate(mg, 999) != 0 { return __syscall(93, 7, 0, 0, 0, 0, 0) } 18 // Reject K < 2. 19 if nx_mg_alloc(1) != (0 as *MisraGries) { 20 return __syscall(93, 8, 0, 0, 0, 0, 0) 21 } 22 23 // ---- under-cap: exact estimates ---- 24 nx_mg_add(mg, 100, 5) 25 nx_mg_add(mg, 200, 3) 26 nx_mg_add(mg, 300, 7) 27 if nx_mg_n_tracked(mg) != 3 { return __syscall(93, 10, 0, 0, 0, 0, 0) } 28 if nx_mg_estimate(mg, 100) != 5 { return __syscall(93, 11, 0, 0, 0, 0, 0) } 29 if nx_mg_estimate(mg, 200) != 3 { return __syscall(93, 12, 0, 0, 0, 0, 0) } 30 if nx_mg_estimate(mg, 300) != 7 { return __syscall(93, 13, 0, 0, 0, 0, 0) } 31 // Unknown key -> 0 (and Misra-Gries says "could be as high as N/k = ~2"). 32 if nx_mg_estimate(mg, 999) != 0 { return __syscall(93, 14, 0, 0, 0, 0, 0) } 33 34 // ---- decrement when full ---- 35 // Fill all 5 slots. Then add a NEW key with count 1 -- should 36 // decrement everyone by 1. 37 nx_mg_add(mg, 400, 4) 38 nx_mg_add(mg, 500, 6) 39 if nx_mg_n_tracked(mg) != 5 { return __syscall(93, 20, 0, 0, 0, 0, 0) } 40 // Counts: 100=5, 200=3, 300=7, 400=4, 500=6. Min = 3. 41 nx_mg_add(mg, 600, 1) 42 // Decrement-loop: absorb min(1, 3) = 1; everyone -= 1. 43 // Counts after: 100=4, 200=2, 300=6, 400=3, 500=5; 600 NOT installed 44 // (because remaining = 0 after absorb). 45 if nx_mg_estimate(mg, 100) != 4 { return __syscall(93, 21, 0, 0, 0, 0, 0) } 46 if nx_mg_estimate(mg, 200) != 2 { return __syscall(93, 22, 0, 0, 0, 0, 0) } 47 if nx_mg_estimate(mg, 300) != 6 { return __syscall(93, 23, 0, 0, 0, 0, 0) } 48 if nx_mg_estimate(mg, 600) != 0 { return __syscall(93, 24, 0, 0, 0, 0, 0) } 49 50 // ---- new key with count > current min: installs after decrement ---- 51 // Current: 100=4, 200=2, 300=6, 400=3, 500=5; min=2. 52 // Add 700 with count=5. absorb=min(5,2)=2; counts decrement by 2. 53 // Counts: 100=2, 200=0, 300=4, 400=1, 500=3. remaining=3. 54 // Now 200's slot is free. Install (700, 3). 55 nx_mg_add(mg, 700, 5) 56 if nx_mg_estimate(mg, 200) != 0 { return __syscall(93, 30, 0, 0, 0, 0, 0) } 57 if nx_mg_estimate(mg, 700) != 3 { return __syscall(93, 31, 0, 0, 0, 0, 0) } 58 if nx_mg_estimate(mg, 100) != 2 { return __syscall(93, 32, 0, 0, 0, 0, 0) } 59 if nx_mg_estimate(mg, 300) != 4 { return __syscall(93, 33, 0, 0, 0, 0, 0) } 60 61 // ---- heavy hitter: dominant key survives ---- 62 let mg2: *MisraGries = nx_mg_alloc(8) 63 var i: i64 = 0 64 while i < 100 { 65 nx_mg_add(mg2, 42, 1) // 100 hits to key 42 66 i = i + 1 67 } 68 // Now flood with 1000 distinct other keys. 69 i = 1000 70 while i < 2000 { 71 nx_mg_add(mg2, i, 1) 72 i = i + 1 73 } 74 // Key 42 has true count 100 in a stream of N=1100; N/k=1100/8=137.5. 75 // Misra-Gries guarantee: estimate(42) >= 100 - 137 = negative, 76 // so under tight pressure could drop to 0. But heavy hitter with 77 // count > N/k should survive. 100 < 137 -> NO guarantee. 78 // Use a more aggressive heavy: 79 let mg3: *MisraGries = nx_mg_alloc(8) 80 i = 0 81 while i < 500 { 82 nx_mg_add(mg3, 42, 1) // 500 to key 42 83 i = i + 1 84 } 85 i = 1000 86 while i < 1500 { 87 nx_mg_add(mg3, i, 1) // 500 distinct fillers 88 i = i + 1 89 } 90 // True 42 count = 500; N = 1000; N/k = 125. 91 // Estimate(42) >= 500 - 125 = 375. 92 let est_heavy: i64 = nx_mg_estimate(mg3, 42) 93 if est_heavy < 375 { 94 return __syscall(93, 40, 0, 0, 0, 0, 0) 95 } 96 // And upper bound check: estimate <= true (Misra-Gries 97 // underestimates), so est <= 500. 98 if est_heavy > 500 { 99 return __syscall(93, 41, 0, 0, 0, 0, 0) 100 } 101 102 // ---- typed envelope ---- 103 let q: *ApproxI64 = nx_mg_query(mg3, 42) 104 if q.envelope_kind != NX_ENV_ABS { 105 return __syscall(93, 50, 0, 0, 0, 0, 0) 106 } 107 if q.conf_ppb != 1000000000 { // deterministic 108 return __syscall(93, 51, 0, 0, 0, 0, 0) 109 } 110 // param_a = max_undercount = ceil(N/k) = ceil(1000/8) = 125. 111 if q.param_a != 125 { 112 return __syscall(93, 52, 0, 0, 0, 0, 0) 113 } 114 115 return 0 116}