waynexia opened a new pull request, #12042:
URL: https://github.com/apache/arrow-rs/pull/12042
# Which issue does this PR close?
- N/A
# Rationale for this change
`BooleanBufferBuilder::append_slice` (which also backs
`BooleanBuilder::append_slice`, `NullBufferBuilder::append_slice`,
`PrimitiveBuilder::append_values`, and `BooleanBuffer::from(&[bool])`)
previously appended booleans one bit at a time:
```rust
for (i, v) in slice.iter().enumerate() {
if *v {
unsafe { bit_util::set_bit_raw(self.buffer.as_mut_ptr(), offset + i)
}
}
}
```
This had two main performance bottlenecks:
1. **Branch mispredictions**: Every element required a conditional branch
(`if *v`), causing frequent branch mispredictions on unpredictable boolean
inputs.
2. **Repeated byte-level read-modify-writes**: `set_bit_raw` performs a byte
read, bitwise OR, and store for every `true` bit, creating a store-to-load
dependency chain on the same target byte up to 8 times.
Packing 8 booleans at a time into a single byte without branches and storing
whole bytes eliminates both the branch mispredictions and the per-bit
read-modify-write traffic.
## Human Rationale
I'm trying to find something to burn my token, and come across this. This PR
is fully written by AI. I have read and understand all logic changes. It
increases complexity, but given that this part is not likely to be touched too
often, I thought it was acceptable.
# What changes are included in this PR?
- Refactor `BooleanBufferBuilder::append_slice` into three phases:
1. **Head**: If the current bit offset is not byte-aligned, pack the
leading booleans into the existing partial byte while preserving
already-written low bits and zeroing upper padding bits.
2. **Middle**: Process 8 booleans at a time (`as_chunks::<8>()`) using a
branchless SWAR multiplication
(`(u64::from_le_bytes(bytes).wrapping_mul(0x0102_0408_1020_4080) >> 56) as u8`)
and write full bytes directly to the buffer.
`wrapping_mul(0x0102_0408_1020_4080) >> 56)` equals to 8 continuous "shift-left
+ OR"
3. **Tail**: Pack any remaining `< 8` booleans into the final byte,
keeping the trailing padding bits zeroed.
- Add unit tests in `arrow-buffer` covering unaligned head/tail
combinations, all-true/all-false inputs, empty slices, zeroed padding
invariants, and randomized comparisons against a reference bit-by-bit
implementation.
# Are these changes tested?
Yes
Performance can also be verified with the existing `bench_bool` benchmark in
`arrow/benches/builder.rs` (`cargo bench -p arrow --bench builder --
bench_bool`).
On my local env, depends on the scenario, this patch can achieve at least 5x
improvement on microbenchmark, except one bad case that append 1 bit a time
# Are there any significant user-facing changes?
No.
--
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]
