sketch_cuckoo_delete_vs_bloom_bench.nx source
↩ module page · 151 lines · 5785 B
1// sketch_cuckoo_delete_vs_bloom_bench.nx -- DELETE capability bench.
2//
3// CLAIM TO VALIDATE:
4// Cuckoo filter (Fan-Andersen-Kaminsky-Mitzenmacher 2014) supports
5// DELETE; Bloom filter (Bloom 1970) does NOT. Substrate ships both;
6// this bench DEMONSTRATES the capability gap: items deleted from
7// Cuckoo are correctly forgotten, while Bloom carries deleted items
8// indefinitely.
9//
10// WORKLOAD:
11// 1. Insert N=500 distinct keys into both.
12// 2. Verify all 500 reported as present.
13// 3. Delete first 100 keys from Cuckoo (Bloom has no delete op).
14// 4. Query: Cuckoo no longer contains the deleted keys (with bounded
15// false-positive noise from fingerprint collisions).
16// Bloom STILL reports the deleted keys as present (cannot delete).
17//
18// MEASUREMENT:
19// delete_forgotten_count_cuckoo: how many of the 100 deleted keys
20// does Cuckoo correctly report as NOT-present? Expected: ~95-100
21// (5% FPR from fingerprint collisions is the Cuckoo theoretical bound).
22// delete_forgotten_count_bloom: how many does Bloom report NOT-present?
23// Expected: 0 (Bloom CANNOT forget).
24//
25// CAPABILITY EXCEED: Cuckoo forgets >=90% of deletes; Bloom forgets 0%.
26
27import "syscalls.nx"
28import "sketch_cuckoo.nx"
29import "sketch_bloom.nx"
30import "sketch_comparator.nx"
31import "sketch_types.nx"
32
33func write_bb(buf: *u8, value: i64) -> i64 {
34 var i: i64 = 0
35 var v: i64 = value
36 while i < 8 {
37 buf[i] = (v & 0xFF) as u8
38 v = v >> 8
39 i = i + 1
40 }
41 return 0
42}
43
44func main() -> i64 {
45 let n_keys: i64 = 500
46 let n_delete: i64 = 100
47
48 // MATCHED-MEMORY rerun: original used Bloom at 4096 bits (512 B) vs
49 // Cuckoo at 256 * 4 * 1 byte = 1024 B. Scaling Bloom UP to 8192
50 // bits = 1024 B matches Cuckoo's storage exactly. The DELETE
51 // capability gap is structural and survives matched memory.
52 let cuckoo: *CuckooFilter = nx_cuckoo_alloc(256, 42)
53 let bloom: *BloomS = nx_bloom_alloc(8192, 6) // 1024 bytes, matches Cuckoo
54 if cuckoo == (0 as *CuckooFilter) { return __syscall(93, 1, 0, 0, 0, 0, 0) }
55 if bloom == (0 as *BloomS) { return __syscall(93, 2, 0, 0, 0, 0, 0) }
56
57 let key_buf_raw: *u8 = sys_mmap(8)
58 let key_buf: *u8 = key_buf_raw
59
60 // ---- Insert N keys (use i+1000 as the hash/value) ----
61 var i: i64 = 0
62 while i < n_keys {
63 let h: i64 = i + 1000
64 nx_cuckoo_insert(cuckoo, h)
65 write_bb(key_buf, h)
66 nx_bloom_insert(bloom, key_buf, 8)
67 i = i + 1
68 }
69
70 // ---- Verify all N keys reported present in both ----
71 var present_cuckoo: i64 = 0
72 var present_bloom: i64 = 0
73 i = 0
74 while i < n_keys {
75 let h: i64 = i + 1000
76 if nx_cuckoo_contains(cuckoo, h) == 1 { present_cuckoo = present_cuckoo + 1 }
77 write_bb(key_buf, h)
78 if nx_bloom_contains(bloom, key_buf, 8) == 1 { present_bloom = present_bloom + 1 }
79 i = i + 1
80 }
81 if present_cuckoo != n_keys { return __syscall(93, 10, 0, 0, 0, 0, 0) }
82 if present_bloom != n_keys { return __syscall(93, 11, 0, 0, 0, 0, 0) }
83
84 // ---- DELETE first 100 keys from Cuckoo (Bloom has no delete) ----
85 var deleted: i64 = 0
86 i = 0
87 while i < n_delete {
88 let h: i64 = i + 1000
89 if nx_cuckoo_delete(cuckoo, h) == 1 { deleted = deleted + 1 }
90 i = i + 1
91 }
92 // All 100 should have been successfully deleted.
93 if deleted != n_delete { return __syscall(93, 20, 0, 0, 0, 0, 0) }
94
95 // ---- Post-delete query: how many of the 100 deleted are still found? ----
96 var still_in_cuckoo: i64 = 0
97 var still_in_bloom: i64 = 0
98 i = 0
99 while i < n_delete {
100 let h: i64 = i + 1000
101 if nx_cuckoo_contains(cuckoo, h) == 1 { still_in_cuckoo = still_in_cuckoo + 1 }
102 write_bb(key_buf, h)
103 if nx_bloom_contains(bloom, key_buf, 8) == 1 { still_in_bloom = still_in_bloom + 1 }
104 i = i + 1
105 }
106
107 // ---- Cuckoo: at most 10% FPR from fingerprint collisions ----
108 if still_in_cuckoo > (n_delete * 10) / 100 {
109 return __syscall(93, 30, 0, 0, 0, 0, 0)
110 }
111 // ---- Bloom: ALL 100 still reported present (cannot delete) ----
112 if still_in_bloom != n_delete {
113 return __syscall(93, 40, 0, 0, 0, 0, 0)
114 }
115
116 // ---- Remaining keys (101..500) still queryable in both ----
117 var remaining_cuckoo: i64 = 0
118 var remaining_bloom: i64 = 0
119 i = n_delete
120 while i < n_keys {
121 let h: i64 = i + 1000
122 if nx_cuckoo_contains(cuckoo, h) == 1 { remaining_cuckoo = remaining_cuckoo + 1 }
123 write_bb(key_buf, h)
124 if nx_bloom_contains(bloom, key_buf, 8) == 1 { remaining_bloom = remaining_bloom + 1 }
125 i = i + 1
126 }
127 let n_remaining: i64 = n_keys - n_delete
128 // Cuckoo: at least 95% of remaining still present (no false negatives in theory; tiny chance of relocation issues)
129 if remaining_cuckoo < (n_remaining * 95) / 100 {
130 return __syscall(93, 50, 0, 0, 0, 0, 0)
131 }
132 if remaining_bloom != n_remaining {
133 return __syscall(93, 51, 0, 0, 0, 0, 0)
134 }
135
136 // ---- HARD-WIN ACCURACY measurement: closer to truth=0 wins ----
137 // truth = 0 keys present after delete; cuckoo close to 0; bloom = 100.
138 // Use "smaller scalar wins" via memory comparator (smaller is better here).
139 // Add a baseline floor of 1 so memory comparator's their > 0 guard passes.
140 let cmp_floor: i64 = 1
141 let acc: *ComparisonResult = nx_cmp_memory(still_in_cuckoo + cmp_floor, still_in_bloom + cmp_floor, 100000)
142 if acc.verdict != NX_CMP_VERDICT_BEATS {
143 return __syscall(93, 60, 0, 0, 0, 0, 0)
144 }
145 // Expect massive delta (Cuckoo ~0, Bloom = 100), so >90% improvement
146 if acc.delta_ppm < 900000 {
147 return __syscall(93, 61, 0, 0, 0, 0, 0)
148 }
149
150 return 0
151}