mightsleep commented on PR #11872:
URL: https://github.com/apache/arrow-rs/pull/11872#issuecomment-6452331257
Yes hello, I had a look at this one. The kernel looks correct to me.
While benchmarking I noticed that contiguous selections come out slower than
on main. With `optimize()`, a selectivity below 0.8 gives `Indices`, and
`filter_offsets` then walks the rows one by one, where `MutableArrayData` went
by slices. The nested cases in `filter_kernels` only use the three random
masks, so runs never show up there. A case with `create_clustered_array` (runs
of 64) and one with short lists would catch it.
64K rows, Zen 5, ns per row:
| case | main | this PR | with the suggestions below |
|---|---|---|---|
| `list<i32>` avg 8, prefix half | 0.86 | 1.87 | 0.085 |
| `list<i32>` avg 8, runs of 64 | 1.56 | 2.36 | 0.56 |
| `list<i32>` avg 1, prefix half | 0.50 | 2.60 | 0.061 |
| `list<i32>` avg 1, runs of 64 | 0.72 | 2.73 | 0.25 |
| `list<i32>` avg 8, kept 1023/1024 | 2.60 | 1.52 | 0.72 |
| `list<i32>` avg 1, kept 1023/1024 | 1.08 | 0.98 | 0.17 |
| `list<struct<i64, utf8>>`, one run in the middle (1/8) | 1.94 | 1.50 |
0.042 |
| `list<i32>` avg 8, kept 1/1024 | 0.044 | 0.026 | 0.025 |
None of the cases I measured got slower than the PR. A few suggestions, take
whichever you like:
Walk the offsets by slices. Runs of rows are runs of child values, so this
keeps the indices only when they are few:
```rust
match &predicate.strategy {
IterationStrategy::Slices(slices) => {
slices.iter().for_each(|&(start, end)| extend(start, end))
}
// Few rows: the precomputed indices beat scanning the whole mask
IterationStrategy::Indices(indices) if predicate.count <=
predicate.filter.len() / 64 => {
indices.iter().for_each(|&idx| extend(idx, idx + 1))
}
IterationStrategy::All | IterationStrategy::None => unreachable!(),
_ => SlicesIterator::new(&predicate.filter).for_each(|(start, end)|
extend(start, end)),
}
```
Shift the offsets of each run by a constant, as in #11880. Unlike the
running sum, this vectorizes:
```rust
let mut extend = |start: usize, end: usize| {
let value_start = offsets[start].as_usize();
let value_end = offsets[end].as_usize();
let shift = cur_offset.wrapping_sub(value_start);
dst_offsets.extend(
offsets[start + 1..=end]
.iter()
.map(|o| O::usize_as(o.as_usize().wrapping_add(shift))),
);
cur_offset += value_end - value_start;
// child_slices as before
};
```
A single run of values as a zero-copy slice, wherever it starts. In
`filter_offsets`, rebase the one slice so that it becomes `All`, and return the
start:
```rust
let base = match child_slices.as_slice() {
[(start, _)] => *start,
_ => 0,
};
for (start, end) in &mut child_slices {
*start -= base;
*end -= base;
}
```
Then in `filter_list`:
```rust
let (offsets, child_predicate, base) = filter_offsets(array.value_offsets(),
predicate);
let values = match child_predicate.strategy {
IterationStrategy::All => array.values().slice(base,
child_predicate.count),
_ => filter_array(array.values(), &child_predicate)?,
};
```
Single run on purpose. Slicing to a shorter length recounts the nulls of
every descendant, and slicing for every selection made the sparse case 3x
slower.
--
This is an automated message from the Apache Git Service.
To respond to the message, please log on to GitHub and use the
URL above to go to the specific comment.
To unsubscribe, e-mail: [email protected]
For queries about this service, please contact Infrastructure at:
[email protected]
