code wiki / (root) / sketch_cuckoo_delete_vs_bloom_bench.nx

sketch_cuckoo_delete_vs_bloom_bench.nx

buildroot/runtime/sketch_cuckoo_delete_vs_bloom_bench.nx

5785 B151 linesdepth 5pulls 8 transitivereach 0 importersview sourcekind benchtopic sketch
docsdependenciesstructsconstsfunctions

about

sketch_cuckoo_delete_vs_bloom_bench.nx -- DELETE capability bench. CLAIM TO VALIDATE: Cuckoo filter (Fan-Andersen-Kaminsky-Mitzenmacher 2014) supports DELETE; Bloom filter (Bloom 1970) does NOT. Substrate ships both; this bench DEMONSTRATES the capability gap: items deleted from Cuckoo are correctly forgotten, while Bloom carries deleted items indefinitely. WORKLOAD: 1. Insert N=500 distinct keys into both. 2. Verify all 500 reported as present. 3. Delete first 100 keys from Cuckoo (Bloom has no delete op). 4. Query: Cuckoo no longer contains the deleted keys (with bounded false-positive noise from fingerprint collisions). Bloom STILL reports the deleted keys as present (cannot delete). MEASUREMENT: delete_forgotten_count_cuckoo: how many of the 100 deleted keys does Cuckoo correctly report as NOT-present? Expected: ~95-100 (5% FPR from fingerprint collisions is the Cuckoo theoretical bound). delete_forgotten_count_bloom: how many does Bloom report NOT-present? Expected: 0 (Bloom CANNOT forget). CAPABILITY EXCEED: Cuckoo forgets >=90% of deletes; Bloom forgets 0%.

dependencies 5 imports · 0 importers

syscalls.nx sketch_cuckoo.nx sketch_bloom.nx sketch_comparator.nx sketch_types.nx sketch_cuckoo_delete_vs_bloom_

imports: syscalls.nxsketch_cuckoo.nxsketch_bloom.nxsketch_comparator.nxsketch_types.nx

imported by: nobody (leaf or entry point)

call flow from main pre-order; caps 40 nodes / depth 6 declared; ↻ = already shown

main nx_cuckoo_alloc nx_bloom_alloc nx_bs_is_pow2 nx_cuckoo_insert nx_cuckoo_fingerprint nx_cuckoo_bucket1 nx_cuckoo_try_insert_bucke nx_cuckoo_bucket_addr nx_cuckoo_bucket2 nx_cuckoo_fp_hash nx_cuckoo_rng_next nx_cuckoo_bucket_addr ↻ write_bb nx_bloom_insert murmur3_32 mm_load_u32_le mm_rotl32 nx_bloom_set_bit nx_cuckoo_contains nx_cuckoo_fingerprint ↻ nx_cuckoo_bucket1 ↻ nx_cuckoo_bucket_contains nx_cuckoo_bucket_addr ↻ nx_cuckoo_bucket2 ↻ nx_bloom_contains murmur3_32 ↻ nx_bloom_get_bit nx_cuckoo_delete nx_cuckoo_fingerprint ↻ nx_cuckoo_bucket1 ↻ nx_cuckoo_bucket_remove nx_cuckoo_bucket_addr ↻ nx_cuckoo_bucket2 ↻ nx_cmp_memory

structs

none

consts

none

functions

33func write_bb(buf: *u8, value: i64) -> i64
called by 1: main
44func main() -> i64