Skip to content

Commit cc29c1e

Browse files
robert3005claude
andcommitted
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_01BAC54whRD3iHLBZfM4TCvd
1 parent 1a42c91 commit cc29c1e

3 files changed

Lines changed: 56 additions & 37 deletions

File tree

‎vortex-layout/src/layouts/zoned/aggregates/bloom_filter/partial/aggregate.rs‎

Lines changed: 10 additions & 2 deletions
Original file line numberDiff line numberDiff line change
@@ -17,7 +17,10 @@ impl BloomPartial {
1717
/// all bits are `1`.
1818
#[inline]
1919
pub(in crate::layouts::zoned) fn is_saturated(&self) -> bool {
20-
self.blocks().iter().all(|split| *split == u32::MAX)
20+
self.blocks()
21+
.as_flattened()
22+
.iter()
23+
.all(|split| *split == u32::MAX)
2124
}
2225

2326
/// Merges a compatible partial into this one.
@@ -37,7 +40,12 @@ impl BloomPartial {
3740
"bloom partial block count mismatch"
3841
);
3942

40-
for (dst_split, src_split) in self.blocks_mut().iter_mut().zip(other.blocks()) {
43+
// One flat `u32` slice each: the compiler turns the flat OR into wide loads and stores,
44+
// where a loop per block spends about as many instructions on the block loop as on the
45+
// OR itself.
46+
let dst = self.blocks_mut().as_flattened_mut();
47+
let src = other.blocks().as_flattened();
48+
for (dst_split, src_split) in dst.iter_mut().zip(src) {
4149
*dst_split |= *src_split;
4250
}
4351

‎vortex-layout/src/layouts/zoned/aggregates/bloom_filter/partial/mod.rs‎

Lines changed: 38 additions & 30 deletions
Original file line numberDiff line numberDiff line change
@@ -34,6 +34,9 @@ pub(super) const BYTES_PER_SPLIT: usize = size_of::<u32>(); // 4 bytes
3434
/// Block size (32 bytes [256 bits])
3535
pub(super) const BLOCK_SIZE: usize = SPLITS_PER_BLOCK * BYTES_PER_SPLIT;
3636

37+
/// One block: the eight splits a hash selects together and a mask is applied to.
38+
pub(super) type Block = [u32; SPLITS_PER_BLOCK];
39+
3740
/// Eight odd constants for multiply-shift hashing.
3841
///
3942
/// They fit in one 256-bit SIMD vector, and the order matches the one
@@ -119,15 +122,15 @@ pub struct BloomPartial {
119122
blocks: Blocks,
120123
}
121124

122-
/// The filter's splits, `SPLITS_PER_BLOCK` per block.
125+
/// The filter's blocks.
123126
///
124127
/// A partial parsed from a stored filter is only ever read, as the second operand of a merge or
125128
/// by a membership query, so it keeps the scalar's own buffer and stays `Frozen`. The partial an
126-
/// accumulator writes into thaws on its first write and then stays `Thawed`, so an insert costs a
127-
/// slice write and nothing more.
129+
/// accumulator writes into thaws on its first write and then stays `Thawed`, so an insert checks
130+
/// which it is once and then writes one block.
128131
enum Blocks {
129-
Frozen(Buffer<u32>),
130-
Thawed(BufferMut<u32>),
132+
Frozen(Buffer<Block>),
133+
Thawed(BufferMut<Block>),
131134
}
132135

133136
impl PartialEq for BloomPartial {
@@ -144,29 +147,29 @@ impl BloomPartial {
144147
/// Matches [BloomOptions::blocks_count]
145148
#[inline]
146149
pub(super) fn len(&self) -> usize {
147-
self.blocks().len() / SPLITS_PER_BLOCK
150+
self.blocks().len()
148151
}
149152

150-
/// Every split of the filter, `SPLITS_PER_BLOCK` per block.
153+
/// Every block of the filter.
151154
#[inline]
152-
fn blocks(&self) -> &[u32] {
155+
fn blocks(&self) -> &[Block] {
153156
match &self.blocks {
154-
Blocks::Frozen(splits) => splits.as_slice(),
155-
Blocks::Thawed(splits) => splits.as_slice(),
157+
Blocks::Frozen(blocks) => blocks.as_slice(),
158+
Blocks::Thawed(blocks) => blocks.as_slice(),
156159
}
157160
}
158161

159-
/// The splits for writing, thawing a frozen partial first.
162+
/// The blocks for writing, thawing a frozen partial first.
160163
///
161164
/// Thawing is free when nothing else holds the buffer; a partial still sharing the scalar it
162165
/// was parsed from copies once and never again.
163166
#[inline]
164-
fn blocks_mut(&mut self) -> &mut [u32] {
165-
if let Blocks::Frozen(splits) = &mut self.blocks {
166-
self.blocks = Blocks::Thawed(std::mem::take(splits).into_mut());
167+
fn blocks_mut(&mut self) -> &mut [Block] {
168+
if let Blocks::Frozen(blocks) = &mut self.blocks {
169+
self.blocks = Blocks::Thawed(std::mem::take(blocks).into_mut());
167170
}
168171
match &mut self.blocks {
169-
Blocks::Thawed(splits) => splits.as_mut_slice(),
172+
Blocks::Thawed(blocks) => blocks.as_mut_slice(),
170173
// Thawed just above; an empty slice keeps this total without a panic path.
171174
Blocks::Frozen(_) => &mut [],
172175
}
@@ -217,32 +220,38 @@ impl BloomPartial {
217220
clippy::cast_possible_truncation,
218221
reason = "the mask uses the low 32 bits of the 64-bit hash"
219222
)]
220-
fn lower_hash_bits(&self, hash: u64) -> u32 {
223+
fn lower_hash_bits(hash: u64) -> u32 {
221224
hash as u32
222225
}
223226

224227
/// Adds a hash into a single block of the bloom filter.
228+
///
229+
/// Inlined so the insert loops here and in other crates see straight through to the block
230+
/// write; a call into this method costs more instructions than the write itself.
231+
#[inline]
225232
fn add_hash(&mut self, hash: u64) {
226-
// 1. Use the upper 32 bits from the hash value to select a block.
227-
let block_idx = self.block_index(hash, self.len());
233+
// 1. Use the lower 32 bits to construct a mask.
234+
let mask = Self::make_mask(Self::lower_hash_bits(hash));
228235

229-
// 2. Use the lower 32 bits to construct a mask.
230-
let mask = self.make_mask(self.lower_hash_bits(hash));
236+
// 2. Use the upper 32 bits from the hash value to select a block. The blocks are fetched
237+
// once, so an insert checks whether the partial is thawed exactly once.
238+
let blocks = self.blocks_mut();
239+
let block = &mut blocks[Self::block_index(hash, blocks.len())];
231240

232-
// 3. Apply the mask to the block selected in step 1.
233-
let block = &mut self.blocks_mut().as_chunks_mut::<SPLITS_PER_BLOCK>().0[block_idx];
241+
// 3. Apply the mask to the block selected in step 2.
234242
for i in 0..8 {
235243
block[i] |= mask[i];
236244
}
237245
}
238246

239247
/// Checks whether a hash is (probably) present in the filter.
248+
#[inline]
240249
fn find_hash(&self, hash: u64) -> bool {
241-
let idx = self.block_index(hash, self.len());
242-
let mask = self.make_mask(self.lower_hash_bits(hash));
250+
let mask = Self::make_mask(Self::lower_hash_bits(hash));
251+
let blocks = self.blocks();
252+
let block = &blocks[Self::block_index(hash, blocks.len())];
243253

244254
let mut missing = 0u32;
245-
let block = &self.blocks().as_chunks::<SPLITS_PER_BLOCK>().0[idx];
246255

247256
// The original solution uses _mm256_testc_si256
248257
// checks if all the bits in mask are also set in *block. Scalar
@@ -256,7 +265,8 @@ impl BloomPartial {
256265

257266
/// Takes a hash value and creates a mask with one bit set in each 32-bit lane.
258267
/// These are the bits to set or check when accessing the block.
259-
fn make_mask(&self, hash: u32) -> [u32; 8] {
268+
#[inline]
269+
fn make_mask(hash: u32) -> Block {
260270
let mut out = [0u32; 8];
261271

262272
for i in 0..8 {
@@ -279,7 +289,7 @@ impl BloomPartial {
279289
/// Although `blocks_count` is a `usize`, its value is limited to `u32::MAX`
280290
/// by [`BloomOptions`] and the serialization format.
281291
#[inline]
282-
fn block_index(&self, hash: u64, blocks_count: usize) -> usize {
292+
fn block_index(hash: u64, blocks_count: usize) -> usize {
283293
(((hash >> 32) * blocks_count as u64) >> 32) as usize
284294
}
285295
}
@@ -291,9 +301,7 @@ impl From<&BloomOptions> for BloomPartial {
291301
// Matched exhaustively: a new hash function must revisit how partials are hashed.
292302
match options.hash_fn {
293303
HashFn::XxHash3_64 => Self {
294-
blocks: Blocks::Thawed(BufferMut::zeroed(
295-
options.blocks_count.get() as usize * SPLITS_PER_BLOCK,
296-
)),
304+
blocks: Blocks::Thawed(BufferMut::zeroed(options.blocks_count.get() as usize)),
297305
},
298306
}
299307
}

‎vortex-layout/src/layouts/zoned/aggregates/bloom_filter/partial/serde.rs‎

Lines changed: 8 additions & 5 deletions
Original file line numberDiff line numberDiff line change
@@ -15,6 +15,7 @@ use vortex_error::VortexResult;
1515
use vortex_error::vortex_ensure;
1616

1717
use super::BLOCK_SIZE;
18+
use super::Block;
1819
use super::Blocks;
1920
use super::BloomPartial;
2021

@@ -23,7 +24,9 @@ impl BloomPartial {
2324
///
2425
/// The bytes are the filter's splits as little-endian `u32`s, which is also how Vortex lays
2526
/// out every primitive buffer, so nothing is decoded: the partial shares `bytes` when they are
26-
/// aligned for `u32` and copies them once otherwise.
27+
/// aligned for `u32` and copies them once otherwise. Both `partial_from_scalar` and
28+
/// `BloomContains` parse stored filters through here.
29+
#[inline]
2730
pub(in crate::layouts::zoned) fn deserialize(bytes: ByteBuffer) -> VortexResult<Self> {
2831
vortex_ensure!(
2932
!bytes.is_empty() && bytes.len().is_multiple_of(BLOCK_SIZE),
@@ -35,9 +38,9 @@ impl BloomPartial {
3538
"bloom blocks length must be non-zero and lower than u32::MAX",
3639
);
3740

38-
let splits = Buffer::<u32>::from_byte_buffer(bytes.aligned(Alignment::of::<u32>()));
41+
let blocks = Buffer::<Block>::from_byte_buffer(bytes.aligned(Alignment::of::<Block>()));
3942
Ok(BloomPartial {
40-
blocks: Blocks::Frozen(splits),
43+
blocks: Blocks::Frozen(blocks),
4144
})
4245
}
4346

@@ -47,8 +50,8 @@ impl BloomPartial {
4750
/// A frozen partial hands back the buffer it was parsed from; a thawed one is copied.
4851
pub(in crate::layouts::zoned) fn serialize(&self) -> ByteBuffer {
4952
match &self.blocks {
50-
Blocks::Frozen(splits) => splits.clone().into_byte_buffer(),
51-
Blocks::Thawed(splits) => Buffer::copy_from(splits.as_slice()).into_byte_buffer(),
53+
Blocks::Frozen(blocks) => blocks.clone().into_byte_buffer(),
54+
Blocks::Thawed(blocks) => Buffer::copy_from(blocks.as_slice()).into_byte_buffer(),
5255
}
5356
}
5457
}

0 commit comments

Comments
 (0)