sketch_bloom.nx source
↩ module page · 162 lines · 5799 B
1// sketch_bloom.nx -- Bloom filter v2 (sovereign-tier with typed envelope).
2//
3// Burton Howard Bloom 1970. Tracks n_inserted so the FPR envelope
4// reflects ACTUAL load, not just design-time spec. Companion to the
5// older runtime/bloom.nx (which lacks the envelope + counted state +
6// proper FPR-by-load reporting).
7//
8// FPR FORMULA (Bloom 1970):
9// FPR = (1 - e^(-kn/m))^k
10// For k = (m/n) ln(2) optimal: FPR = 0.6185^(m/n)
11//
12// We can't compute exp / pow in i64-only. Conservative approach:
13// tabulate FPR-by-(m/n) at integer ratios assuming OPTIMAL k. If the
14// caller chose non-optimal k, real FPR is worse than reported -- we
15// document this. v2 will swap in a tighter integer approximation.
16//
17// LOSSLESS-LANGUAGE DISCIPLINE (doc 20):
18// contains -> 1 means "probably present" with envelope FPR; 0 means
19// "definitely absent" with envelope FPR = 0. Both cases ship the
20// ApproxI64 with NX_ENV_ABS / conf_ppb = 1e9 - fpr_ppb.
21//
22// Complements sketch_cuckoo.nx (which supports delete). Bloom is more
23// space-efficient at high FPR; Cuckoo wins below ~3% FPR with delete.
24
25import "syscalls.nx"
26import "murmur3.nx"
27import "sketch_types.nx"
28
29struct BloomS {
30 bits: *u8,
31 cap_bits: i64, // power of 2
32 mask: i64, // cap_bits - 1
33 k: i64, // hash functions
34 n_inserted: i64,
35}
36
37// === alloc =======================================================
38
39func nx_bs_is_pow2(n: i64) -> i64 {
40 if n < 64 { return 0 }
41 if (n & (n - 1)) != 0 { return 0 }
42 return 1
43}
44
45func nx_bloom_alloc(cap_bits: i64, k: i64) -> *BloomS {
46 if nx_bs_is_pow2(cap_bits) != 1 { return 0 as *BloomS }
47 if k < 1 { return 0 as *BloomS }
48 if k > 32 { return 0 as *BloomS }
49 let raw: *u8 = sys_mmap(48)
50 let bf: *BloomS = raw as *BloomS
51 let bytes: i64 = cap_bits / 8
52 bf.bits = sys_mmap(bytes)
53 var i: i64 = 0
54 while i < bytes {
55 bf.bits[i] = 0
56 i = i + 1
57 }
58 bf.cap_bits = cap_bits
59 bf.mask = cap_bits - 1
60 bf.k = k
61 bf.n_inserted = 0
62 return bf
63}
64
65// === bit helpers ================================================
66
67func nx_bloom_set_bit(bf: *BloomS, bit_idx: i64) -> i64 {
68 let byte_idx: i64 = bit_idx >> 3
69 let bit_pos: i64 = bit_idx & 7
70 bf.bits[byte_idx] = bf.bits[byte_idx] | (1 << bit_pos)
71 return 0
72}
73
74func nx_bloom_get_bit(bf: *BloomS, bit_idx: i64) -> i64 {
75 let byte_idx: i64 = bit_idx >> 3
76 let bit_pos: i64 = bit_idx & 7
77 return (bf.bits[byte_idx] >> bit_pos) & 1
78}
79
80// === insert / contains ==========================================
81//
82// Kirsch-Mitzenmacher double hashing: derive k bit positions from
83// two base hashes via (h1 + i*h2) for i in 0..k-1.
84
85func nx_bloom_insert(bf: *BloomS, key: *u8, len: i64) -> i64 {
86 let h1: i64 = murmur3_32(0, key, len) & 0xFFFFFFFF
87 let h2: i64 = murmur3_32(1, key, len) & 0xFFFFFFFF
88 var i: i64 = 0
89 while i < bf.k {
90 let combined: i64 = (h1 + (i * h2)) & 0xFFFFFFFF
91 let bit_idx: i64 = combined & bf.mask
92 nx_bloom_set_bit(bf, bit_idx)
93 i = i + 1
94 }
95 bf.n_inserted = bf.n_inserted + 1
96 return 0
97}
98
99func nx_bloom_contains(bf: *BloomS, key: *u8, len: i64) -> i64 {
100 let h1: i64 = murmur3_32(0, key, len) & 0xFFFFFFFF
101 let h2: i64 = murmur3_32(1, key, len) & 0xFFFFFFFF
102 var i: i64 = 0
103 while i < bf.k {
104 let combined: i64 = (h1 + (i * h2)) & 0xFFFFFFFF
105 let bit_idx: i64 = combined & bf.mask
106 if nx_bloom_get_bit(bf, bit_idx) == 0 { return 0 }
107 i = i + 1
108 }
109 return 1
110}
111
112// === FPR estimation =============================================
113//
114// Assuming OPTIMAL k (= (m/n) ln(2)), FPR = 0.6185^(m/n). We
115// tabulate by integer m/n ratio. Non-optimal k -> WORSE FPR.
116//
117// Real load: m/n where n = n_inserted, m = cap_bits. If n == 0,
118// FPR = 0.
119
120func nx_bloom_fpr_ppb(bf: *BloomS) -> i64 {
121 if bf.n_inserted == 0 { return 0 }
122 let m_over_n: i64 = bf.cap_bits / bf.n_inserted
123 if m_over_n <= 0 { return 1000000000 } // overloaded -> ~100% FPR
124 if m_over_n == 1 { return 618500000 } // 61.85%
125 if m_over_n == 2 { return 382500000 } // 38.25%
126 if m_over_n == 3 { return 236600000 } // 23.66%
127 if m_over_n == 4 { return 146300000 } // 14.63%
128 if m_over_n == 5 { return 90500000 } // 9.05%
129 if m_over_n == 6 { return 55960000 } // 5.60%
130 if m_over_n == 7 { return 34630000 } // 3.46%
131 if m_over_n == 8 { return 21420000 } // 2.14%
132 if m_over_n == 10 { return 8160000 } // 0.816%
133 if m_over_n == 12 { return 3110000 } // 0.311%
134 if m_over_n == 16 { return 458000 } // 0.0458%
135 if m_over_n == 20 { return 67500 } // 0.00675%
136 if m_over_n == 24 { return 9930 } // 0.000993%
137 if m_over_n == 32 { return 216 } // 2.16e-7
138 // m/n above 32: vanishing.
139 return 0
140}
141
142// === typed query ================================================
143
144func nx_bloom_query(bf: *BloomS, key: *u8, len: i64) -> *ApproxI64 {
145 let present: i64 = nx_bloom_contains(bf, key, len)
146 let fpr: i64 = nx_bloom_fpr_ppb(bf)
147 return nx_approx_new(present, NX_ENV_ABS, 0,
148 1000000000 - fpr,
149 NX_MATURITY_REFERENCE_IMPL,
150 NX_ADV_HONEST)
151}
152
153// === introspection ==============================================
154
155func nx_bloom_memory_bytes(bf: *BloomS) -> i64 {
156 return 48 + bf.cap_bits / 8
157}
158
159func nx_bloom_load_ppt(bf: *BloomS) -> i64 {
160 if bf.cap_bits == 0 { return 0 }
161 return (bf.n_inserted * 1000) / bf.cap_bits
162}