viirya opened a new issue, #12023:
URL: https://github.com/apache/arrow-rs/issues/12023
### Is your feature request related to a problem or challenge?
`BooleanBufferBuilder::append_slice(&[bool])` loops over the slice and, for
each `true`, does a read-modify-write of a single bit via `set_bit_raw`:
```rust
for (i, v) in slice.iter().enumerate() {
if *v {
unsafe { bit_util::set_bit_raw(self.buffer.as_mut_ptr(), offset + i)
}
}
}
```
That is a data-dependent branch per element (which mispredicts on random
data) plus a serial read-modify-write of the same output byte for every bit. It
runs at roughly 0.4–0.9 billion elements/s depending on the data, even for an
all-`true` slice.
This matters for the Parquet reader: BOOLEAN columns are decoded into a
`Vec<bool>` and turned into a bitmap with `BooleanBuffer::from(&[bool])`
(`parquet/src/arrow/array_reader/primitive_array.rs`), which calls
`append_slice`. In an end-to-end benchmark that reads 1M rows of an optional
BOOLEAN column (10% nulls, random values) from an in-memory file, most of the
time goes to this loop.
Measured on an Apple M-series machine (aarch64), 64Ki bools per call:
| input | current |
|---|---|
| random | ~165–174 µs |
| 90% true | ~75–79 µs |
| all true | ~95–106 µs |
### Describe the solution you'd like
Pack 8 bools into a byte at once without branching. A `bool` is a byte
holding 0 or 1, so loading 8 of them as a little-endian `u64` and multiplying
by `0x0102_0408_1020_4080` moves byte `i` to bit `56 + i`, and the top byte is
the packed bitmap. Set bits one at a time only for the unaligned head (until
the write position is byte aligned) and the tail of fewer than 8 values.
In a prototype this makes `append_slice` about 70x faster on every input
(about 2.3 µs per 64Ki bools), and the Parquet optional BOOLEAN read about 57%
faster (4.95 ms to 2.10 ms).
### Describe alternatives you've considered
- Building the bitmap with `MutableBuffer::collect_bool(len, |i| slice[i])`,
which packs 64 bits per word by shifts. That works for a fresh buffer but not
for appending at an arbitrary bit offset into an existing builder.
- A `std::simd` / platform intrinsic (`movemask`) version: faster still in
principle, but needs `unsafe` or nightly, while the safe, portable multiply
version already gets most of the win.
### Additional context
Other `bool`-to-bitmap paths use the same per-bit pattern and could benefit
separately, e.g. `impl From<Vec<bool>> for BooleanArray` (per-bit `set_bit`
loop) and `impl FromIterator<bool> for BooleanBuffer` (per-element `append`).
--
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]
