code wiki / (root) / nx_sketch_bloom.nx

nx_sketch_bloom.nx

buildroot/runtime/nx_sketch_bloom.nx

5897 B168 linesdepth 3pulls 4 transitivereach 1 importersview sourcekind sketch/demotopic sketch
docsdependenciesstructsconstsfunctions

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

nx_syscalls.nx nx_murmur3.nx nx_sketch_types.nx nx_sketch_bloom.nx nx_triangulation_crypto_fft.nx

imports: nx_syscalls.nxnx_murmur3.nxnx_sketch_types.nx

imported by: nx_triangulation_crypto_fft.nx

structs

35struct BloomS

consts

none

functions

45func nx_bs_is_pow2(n: i64) -> i64
called by 1: nx_bloom_alloc
51func nx_bloom_alloc(cap_bits: i64, k: i64) -> *BloomS
called by 1: main calls 2: nx_bs_is_pow2sys_mmap
73func nx_bloom_set_bit(bf: *BloomS, bit_idx: i64) -> i64
called by 1: nx_bloom_insert
80func nx_bloom_get_bit(bf: *BloomS, bit_idx: i64) -> i64
called by 1: nx_bloom_contains
91func nx_bloom_insert(bf: *BloomS, key: *u8, len: i64) -> i64
called by 1: main calls 2: murmur3_32nx_bloom_set_bit
105func nx_bloom_contains(bf: *BloomS, key: *u8, len: i64) -> i64
126func nx_bloom_fpr_ppb(bf: *BloomS) -> i64
called by 1: nx_bloom_query
150func nx_bloom_query(bf: *BloomS, key: *u8, len: i64) -> *ApproxI64
161func nx_bloom_memory_bytes(bf: *BloomS) -> i64
165func nx_bloom_load_ppt(bf: *BloomS) -> i64