Repository navigation
Commit cc29c1e
Store bloom blocks as [u32; 8] and inline the insert path
Sharing a stored filter's bytes moved the accumulator's blocks into a
`Buffer<u32>` behind an enum, and the insert path paid for it on every value:
`len` matched the enum, `blocks_mut` branched and matched again, and
`as_chunks_mut` divided the length and re-split the slice before indexing.
CodSpeed put `insert` 15-28% over develop.
Blocks are now stored as `[u32; 8]`, so indexing yields a block directly and
the block count needs no division, and an insert fetches the blocks once, so
it checks whether the partial is thawed exactly once. `add_hash`, `find_hash`
and `make_mask` are `#[inline]`: `insert` already was, so callers in other
crates inlined it and then paid a call into `add_hash` for every value, on
develop too. `make_mask`, `block_index` and `lower_hash_bits` never used
`self` and are associated functions, so the borrow of the blocks can span
the index computation.
`union` and `is_saturated` flatten the blocks back to one `u32` slice: the
flat OR compiles to wide loads and stores, where a loop per block spends
about as many instructions on the loop as on the OR.
Instructions inside the benchmark frame under callgrind, develop / previous
commit / now: insert 828,558 / 935,141 / 763,108; contains_present 926,400 /
1,008,320 / 778,950; the bloom merge group 349,006 / 213,637 / 213,181.
`deserialize` is `#[inline]` as well; `partial_from_scalar` and
`BloomContains` both parse stored filters through it.
Signed-off-by: Robert Kruszewski <[email protected]>
Co-Authored-By: Claude Fable 5.1 <[email protected]>
Claude-Session: https://claude.ai/code/session_01BAC54whRD3iHLBZfM4TCvd1 parent 1a42c91 commit cc29c1e
3 files changed
Lines changed: 56 additions & 37 deletions
| Original file line number | Diff line number | Diff line change | |
|---|---|---|---|
| |||
17 | 17 | | |
18 | 18 | | |
19 | 19 | | |
20 | | - | |
| 20 | + | |
| 21 | + | |
| 22 | + | |
| 23 | + | |
21 | 24 | | |
22 | 25 | | |
23 | 26 | | |
| |||
37 | 40 | | |
38 | 41 | | |
39 | 42 | | |
40 | | - | |
| 43 | + | |
| 44 | + | |
| 45 | + | |
| 46 | + | |
| 47 | + | |
| 48 | + | |
41 | 49 | | |
42 | 50 | | |
43 | 51 | | |
| |||
| Original file line number | Diff line number | Diff line change | |
|---|---|---|---|
| |||
34 | 34 | | |
35 | 35 | | |
36 | 36 | | |
| 37 | + | |
| 38 | + | |
| 39 | + | |
37 | 40 | | |
38 | 41 | | |
39 | 42 | | |
| |||
119 | 122 | | |
120 | 123 | | |
121 | 124 | | |
122 | | - | |
| 125 | + | |
123 | 126 | | |
124 | 127 | | |
125 | 128 | | |
126 | | - | |
127 | | - | |
| 129 | + | |
| 130 | + | |
128 | 131 | | |
129 | | - | |
130 | | - | |
| 132 | + | |
| 133 | + | |
131 | 134 | | |
132 | 135 | | |
133 | 136 | | |
| |||
144 | 147 | | |
145 | 148 | | |
146 | 149 | | |
147 | | - | |
| 150 | + | |
148 | 151 | | |
149 | 152 | | |
150 | | - | |
| 153 | + | |
151 | 154 | | |
152 | | - | |
| 155 | + | |
153 | 156 | | |
154 | | - | |
155 | | - | |
| 157 | + | |
| 158 | + | |
156 | 159 | | |
157 | 160 | | |
158 | 161 | | |
159 | | - | |
| 162 | + | |
160 | 163 | | |
161 | 164 | | |
162 | 165 | | |
163 | 166 | | |
164 | | - | |
165 | | - | |
166 | | - | |
| 167 | + | |
| 168 | + | |
| 169 | + | |
167 | 170 | | |
168 | 171 | | |
169 | | - | |
| 172 | + | |
170 | 173 | | |
171 | 174 | | |
172 | 175 | | |
| |||
217 | 220 | | |
218 | 221 | | |
219 | 222 | | |
220 | | - | |
| 223 | + | |
221 | 224 | | |
222 | 225 | | |
223 | 226 | | |
224 | 227 | | |
| 228 | + | |
| 229 | + | |
| 230 | + | |
| 231 | + | |
225 | 232 | | |
226 | | - | |
227 | | - | |
| 233 | + | |
| 234 | + | |
228 | 235 | | |
229 | | - | |
230 | | - | |
| 236 | + | |
| 237 | + | |
| 238 | + | |
| 239 | + | |
231 | 240 | | |
232 | | - | |
233 | | - | |
| 241 | + | |
234 | 242 | | |
235 | 243 | | |
236 | 244 | | |
237 | 245 | | |
238 | 246 | | |
239 | 247 | | |
| 248 | + | |
240 | 249 | | |
241 | | - | |
242 | | - | |
| 250 | + | |
| 251 | + | |
| 252 | + | |
243 | 253 | | |
244 | 254 | | |
245 | | - | |
246 | 255 | | |
247 | 256 | | |
248 | 257 | | |
| |||
256 | 265 | | |
257 | 266 | | |
258 | 267 | | |
259 | | - | |
| 268 | + | |
| 269 | + | |
260 | 270 | | |
261 | 271 | | |
262 | 272 | | |
| |||
279 | 289 | | |
280 | 290 | | |
281 | 291 | | |
282 | | - | |
| 292 | + | |
283 | 293 | | |
284 | 294 | | |
285 | 295 | | |
| |||
291 | 301 | | |
292 | 302 | | |
293 | 303 | | |
294 | | - | |
295 | | - | |
296 | | - | |
| 304 | + | |
297 | 305 | | |
298 | 306 | | |
299 | 307 | | |
| |||
| Original file line number | Diff line number | Diff line change | |
|---|---|---|---|
| |||
15 | 15 | | |
16 | 16 | | |
17 | 17 | | |
| 18 | + | |
18 | 19 | | |
19 | 20 | | |
20 | 21 | | |
| |||
23 | 24 | | |
24 | 25 | | |
25 | 26 | | |
26 | | - | |
| 27 | + | |
| 28 | + | |
| 29 | + | |
27 | 30 | | |
28 | 31 | | |
29 | 32 | | |
| |||
35 | 38 | | |
36 | 39 | | |
37 | 40 | | |
38 | | - | |
| 41 | + | |
39 | 42 | | |
40 | | - | |
| 43 | + | |
41 | 44 | | |
42 | 45 | | |
43 | 46 | | |
| |||
47 | 50 | | |
48 | 51 | | |
49 | 52 | | |
50 | | - | |
51 | | - | |
| 53 | + | |
| 54 | + | |
52 | 55 | | |
53 | 56 | | |
54 | 57 | | |
| |||
0 commit comments