sketch_linear_counter_test.nx source

1// sketch_linear_counter_test.nx -- Whang-Vander Zanden 1990 cardinality. 2 3import "syscalls.nx" 4import "sketch_linear_counter.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 ---- 14 let lc: *LinearCounter = nx_lc_alloc(8192, 42) 15 if lc == (0 as *LinearCounter) { return __syscall(93, 5, 0, 0, 0, 0, 0) } 16 // Reject non-power-of-2 + too-small. 17 if nx_lc_alloc(100, 1) != (0 as *LinearCounter) { 18 return __syscall(93, 6, 0, 0, 0, 0, 0) 19 } 20 if nx_lc_alloc(32, 1) != (0 as *LinearCounter) { 21 return __syscall(93, 7, 0, 0, 0, 0, 0) 22 } 23 24 // ---- empty ---- 25 if nx_lc_zeros(lc) != 8192 { 26 return __syscall(93, 10, 0, 0, 0, 0, 0) 27 } 28 if nx_lc_estimate(lc) != 0 { 29 return __syscall(93, 11, 0, 0, 0, 0, 0) 30 } 31 32 // ---- small cardinality: LC's sweet spot ---- 33 // Insert 100 distinct values into m=8192 bits. 34 // Expected zeros ~ 8192 * e^(-100/8192) ~ 8192 * 0.988 ~ 8093. 35 // estimate = -8192 * ln(8093/8192) = -8192 * (-0.01207) ~ 99. 36 let buf: *u8 = sys_mmap(8) 37 var i: i64 = 0 38 while i < 100 { 39 buf[0] = (i ) & 0xFF 40 buf[1] = (i >> 8 ) & 0xFF 41 buf[2] = 0xA1 42 buf[3] = 0 43 buf[4] = 0 44 buf[5] = 0 45 buf[6] = 0 46 buf[7] = 0 47 nx_lc_add(lc, buf, 8) 48 i = i + 1 49 } 50 let est_small: i64 = nx_lc_estimate(lc) 51 // Allow +/-20% since our ln lookup is coarse. 52 if iabs(est_small - 100) > 50 { 53 return __syscall(93, 20, 0, 0, 0, 0, 0) 54 } 55 56 // ---- medium cardinality ---- 57 let lc2: *LinearCounter = nx_lc_alloc(8192, 42) 58 i = 0 59 while i < 1000 { 60 buf[0] = (i ) & 0xFF 61 buf[1] = (i >> 8 ) & 0xFF 62 buf[2] = 0xB1 63 buf[3] = 0 64 buf[4] = 0 65 buf[5] = 0 66 buf[6] = 0 67 buf[7] = 0 68 nx_lc_add(lc2, buf, 8) 69 i = i + 1 70 } 71 let est_med: i64 = nx_lc_estimate(lc2) 72 // True = 1000. Allow +/-30% margin. 73 if iabs(est_med - 1000) > 300 { 74 return __syscall(93, 30, 0, 0, 0, 0, 0) 75 } 76 77 // ---- saturated bitmap returns m (ceiling) ---- 78 let lc3: *LinearCounter = nx_lc_alloc(64, 42) // tiny, easily saturates 79 i = 0 80 while i < 1000 { 81 buf[0] = (i ) & 0xFF 82 buf[1] = (i >> 8 ) & 0xFF 83 buf[2] = 0xC1 84 buf[3] = 0 85 buf[4] = 0 86 buf[5] = 0 87 buf[6] = 0 88 buf[7] = 0 89 nx_lc_add(lc3, buf, 8) 90 i = i + 1 91 } 92 // With 1000 inserts into 64 bits, almost certainly all set. 93 let z3: i64 = nx_lc_zeros(lc3) 94 if z3 == 0 { 95 // Saturated: estimate should return m as ceiling, not blow up. 96 if nx_lc_estimate(lc3) != 64 { 97 return __syscall(93, 40, 0, 0, 0, 0, 0) 98 } 99 } 100 101 // ---- typed envelope ---- 102 let q: *ApproxI64 = nx_lc_query(lc2) 103 if q.envelope_kind != NX_ENV_REL_STDDEV { 104 return __syscall(93, 50, 0, 0, 0, 0, 0) 105 } 106 if q.maturity != NX_MATURITY_REFERENCE_IMPL { 107 return __syscall(93, 51, 0, 0, 0, 0, 0) 108 } 109 if q.adv_safety != NX_ADV_HONEST { 110 return __syscall(93, 52, 0, 0, 0, 0, 0) 111 } 112 113 // ---- merge ---- 114 let m_a: *LinearCounter = nx_lc_alloc(8192, 99) 115 let m_b: *LinearCounter = nx_lc_alloc(8192, 99) 116 i = 0 117 while i < 200 { 118 buf[0] = (i ) & 0xFF 119 buf[1] = (i >> 8 ) & 0xFF 120 buf[2] = 0xD1 121 buf[3] = 0 122 buf[4] = 0 123 buf[5] = 0 124 buf[6] = 0 125 buf[7] = 0 126 nx_lc_add(m_a, buf, 8) 127 i = i + 1 128 } 129 i = 100 130 while i < 300 { 131 buf[0] = (i ) & 0xFF 132 buf[1] = (i >> 8 ) & 0xFF 133 buf[2] = 0xD1 134 buf[3] = 0 135 buf[4] = 0 136 buf[5] = 0 137 buf[6] = 0 138 buf[7] = 0 139 nx_lc_add(m_b, buf, 8) 140 i = i + 1 141 } 142 let merged: *LinearCounter = nx_lc_merge(m_a, m_b) 143 if merged == (0 as *LinearCounter) { 144 return __syscall(93, 60, 0, 0, 0, 0, 0) 145 } 146 // Union: distinct values 0..299 = 300 total. 147 let est_merge: i64 = nx_lc_estimate(merged) 148 if iabs(est_merge - 300) > 100 { 149 return __syscall(93, 61, 0, 0, 0, 0, 0) 150 } 151 // Mismatched m -> NULL. 152 let m_c: *LinearCounter = nx_lc_alloc(16384, 99) 153 if nx_lc_merge(m_a, m_c) != (0 as *LinearCounter) { 154 return __syscall(93, 62, 0, 0, 0, 0, 0) 155 } 156 157 return 0 158}