Skip to content

Commit 78834e5

Browse files
committed
let claude change it back from mmap to vec deque
``` mmap vs VecDeque (branch/main medians, same box, same day) ┌──────────────────────────────────┬──────────────────────────────────┬──────────────────────────────────┐ │ │ mmap + pool │ VecDeque │ ├──────────────────────────────────┼──────────────────────────────────┼──────────────────────────────────┤ │ TPC-DS Q1 / Q43 / Q36 / Q27 │ 1.02 / 1.09 / 0.96 / 1.02 │ 1.06 / 0.98 / 1.04 / 1.05 │ ├──────────────────────────────────┼──────────────────────────────────┼──────────────────────────────────┤ │ TPC-DS Q76 / Q81 / Q23 / Q39 │ 1.09 / 1.05 / 1.14 / 1.10 │ 1.03 / 1.02 / 1.08 / 1.07 │ ├──────────────────────────────────┼──────────────────────────────────┼──────────────────────────────────┤ │ TPC-DS Q11 / Q57 / others │ 1.07 / 1.10 / 1.00–1.06 │ 1.07 / 1.07 / 0.99–1.03 │ ├──────────────────────────────────┼──────────────────────────────────┼──────────────────────────────────┤ │ external_aggr Q1 (64/32/16 MB) │ 1.19 / 1.08 / 1.05 │ 1.22 / 1.12 / 1.13 │ ├──────────────────────────────────┼──────────────────────────────────┼──────────────────────────────────┤ │ external_aggr Q2 (512…32 MB) │ 1.03 / 0.99 / 1.07 / 1.06 / 1.09 │ 1.05 / 0.94 / 1.08 / 1.07 / 1.04 │ ├──────────────────────────────────┼──────────────────────────────────┼──────────────────────────────────┤ │ ClickBench Q33 / Q16 / Q18 / Q32 │ 1.02 / 1.11 / 0.87 / ~1.05 │ 1.17 / 1.09 / 1.10 / 1.07 │ └──────────────────────────────────┴──────────────────────────────────┴──────────────────────────────────┘ So: VecDeque wins on TPC-DS (mid-size aggregations, less setup and teardown), loses clearly on the big single-column string aggregations. Q33's profile shows why: GroupValuesBytesView::intern +24% and BlockedCount::update_batch +53%, from the two-level lookup (VecDeque slot → Vec → element) on every row versus one flat offset with mmap. ```
1 parent bb36d00 commit 78834e5

7 files changed

Lines changed: 271 additions & 599 deletions

File tree

‎datafusion/expr-common/src/blocked_helpers/blocked_custom_input_builder.rs‎

Lines changed: 42 additions & 5 deletions
Original file line numberDiff line numberDiff line change
@@ -341,11 +341,13 @@ impl<const FIXED_BLOCK_SIZING: bool, CustomBlockProvider: BlockProvider>
341341
if self.len == 0 {
342342
return None;
343343
}
344+
Some(self.take_first_block())
345+
}
344346

345-
let block = self
346-
.blocks
347-
.pop_front()
348-
.expect("len > 0 so must have a block");
347+
/// Take the first block even when it is empty, for callers that know from
348+
/// elsewhere that the block holds items
349+
pub fn take_first_block(&mut self) -> CustomBlockProvider::Block {
350+
let block = self.blocks.pop_front().expect("always at least one block");
349351

350352
if self.blocks.is_empty() {
351353
self.current_block_index = 0;
@@ -359,7 +361,42 @@ impl<const FIXED_BLOCK_SIZING: bool, CustomBlockProvider: BlockProvider>
359361

360362
self.len -= block.len();
361363

362-
Some(block)
364+
block
365+
}
366+
367+
/// Block `block_index` without bounds checking
368+
///
369+
/// # Safety
370+
/// `block_index < self.num_blocks()`
371+
#[inline]
372+
pub unsafe fn block_unchecked(&self, block_index: usize) -> &CustomBlockProvider::Block {
373+
debug_assert!(block_index < self.blocks.len());
374+
unsafe { self.blocks.get(block_index).unwrap_unchecked() }
375+
}
376+
377+
/// Mutable block `block_index` without bounds checking
378+
///
379+
/// # Safety
380+
/// `block_index < self.num_blocks()`
381+
#[inline]
382+
pub unsafe fn block_unchecked_mut(
383+
&mut self,
384+
block_index: usize,
385+
) -> &mut CustomBlockProvider::Block {
386+
debug_assert!(block_index < self.blocks.len());
387+
unsafe { self.blocks.get_mut(block_index).unwrap_unchecked() }
388+
}
389+
390+
pub fn blocks_mut(&mut self) -> impl Iterator<Item = &mut CustomBlockProvider::Block> {
391+
self.blocks.iter_mut()
392+
}
393+
394+
pub fn current_block_mut(&mut self) -> &mut CustomBlockProvider::Block {
395+
&mut self.blocks[self.current_block_index]
396+
}
397+
398+
pub fn current_or_block_mut(&mut self, block_index: usize) -> &mut CustomBlockProvider::Block {
399+
&mut self.blocks[block_index]
363400
}
364401

365402
pub fn take_block_finished(&mut self) -> Option<CustomBlockProvider::FinishedBlock>

‎datafusion/expr-common/src/blocked_helpers/blocked_offset_buffer_builder.rs‎

Lines changed: 15 additions & 25 deletions
Original file line numberDiff line numberDiff line change
@@ -74,25 +74,13 @@ impl<const FIXED_BLOCK_SIZING: bool, O: OffsetSizeTrait>
7474
self.last_offset
7575
}
7676

