You are viewing a plain text version of this content. The canonical link for it is here.
Posted to github@arrow.apache.org by "alamb (via GitHub)" <gi...@apache.org> on 2026/01/02 14:26:50 UTC
[PR] Speed up binary kernels, add `BooleanBuffer::from_bitwise_binary_op` [arrow-rs]
alamb opened a new pull request, #9090:
URL: https://github.com/apache/arrow-rs/pull/9090
- Draft as it builds on https://github.com/apache/arrow-rs/pull/9087
# Which issue does this PR close?
- Part of https://github.com/apache/arrow-rs/issues/8806
- Closes https://github.com/apache/arrow-rs/pull/8854
- Closes https://github.com/apache/arrow-rs/pull/8807
This is the next step after
- https://github.com/apache/arrow-rs/pull/8996
# Rationale for this change
- we can help rust / LLVM generate more optimal code by processing u64 words at a time when the buffer is already u64 aligned (see #8807)
Also, it is hard to find the code to create new Buffers by applying bitwise unary operations.
# What changes are included in this PR?
- Introduce optimized `BooleanBuffer::from_bitwise_binary`
- Migrate several kernels that use `bitwise_bin_op_helper` to use the new BooleanBuffer
# Are these changes tested?
Yes new tests are added
Performance results show XXX performance improvements
# Are there any user-facing changes?
A new API
--
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: github-unsubscribe@arrow.apache.org
For queries about this service, please contact Infrastructure at:
users@infra.apache.org
Re: [PR] Speed up binary kernels (30% faster `and` and `or`), add `BooleanBuffer::from_bitwise_binary_op` [arrow-rs]
Posted by "Dandandan (via GitHub)" <gi...@apache.org>.
Dandandan merged PR #9090:
URL: https://github.com/apache/arrow-rs/pull/9090
--
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: github-unsubscribe@arrow.apache.org
For queries about this service, please contact Infrastructure at:
users@infra.apache.org
Re: [PR] Speed up binary kernels, add `BooleanBuffer::from_bitwise_binary_op` [arrow-rs]
Posted by "alamb (via GitHub)" <gi...@apache.org>.
alamb commented on code in PR #9090:
URL: https://github.com/apache/arrow-rs/pull/9090#discussion_r2657818566
##########
arrow-buffer/src/buffer/ops.rs:
##########
@@ -207,19 +210,19 @@ pub fn buffer_bin_and_not(
right_offset_in_bits: usize,
len_in_bits: usize,
) -> Buffer {
- bitwise_bin_op_helper(
+ BooleanBuffer::from_bitwise_binary_op(
left,
left_offset_in_bits,
right,
right_offset_in_bits,
len_in_bits,
|a, b| a & !b,
)
+ .into_inner()
}
/// Apply a bitwise not to one input and return the result as a Buffer.
/// The input is treated as a bitmap, meaning that offset and length are specified in number of bits.
pub fn buffer_unary_not(left: &Buffer, offset_in_bits: usize, len_in_bits: usize) -> Buffer {
- // TODO: should we deprecate this function in favor of the Buffer ! impl ?
Review Comment:
there is no Buffer impl of `!` (there is an implementation in BooleanBuffer)
--
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: github-unsubscribe@arrow.apache.org
For queries about this service, please contact Infrastructure at:
users@infra.apache.org
Re: [PR] Speed up binary kernels (30% faster `and` and `or`), add `BooleanBuffer::from_bitwise_binary_op` [arrow-rs]
Posted by "alamb (via GitHub)" <gi...@apache.org>.
alamb commented on code in PR #9090:
URL: https://github.com/apache/arrow-rs/pull/9090#discussion_r2669471569
##########
arrow-buffer/src/buffer/boolean.rs:
##########
@@ -254,6 +254,112 @@ impl BooleanBuffer {
Some(BooleanBuffer::new(buffer, 0, len_in_bits))
}
+ /// Create a new [`BooleanBuffer`] by applying the bitwise operation `op` to
+ /// the relevant bits from two input buffers.
+ ///
+ /// This function is faster than applying the operation bit by bit as
+ /// it processes input buffers in chunks of 64 bits (8 bytes) at a time
+ ///
+ /// # Notes:
+ /// See notes on [Self::from_bitwise_unary_op]
+ ///
+ /// # See Also
+ /// - [`BooleanBuffer::from_bitwise_unary_op`] for unary operations on a single input buffer.
+ /// - [`apply_bitwise_binary_op`](bit_util::apply_bitwise_binary_op) for in-place binary bitwise operations
+ ///
+ /// # Example: Create new [`BooleanBuffer`] from bitwise `AND` of two [`Buffer`]s
+ /// ```
+ /// # use arrow_buffer::{Buffer, BooleanBuffer};
+ /// let left = Buffer::from(vec![0b11001100u8, 0b10111010u8]); // 2 bytes = 16 bits
+ /// let right = Buffer::from(vec![0b10101010u8, 0b11011100u8, 0b11110000u8]); // 3 bytes = 24 bits
+ /// // AND of the first 12 bits
+ /// let result = BooleanBuffer::from_bitwise_binary_op(
+ /// &left, 0, &right, 0, 12, |a, b| a & b
+ /// );
+ /// assert_eq!(result.inner().as_slice(), &[0b10001000u8, 0b00001000u8]);
+ /// ```
+ ///
+ /// # Example: Create new [`BooleanBuffer`] from bitwise `OR` of two byte slices
+ /// ```
+ /// # use arrow_buffer::BooleanBuffer;
+ /// let left = [0b11001100u8, 0b10111010u8];
+ /// let right = [0b10101010u8, 0b11011100u8];
+ /// // OR of bits 4..16 from left and bits 0..12 from right
+ /// let result = BooleanBuffer::from_bitwise_binary_op(
+ /// &left, 4, &right, 0, 12, |a, b| a | b
+ /// );
+ /// assert_eq!(result.inner().as_slice(), &[0b10101110u8, 0b00001111u8]);
+ /// ```
+ pub fn from_bitwise_binary_op<F>(
+ left: impl AsRef<[u8]>,
+ left_offset_in_bits: usize,
+ right: impl AsRef<[u8]>,
+ right_offset_in_bits: usize,
+ len_in_bits: usize,
+ mut op: F,
+ ) -> Self
+ where
+ F: FnMut(u64, u64) -> u64,
+ {
+ let left = left.as_ref();
+ let right = right.as_ref();
+ // try fast path for aligned input
+ // If the underlying buffers are aligned to u64 we can apply the operation directly on the u64 slices
+ // to improve performance.
+ if left_offset_in_bits & 0x7 == 0 && right_offset_in_bits & 0x7 == 0 {
+ // align to byte boundary
+ let left = &left[left_offset_in_bits / 8..];
+ let right = &right[right_offset_in_bits / 8..];
+
+ unsafe {
+ let (left_prefix, left_u64s, left_suffix) = left.align_to::<u64>();
+ let (right_prefix, right_u64s, right_suffix) = right.align_to::<u64>();
+ // if there is no prefix or suffix, both buffers are aligned and
+ // we can do the operation directly on u64s.
+ // TODO: consider `slice::as_chunks` and `u64::from_le_bytes` when MSRV reaches 1.88.
+ // https://github.com/apache/arrow-rs/pull/9022#discussion_r2639949361
+ if left_prefix.is_empty()
+ && right_prefix.is_empty()
+ && left_suffix.is_empty()
+ && right_suffix.is_empty()
+ {
+ let result_u64s = left_u64s
+ .iter()
+ .zip(right_u64s.iter())
+ .map(|(l, r)| op(*l, *r))
+ .collect::<Vec<u64>>();
+ return BooleanBuffer {
+ buffer: Buffer::from(result_u64s),
+ bit_offset: 0,
+ bit_len: len_in_bits,
+ };
+ }
+ }
+ }
+ let left_chunks = BitChunks::new(left, left_offset_in_bits, len_in_bits);
+ let right_chunks = BitChunks::new(right, right_offset_in_bits, len_in_bits);
+
+ let chunks = left_chunks
+ .iter()
+ .zip(right_chunks.iter())
+ .map(|(left, right)| op(left, right));
+ // Soundness: `BitChunks` is a `BitChunks` iterator which
Review Comment:
Updated in a22ad8d3d26
--
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: github-unsubscribe@arrow.apache.org
For queries about this service, please contact Infrastructure at:
users@infra.apache.org
Re: [PR] Speed up binary kernels, add `BooleanBuffer::from_bitwise_binary_op` [arrow-rs]
Posted by "alamb (via GitHub)" <gi...@apache.org>.
alamb commented on PR #9090:
URL: https://github.com/apache/arrow-rs/pull/9090#issuecomment-3705481482
run benchmark boolean_kernels
--
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: github-unsubscribe@arrow.apache.org
For queries about this service, please contact Infrastructure at:
users@infra.apache.org
Re: [PR] Speed up binary kernels, add `BooleanBuffer::from_bitwise_binary_op` [arrow-rs]
Posted by "alamb-ghbot (via GitHub)" <gi...@apache.org>.
alamb-ghbot commented on PR #9090:
URL: https://github.com/apache/arrow-rs/pull/9090#issuecomment-3705493065
🤖: Benchmark completed
<details><summary>Details</summary>
<p>
```
group alamb_boolean_kernel main
----- -------------------- ----
and 1.00 208.4±2.61ns ? ?/sec 1.31 273.8±4.63ns ? ?/sec
and_sliced_1 1.01 1101.0±3.25ns ? ?/sec 1.00 1094.0±7.12ns ? ?/sec
and_sliced_24 1.05 250.9±1.84ns ? ?/sec 1.00 239.4±2.17ns ? ?/sec
not 1.02 148.5±3.30ns ? ?/sec 1.00 145.6±0.72ns ? ?/sec
not_slice_24 1.02 198.9±7.14ns ? ?/sec 1.00 194.4±4.51ns ? ?/sec
not_sliced_1 1.01 623.8±9.34ns ? ?/sec 1.00 620.0±6.84ns ? ?/sec
or 1.00 197.8±1.30ns ? ?/sec 1.28 252.9±2.20ns ? ?/sec
or_sliced_1 1.00 1106.9±50.01ns ? ?/sec 1.11 1228.1±13.41ns ? ?/sec
or_sliced_24 1.02 248.3±1.07ns ? ?/sec 1.00 242.4±4.02ns ? ?/sec
```
</p>
</details>
--
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: github-unsubscribe@arrow.apache.org
For queries about this service, please contact Infrastructure at:
users@infra.apache.org
Re: [PR] Speed up binary kernels (30% faster `and` and `or`), add `BooleanBuffer::from_bitwise_binary_op` [arrow-rs]
Posted by "Dandandan (via GitHub)" <gi...@apache.org>.
Dandandan commented on code in PR #9090:
URL: https://github.com/apache/arrow-rs/pull/9090#discussion_r2668087357
##########
arrow-buffer/src/buffer/boolean.rs:
##########
@@ -254,6 +254,112 @@ impl BooleanBuffer {
Some(BooleanBuffer::new(buffer, 0, len_in_bits))
}
+ /// Create a new [`BooleanBuffer`] by applying the bitwise operation `op` to
+ /// the relevant bits from two input buffers.
+ ///
+ /// This function is faster than applying the operation bit by bit as
+ /// it processes input buffers in chunks of 64 bits (8 bytes) at a time
+ ///
+ /// # Notes:
+ /// See notes on [Self::from_bitwise_unary_op]
+ ///
+ /// # See Also
+ /// - [`BooleanBuffer::from_bitwise_unary_op`] for unary operations on a single input buffer.
+ /// - [`apply_bitwise_binary_op`](bit_util::apply_bitwise_binary_op) for in-place binary bitwise operations
+ ///
+ /// # Example: Create new [`BooleanBuffer`] from bitwise `AND` of two [`Buffer`]s
+ /// ```
+ /// # use arrow_buffer::{Buffer, BooleanBuffer};
+ /// let left = Buffer::from(vec![0b11001100u8, 0b10111010u8]); // 2 bytes = 16 bits
+ /// let right = Buffer::from(vec![0b10101010u8, 0b11011100u8, 0b11110000u8]); // 3 bytes = 24 bits
+ /// // AND of the first 12 bits
+ /// let result = BooleanBuffer::from_bitwise_binary_op(
+ /// &left, 0, &right, 0, 12, |a, b| a & b
+ /// );
+ /// assert_eq!(result.inner().as_slice(), &[0b10001000u8, 0b00001000u8]);
+ /// ```
+ ///
+ /// # Example: Create new [`BooleanBuffer`] from bitwise `OR` of two byte slices
+ /// ```
+ /// # use arrow_buffer::BooleanBuffer;
+ /// let left = [0b11001100u8, 0b10111010u8];
+ /// let right = [0b10101010u8, 0b11011100u8];
+ /// // OR of bits 4..16 from left and bits 0..12 from right
+ /// let result = BooleanBuffer::from_bitwise_binary_op(
+ /// &left, 4, &right, 0, 12, |a, b| a | b
+ /// );
+ /// assert_eq!(result.inner().as_slice(), &[0b10101110u8, 0b00001111u8]);
+ /// ```
+ pub fn from_bitwise_binary_op<F>(
+ left: impl AsRef<[u8]>,
+ left_offset_in_bits: usize,
+ right: impl AsRef<[u8]>,
+ right_offset_in_bits: usize,
+ len_in_bits: usize,
+ mut op: F,
+ ) -> Self
+ where
+ F: FnMut(u64, u64) -> u64,
+ {
+ let left = left.as_ref();
+ let right = right.as_ref();
+ // try fast path for aligned input
+ // If the underlying buffers are aligned to u64 we can apply the operation directly on the u64 slices
+ // to improve performance.
+ if left_offset_in_bits & 0x7 == 0 && right_offset_in_bits & 0x7 == 0 {
+ // align to byte boundary
+ let left = &left[left_offset_in_bits / 8..];
+ let right = &right[right_offset_in_bits / 8..];
+
+ unsafe {
+ let (left_prefix, left_u64s, left_suffix) = left.align_to::<u64>();
+ let (right_prefix, right_u64s, right_suffix) = right.align_to::<u64>();
+ // if there is no prefix or suffix, both buffers are aligned and
+ // we can do the operation directly on u64s.
+ // TODO: consider `slice::as_chunks` and `u64::from_le_bytes` when MSRV reaches 1.88.
+ // https://github.com/apache/arrow-rs/pull/9022#discussion_r2639949361
+ if left_prefix.is_empty()
+ && right_prefix.is_empty()
+ && left_suffix.is_empty()
+ && right_suffix.is_empty()
+ {
+ let result_u64s = left_u64s
+ .iter()
+ .zip(right_u64s.iter())
+ .map(|(l, r)| op(*l, *r))
+ .collect::<Vec<u64>>();
+ return BooleanBuffer {
+ buffer: Buffer::from(result_u64s),
+ bit_offset: 0,
+ bit_len: len_in_bits,
+ };
+ }
+ }
+ }
+ let left_chunks = BitChunks::new(left, left_offset_in_bits, len_in_bits);
+ let right_chunks = BitChunks::new(right, right_offset_in_bits, len_in_bits);
+
+ let chunks = left_chunks
+ .iter()
+ .zip(right_chunks.iter())
+ .map(|(left, right)| op(left, right));
+ // Soundness: `BitChunks` is a `BitChunks` iterator which
Review Comment:
Trusted Len ?
--
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: github-unsubscribe@arrow.apache.org
For queries about this service, please contact Infrastructure at:
users@infra.apache.org
Re: [PR] Speed up binary kernels (30% faster `and` and `or`), add `BooleanBuffer::from_bitwise_binary_op` [arrow-rs]
Posted by "alamb (via GitHub)" <gi...@apache.org>.
alamb commented on PR #9090:
URL: https://github.com/apache/arrow-rs/pull/9090#issuecomment-3729518751
Thank you @Dandandan
--
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: github-unsubscribe@arrow.apache.org
For queries about this service, please contact Infrastructure at:
users@infra.apache.org
Re: [PR] Speed up binary kernels, add `BooleanBuffer::from_bitwise_binary_op` [arrow-rs]
Posted by "alamb-ghbot (via GitHub)" <gi...@apache.org>.
alamb-ghbot commented on PR #9090:
URL: https://github.com/apache/arrow-rs/pull/9090#issuecomment-3705481850
🤖 `./gh_compare_arrow.sh` [gh_compare_arrow.sh](https://github.com/alamb/datafusion-benchmarking/blob/main/scripts/gh_compare_arrow.sh) Running
Linux aal-dev 6.14.0-1018-gcp #19~24.04.1-Ubuntu SMP Wed Sep 24 23:23:09 UTC 2025 x86_64 x86_64 x86_64 GNU/Linux
Comparing alamb/boolean_kernel (577dfa8d4959f9f608a335d54329553d131e80fc) to 44d4c906c6775d2809d0640e74a0d34ea328c533 [diff](https://github.com/apache/arrow-rs/compare/44d4c906c6775d2809d0640e74a0d34ea328c533..577dfa8d4959f9f608a335d54329553d131e80fc)
BENCH_NAME=boolean_kernels
BENCH_COMMAND=cargo bench --features=arrow,async,test_common,experimental --bench boolean_kernels
BENCH_FILTER=
BENCH_BRANCH_NAME=alamb_boolean_kernel
Results will be posted here when complete
--
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: github-unsubscribe@arrow.apache.org
For queries about this service, please contact Infrastructure at:
users@infra.apache.org
Re: [PR] Speed up binary kernels, add `BooleanBuffer::from_bitwise_binary_op` [arrow-rs]
Posted by "alamb (via GitHub)" <gi...@apache.org>.
alamb commented on code in PR #9090:
URL: https://github.com/apache/arrow-rs/pull/9090#discussion_r2657810925
##########
arrow-buffer/src/buffer/boolean.rs:
##########
@@ -254,6 +254,111 @@ impl BooleanBuffer {
Some(BooleanBuffer::new(buffer, 0, len_in_bits))
}
+ /// Create a new [`BooleanBuffer`] by applying the bitwise operation `op` to
+ /// the relevant bits from two input buffers.
+ ///
+ /// This function is faster than applying the operation bit by bit as
+ /// it processes input buffers in chunks of 64 bits (8 bytes) at a time
+ ///
+ /// # Notes:
+ /// See notes on [Self::from_bitwise_unary_op]
+ ///
+ /// # See Also
+ /// - [`BooleanBuffer::from_bitwise_unary_op`] for unary operations on a single input buffer.
+ /// - [`apply_bitwise_binary_op`](bit_util::apply_bitwise_binary_op) for in-place binary bitwise operations
+ ///
+ /// # Example: Create new [`BooleanBuffer`] from bitwise `AND` of two [`Buffer`]s
+ /// ```
+ /// # use arrow_buffer::{Buffer, BooleanBuffer};
+ /// let left = Buffer::from(vec![0b11001100u8, 0b10111010u8]); // 2 bytes = 16 bits
+ /// let right = Buffer::from(vec![0b10101010u8, 0b11011100u8, 0b11110000u8]); // 3 bytes = 24 bits
+ /// // AND of the first 12 bits
+ /// let result = BooleanBuffer::from_bitwise_binary_op(
+ /// &left, 0, &right, 0, 12, |a, b| a & b
+ /// );
+ /// assert_eq!(result.inner().as_slice(), &[0b10001000u8, 0b00001000u8]);
+ /// ```
+ ///
+ /// # Example: Create new [`BooleanBuffer`] from bitwise `OR` of two byte slices
+ /// ```
+ /// # use arrow_buffer::BooleanBuffer;
+ /// let left = [0b11001100u8, 0b10111010u8];
+ /// let right = [0b10101010u8, 0b11011100u8];
+ /// // OR of bits 4..16 from left and bits 0..12 from right
+ /// let result = BooleanBuffer::from_bitwise_binary_op(
+ /// &left, 4, &right, 0, 12, |a, b| a | b
+ /// );
+ /// assert_eq!(result.inner().as_slice(), &[0b10101110u8, 0b00001111u8]);
+ /// ```
+ pub fn from_bitwise_binary_op<F>(
Review Comment:
this is the new API
--
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: github-unsubscribe@arrow.apache.org
For queries about this service, please contact Infrastructure at:
users@infra.apache.org