sketch_cuckoo_delete_vs_bloom_bench.nx
buildroot/runtime/sketch_cuckoo_delete_vs_bloom_bench.nx
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
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
structs
| none |
consts
| none |
functions
| 33 | func write_bb(buf: *u8, value: i64) -> i64 called by 1: main |
| 44 | func main() -> i64 |