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 128d200558 perf(NullBuffer::Exapand) optimize 8 byte chunks (#10976)
128d200558 is described below
commit 128d2005583500461c49e90a9b7d485dd4b76992
Author: RIchard Baah <[email protected]>
AuthorDate: Fri Sep 4 07:33:18 2026 -0400
perf(NullBuffer::Exapand) optimize 8 byte chunks (#10976)
# 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.
-->
- Closes #10883.
# Rationale for this change
see #10883.
`NullBuffer::expand` repeats each validity bit count times, used
whenever a parent null must be propagated to a fixed-size group of child
elements. The previous implementation set output bits one at a time
regardless of count, which is unnecessarily slow for common sizes.
<!--
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?
Three tiered fast paths are added to try_expand, checked in order:
- count % 8 == 0 : each expanded run is byte-aligned, so contiguous runs
of valid bits are filled with memset(0xFF) via BitSliceIterator rather
than setting bits individually.
- count % 4 == 0 : each bit's range starts and ends on a nibble
boundary. Full interior bytes are filled with 0xFF; the one partial
boundary byte is set with |= 0x0F or |= 0xF0 depending on alignment. No
inner loop.
- General case : unchanged bit-by-bit path.
<!--
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, existing test cover this as well as 1 new test
<!--
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 | 63 ++++++++++++++++++++++++++++++++++++-----
1 file changed, 56 insertions(+), 7 deletions(-)
diff --git a/arrow-buffer/src/buffer/null.rs b/arrow-buffer/src/buffer/null.rs
index 003585d91b..fb7df56e97 100644
--- a/arrow-buffer/src/buffer/null.rs
+++ b/arrow-buffer/src/buffer/null.rs
@@ -142,14 +142,49 @@ impl NullBuffer {
.ok_or_else(|| OverflowError::new::<usize>("buffer length"))?;
let mut buffer = MutableBuffer::new_null(capacity);
- // Expand each bit within `null_mask` into `element_len`
- // bits, constructing the implicit mask of the child elements
- for i in 0..self.buffer.len() {
- if self.is_null(i) {
- continue;
+ if count.is_multiple_of(8) {
+ // When count is a multiple of 8 every expanded run starts on a
byte
+ // boundary (bit i starts at bit i*count, which is divisible by 8),
+ // so we can fill count/8 bytes of 0xFF at a time instead of
setting
+ // bits individually.
+ let bytes_per_bit = count / 8;
+ let buf = buffer.as_mut();
+ for (start, end) in BitSliceIterator::new(
+ self.buffer.values(),
+ self.buffer.offset(),
+ self.buffer.len(),
+ ) {
+ let byte_start = start * bytes_per_bit;
+ let byte_end = end * bytes_per_bit;
+ buf[byte_start..byte_end].fill(0xFF);
}
- for j in 0..count {
- crate::bit_util::set_bit(buffer.as_mut(), i * count + j)
+ } else if count.is_multiple_of(4) {
+ // count is a multiple of 4 but not 8: each bit's range starts and
ends
+ // on a nibble boundary. Fill any full bytes, then OR in the
partial nibble
+ // (0x0F if the range ends mid-byte, 0xF0 if it starts mid-byte).
+ let buf = buffer.as_mut();
+ for i in 0..self.buffer.len() {
+ if self.is_null(i) {
+ continue;
+ }
+ let start_bit = i * count;
+ let end_bit = start_bit + count;
+ if start_bit.is_multiple_of(8) {
+ buf[start_bit / 8..end_bit / 8].fill(0xFF);
+ buf[end_bit / 8] |= 0x0F;
+ } else {
+ buf[start_bit / 8] |= 0xF0;
+ buf[start_bit / 8 + 1..end_bit / 8].fill(0xFF);
+ }
+ }
+ } 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)
+ }
}
}
Ok(Self {
@@ -470,4 +505,18 @@ mod tests {
let result = NullBuffer::union(Some(&all_null), Some(&all_valid));
assert_eq!(result, Some(all_null.clone()));
}
+
+ #[test]
+ fn test_expand_code_paths() {
+ let source = NullBuffer::from(&[true, false, true] as &[bool]);
+
+ for count in [8, 4, 3] {
+ let expanded = source.expand(count);
+ assert_eq!(expanded.len(), 3 * count);
+ assert_eq!(expanded.null_count(), count);
+ assert!((0..count).all(|i| expanded.is_valid(i)));
+ assert!((count..2 * count).all(|i| expanded.is_null(i)));
+ assert!((2 * count..3 * count).all(|i| expanded.is_valid(i)));
+ }
+ }
}
