This is an automated email from the ASF dual-hosted git repository.
Jefffrey pushed a commit to branch main
in repository https://gitbox.apache.org/repos/asf/arrow-rs.git
The following commit(s) were added to refs/heads/main by this push:
new dbd24cc95d perf(nullbuf::expand) non aligned counts (#10980)
dbd24cc95d is described below
commit dbd24cc95d85aa4c14f4719dd3140d723c715517
Author: RIchard Baah <[email protected]>
AuthorDate: Sun Sep 6 00:50:21 2026 -0400
perf(nullbuf::expand) non aligned counts (#10980)
## note I did use ai to help me with the bit maniluplation logic!
# Which issue does this PR close?
<!--
We generally require a GitHub issue to be filed for all bug fixes and
enhancements and this helps us generate change logs for our releases.
You can link an issue to this PR using the GitHub syntax.
-->
- follow up to #10976
# Rationale for this change
`NullBuffer::expand` now has a fast path for count % 8 == 0
(byte-aligned) and count % 4 == 0 (nibble-aligned) counts. For all other
values of count the fallback iterated every bit individually, calling
set_bit per valid index. This is O(n × count) bit-level writes even when
the validity buffer is mostly non-null.
<!--
Why are you proposing this change? If this is already explained clearly
in the issue then this section is not needed.
Explaining clearly why changes are proposed helps reviewers understand
your changes and offer better suggestions for fixes.
-->
# What changes are included in this PR?
Replaces the bit-by-bit fallback in `NullBuffer::try_expand` with a
BitSliceIterator based approach that works over contiguous runs of valid
bits rather than individual bits. For each run [start, end) it computes
the output byte range [start*count/8, end*count/8] and sets it with
byte-level OR masks:
- A partial leading byte is ORed with 0xFF << start_offset.
- Full interior bytes are filled with 0xFF.
- A partial trailing byte is ORed with (1 << end_offset) - 1.
- When the entire run fits in a single byte, both masks are ANDed
together.
<!--
There is no need to duplicate the description in the issue here but it
is sometimes worth providing a summary of the individual changes in this
PR.
-->
# Are these changes tested?
yes, test was introduced in #10976
<!--
We typically require tests for all PRs in order to:
1. Prevent the code from being accidentally broken by subsequent changes
2. Serve as another way to document the expected behavior of the code
If tests are not included in your PR, please explain why (for example,
are they covered by existing tests)?
If this PR claims a performance improvement, please include evidence
such as benchmark results.
-->
# Are there any user-facing changes?
no
<!--
If there are user-facing changes then we may require documentation to be
updated before approving the PR.
If there are any breaking changes to public APIs, please call them out.
-->
---
arrow-buffer/src/buffer/null.rs | 42 +++++++++++++++++++++++++++++++++++------
1 file changed, 36 insertions(+), 6 deletions(-)
diff --git a/arrow-buffer/src/buffer/null.rs b/arrow-buffer/src/buffer/null.rs
index fb7df56e97..04dbfa2b41 100644
--- a/arrow-buffer/src/buffer/null.rs
+++ b/arrow-buffer/src/buffer/null.rs
@@ -178,12 +178,42 @@ impl NullBuffer {
}
}
} else {
- for i in 0..self.buffer.len() {
- if self.is_null(i) {
- continue;
- }
- for j in 0..count {
- crate::bit_util::set_bit(buffer.as_mut(), i * count + j)
+ // For each contiguous run of valid bits [start, end), the
corresponding
+ // output bits [start*count, end*count) are set. Boundary bytes
that are
+ // only partially covered are ORed with a mask; fully covered
interior
+ // bytes are filled with 0xFF.
+ let buf = buffer.as_mut();
+ for (start, end) in BitSliceIterator::new(
+ self.buffer.values(),
+ self.buffer.offset(),
+ self.buffer.len(),
+ ) {
+ let start_bit = start * count;
+ let end_bit = end * count;
+ let start_byte = start_bit / 8;
+ let start_offset = (start_bit % 8) as u32; // first bit to set
within start_byte
+ let end_byte = end_bit / 8;
+ let end_offset = (end_bit % 8) as u32; // one-past-last bit
within end_byte
+
+ if start_byte == end_byte {
+ // All bits land in one byte: mask from start_offset up to
end_offset.
+ // 0xFF << start_offset → bits [start_offset, 7] set
+ // (1 << end_offset) - 1 → bits [0, end_offset) set
+ // AND of both → bits [start_offset, end_offset)
set
+ buf[start_byte] |= (0xFFu8 << start_offset) & ((1u8 <<
end_offset) - 1);
+ } else {
+ if start_offset != 0 {
+ // Partial leading byte: set bits from start_offset to
bit 7.
+ buf[start_byte] |= 0xFFu8 << start_offset;
+ }
+ // Full interior bytes (skip start_byte if it was only
partially covered).
+ let full_start = start_byte + (start_offset != 0) as usize;
+ buf[full_start..end_byte].fill(0xFF);
+ if end_offset != 0 {
+ // Partial trailing byte: set bits 0 up to end_offset.
+ // (1 << end_offset) - 1 → bits [0, end_offset) set
+ buf[end_byte] |= (1u8 << end_offset) - 1;
+ }
}
}
}
