nx_sketch_bloom.nx
buildroot/runtime/nx_sketch_bloom.nx
about
sketch_bloom.nx -- Bloom filter v2 (sovereign-tier with typed envelope).
Burton Howard Bloom 1970. Tracks n_inserted so the FPR envelope
reflects ACTUAL load, not just design-time spec. Companion to the
older runtime/bloom.nx (which lacks the envelope + counted state +
proper FPR-by-load reporting).
FPR FORMULA (Bloom 1970):
FPR = (1 - e^(-kn/m))^k
For k = (m/n) ln(2) optimal: FPR = 0.6185^(m/n)
We can't compute exp / pow in i64-only. Conservative approach:
tabulate FPR-by-(m/n) at integer ratios assuming OPTIMAL k. If the
caller chose non-optimal k, real FPR is worse than reported -- we
document this. v2 will swap in a tighter integer approximation.
LOSSLESS-LANGUAGE DISCIPLINE (doc 20):
contains -> 1 means "probably present" with envelope FPR; 0 means
"definitely absent" with envelope FPR = 0. Both cases ship the
ApproxI64 with NX_ENV_ABS / conf_ppb = 1e9 - fpr_ppb.
Complements sketch_cuckoo.nx (which supports delete). Bloom is more
space-efficient at high FPR; Cuckoo wins below ~3% FPR with delete.
dependencies 3 imports · 1 importers
imports: nx_syscalls.nxnx_murmur3.nxnx_sketch_types.nx
imported by: nx_triangulation_crypto_fft.nx
structs
| 35 | struct BloomS |
consts
| none |
functions
| 45 | func nx_bs_is_pow2(n: i64) -> i64 called by 1: nx_bloom_alloc |
| 51 | func nx_bloom_alloc(cap_bits: i64, k: i64) -> *BloomS |
| 73 | func nx_bloom_set_bit(bf: *BloomS, bit_idx: i64) -> i64 called by 1: nx_bloom_insert |
| 80 | func nx_bloom_get_bit(bf: *BloomS, bit_idx: i64) -> i64 called by 1: nx_bloom_contains |
| 91 | func nx_bloom_insert(bf: *BloomS, key: *u8, len: i64) -> i64 |
| 105 | func nx_bloom_contains(bf: *BloomS, key: *u8, len: i64) -> i64 |
| 126 | func nx_bloom_fpr_ppb(bf: *BloomS) -> i64 called by 1: nx_bloom_query |
| 150 | func nx_bloom_query(bf: *BloomS, key: *u8, len: i64) -> *ApproxI64 |
| 161 | func nx_bloom_memory_bytes(bf: *BloomS) -> i64 |
| 165 | func nx_bloom_load_ppt(bf: *BloomS) -> i64 |