77-
/// Slot of the start offset of item `index`, the item index counts `block_size`
78-
/// items per block while the slots have one more (the leading zero) per block
79-
#[inline]
80-
fn slot(&self, index: BlocksIndex) -> usize {
81-
assert!(
82-
FIXED_BLOCK_SIZING,
83-
"indexing by BlocksIndex is only supported for fixed block sizing"
84-
);
85-
let block_size = self.block_size();
86-
index.block_index(block_size) * (block_size + 1)
87-
+ index.index_in_block(block_size)
88-
}
89-
9077
/// `(start, end)` offsets within the block of item `index`
9178
#[inline]
9279
pub fn value_offsets(&self, index: BlocksIndex) -> (O, O) {
93-
let slot = self.slot(index);
94-
let slots = self.slots.as_slice();
95-
(slots[slot], slots[slot + 1])
80+
let block_size = self.block_size();
81+
let block = self.slots.block(index.block_index(block_size));
82+
let slot = index.index_in_block(block_size);
83+
(block[slot], block[slot + 1])
9684
}
9785

9886
pub fn start_new_block(&mut self) {
@@ -158,17 +146,17 @@ impl<const FIXED_BLOCK_SIZING: bool, O: OffsetSizeTrait>
158146
}
159147

160148
let added = offset_buffer_slice.len() - 1;
161-
let start = self.slots.len();
162-
self.slots.extend_from_slice(&offset_buffer_slice[1..]);
163149

164150
// Rebase, easily SIMD-ed: `[0, 2, 3]` extended with `[6, 9, 10]` becomes `[0, 2, 3, 6, 7]`
165151
let base = offset_buffer_slice[0];
166152
let last_offset = self.last_offset;
167-
for offset in &mut self.slots.as_mut_slice()[start..] {
168-
*offset = *offset - base + last_offset;
169-
}
153+
let rebased: Vec<O> = offset_buffer_slice[1..]
154+
.iter()
155+
.map(|offset| *offset - base + last_offset)
156+
.collect();
157+
self.slots.extend_from_slice(&rebased);
170158

171-
self.last_offset = self.slots.as_slice()[self.slots.len() - 1];
159+
self.last_offset = *rebased.last().expect("at least one offset was added");
172160
self.len += added;
173161
self.finish_block_if_full()
174162
}
@@ -365,13 +353,14 @@ impl<const FIXED_BLOCK_SIZING: bool, O: OffsetSizeTrait>
365353
if FIXED_BLOCK_SIZING {
366354
old.take_n(n + 1, None::<std::iter::Empty<usize>>)
367355
} else {
368-
old.take_n(n + 1, Some(std::iter::once(old.len() - n - 1)))
356+
let rest = old.len() - n - 1;
357+
old.take_n(n + 1, Some(std::iter::once(rest)))
369358
}
370359
.into_scalar_buffer()
371360
}
372361

373362
pub fn blocks_iter(&self) -> impl Iterator<Item = &[O]> + Clone {
374-
(0..self.num_blocks()).map(|b| self.slots.block(b))
363+
(0..self.num_blocks()).map(|b| self.slots.block(b).as_slice())
375364
}
376365
}
377366

@@ -408,7 +397,8 @@ impl<const FIXED_BLOCK_SIZING: bool, O: OffsetSizeTrait> Index<BlocksIndex>
408397

409398
#[inline]
410399
fn index(&self, index: BlocksIndex) -> &Self::Output {
411-
&self.slots.as_slice()[self.slot(index)]
400+
let block_size = self.block_size();
401+
&self.slots.block(index.block_index(block_size))[index.index_in_block(block_size)]
412402
}
413403
}
414404

0 commit comments

Comments
 (0)