code wiki / (root) / sketch_bloom.nx

sketch_bloom.nx

buildroot/runtime/sketch_bloom.nx

5799 B162 linesdepth 4pulls 5 transitivereach 2 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 · 2 importers

syscalls.nx murmur3.nx sketch_types.nx sketch_bloom.nx sketch_bloom_test.nx sketch_cuckoo_delete_vs_bloom_benc

imports: syscalls.nxmurmur3.nxsketch_types.nx

imported by: sketch_bloom_test.nxsketch_cuckoo_delete_vs_bloom_bench.nx

structs

29struct BloomS {

consts

none

functions

39func nx_bs_is_pow2(n: i64) -> i64 {
called by 1: nx_bloom_alloc
45func nx_bloom_alloc(cap_bits: i64, k: i64) -> *BloomS {
called by 2: mainmain calls 1: nx_bs_is_pow2
67func nx_bloom_set_bit(bf: *BloomS, bit_idx: i64) -> i64 {
called by 1: nx_bloom_insert
74func nx_bloom_get_bit(bf: *BloomS, bit_idx: i64) -> i64 {
called by 1: nx_bloom_contains
85func nx_bloom_insert(bf: *BloomS, key: *u8, len: i64) -> i64 {
called by 2: mainmain calls 2: murmur3_32nx_bloom_set_bit
99func nx_bloom_contains(bf: *BloomS, key: *u8, len: i64) -> i64 {
120func nx_bloom_fpr_ppb(bf: *BloomS) -> i64 {
called by 2: nx_bloom_querymain
144func nx_bloom_query(bf: *BloomS, key: *u8, len: i64) -> *ApproxI64 {
155func nx_bloom_memory_bytes(bf: *BloomS) -> i64 {
159func nx_bloom_load_ppt(bf: *BloomS) -> i64 {
called by 1: main