sketch_cb_vs_cuckoo_delete_bench.nx
buildroot/runtime/sketch_cb_vs_cuckoo_delete_bench.nx
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
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
structs
| none |
consts
| none |
functions
| 30 | func write_bcb(buf: *u8, value: i64) -> i64 called by 1: main |
| 41 | func main() -> i64 |