You are viewing a plain text version of this content. The canonical link for it is here.
Posted to commits@arrow.apache.org by ne...@apache.org on 2021/02/04 23:22:39 UTC
[arrow] branch master updated: ARROW-11383: [Rust] Faster bit AND
and OR (2x)
This is an automated email from the ASF dual-hosted git repository.
nevime pushed a commit to branch master
in repository https://gitbox.apache.org/repos/asf/arrow.git
The following commit(s) were added to refs/heads/master by this push:
new 65f5eb2 ARROW-11383: [Rust] Faster bit AND and OR (2x)
65f5eb2 is described below
commit 65f5eb2ad92efcb5cbde1471c14870399c57a28c
Author: Jorge C. Leitao <jo...@gmail.com>
AuthorDate: Fri Feb 5 01:21:20 2021 +0200
ARROW-11383: [Rust] Faster bit AND and OR (2x)
This PR speeds up the (non-SIMD) bit operations by using the `from_trusted_len_iterator`. I had to expose it also for `MutableBuffer`, and there is a potential optimization, but I left it as an exercise to the future.
Since this operation is used throughout many kernels and operations, there is some chance of a speedup on other benches and datafusion.
```
git checkout master
cargo bench --bench buffer_bit_ops
git checkout fast_bit_ops
cargo bench --bench buffer_bit_ops
```
```
buffer_bit_ops and time: [338.19 ns 339.51 ns 341.21 ns]
change: [-56.005% -50.176% -45.754%] (p = 0.00 < 0.05)
Performance has improved.
Found 3 outliers among 100 measurements (3.00%)
1 (1.00%) high mild
2 (2.00%) high severe
buffer_bit_ops or time: [341.55 ns 343.00 ns 344.43 ns]
change: [-47.595% -46.537% -45.633%] (p = 0.00 < 0.05)
Performance has improved.
Found 7 outliers among 100 measurements (7.00%)
2 (2.00%) high mild
5 (5.00%) high severe
```
Closes #9318 from jorgecarleitao/fast_bit_ops
Lead-authored-by: Jorge C. Leitao <jo...@gmail.com>
Co-authored-by: Jorge Leitao <jo...@gmail.com>
Signed-off-by: Neville Dipale <ne...@gmail.com>
---
rust/arrow/src/buffer.rs | 75 +++++++++++++++++++++++++++++++++++-------------
1 file changed, 55 insertions(+), 20 deletions(-)
diff --git a/rust/arrow/src/buffer.rs b/rust/arrow/src/buffer.rs
index 222a6ac..024db5e 100644
--- a/rust/arrow/src/buffer.rs
+++ b/rust/arrow/src/buffer.rs
@@ -364,27 +364,23 @@ fn bitwise_bin_op_helper<F>(
where
F: Fn(u64, u64) -> u64,
{
- // reserve capacity and set length so we can get a typed view of u64 chunks
- let mut result =
- MutableBuffer::new(ceil(len_in_bits, 8)).with_bitset(len_in_bits / 64 * 8, false);
-
let left_chunks = left.bit_chunks(left_offset_in_bits, len_in_bits);
let right_chunks = right.bit_chunks(right_offset_in_bits, len_in_bits);
- let result_chunks = result.typed_data_mut::<u64>().iter_mut();
- result_chunks
- .zip(left_chunks.iter().zip(right_chunks.iter()))
- .for_each(|(res, (left, right))| {
- *res = op(left, right);
- });
+ let chunks = left_chunks
+ .iter()
+ .zip(right_chunks.iter())
+ .map(|(left, right)| op(left, right));
+ // Soundness: `BitChunks` is a trusted len iterator
+ let mut buffer = unsafe { MutableBuffer::from_trusted_len_iter(chunks) };
let remainder_bytes = ceil(left_chunks.remainder_len(), 8);
let rem = op(left_chunks.remainder_bits(), right_chunks.remainder_bits());
// we are counting its starting from the least significant bit, to to_le_bytes should be correct
let rem = &rem.to_le_bytes()[0..remainder_bytes];
- result.extend_from_slice(rem);
+ buffer.extend_from_slice(rem);
- result.into()
+ buffer.into()
}
/// Apply a bitwise operation `op` to one input and return the result as a Buffer.
@@ -1049,17 +1045,15 @@ impl MutableBuffer {
iterator.for_each(|item| self.push(item));
}
-}
-impl Buffer {
- /// Creates a [`Buffer`] from an [`Iterator`] with a trusted (upper) length.
+ /// Creates a [`MutableBuffer`] from an [`Iterator`] with a trusted (upper) length.
/// Prefer this to `collect` whenever possible, as it is faster ~60% faster.
/// # Example
/// ```
- /// # use arrow::buffer::Buffer;
+ /// # use arrow::buffer::MutableBuffer;
/// let v = vec![1u32];
/// let iter = v.iter().map(|x| x * 2);
- /// let buffer = unsafe { Buffer::from_trusted_len_iter(iter) };
+ /// let buffer = unsafe { MutableBuffer::from_trusted_len_iter(iter) };
/// assert_eq!(buffer.len(), 4) // u32 has 4 bytes
/// ```
/// # Safety
@@ -1090,10 +1084,10 @@ impl Buffer {
"Trusted iterator length was not accurately reported"
);
buffer.len = len;
- buffer.into()
+ buffer
}
- /// Creates a [`Buffer`] from an [`Iterator`] with a trusted (upper) length or errors
+ /// Creates a [`MutableBuffer`] from an [`Iterator`] with a trusted (upper) length or errors
/// if any of the items of the iterator is an error.
/// Prefer this to `collect` whenever possible, as it is faster ~60% faster.
/// # Safety
@@ -1124,7 +1118,48 @@ impl Buffer {
"Trusted iterator length was not accurately reported"
);
buffer.len = len;
- Ok(buffer.into())
+ Ok(buffer)
+ }
+}
+
+impl Buffer {
+ /// Creates a [`Buffer`] from an [`Iterator`] with a trusted (upper) length.
+ /// Prefer this to `collect` whenever possible, as it is ~60% faster.
+ /// # Example
+ /// ```
+ /// # use arrow::buffer::Buffer;
+ /// let v = vec![1u32];
+ /// let iter = v.iter().map(|x| x * 2);
+ /// let buffer = unsafe { Buffer::from_trusted_len_iter(iter) };
+ /// assert_eq!(buffer.len(), 4) // u32 has 4 bytes
+ /// ```
+ /// # Safety
+ /// This method assumes that the iterator's size is correct and is undefined behavior
+ /// to use it on an iterator that reports an incorrect length.
+ // This implementation is required for two reasons:
+ // 1. there is no trait `TrustedLen` in stable rust and therefore
+ // we can't specialize `extend` for `TrustedLen` like `Vec` does.
+ // 2. `from_trusted_len_iter` is faster.
+ pub unsafe fn from_trusted_len_iter<T: ArrowNativeType, I: Iterator<Item = T>>(
+ iterator: I,
+ ) -> Self {
+ MutableBuffer::from_trusted_len_iter(iterator).into()
+ }
+
+ /// Creates a [`Buffer`] from an [`Iterator`] with a trusted (upper) length or errors
+ /// if any of the items of the iterator is an error.
+ /// Prefer this to `collect` whenever possible, as it is faster ~60% faster.
+ /// # Safety
+ /// This method assumes that the iterator's size is correct and is undefined behavior
+ /// to use it on an iterator that reports an incorrect length.
+ pub unsafe fn try_from_trusted_len_iter<
+ E,
+ T: ArrowNativeType,
+ I: Iterator<Item = std::result::Result<T, E>>,
+ >(
+ iterator: I,
+ ) -> std::result::Result<Self, E> {
+ Ok(MutableBuffer::try_from_trusted_len_iter(iterator)?.into())
}
}