code wiki / (root) / sketch_cb_vs_cuckoo_delete_bench.nx

sketch_cb_vs_cuckoo_delete_bench.nx

buildroot/runtime/sketch_cb_vs_cuckoo_delete_bench.nx

4572 B135 linesdepth 5pulls 8 transitivereach 0 importersview sourcekind benchtopic sketch
docsdependenciesstructsconstsfunctions

about

sketch_cb_vs_cuckoo_delete_bench.nx -- both-support-delete paired bench. CLAIM TO VALIDATE: Counting Bloom (Fan-Cao-Almeida-Broder 1998) supports DELETE via per-counter decrement. Cuckoo (Fan-Andersen-Kaminsky-Mitzenmacher 2014) also supports DELETE via fingerprint clear. Substrate ships both. Different trade-offs: - Counting Bloom: per-counter byte (8x more memory than Bloom) but multi-set multiplicity tracking. - Cuckoo: 1-byte fingerprint per slot, tighter FPR per byte. Bench measures: at MATCHED memory, both correctly forget deleted items (within FPR bounds); Cuckoo's FPR is tighter at typical load. WORKLOAD: Insert 500 distinct keys into both. Delete first 100. Verify >=90% of deleted keys correctly forgotten by EACH (capability axis = both pass). Compare FPR post-delete on a 1000-key disjoint test set (accuracy axis = Cuckoo's tighter wins).

dependencies 5 imports · 0 importers

syscalls.nx sketch_counting_bloom.nx sketch_cuckoo.nx sketch_comparator.nx sketch_types.nx sketch_cb_vs_cuckoo_delete_ben

imports: syscalls.nxsketch_counting_bloom.nxsketch_cuckoo.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_cb_alloc nx_cb_is_pow2 nx_cuckoo_alloc write_bcb nx_cb_insert murmur3_32 mm_load_u32_le mm_rotl32 nx_cb_counter_get nx_cb_counter_set 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 ↻ nx_cb_delete murmur3_32 ↻ nx_cb_counter_get ↻ nx_cb_counter_set ↻ nx_cuckoo_delete nx_cuckoo_fingerprint ↻ nx_cuckoo_bucket1 ↻ nx_cuckoo_bucket_remove nx_cuckoo_bucket_addr ↻ nx_cuckoo_bucket2 ↻ nx_cb_contains murmur3_32 ↻ nx_cb_counter_get ↻ nx_cuckoo_contains nx_cuckoo_fingerprint ↻ nx_cuckoo_bucket1 ↻ nx_cuckoo_bucket_contains nx_cuckoo_bucket_addr ↻ nx_cuckoo_bucket2 ↻ nx_cb_memory_bytes

structs

none

consts

none

functions

30func write_bcb(buf: *u8, value: i64) -> i64
called by 1: main
41func main() -> i64