You are viewing a plain text version of this content. The canonical link for it is here.
Posted to github@arrow.apache.org by GitBox <gi...@apache.org> on 2022/03/31 12:41:08 UTC
[GitHub] [arrow-rs] HaoYang670 opened a new pull request #1512: Speed up substring
HaoYang670 opened a new pull request #1512:
URL: https://github.com/apache/arrow-rs/pull/1512
# Which issue does this PR close?
Closes #1511.
# Rationale for this change
Improve the performance and do some clean-up work.
# What changes are included in this PR?
1. calculate `new_offsets` first to estimate the memory needed for buffer
2. clean up the code: remove redundant comparisons.
# Benchmark
```
substring time: [19.828 ms 19.842 ms 19.858 ms]
change: [-45.409% -45.344% -45.279%] (p = 0.00 < 0.05)
Performance has improved.
Found 14 outliers among 100 measurements (14.00%)
6 (6.00%) high mild
8 (8.00%) high severe
```
2X speed-up
# Are there any 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: github-unsubscribe@arrow.apache.org
For queries about this service, please contact Infrastructure at:
users@infra.apache.org
[GitHub] [arrow-rs] HaoYang670 commented on a change in pull request #1512: Speed up the `substring` kernel
Posted by GitBox <gi...@apache.org>.
HaoYang670 commented on a change in pull request #1512:
URL: https://github.com/apache/arrow-rs/pull/1512#discussion_r839632463
##########
File path: arrow/src/compute/kernels/substring.rs
##########
@@ -24,56 +24,74 @@ use crate::{
error::{ArrowError, Result},
};
-#[allow(clippy::unnecessary_wraps)]
fn generic_substring<OffsetSize: StringOffsetSizeTrait>(
array: &GenericStringArray<OffsetSize>,
start: OffsetSize,
length: &Option<OffsetSize>,
) -> Result<ArrayRef> {
- // compute current offsets
- let offsets = array.data_ref().clone().buffers()[0].clone();
- let offsets: &[OffsetSize] = unsafe { offsets.typed_data::<OffsetSize>() };
-
- // compute null bitmap (copy)
+ let offsets = array.value_offsets();
let null_bit_buffer = array.data_ref().null_buffer().cloned();
-
- // compute values
- let values = &array.data_ref().buffers()[1];
+ let values = array.value_data();
let data = values.as_slice();
+ let zero = OffsetSize::zero();
- let mut new_values = MutableBuffer::new(0); // we have no way to estimate how much this will be.
- let mut new_offsets: Vec<OffsetSize> = Vec::with_capacity(array.len() + 1);
-
- let mut length_so_far = OffsetSize::zero();
- new_offsets.push(length_so_far);
- (0..array.len()).for_each(|i| {
- // the length of this entry
- let length_i: OffsetSize = offsets[i + 1] - offsets[i];
- // compute where we should start slicing this entry
- let start = offsets[i]
- + if start >= OffsetSize::zero() {
- start
- } else {
- length_i + start
- };
-
- let start = start.max(offsets[i]).min(offsets[i + 1]);
- // compute the length of the slice
- let length: OffsetSize = length
- .unwrap_or(length_i)
- // .max(0) is not needed as it is guaranteed
- .min(offsets[i + 1] - start); // so we do not go beyond this entry
-
- length_so_far += length;
+ // calculate the start offset for each substring
+ // if `start` >= 0
+ // then, count from the start of each string
+ // else, count from the end of each string
+ let new_starts: Vec<OffsetSize> = if start >= zero {
+ offsets
+ .windows(2)
+ .map(|pair| (pair[0] + start).min(pair[1]))
+ .collect()
+ } else {
+ offsets
+ .windows(2)
+ .map(|pair| (pair[1] + start).max(pair[0]))
+ .collect()
+ };
- new_offsets.push(length_so_far);
+ // count the length of each substring
+ // if `length` is given
+ // then, use it
+ // else, length is `string[new_start..].len()`
+ let new_length: Vec<OffsetSize> = if let Some(length) = length {
Review comment:
We don't need to `unwrap` the `length` in each loop. So move this outside the loop.
--
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
[GitHub] [arrow-rs] HaoYang670 commented on a change in pull request #1512: Speed up the `substring` kernel
Posted by GitBox <gi...@apache.org>.
HaoYang670 commented on a change in pull request #1512:
URL: https://github.com/apache/arrow-rs/pull/1512#discussion_r840355050
##########
File path: arrow/src/compute/kernels/substring.rs
##########
@@ -24,56 +24,61 @@ use crate::{
error::{ArrowError, Result},
};
-#[allow(clippy::unnecessary_wraps)]
fn generic_substring<OffsetSize: StringOffsetSizeTrait>(
array: &GenericStringArray<OffsetSize>,
start: OffsetSize,
length: &Option<OffsetSize>,
) -> Result<ArrayRef> {
- // compute current offsets
- let offsets = array.data_ref().clone().buffers()[0].clone();
- let offsets: &[OffsetSize] = unsafe { offsets.typed_data::<OffsetSize>() };
-
- // compute null bitmap (copy)
+ let offsets = array.value_offsets();
let null_bit_buffer = array.data_ref().null_buffer().cloned();
-
- // compute values
- let values = &array.data_ref().buffers()[1];
+ let values = array.value_data();
let data = values.as_slice();
+ let zero = OffsetSize::zero();
- let mut new_values = MutableBuffer::new(0); // we have no way to estimate how much this will be.
- let mut new_offsets: Vec<OffsetSize> = Vec::with_capacity(array.len() + 1);
-
- let mut length_so_far = OffsetSize::zero();
- new_offsets.push(length_so_far);
- (0..array.len()).for_each(|i| {
- // the length of this entry
- let length_i: OffsetSize = offsets[i + 1] - offsets[i];
- // compute where we should start slicing this entry
- let start = offsets[i]
- + if start >= OffsetSize::zero() {
- start
- } else {
- length_i + start
- };
+ let cal_new_start: Box<dyn Fn(OffsetSize, OffsetSize) -> OffsetSize> = if start
+ >= zero
+ {
+ // count from the start of string
+ Box::new(|old_start: OffsetSize, end: OffsetSize| (old_start + start).min(end))
+ } else {
+ // count from the end of string
+ Box::new(|old_start: OffsetSize, end: OffsetSize| (end + start).max(old_start))
+ };
- let start = start.max(offsets[i]).min(offsets[i + 1]);
- // compute the length of the slice
- let length: OffsetSize = length
- .unwrap_or(length_i)
- // .max(0) is not needed as it is guaranteed
- .min(offsets[i + 1] - start); // so we do not go beyond this entry
+ let cal_new_length: Box<dyn Fn(OffsetSize, OffsetSize) -> OffsetSize> =
+ if let Some(length) = length {
+ Box::new(|start: OffsetSize, end: OffsetSize| (*length).min(end - start))
+ } else {
+ Box::new(|start: OffsetSize, end: OffsetSize| end - start)
+ };
- length_so_far += length;
+ // start and end offsets for each substring
+ let mut new_starts_ends: Vec<(OffsetSize, OffsetSize)> =
+ Vec::with_capacity(array.len());
+ let mut new_offsets: Vec<OffsetSize> = Vec::with_capacity(array.len() + 1);
+ let mut len_so_far = zero;
+ new_offsets.push(zero);
- new_offsets.push(length_so_far);
+ offsets.windows(2).for_each(|pair| {
Review comment:
Purely functional style is not appropriate because `new_offsets` and `new_starts_ends` have different number of elements. After trying some different ways, I find that `mut vec` + `for each` is more readable and efficient.
--
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
[GitHub] [arrow-rs] HaoYang670 commented on a change in pull request #1512: Speed up the `substring` kernel
Posted by GitBox <gi...@apache.org>.
HaoYang670 commented on a change in pull request #1512:
URL: https://github.com/apache/arrow-rs/pull/1512#discussion_r840187012
##########
File path: arrow/src/compute/kernels/substring.rs
##########
@@ -24,56 +24,74 @@ use crate::{
error::{ArrowError, Result},
};
-#[allow(clippy::unnecessary_wraps)]
fn generic_substring<OffsetSize: StringOffsetSizeTrait>(
array: &GenericStringArray<OffsetSize>,
start: OffsetSize,
length: &Option<OffsetSize>,
) -> Result<ArrayRef> {
- // compute current offsets
- let offsets = array.data_ref().clone().buffers()[0].clone();
- let offsets: &[OffsetSize] = unsafe { offsets.typed_data::<OffsetSize>() };
-
- // compute null bitmap (copy)
+ let offsets = array.value_offsets();
let null_bit_buffer = array.data_ref().null_buffer().cloned();
-
- // compute values
- let values = &array.data_ref().buffers()[1];
+ let values = array.value_data();
let data = values.as_slice();
+ let zero = OffsetSize::zero();
- let mut new_values = MutableBuffer::new(0); // we have no way to estimate how much this will be.
- let mut new_offsets: Vec<OffsetSize> = Vec::with_capacity(array.len() + 1);
-
- let mut length_so_far = OffsetSize::zero();
- new_offsets.push(length_so_far);
- (0..array.len()).for_each(|i| {
- // the length of this entry
- let length_i: OffsetSize = offsets[i + 1] - offsets[i];
- // compute where we should start slicing this entry
- let start = offsets[i]
- + if start >= OffsetSize::zero() {
- start
- } else {
- length_i + start
- };
-
- let start = start.max(offsets[i]).min(offsets[i + 1]);
- // compute the length of the slice
- let length: OffsetSize = length
- .unwrap_or(length_i)
- // .max(0) is not needed as it is guaranteed
- .min(offsets[i + 1] - start); // so we do not go beyond this entry
-
- length_so_far += length;
+ // calculate the start offset for each substring
+ // if `start` >= 0
+ // then, count from the start of each string
+ // else, count from the end of each string
+ let new_starts: Vec<OffsetSize> = if start >= zero {
+ offsets
+ .windows(2)
+ .map(|pair| (pair[0] + start).min(pair[1]))
+ .collect()
+ } else {
+ offsets
+ .windows(2)
+ .map(|pair| (pair[1] + start).max(pair[0]))
+ .collect()
Review comment:
> Yes, that is not possible in Rust (I think only by Boxing or manually inlining / macros).
>
> Calculating the length in two places with something like `let length = *end - *start` within both the `new_offsets` `new_values` doesn´t seem too bad in terms of duplication?
One way is to let the closure not capture the environment, and the compiler will downcast closure to function. This works for calculating `new_starts`, but doesn't work for `new_length` where we must capture `Some(length) = length`
--
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
[GitHub] [arrow-rs] Dandandan commented on a change in pull request #1512: Speed up the `substring` kernel
Posted by GitBox <gi...@apache.org>.
Dandandan commented on a change in pull request #1512:
URL: https://github.com/apache/arrow-rs/pull/1512#discussion_r839784293
##########
File path: arrow/src/compute/kernels/substring.rs
##########
@@ -24,56 +24,74 @@ use crate::{
error::{ArrowError, Result},
};
-#[allow(clippy::unnecessary_wraps)]
fn generic_substring<OffsetSize: StringOffsetSizeTrait>(
array: &GenericStringArray<OffsetSize>,
start: OffsetSize,
length: &Option<OffsetSize>,
) -> Result<ArrayRef> {
- // compute current offsets
- let offsets = array.data_ref().clone().buffers()[0].clone();
- let offsets: &[OffsetSize] = unsafe { offsets.typed_data::<OffsetSize>() };
-
- // compute null bitmap (copy)
+ let offsets = array.value_offsets();
let null_bit_buffer = array.data_ref().null_buffer().cloned();
-
- // compute values
- let values = &array.data_ref().buffers()[1];
+ let values = array.value_data();
let data = values.as_slice();
+ let zero = OffsetSize::zero();
- let mut new_values = MutableBuffer::new(0); // we have no way to estimate how much this will be.
- let mut new_offsets: Vec<OffsetSize> = Vec::with_capacity(array.len() + 1);
-
- let mut length_so_far = OffsetSize::zero();
- new_offsets.push(length_so_far);
- (0..array.len()).for_each(|i| {
- // the length of this entry
- let length_i: OffsetSize = offsets[i + 1] - offsets[i];
- // compute where we should start slicing this entry
- let start = offsets[i]
- + if start >= OffsetSize::zero() {
- start
- } else {
- length_i + start
- };
-
- let start = start.max(offsets[i]).min(offsets[i + 1]);
- // compute the length of the slice
- let length: OffsetSize = length
- .unwrap_or(length_i)
- // .max(0) is not needed as it is guaranteed
- .min(offsets[i + 1] - start); // so we do not go beyond this entry
-
- length_so_far += length;
+ // calculate the start offset for each substring
+ // if `start` >= 0
+ // then, count from the start of each string
+ // else, count from the end of each string
+ let new_starts: Vec<OffsetSize> = if start >= zero {
+ offsets
+ .windows(2)
+ .map(|pair| (pair[0] + start).min(pair[1]))
+ .collect()
+ } else {
+ offsets
+ .windows(2)
+ .map(|pair| (pair[1] + start).max(pair[0]))
+ .collect()
+ };
- new_offsets.push(length_so_far);
+ // count the length of each substring
+ // if `length` is given
+ // then, use it
+ // else, length is `string[new_start..].len()`
+ let new_length: Vec<OffsetSize> = if let Some(length) = length {
+ offsets[1..]
+ .iter()
+ .zip(new_starts.iter())
+ .map(|(end, start)| *(length.min(&(*end - *start))))
+ .collect()
+ } else {
+ offsets[1..]
+ .iter()
+ .zip(new_starts.iter())
+ .map(|(end, start)| *end - *start)
+ .collect()
+ };
- // we need usize for ranges
- let start = start.to_usize().unwrap();
- let length = length.to_usize().unwrap();
+ let new_offsets: Vec<OffsetSize> = [zero]
+ .iter()
+ .copied()
+ .chain(new_length.iter().scan(zero, |len_so_far, &len| {
+ *len_so_far += len;
+ Some(*len_so_far)
+ }))
+ .collect();
- new_values.extend_from_slice(&data[start..start + length]);
- });
+ // concatenate substrings into a buffer
+ let new_values = {
+ let mut new_values =
+ MutableBuffer::new(new_offsets.last().unwrap().to_usize().unwrap());
+ new_starts
+ .iter()
+ .zip(new_length.iter())
+ .map(|(start, length)| {
+ (start.to_usize().unwrap(), length.to_usize().unwrap())
+ })
+ .map(|(start, length)| &data[start..start + length])
Review comment:
```suggestion
.map(|(start, length)| {
let start = start.to_usize().unwrap();
let length = length.to_usize().unwrap();
&data[start..start + length]
})
```
--
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
[GitHub] [arrow-rs] codecov-commenter edited a comment on pull request #1512: Speed up the `substring` kernel
Posted by GitBox <gi...@apache.org>.
codecov-commenter edited a comment on pull request #1512:
URL: https://github.com/apache/arrow-rs/pull/1512#issuecomment-1085408190
# [Codecov](https://codecov.io/gh/apache/arrow-rs/pull/1512?src=pr&el=h1&utm_medium=referral&utm_source=github&utm_content=comment&utm_campaign=pr+comments&utm_term=The+Apache+Software+Foundation) Report
> Merging [#1512](https://codecov.io/gh/apache/arrow-rs/pull/1512?src=pr&el=desc&utm_medium=referral&utm_source=github&utm_content=comment&utm_campaign=pr+comments&utm_term=The+Apache+Software+Foundation) (f66990a) into [master](https://codecov.io/gh/apache/arrow-rs/commit/15c87aea3394c1fb6f0edfee7f7e1562ca71efb3?el=desc&utm_medium=referral&utm_source=github&utm_content=comment&utm_campaign=pr+comments&utm_term=The+Apache+Software+Foundation) (15c87ae) will **increase** coverage by `0.02%`.
> The diff coverage is `100.00%`.
```diff
@@ Coverage Diff @@
## master #1512 +/- ##
==========================================
+ Coverage 82.72% 82.75% +0.02%
==========================================
Files 189 190 +1
Lines 54561 54707 +146
==========================================
+ Hits 45137 45274 +137
- Misses 9424 9433 +9
```
| [Impacted Files](https://codecov.io/gh/apache/arrow-rs/pull/1512?src=pr&el=tree&utm_medium=referral&utm_source=github&utm_content=comment&utm_campaign=pr+comments&utm_term=The+Apache+Software+Foundation) | Coverage Δ | |
|---|---|---|
| [arrow/src/compute/kernels/substring.rs](https://codecov.io/gh/apache/arrow-rs/pull/1512/diff?src=pr&el=tree&utm_medium=referral&utm_source=github&utm_content=comment&utm_campaign=pr+comments&utm_term=The+Apache+Software+Foundation#diff-YXJyb3cvc3JjL2NvbXB1dGUva2VybmVscy9zdWJzdHJpbmcucnM=) | `98.31% <100.00%> (+0.07%)` | :arrow_up: |
| [arrow/src/array/equal/utils.rs](https://codecov.io/gh/apache/arrow-rs/pull/1512/diff?src=pr&el=tree&utm_medium=referral&utm_source=github&utm_content=comment&utm_campaign=pr+comments&utm_term=The+Apache+Software+Foundation#diff-YXJyb3cvc3JjL2FycmF5L2VxdWFsL3V0aWxzLnJz) | `74.45% <0.00%> (-3.24%)` | :arrow_down: |
| [parquet/src/encodings/encoding.rs](https://codecov.io/gh/apache/arrow-rs/pull/1512/diff?src=pr&el=tree&utm_medium=referral&utm_source=github&utm_content=comment&utm_campaign=pr+comments&utm_term=The+Apache+Software+Foundation#diff-cGFycXVldC9zcmMvZW5jb2RpbmdzL2VuY29kaW5nLnJz) | `93.37% <0.00%> (-0.19%)` | :arrow_down: |
| [arrow/src/array/builder.rs](https://codecov.io/gh/apache/arrow-rs/pull/1512/diff?src=pr&el=tree&utm_medium=referral&utm_source=github&utm_content=comment&utm_campaign=pr+comments&utm_term=The+Apache+Software+Foundation#diff-YXJyb3cvc3JjL2FycmF5L2J1aWxkZXIucnM=) | `86.68% <0.00%> (-0.05%)` | :arrow_down: |
| [arrow/src/array/equal/union.rs](https://codecov.io/gh/apache/arrow-rs/pull/1512/diff?src=pr&el=tree&utm_medium=referral&utm_source=github&utm_content=comment&utm_campaign=pr+comments&utm_term=The+Apache+Software+Foundation#diff-YXJyb3cvc3JjL2FycmF5L2VxdWFsL3VuaW9uLnJz) | `100.00% <0.00%> (ø)` | |
| [arrow/src/array/transform/mod.rs](https://codecov.io/gh/apache/arrow-rs/pull/1512/diff?src=pr&el=tree&utm_medium=referral&utm_source=github&utm_content=comment&utm_campaign=pr+comments&utm_term=The+Apache+Software+Foundation#diff-YXJyb3cvc3JjL2FycmF5L3RyYW5zZm9ybS9tb2QucnM=) | `86.46% <0.00%> (+0.11%)` | :arrow_up: |
| [parquet\_derive/src/parquet\_field.rs](https://codecov.io/gh/apache/arrow-rs/pull/1512/diff?src=pr&el=tree&utm_medium=referral&utm_source=github&utm_content=comment&utm_campaign=pr+comments&utm_term=The+Apache+Software+Foundation#diff-cGFycXVldF9kZXJpdmUvc3JjL3BhcnF1ZXRfZmllbGQucnM=) | `66.21% <0.00%> (+0.22%)` | :arrow_up: |
| [arrow/src/array/equal/mod.rs](https://codecov.io/gh/apache/arrow-rs/pull/1512/diff?src=pr&el=tree&utm_medium=referral&utm_source=github&utm_content=comment&utm_campaign=pr+comments&utm_term=The+Apache+Software+Foundation#diff-YXJyb3cvc3JjL2FycmF5L2VxdWFsL21vZC5ycw==) | `93.98% <0.00%> (+0.65%)` | :arrow_up: |
------
[Continue to review full report at Codecov](https://codecov.io/gh/apache/arrow-rs/pull/1512?src=pr&el=continue&utm_medium=referral&utm_source=github&utm_content=comment&utm_campaign=pr+comments&utm_term=The+Apache+Software+Foundation).
> **Legend** - [Click here to learn more](https://docs.codecov.io/docs/codecov-delta?utm_medium=referral&utm_source=github&utm_content=comment&utm_campaign=pr+comments&utm_term=The+Apache+Software+Foundation)
> `Δ = absolute <relative> (impact)`, `ø = not affected`, `? = missing data`
> Powered by [Codecov](https://codecov.io/gh/apache/arrow-rs/pull/1512?src=pr&el=footer&utm_medium=referral&utm_source=github&utm_content=comment&utm_campaign=pr+comments&utm_term=The+Apache+Software+Foundation). Last update [15c87ae...f66990a](https://codecov.io/gh/apache/arrow-rs/pull/1512?src=pr&el=lastupdated&utm_medium=referral&utm_source=github&utm_content=comment&utm_campaign=pr+comments&utm_term=The+Apache+Software+Foundation). Read the [comment docs](https://docs.codecov.io/docs/pull-request-comments?utm_medium=referral&utm_source=github&utm_content=comment&utm_campaign=pr+comments&utm_term=The+Apache+Software+Foundation).
--
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
[GitHub] [arrow-rs] Dandandan commented on a change in pull request #1512: Speed up the `substring` kernel
Posted by GitBox <gi...@apache.org>.
Dandandan commented on a change in pull request #1512:
URL: https://github.com/apache/arrow-rs/pull/1512#discussion_r839589250
##########
File path: arrow/src/compute/kernels/substring.rs
##########
@@ -24,56 +24,74 @@ use crate::{
error::{ArrowError, Result},
};
-#[allow(clippy::unnecessary_wraps)]
fn generic_substring<OffsetSize: StringOffsetSizeTrait>(
array: &GenericStringArray<OffsetSize>,
start: OffsetSize,
length: &Option<OffsetSize>,
) -> Result<ArrayRef> {
- // compute current offsets
- let offsets = array.data_ref().clone().buffers()[0].clone();
- let offsets: &[OffsetSize] = unsafe { offsets.typed_data::<OffsetSize>() };
-
- // compute null bitmap (copy)
+ let offsets = array.value_offsets();
let null_bit_buffer = array.data_ref().null_buffer().cloned();
-
- // compute values
- let values = &array.data_ref().buffers()[1];
+ let values = array.value_data();
let data = values.as_slice();
+ let zero = OffsetSize::zero();
- let mut new_values = MutableBuffer::new(0); // we have no way to estimate how much this will be.
- let mut new_offsets: Vec<OffsetSize> = Vec::with_capacity(array.len() + 1);
-
- let mut length_so_far = OffsetSize::zero();
- new_offsets.push(length_so_far);
- (0..array.len()).for_each(|i| {
- // the length of this entry
- let length_i: OffsetSize = offsets[i + 1] - offsets[i];
- // compute where we should start slicing this entry
- let start = offsets[i]
- + if start >= OffsetSize::zero() {
- start
- } else {
- length_i + start
- };
-
- let start = start.max(offsets[i]).min(offsets[i + 1]);
- // compute the length of the slice
- let length: OffsetSize = length
- .unwrap_or(length_i)
- // .max(0) is not needed as it is guaranteed
- .min(offsets[i + 1] - start); // so we do not go beyond this entry
-
- length_so_far += length;
+ // calculate the start offset for each substring
+ // if `start` >= 0
+ // then, count from the start of each string
+ // else, count from the end of each string
+ let new_starts: Vec<OffsetSize> = if start >= zero {
+ offsets
+ .windows(2)
+ .map(|pair| (pair[0] + start).min(pair[1]))
+ .collect()
+ } else {
+ offsets
+ .windows(2)
+ .map(|pair| (pair[1] + start).max(pair[0]))
+ .collect()
Review comment:
Might be better to do `new_starts`/`new_length` in one iteration over `offsets` and use `unzip` to materialize into two Vecs?
--
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
[GitHub] [arrow-rs] codecov-commenter commented on pull request #1512: Speed up the `substring` kernel
Posted by GitBox <gi...@apache.org>.
codecov-commenter commented on pull request #1512:
URL: https://github.com/apache/arrow-rs/pull/1512#issuecomment-1085408190
# [Codecov](https://codecov.io/gh/apache/arrow-rs/pull/1512?src=pr&el=h1&utm_medium=referral&utm_source=github&utm_content=comment&utm_campaign=pr+comments&utm_term=The+Apache+Software+Foundation) Report
> Merging [#1512](https://codecov.io/gh/apache/arrow-rs/pull/1512?src=pr&el=desc&utm_medium=referral&utm_source=github&utm_content=comment&utm_campaign=pr+comments&utm_term=The+Apache+Software+Foundation) (afb56c8) into [master](https://codecov.io/gh/apache/arrow-rs/commit/15c87aea3394c1fb6f0edfee7f7e1562ca71efb3?el=desc&utm_medium=referral&utm_source=github&utm_content=comment&utm_campaign=pr+comments&utm_term=The+Apache+Software+Foundation) (15c87ae) will **increase** coverage by `0.03%`.
> The diff coverage is `100.00%`.
```diff
@@ Coverage Diff @@
## master #1512 +/- ##
==========================================
+ Coverage 82.72% 82.76% +0.03%
==========================================
Files 189 190 +1
Lines 54561 54708 +147
==========================================
+ Hits 45137 45277 +140
- Misses 9424 9431 +7
```
| [Impacted Files](https://codecov.io/gh/apache/arrow-rs/pull/1512?src=pr&el=tree&utm_medium=referral&utm_source=github&utm_content=comment&utm_campaign=pr+comments&utm_term=The+Apache+Software+Foundation) | Coverage Δ | |
|---|---|---|
| [arrow/src/compute/kernels/substring.rs](https://codecov.io/gh/apache/arrow-rs/pull/1512/diff?src=pr&el=tree&utm_medium=referral&utm_source=github&utm_content=comment&utm_campaign=pr+comments&utm_term=The+Apache+Software+Foundation#diff-YXJyb3cvc3JjL2NvbXB1dGUva2VybmVscy9zdWJzdHJpbmcucnM=) | `98.33% <100.00%> (+0.08%)` | :arrow_up: |
| [arrow/src/array/equal/utils.rs](https://codecov.io/gh/apache/arrow-rs/pull/1512/diff?src=pr&el=tree&utm_medium=referral&utm_source=github&utm_content=comment&utm_campaign=pr+comments&utm_term=The+Apache+Software+Foundation#diff-YXJyb3cvc3JjL2FycmF5L2VxdWFsL3V0aWxzLnJz) | `74.45% <0.00%> (-3.24%)` | :arrow_down: |
| [arrow/src/array/builder.rs](https://codecov.io/gh/apache/arrow-rs/pull/1512/diff?src=pr&el=tree&utm_medium=referral&utm_source=github&utm_content=comment&utm_campaign=pr+comments&utm_term=The+Apache+Software+Foundation#diff-YXJyb3cvc3JjL2FycmF5L2J1aWxkZXIucnM=) | `86.68% <0.00%> (-0.05%)` | :arrow_down: |
| [parquet\_derive/src/parquet\_field.rs](https://codecov.io/gh/apache/arrow-rs/pull/1512/diff?src=pr&el=tree&utm_medium=referral&utm_source=github&utm_content=comment&utm_campaign=pr+comments&utm_term=The+Apache+Software+Foundation#diff-cGFycXVldF9kZXJpdmUvc3JjL3BhcnF1ZXRfZmllbGQucnM=) | `65.98% <0.00%> (ø)` | |
| [arrow/src/array/equal/union.rs](https://codecov.io/gh/apache/arrow-rs/pull/1512/diff?src=pr&el=tree&utm_medium=referral&utm_source=github&utm_content=comment&utm_campaign=pr+comments&utm_term=The+Apache+Software+Foundation#diff-YXJyb3cvc3JjL2FycmF5L2VxdWFsL3VuaW9uLnJz) | `100.00% <0.00%> (ø)` | |
| [arrow/src/array/transform/mod.rs](https://codecov.io/gh/apache/arrow-rs/pull/1512/diff?src=pr&el=tree&utm_medium=referral&utm_source=github&utm_content=comment&utm_campaign=pr+comments&utm_term=The+Apache+Software+Foundation#diff-YXJyb3cvc3JjL2FycmF5L3RyYW5zZm9ybS9tb2QucnM=) | `86.57% <0.00%> (+0.22%)` | :arrow_up: |
| [arrow/src/datatypes/datatype.rs](https://codecov.io/gh/apache/arrow-rs/pull/1512/diff?src=pr&el=tree&utm_medium=referral&utm_source=github&utm_content=comment&utm_campaign=pr+comments&utm_term=The+Apache+Software+Foundation#diff-YXJyb3cvc3JjL2RhdGF0eXBlcy9kYXRhdHlwZS5ycw==) | `66.80% <0.00%> (+0.39%)` | :arrow_up: |
| [arrow/src/array/equal/mod.rs](https://codecov.io/gh/apache/arrow-rs/pull/1512/diff?src=pr&el=tree&utm_medium=referral&utm_source=github&utm_content=comment&utm_campaign=pr+comments&utm_term=The+Apache+Software+Foundation#diff-YXJyb3cvc3JjL2FycmF5L2VxdWFsL21vZC5ycw==) | `93.98% <0.00%> (+0.65%)` | :arrow_up: |
------
[Continue to review full report at Codecov](https://codecov.io/gh/apache/arrow-rs/pull/1512?src=pr&el=continue&utm_medium=referral&utm_source=github&utm_content=comment&utm_campaign=pr+comments&utm_term=The+Apache+Software+Foundation).
> **Legend** - [Click here to learn more](https://docs.codecov.io/docs/codecov-delta?utm_medium=referral&utm_source=github&utm_content=comment&utm_campaign=pr+comments&utm_term=The+Apache+Software+Foundation)
> `Δ = absolute <relative> (impact)`, `ø = not affected`, `? = missing data`
> Powered by [Codecov](https://codecov.io/gh/apache/arrow-rs/pull/1512?src=pr&el=footer&utm_medium=referral&utm_source=github&utm_content=comment&utm_campaign=pr+comments&utm_term=The+Apache+Software+Foundation). Last update [15c87ae...afb56c8](https://codecov.io/gh/apache/arrow-rs/pull/1512?src=pr&el=lastupdated&utm_medium=referral&utm_source=github&utm_content=comment&utm_campaign=pr+comments&utm_term=The+Apache+Software+Foundation). Read the [comment docs](https://docs.codecov.io/docs/pull-request-comments?utm_medium=referral&utm_source=github&utm_content=comment&utm_campaign=pr+comments&utm_term=The+Apache+Software+Foundation).
--
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
[GitHub] [arrow-rs] HaoYang670 commented on a change in pull request #1512: Speed up the `substring` kernel
Posted by GitBox <gi...@apache.org>.
HaoYang670 commented on a change in pull request #1512:
URL: https://github.com/apache/arrow-rs/pull/1512#discussion_r840344253
##########
File path: arrow/src/compute/kernels/substring.rs
##########
@@ -24,56 +24,61 @@ use crate::{
error::{ArrowError, Result},
};
-#[allow(clippy::unnecessary_wraps)]
fn generic_substring<OffsetSize: StringOffsetSizeTrait>(
array: &GenericStringArray<OffsetSize>,
start: OffsetSize,
length: &Option<OffsetSize>,
) -> Result<ArrayRef> {
- // compute current offsets
- let offsets = array.data_ref().clone().buffers()[0].clone();
- let offsets: &[OffsetSize] = unsafe { offsets.typed_data::<OffsetSize>() };
-
- // compute null bitmap (copy)
+ let offsets = array.value_offsets();
let null_bit_buffer = array.data_ref().null_buffer().cloned();
-
- // compute values
- let values = &array.data_ref().buffers()[1];
+ let values = array.value_data();
let data = values.as_slice();
+ let zero = OffsetSize::zero();
- let mut new_values = MutableBuffer::new(0); // we have no way to estimate how much this will be.
- let mut new_offsets: Vec<OffsetSize> = Vec::with_capacity(array.len() + 1);
-
- let mut length_so_far = OffsetSize::zero();
- new_offsets.push(length_so_far);
- (0..array.len()).for_each(|i| {
- // the length of this entry
- let length_i: OffsetSize = offsets[i + 1] - offsets[i];
- // compute where we should start slicing this entry
- let start = offsets[i]
- + if start >= OffsetSize::zero() {
- start
- } else {
- length_i + start
- };
+ let cal_new_start: Box<dyn Fn(OffsetSize, OffsetSize) -> OffsetSize> = if start
+ >= zero
+ {
+ // count from the start of string
+ Box::new(|old_start: OffsetSize, end: OffsetSize| (old_start + start).min(end))
+ } else {
+ // count from the end of string
+ Box::new(|old_start: OffsetSize, end: OffsetSize| (end + start).max(old_start))
+ };
- let start = start.max(offsets[i]).min(offsets[i + 1]);
- // compute the length of the slice
- let length: OffsetSize = length
- .unwrap_or(length_i)
- // .max(0) is not needed as it is guaranteed
- .min(offsets[i + 1] - start); // so we do not go beyond this entry
+ let cal_new_length: Box<dyn Fn(OffsetSize, OffsetSize) -> OffsetSize> =
+ if let Some(length) = length {
+ Box::new(|start: OffsetSize, end: OffsetSize| (*length).min(end - start))
+ } else {
+ Box::new(|start: OffsetSize, end: OffsetSize| end - start)
+ };
- length_so_far += length;
+ // start and end offsets for each substring
+ let mut new_starts_ends: Vec<(OffsetSize, OffsetSize)> =
+ Vec::with_capacity(array.len());
Review comment:
If we don't materialize `new_starts_ends` here, we have to calculate them twice when calculating `new_values`
--
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
[GitHub] [arrow-rs] HaoYang670 commented on a change in pull request #1512: Speed up the `substring` kernel
Posted by GitBox <gi...@apache.org>.
HaoYang670 commented on a change in pull request #1512:
URL: https://github.com/apache/arrow-rs/pull/1512#discussion_r840187012
##########
File path: arrow/src/compute/kernels/substring.rs
##########
@@ -24,56 +24,74 @@ use crate::{
error::{ArrowError, Result},
};
-#[allow(clippy::unnecessary_wraps)]
fn generic_substring<OffsetSize: StringOffsetSizeTrait>(
array: &GenericStringArray<OffsetSize>,
start: OffsetSize,
length: &Option<OffsetSize>,
) -> Result<ArrayRef> {
- // compute current offsets
- let offsets = array.data_ref().clone().buffers()[0].clone();
- let offsets: &[OffsetSize] = unsafe { offsets.typed_data::<OffsetSize>() };
-
- // compute null bitmap (copy)
+ let offsets = array.value_offsets();
let null_bit_buffer = array.data_ref().null_buffer().cloned();
-
- // compute values
- let values = &array.data_ref().buffers()[1];
+ let values = array.value_data();
let data = values.as_slice();
+ let zero = OffsetSize::zero();
- let mut new_values = MutableBuffer::new(0); // we have no way to estimate how much this will be.
- let mut new_offsets: Vec<OffsetSize> = Vec::with_capacity(array.len() + 1);
-
- let mut length_so_far = OffsetSize::zero();
- new_offsets.push(length_so_far);
- (0..array.len()).for_each(|i| {
- // the length of this entry
- let length_i: OffsetSize = offsets[i + 1] - offsets[i];
- // compute where we should start slicing this entry
- let start = offsets[i]
- + if start >= OffsetSize::zero() {
- start
- } else {
- length_i + start
- };
-
- let start = start.max(offsets[i]).min(offsets[i + 1]);
- // compute the length of the slice
- let length: OffsetSize = length
- .unwrap_or(length_i)
- // .max(0) is not needed as it is guaranteed
- .min(offsets[i + 1] - start); // so we do not go beyond this entry
-
- length_so_far += length;
+ // calculate the start offset for each substring
+ // if `start` >= 0
+ // then, count from the start of each string
+ // else, count from the end of each string
+ let new_starts: Vec<OffsetSize> = if start >= zero {
+ offsets
+ .windows(2)
+ .map(|pair| (pair[0] + start).min(pair[1]))
+ .collect()
+ } else {
+ offsets
+ .windows(2)
+ .map(|pair| (pair[1] + start).max(pair[0]))
+ .collect()
Review comment:
> Yes, that is not possible in Rust (I think only by Boxing or manually inlining / macros).
>
> Calculating the length in two places with something like `let length = *end - *start` within both the `new_offsets` `new_values` doesn´t seem too bad in terms of duplication?
One way is to allow the closure not to capture the environment by adding more parameters, and the compiler will downcast closure to function. This works for calculating `new_starts`, but doesn't work for `new_length` where we must capture `Some(length) = length`
--
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
[GitHub] [arrow-rs] HaoYang670 commented on a change in pull request #1512: Speed up the `substring` kernel
Posted by GitBox <gi...@apache.org>.
HaoYang670 commented on a change in pull request #1512:
URL: https://github.com/apache/arrow-rs/pull/1512#discussion_r840126475
##########
File path: arrow/src/compute/kernels/substring.rs
##########
@@ -24,56 +24,74 @@ use crate::{
error::{ArrowError, Result},
};
-#[allow(clippy::unnecessary_wraps)]
fn generic_substring<OffsetSize: StringOffsetSizeTrait>(
array: &GenericStringArray<OffsetSize>,
start: OffsetSize,
length: &Option<OffsetSize>,
) -> Result<ArrayRef> {
- // compute current offsets
- let offsets = array.data_ref().clone().buffers()[0].clone();
- let offsets: &[OffsetSize] = unsafe { offsets.typed_data::<OffsetSize>() };
-
- // compute null bitmap (copy)
+ let offsets = array.value_offsets();
let null_bit_buffer = array.data_ref().null_buffer().cloned();
-
- // compute values
- let values = &array.data_ref().buffers()[1];
+ let values = array.value_data();
let data = values.as_slice();
+ let zero = OffsetSize::zero();
- let mut new_values = MutableBuffer::new(0); // we have no way to estimate how much this will be.
- let mut new_offsets: Vec<OffsetSize> = Vec::with_capacity(array.len() + 1);
-
- let mut length_so_far = OffsetSize::zero();
- new_offsets.push(length_so_far);
- (0..array.len()).for_each(|i| {
- // the length of this entry
- let length_i: OffsetSize = offsets[i + 1] - offsets[i];
- // compute where we should start slicing this entry
- let start = offsets[i]
- + if start >= OffsetSize::zero() {
- start
- } else {
- length_i + start
- };
-
- let start = start.max(offsets[i]).min(offsets[i + 1]);
- // compute the length of the slice
- let length: OffsetSize = length
- .unwrap_or(length_i)
- // .max(0) is not needed as it is guaranteed
- .min(offsets[i + 1] - start); // so we do not go beyond this entry
-
- length_so_far += length;
+ // calculate the start offset for each substring
+ // if `start` >= 0
+ // then, count from the start of each string
+ // else, count from the end of each string
+ let new_starts: Vec<OffsetSize> = if start >= zero {
+ offsets
+ .windows(2)
+ .map(|pair| (pair[0] + start).min(pair[1]))
+ .collect()
+ } else {
+ offsets
+ .windows(2)
+ .map(|pair| (pair[1] + start).max(pair[0]))
+ .collect()
+ };
- new_offsets.push(length_so_far);
+ // count the length of each substring
+ // if `length` is given
+ // then, use it
+ // else, length is `string[new_start..].len()`
+ let new_length: Vec<OffsetSize> = if let Some(length) = length {
+ offsets[1..]
+ .iter()
+ .zip(new_starts.iter())
+ .map(|(end, start)| *(length.min(&(*end - *start))))
+ .collect()
+ } else {
+ offsets[1..]
+ .iter()
+ .zip(new_starts.iter())
+ .map(|(end, start)| *end - *start)
+ .collect()
+ };
- // we need usize for ranges
- let start = start.to_usize().unwrap();
- let length = length.to_usize().unwrap();
+ let new_offsets: Vec<OffsetSize> = [zero]
+ .iter()
+ .copied()
+ .chain(new_length.iter().scan(zero, |len_so_far, &len| {
+ *len_so_far += len;
+ Some(*len_so_far)
+ }))
+ .collect();
- new_values.extend_from_slice(&data[start..start + length]);
- });
+ // concatenate substrings into a buffer
+ let new_values = {
+ let mut new_values =
+ MutableBuffer::new(new_offsets.last().unwrap().to_usize().unwrap());
+ new_starts
+ .iter()
+ .zip(new_length.iter())
+ .map(|(start, length)| {
+ (start.to_usize().unwrap(), length.to_usize().unwrap())
+ })
+ .map(|(start, length)| &data[start..start + length])
Review comment:
Done!
--
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
[GitHub] [arrow-rs] Dandandan commented on a change in pull request #1512: Speed up the `substring` kernel
Posted by GitBox <gi...@apache.org>.
Dandandan commented on a change in pull request #1512:
URL: https://github.com/apache/arrow-rs/pull/1512#discussion_r839592294
##########
File path: arrow/src/compute/kernels/substring.rs
##########
@@ -24,56 +24,74 @@ use crate::{
error::{ArrowError, Result},
};
-#[allow(clippy::unnecessary_wraps)]
fn generic_substring<OffsetSize: StringOffsetSizeTrait>(
array: &GenericStringArray<OffsetSize>,
start: OffsetSize,
length: &Option<OffsetSize>,
) -> Result<ArrayRef> {
- // compute current offsets
- let offsets = array.data_ref().clone().buffers()[0].clone();
- let offsets: &[OffsetSize] = unsafe { offsets.typed_data::<OffsetSize>() };
-
- // compute null bitmap (copy)
+ let offsets = array.value_offsets();
let null_bit_buffer = array.data_ref().null_buffer().cloned();
-
- // compute values
- let values = &array.data_ref().buffers()[1];
+ let values = array.value_data();
let data = values.as_slice();
+ let zero = OffsetSize::zero();
- let mut new_values = MutableBuffer::new(0); // we have no way to estimate how much this will be.
- let mut new_offsets: Vec<OffsetSize> = Vec::with_capacity(array.len() + 1);
-
- let mut length_so_far = OffsetSize::zero();
- new_offsets.push(length_so_far);
- (0..array.len()).for_each(|i| {
- // the length of this entry
- let length_i: OffsetSize = offsets[i + 1] - offsets[i];
- // compute where we should start slicing this entry
- let start = offsets[i]
- + if start >= OffsetSize::zero() {
- start
- } else {
- length_i + start
- };
-
- let start = start.max(offsets[i]).min(offsets[i + 1]);
- // compute the length of the slice
- let length: OffsetSize = length
- .unwrap_or(length_i)
- // .max(0) is not needed as it is guaranteed
- .min(offsets[i + 1] - start); // so we do not go beyond this entry
-
- length_so_far += length;
+ // calculate the start offset for each substring
+ // if `start` >= 0
+ // then, count from the start of each string
+ // else, count from the end of each string
+ let new_starts: Vec<OffsetSize> = if start >= zero {
+ offsets
+ .windows(2)
+ .map(|pair| (pair[0] + start).min(pair[1]))
+ .collect()
+ } else {
+ offsets
+ .windows(2)
+ .map(|pair| (pair[1] + start).max(pair[0]))
+ .collect()
Review comment:
Thinking about it, I think actually materializing `new_length` to a Vec is not needed. It probably is faster (and saves allocating this Vec) to compute the length again when calculating `new_values`.
--
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
[GitHub] [arrow-rs] HaoYang670 commented on a change in pull request #1512: Speed up the `substring` kernel
Posted by GitBox <gi...@apache.org>.
HaoYang670 commented on a change in pull request #1512:
URL: https://github.com/apache/arrow-rs/pull/1512#discussion_r839630865
##########
File path: arrow/src/compute/kernels/substring.rs
##########
@@ -24,56 +24,74 @@ use crate::{
error::{ArrowError, Result},
};
-#[allow(clippy::unnecessary_wraps)]
fn generic_substring<OffsetSize: StringOffsetSizeTrait>(
array: &GenericStringArray<OffsetSize>,
start: OffsetSize,
length: &Option<OffsetSize>,
) -> Result<ArrayRef> {
- // compute current offsets
- let offsets = array.data_ref().clone().buffers()[0].clone();
- let offsets: &[OffsetSize] = unsafe { offsets.typed_data::<OffsetSize>() };
-
- // compute null bitmap (copy)
+ let offsets = array.value_offsets();
let null_bit_buffer = array.data_ref().null_buffer().cloned();
-
- // compute values
- let values = &array.data_ref().buffers()[1];
+ let values = array.value_data();
let data = values.as_slice();
+ let zero = OffsetSize::zero();
- let mut new_values = MutableBuffer::new(0); // we have no way to estimate how much this will be.
- let mut new_offsets: Vec<OffsetSize> = Vec::with_capacity(array.len() + 1);
-
- let mut length_so_far = OffsetSize::zero();
- new_offsets.push(length_so_far);
- (0..array.len()).for_each(|i| {
- // the length of this entry
- let length_i: OffsetSize = offsets[i + 1] - offsets[i];
- // compute where we should start slicing this entry
- let start = offsets[i]
- + if start >= OffsetSize::zero() {
- start
- } else {
- length_i + start
- };
-
- let start = start.max(offsets[i]).min(offsets[i + 1]);
- // compute the length of the slice
- let length: OffsetSize = length
- .unwrap_or(length_i)
- // .max(0) is not needed as it is guaranteed
- .min(offsets[i + 1] - start); // so we do not go beyond this entry
-
- length_so_far += length;
+ // calculate the start offset for each substring
+ // if `start` >= 0
+ // then, count from the start of each string
+ // else, count from the end of each string
+ let new_starts: Vec<OffsetSize> = if start >= zero {
Review comment:
We don't need to compare `start` with `zero` in each for loop. So move this outside the loop
--
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
[GitHub] [arrow-rs] HaoYang670 commented on a change in pull request #1512: Speed up the `substring` kernel
Posted by GitBox <gi...@apache.org>.
HaoYang670 commented on a change in pull request #1512:
URL: https://github.com/apache/arrow-rs/pull/1512#discussion_r840139836
##########
File path: arrow/src/compute/kernels/substring.rs
##########
@@ -24,56 +24,74 @@ use crate::{
error::{ArrowError, Result},
};
-#[allow(clippy::unnecessary_wraps)]
fn generic_substring<OffsetSize: StringOffsetSizeTrait>(
array: &GenericStringArray<OffsetSize>,
start: OffsetSize,
length: &Option<OffsetSize>,
) -> Result<ArrayRef> {
- // compute current offsets
- let offsets = array.data_ref().clone().buffers()[0].clone();
- let offsets: &[OffsetSize] = unsafe { offsets.typed_data::<OffsetSize>() };
-
- // compute null bitmap (copy)
+ let offsets = array.value_offsets();
let null_bit_buffer = array.data_ref().null_buffer().cloned();
-
- // compute values
- let values = &array.data_ref().buffers()[1];
+ let values = array.value_data();
let data = values.as_slice();
+ let zero = OffsetSize::zero();
- let mut new_values = MutableBuffer::new(0); // we have no way to estimate how much this will be.
- let mut new_offsets: Vec<OffsetSize> = Vec::with_capacity(array.len() + 1);
-
- let mut length_so_far = OffsetSize::zero();
- new_offsets.push(length_so_far);
- (0..array.len()).for_each(|i| {
- // the length of this entry
- let length_i: OffsetSize = offsets[i + 1] - offsets[i];
- // compute where we should start slicing this entry
- let start = offsets[i]
- + if start >= OffsetSize::zero() {
- start
- } else {
- length_i + start
- };
-
- let start = start.max(offsets[i]).min(offsets[i + 1]);
- // compute the length of the slice
- let length: OffsetSize = length
- .unwrap_or(length_i)
- // .max(0) is not needed as it is guaranteed
- .min(offsets[i + 1] - start); // so we do not go beyond this entry
-
- length_so_far += length;
+ // calculate the start offset for each substring
+ // if `start` >= 0
+ // then, count from the start of each string
+ // else, count from the end of each string
+ let new_starts: Vec<OffsetSize> = if start >= zero {
+ offsets
+ .windows(2)
+ .map(|pair| (pair[0] + start).min(pair[1]))
+ .collect()
+ } else {
+ offsets
+ .windows(2)
+ .map(|pair| (pair[1] + start).max(pair[0]))
+ .collect()
Review comment:
> Might be better to do `new_starts`/`new_length` in one iteration over `offsets` and use `unzip` to materialize into two Vecs?
I guess it will not make the code simple. Because there are 4 branches that has to be considered:
```rust
let (new_starts, new_length): (Vec, Vec) = match (start>=0, length) {
(true, Some(length)) => ...,
(true, None) => ...,
(false, Some(length)) =>... ,
(false, None) =>...,
};
```
--
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
[GitHub] [arrow-rs] HaoYang670 commented on a change in pull request #1512: Speed up the `substring` kernel
Posted by GitBox <gi...@apache.org>.
HaoYang670 commented on a change in pull request #1512:
URL: https://github.com/apache/arrow-rs/pull/1512#discussion_r839625876
##########
File path: arrow/src/compute/kernels/substring.rs
##########
@@ -24,56 +24,74 @@ use crate::{
error::{ArrowError, Result},
};
-#[allow(clippy::unnecessary_wraps)]
fn generic_substring<OffsetSize: StringOffsetSizeTrait>(
array: &GenericStringArray<OffsetSize>,
start: OffsetSize,
length: &Option<OffsetSize>,
) -> Result<ArrayRef> {
- // compute current offsets
- let offsets = array.data_ref().clone().buffers()[0].clone();
- let offsets: &[OffsetSize] = unsafe { offsets.typed_data::<OffsetSize>() };
-
- // compute null bitmap (copy)
+ let offsets = array.value_offsets();
let null_bit_buffer = array.data_ref().null_buffer().cloned();
-
- // compute values
- let values = &array.data_ref().buffers()[1];
+ let values = array.value_data();
let data = values.as_slice();
+ let zero = OffsetSize::zero();
- let mut new_values = MutableBuffer::new(0); // we have no way to estimate how much this will be.
- let mut new_offsets: Vec<OffsetSize> = Vec::with_capacity(array.len() + 1);
-
- let mut length_so_far = OffsetSize::zero();
- new_offsets.push(length_so_far);
- (0..array.len()).for_each(|i| {
- // the length of this entry
- let length_i: OffsetSize = offsets[i + 1] - offsets[i];
- // compute where we should start slicing this entry
- let start = offsets[i]
- + if start >= OffsetSize::zero() {
- start
- } else {
- length_i + start
- };
-
- let start = start.max(offsets[i]).min(offsets[i + 1]);
- // compute the length of the slice
- let length: OffsetSize = length
- .unwrap_or(length_i)
- // .max(0) is not needed as it is guaranteed
- .min(offsets[i + 1] - start); // so we do not go beyond this entry
-
- length_so_far += length;
+ // calculate the start offset for each substring
+ // if `start` >= 0
+ // then, count from the start of each string
+ // else, count from the end of each string
+ let new_starts: Vec<OffsetSize> = if start >= zero {
+ offsets
+ .windows(2)
+ .map(|pair| (pair[0] + start).min(pair[1]))
+ .collect()
+ } else {
+ offsets
+ .windows(2)
+ .map(|pair| (pair[1] + start).max(pair[0]))
+ .collect()
Review comment:
I tried to remove `.collect`, actually. But you know, closure values with generic type in `if-else` branch can get `no two closures, even if identical, have the same type` error. And I did not find a good solution except adding `.collect`
https://github.com/rust-lang/rust/issues/87961
--
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
[GitHub] [arrow-rs] HaoYang670 commented on a change in pull request #1512: Speed up the `substring` kernel
Posted by GitBox <gi...@apache.org>.
HaoYang670 commented on a change in pull request #1512:
URL: https://github.com/apache/arrow-rs/pull/1512#discussion_r840350610
##########
File path: arrow/src/compute/kernels/substring.rs
##########
@@ -24,56 +24,61 @@ use crate::{
error::{ArrowError, Result},
};
-#[allow(clippy::unnecessary_wraps)]
fn generic_substring<OffsetSize: StringOffsetSizeTrait>(
array: &GenericStringArray<OffsetSize>,
start: OffsetSize,
length: &Option<OffsetSize>,
) -> Result<ArrayRef> {
- // compute current offsets
- let offsets = array.data_ref().clone().buffers()[0].clone();
- let offsets: &[OffsetSize] = unsafe { offsets.typed_data::<OffsetSize>() };
-
- // compute null bitmap (copy)
+ let offsets = array.value_offsets();
let null_bit_buffer = array.data_ref().null_buffer().cloned();
-
- // compute values
- let values = &array.data_ref().buffers()[1];
+ let values = array.value_data();
let data = values.as_slice();
+ let zero = OffsetSize::zero();
- let mut new_values = MutableBuffer::new(0); // we have no way to estimate how much this will be.
- let mut new_offsets: Vec<OffsetSize> = Vec::with_capacity(array.len() + 1);
-
- let mut length_so_far = OffsetSize::zero();
- new_offsets.push(length_so_far);
- (0..array.len()).for_each(|i| {
- // the length of this entry
- let length_i: OffsetSize = offsets[i + 1] - offsets[i];
- // compute where we should start slicing this entry
- let start = offsets[i]
- + if start >= OffsetSize::zero() {
- start
- } else {
- length_i + start
- };
+ let cal_new_start: Box<dyn Fn(OffsetSize, OffsetSize) -> OffsetSize> = if start
+ >= zero
+ {
+ // count from the start of string
+ Box::new(|old_start: OffsetSize, end: OffsetSize| (old_start + start).min(end))
+ } else {
+ // count from the end of string
+ Box::new(|old_start: OffsetSize, end: OffsetSize| (end + start).max(old_start))
+ };
- let start = start.max(offsets[i]).min(offsets[i + 1]);
- // compute the length of the slice
- let length: OffsetSize = length
- .unwrap_or(length_i)
- // .max(0) is not needed as it is guaranteed
- .min(offsets[i + 1] - start); // so we do not go beyond this entry
+ let cal_new_length: Box<dyn Fn(OffsetSize, OffsetSize) -> OffsetSize> =
+ if let Some(length) = length {
+ Box::new(|start: OffsetSize, end: OffsetSize| (*length).min(end - start))
+ } else {
+ Box::new(|start: OffsetSize, end: OffsetSize| end - start)
+ };
- length_so_far += length;
+ // start and end offsets for each substring
+ let mut new_starts_ends: Vec<(OffsetSize, OffsetSize)> =
+ Vec::with_capacity(array.len());
Review comment:
It is a time-space trade-off, but not the major factor affecting performance
--
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
[GitHub] [arrow-rs] HaoYang670 commented on a change in pull request #1512: Speed up the `substring` kernel
Posted by GitBox <gi...@apache.org>.
HaoYang670 commented on a change in pull request #1512:
URL: https://github.com/apache/arrow-rs/pull/1512#discussion_r840342708
##########
File path: arrow/src/compute/kernels/substring.rs
##########
@@ -24,56 +24,61 @@ use crate::{
error::{ArrowError, Result},
};
-#[allow(clippy::unnecessary_wraps)]
fn generic_substring<OffsetSize: StringOffsetSizeTrait>(
array: &GenericStringArray<OffsetSize>,
start: OffsetSize,
length: &Option<OffsetSize>,
) -> Result<ArrayRef> {
- // compute current offsets
- let offsets = array.data_ref().clone().buffers()[0].clone();
- let offsets: &[OffsetSize] = unsafe { offsets.typed_data::<OffsetSize>() };
-
- // compute null bitmap (copy)
+ let offsets = array.value_offsets();
let null_bit_buffer = array.data_ref().null_buffer().cloned();
-
- // compute values
- let values = &array.data_ref().buffers()[1];
+ let values = array.value_data();
let data = values.as_slice();
+ let zero = OffsetSize::zero();
- let mut new_values = MutableBuffer::new(0); // we have no way to estimate how much this will be.
- let mut new_offsets: Vec<OffsetSize> = Vec::with_capacity(array.len() + 1);
-
- let mut length_so_far = OffsetSize::zero();
- new_offsets.push(length_so_far);
- (0..array.len()).for_each(|i| {
- // the length of this entry
- let length_i: OffsetSize = offsets[i + 1] - offsets[i];
- // compute where we should start slicing this entry
- let start = offsets[i]
- + if start >= OffsetSize::zero() {
- start
- } else {
- length_i + start
- };
+ let cal_new_start: Box<dyn Fn(OffsetSize, OffsetSize) -> OffsetSize> = if start
+ >= zero
Review comment:
`cargo fmt` likes this weird format.
--
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
[GitHub] [arrow-rs] HaoYang670 commented on pull request #1512: Speed up the `substring` kernel
Posted by GitBox <gi...@apache.org>.
HaoYang670 commented on pull request #1512:
URL: https://github.com/apache/arrow-rs/pull/1512#issuecomment-1085574499
Hi @Dandandan ! These are some changes since your last review:
1. Use dynamic `Fn` trait with `Box`, so that there is no repeated code.
2. Give up using purely functional way. Because it is not suitable in this context. `mut vec` and `for each` are more straightforward.
3. We have to materialize `new_offset`, `new_length`(`new_end` now) and `new_start` before calculating `new_value`. Because we need `new_offset` to estimate the size of array. And `new_offset` depends on `new_length` which depends on `new_start`.
4. `dyn Fn` may introduce just a little performance penalty. I will update the benchmark.
--
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
[GitHub] [arrow-rs] HaoYang670 commented on a change in pull request #1512: Speed up the `substring` kernel
Posted by GitBox <gi...@apache.org>.
HaoYang670 commented on a change in pull request #1512:
URL: https://github.com/apache/arrow-rs/pull/1512#discussion_r839625876
##########
File path: arrow/src/compute/kernels/substring.rs
##########
@@ -24,56 +24,74 @@ use crate::{
error::{ArrowError, Result},
};
-#[allow(clippy::unnecessary_wraps)]
fn generic_substring<OffsetSize: StringOffsetSizeTrait>(
array: &GenericStringArray<OffsetSize>,
start: OffsetSize,
length: &Option<OffsetSize>,
) -> Result<ArrayRef> {
- // compute current offsets
- let offsets = array.data_ref().clone().buffers()[0].clone();
- let offsets: &[OffsetSize] = unsafe { offsets.typed_data::<OffsetSize>() };
-
- // compute null bitmap (copy)
+ let offsets = array.value_offsets();
let null_bit_buffer = array.data_ref().null_buffer().cloned();
-
- // compute values
- let values = &array.data_ref().buffers()[1];
+ let values = array.value_data();
let data = values.as_slice();
+ let zero = OffsetSize::zero();
- let mut new_values = MutableBuffer::new(0); // we have no way to estimate how much this will be.
- let mut new_offsets: Vec<OffsetSize> = Vec::with_capacity(array.len() + 1);
-
- let mut length_so_far = OffsetSize::zero();
- new_offsets.push(length_so_far);
- (0..array.len()).for_each(|i| {
- // the length of this entry
- let length_i: OffsetSize = offsets[i + 1] - offsets[i];
- // compute where we should start slicing this entry
- let start = offsets[i]
- + if start >= OffsetSize::zero() {
- start
- } else {
- length_i + start
- };
-
- let start = start.max(offsets[i]).min(offsets[i + 1]);
- // compute the length of the slice
- let length: OffsetSize = length
- .unwrap_or(length_i)
- // .max(0) is not needed as it is guaranteed
- .min(offsets[i + 1] - start); // so we do not go beyond this entry
-
- length_so_far += length;
+ // calculate the start offset for each substring
+ // if `start` >= 0
+ // then, count from the start of each string
+ // else, count from the end of each string
+ let new_starts: Vec<OffsetSize> = if start >= zero {
+ offsets
+ .windows(2)
+ .map(|pair| (pair[0] + start).min(pair[1]))
+ .collect()
+ } else {
+ offsets
+ .windows(2)
+ .map(|pair| (pair[1] + start).max(pair[0]))
+ .collect()
Review comment:
I tried to remove `.collect`, actually. But you know, closure values in `if-else` branch can get `no two closures, even if identical, have the same type` error. And I did not find a good solution except adding `.collect`
https://github.com/rust-lang/rust/issues/87961
--
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
[GitHub] [arrow-rs] Dandandan commented on a change in pull request #1512: Speed up the `substring` kernel
Posted by GitBox <gi...@apache.org>.
Dandandan commented on a change in pull request #1512:
URL: https://github.com/apache/arrow-rs/pull/1512#discussion_r839592294
##########
File path: arrow/src/compute/kernels/substring.rs
##########
@@ -24,56 +24,74 @@ use crate::{
error::{ArrowError, Result},
};
-#[allow(clippy::unnecessary_wraps)]
fn generic_substring<OffsetSize: StringOffsetSizeTrait>(
array: &GenericStringArray<OffsetSize>,
start: OffsetSize,
length: &Option<OffsetSize>,
) -> Result<ArrayRef> {
- // compute current offsets
- let offsets = array.data_ref().clone().buffers()[0].clone();
- let offsets: &[OffsetSize] = unsafe { offsets.typed_data::<OffsetSize>() };
-
- // compute null bitmap (copy)
+ let offsets = array.value_offsets();
let null_bit_buffer = array.data_ref().null_buffer().cloned();
-
- // compute values
- let values = &array.data_ref().buffers()[1];
+ let values = array.value_data();
let data = values.as_slice();
+ let zero = OffsetSize::zero();
- let mut new_values = MutableBuffer::new(0); // we have no way to estimate how much this will be.
- let mut new_offsets: Vec<OffsetSize> = Vec::with_capacity(array.len() + 1);
-
- let mut length_so_far = OffsetSize::zero();
- new_offsets.push(length_so_far);
- (0..array.len()).for_each(|i| {
- // the length of this entry
- let length_i: OffsetSize = offsets[i + 1] - offsets[i];
- // compute where we should start slicing this entry
- let start = offsets[i]
- + if start >= OffsetSize::zero() {
- start
- } else {
- length_i + start
- };
-
- let start = start.max(offsets[i]).min(offsets[i + 1]);
- // compute the length of the slice
- let length: OffsetSize = length
- .unwrap_or(length_i)
- // .max(0) is not needed as it is guaranteed
- .min(offsets[i + 1] - start); // so we do not go beyond this entry
-
- length_so_far += length;
+ // calculate the start offset for each substring
+ // if `start` >= 0
+ // then, count from the start of each string
+ // else, count from the end of each string
+ let new_starts: Vec<OffsetSize> = if start >= zero {
+ offsets
+ .windows(2)
+ .map(|pair| (pair[0] + start).min(pair[1]))
+ .collect()
+ } else {
+ offsets
+ .windows(2)
+ .map(|pair| (pair[1] + start).max(pair[0]))
+ .collect()
Review comment:
Thinking about it, I think actually materializing `new_length` to a Vec is not needed. It probably is faster to compute the length again when calculating `new_values`.
--
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
[GitHub] [arrow-rs] HaoYang670 commented on a change in pull request #1512: Speed up the `substring` kernel
Posted by GitBox <gi...@apache.org>.
HaoYang670 commented on a change in pull request #1512:
URL: https://github.com/apache/arrow-rs/pull/1512#discussion_r839627593
##########
File path: arrow/src/compute/kernels/substring.rs
##########
@@ -24,56 +24,74 @@ use crate::{
error::{ArrowError, Result},
};
-#[allow(clippy::unnecessary_wraps)]
fn generic_substring<OffsetSize: StringOffsetSizeTrait>(
array: &GenericStringArray<OffsetSize>,
start: OffsetSize,
length: &Option<OffsetSize>,
) -> Result<ArrayRef> {
- // compute current offsets
- let offsets = array.data_ref().clone().buffers()[0].clone();
- let offsets: &[OffsetSize] = unsafe { offsets.typed_data::<OffsetSize>() };
-
- // compute null bitmap (copy)
+ let offsets = array.value_offsets();
let null_bit_buffer = array.data_ref().null_buffer().cloned();
-
- // compute values
- let values = &array.data_ref().buffers()[1];
+ let values = array.value_data();
let data = values.as_slice();
+ let zero = OffsetSize::zero();
- let mut new_values = MutableBuffer::new(0); // we have no way to estimate how much this will be.
- let mut new_offsets: Vec<OffsetSize> = Vec::with_capacity(array.len() + 1);
-
- let mut length_so_far = OffsetSize::zero();
- new_offsets.push(length_so_far);
- (0..array.len()).for_each(|i| {
- // the length of this entry
- let length_i: OffsetSize = offsets[i + 1] - offsets[i];
- // compute where we should start slicing this entry
- let start = offsets[i]
- + if start >= OffsetSize::zero() {
Review comment:
We don't need to compare `start` with `zero` multiple time. So I move this outside the for loop
--
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
[GitHub] [arrow-rs] HaoYang670 commented on a change in pull request #1512: Speed up the `substring` kernel
Posted by GitBox <gi...@apache.org>.
HaoYang670 commented on a change in pull request #1512:
URL: https://github.com/apache/arrow-rs/pull/1512#discussion_r840139836
##########
File path: arrow/src/compute/kernels/substring.rs
##########
@@ -24,56 +24,74 @@ use crate::{
error::{ArrowError, Result},
};
-#[allow(clippy::unnecessary_wraps)]
fn generic_substring<OffsetSize: StringOffsetSizeTrait>(
array: &GenericStringArray<OffsetSize>,
start: OffsetSize,
length: &Option<OffsetSize>,
) -> Result<ArrayRef> {
- // compute current offsets
- let offsets = array.data_ref().clone().buffers()[0].clone();
- let offsets: &[OffsetSize] = unsafe { offsets.typed_data::<OffsetSize>() };
-
- // compute null bitmap (copy)
+ let offsets = array.value_offsets();
let null_bit_buffer = array.data_ref().null_buffer().cloned();
-
- // compute values
- let values = &array.data_ref().buffers()[1];
+ let values = array.value_data();
let data = values.as_slice();
+ let zero = OffsetSize::zero();
- let mut new_values = MutableBuffer::new(0); // we have no way to estimate how much this will be.
- let mut new_offsets: Vec<OffsetSize> = Vec::with_capacity(array.len() + 1);
-
- let mut length_so_far = OffsetSize::zero();
- new_offsets.push(length_so_far);
- (0..array.len()).for_each(|i| {
- // the length of this entry
- let length_i: OffsetSize = offsets[i + 1] - offsets[i];
- // compute where we should start slicing this entry
- let start = offsets[i]
- + if start >= OffsetSize::zero() {
- start
- } else {
- length_i + start
- };
-
- let start = start.max(offsets[i]).min(offsets[i + 1]);
- // compute the length of the slice
- let length: OffsetSize = length
- .unwrap_or(length_i)
- // .max(0) is not needed as it is guaranteed
- .min(offsets[i + 1] - start); // so we do not go beyond this entry
-
- length_so_far += length;
+ // calculate the start offset for each substring
+ // if `start` >= 0
+ // then, count from the start of each string
+ // else, count from the end of each string
+ let new_starts: Vec<OffsetSize> = if start >= zero {
+ offsets
+ .windows(2)
+ .map(|pair| (pair[0] + start).min(pair[1]))
+ .collect()
+ } else {
+ offsets
+ .windows(2)
+ .map(|pair| (pair[1] + start).max(pair[0]))
+ .collect()
Review comment:
> Might be better to do `new_starts`/`new_length` in one iteration over `offsets` and use `unzip` to materialize into two Vecs?
I guess it will not make the code simple. Because there are 4 branches that has to be considered:
```rust
let (new_starts, new_length) = match (start>=0, length) {
(true, Some(length)) => ...,
(true, None) => ...,
(false, Some(length)) => ,
(false, None) =>,
};
```
--
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
[GitHub] [arrow-rs] Dandandan commented on a change in pull request #1512: Speed up the `substring` kernel
Posted by GitBox <gi...@apache.org>.
Dandandan commented on a change in pull request #1512:
URL: https://github.com/apache/arrow-rs/pull/1512#discussion_r840252763
##########
File path: arrow/src/compute/kernels/substring.rs
##########
@@ -24,56 +24,74 @@ use crate::{
error::{ArrowError, Result},
};
-#[allow(clippy::unnecessary_wraps)]
fn generic_substring<OffsetSize: StringOffsetSizeTrait>(
array: &GenericStringArray<OffsetSize>,
start: OffsetSize,
length: &Option<OffsetSize>,
) -> Result<ArrayRef> {
- // compute current offsets
- let offsets = array.data_ref().clone().buffers()[0].clone();
- let offsets: &[OffsetSize] = unsafe { offsets.typed_data::<OffsetSize>() };
-
- // compute null bitmap (copy)
+ let offsets = array.value_offsets();
let null_bit_buffer = array.data_ref().null_buffer().cloned();
-
- // compute values
- let values = &array.data_ref().buffers()[1];
+ let values = array.value_data();
let data = values.as_slice();
+ let zero = OffsetSize::zero();
- let mut new_values = MutableBuffer::new(0); // we have no way to estimate how much this will be.
- let mut new_offsets: Vec<OffsetSize> = Vec::with_capacity(array.len() + 1);
-
- let mut length_so_far = OffsetSize::zero();
- new_offsets.push(length_so_far);
- (0..array.len()).for_each(|i| {
- // the length of this entry
- let length_i: OffsetSize = offsets[i + 1] - offsets[i];
- // compute where we should start slicing this entry
- let start = offsets[i]
- + if start >= OffsetSize::zero() {
- start
- } else {
- length_i + start
- };
-
- let start = start.max(offsets[i]).min(offsets[i + 1]);
- // compute the length of the slice
- let length: OffsetSize = length
- .unwrap_or(length_i)
- // .max(0) is not needed as it is guaranteed
- .min(offsets[i + 1] - start); // so we do not go beyond this entry
-
- length_so_far += length;
+ // calculate the start offset for each substring
+ // if `start` >= 0
+ // then, count from the start of each string
+ // else, count from the end of each string
+ let new_starts: Vec<OffsetSize> = if start >= zero {
+ offsets
+ .windows(2)
+ .map(|pair| (pair[0] + start).min(pair[1]))
+ .collect()
+ } else {
+ offsets
+ .windows(2)
+ .map(|pair| (pair[1] + start).max(pair[0]))
+ .collect()
Review comment:
My later comment mentioned not allocating the new vec but not allocating the array at all (by moving the calculation to the iteration in `new_values`). Is that something you want to try?
> Thinking about it, I think actually materializing new_length to a Vec is not needed. It probably is faster (and saves allocating this Vec) to compute the length again when calculating new_values.
--
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
[GitHub] [arrow-rs] HaoYang670 commented on a change in pull request #1512: Speed up the `substring` kernel
Posted by GitBox <gi...@apache.org>.
HaoYang670 commented on a change in pull request #1512:
URL: https://github.com/apache/arrow-rs/pull/1512#discussion_r840139836
##########
File path: arrow/src/compute/kernels/substring.rs
##########
@@ -24,56 +24,74 @@ use crate::{
error::{ArrowError, Result},
};
-#[allow(clippy::unnecessary_wraps)]
fn generic_substring<OffsetSize: StringOffsetSizeTrait>(
array: &GenericStringArray<OffsetSize>,
start: OffsetSize,
length: &Option<OffsetSize>,
) -> Result<ArrayRef> {
- // compute current offsets
- let offsets = array.data_ref().clone().buffers()[0].clone();
- let offsets: &[OffsetSize] = unsafe { offsets.typed_data::<OffsetSize>() };
-
- // compute null bitmap (copy)
+ let offsets = array.value_offsets();
let null_bit_buffer = array.data_ref().null_buffer().cloned();
-
- // compute values
- let values = &array.data_ref().buffers()[1];
+ let values = array.value_data();
let data = values.as_slice();
+ let zero = OffsetSize::zero();
- let mut new_values = MutableBuffer::new(0); // we have no way to estimate how much this will be.
- let mut new_offsets: Vec<OffsetSize> = Vec::with_capacity(array.len() + 1);
-
- let mut length_so_far = OffsetSize::zero();
- new_offsets.push(length_so_far);
- (0..array.len()).for_each(|i| {
- // the length of this entry
- let length_i: OffsetSize = offsets[i + 1] - offsets[i];
- // compute where we should start slicing this entry
- let start = offsets[i]
- + if start >= OffsetSize::zero() {
- start
- } else {
- length_i + start
- };
-
- let start = start.max(offsets[i]).min(offsets[i + 1]);
- // compute the length of the slice
- let length: OffsetSize = length
- .unwrap_or(length_i)
- // .max(0) is not needed as it is guaranteed
- .min(offsets[i + 1] - start); // so we do not go beyond this entry
-
- length_so_far += length;
+ // calculate the start offset for each substring
+ // if `start` >= 0
+ // then, count from the start of each string
+ // else, count from the end of each string
+ let new_starts: Vec<OffsetSize> = if start >= zero {
+ offsets
+ .windows(2)
+ .map(|pair| (pair[0] + start).min(pair[1]))
+ .collect()
+ } else {
+ offsets
+ .windows(2)
+ .map(|pair| (pair[1] + start).max(pair[0]))
+ .collect()
Review comment:
> Might be better to do `new_starts`/`new_length` in one iteration over `offsets` and use `unzip` to materialize into two Vecs?
I guess it will not make the code simple. Because there are 4 branches that has to be considered:
```rust
let (new_starts, new_length): (Vec, Vec) = match (start>=0, length) {
(true, Some(length)) => ...,
(true, None) => ...,
(false, Some(length)) =>... ,
(false, None) =>...,
};
```
Also, after doing some benchmark tests, iterating on `offsets` for multi times will not make the function slower, because `MutableBuffer::extend_from_slice` is the hotspot of the code.
--
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
[GitHub] [arrow-rs] HaoYang670 commented on a change in pull request #1512: Speed up the `substring` kernel
Posted by GitBox <gi...@apache.org>.
HaoYang670 commented on a change in pull request #1512:
URL: https://github.com/apache/arrow-rs/pull/1512#discussion_r839629274
##########
File path: arrow/src/compute/kernels/substring.rs
##########
@@ -24,56 +24,74 @@ use crate::{
error::{ArrowError, Result},
};
-#[allow(clippy::unnecessary_wraps)]
fn generic_substring<OffsetSize: StringOffsetSizeTrait>(
array: &GenericStringArray<OffsetSize>,
start: OffsetSize,
length: &Option<OffsetSize>,
) -> Result<ArrayRef> {
- // compute current offsets
- let offsets = array.data_ref().clone().buffers()[0].clone();
- let offsets: &[OffsetSize] = unsafe { offsets.typed_data::<OffsetSize>() };
-
- // compute null bitmap (copy)
+ let offsets = array.value_offsets();
let null_bit_buffer = array.data_ref().null_buffer().cloned();
-
- // compute values
- let values = &array.data_ref().buffers()[1];
+ let values = array.value_data();
let data = values.as_slice();
+ let zero = OffsetSize::zero();
- let mut new_values = MutableBuffer::new(0); // we have no way to estimate how much this will be.
- let mut new_offsets: Vec<OffsetSize> = Vec::with_capacity(array.len() + 1);
-
- let mut length_so_far = OffsetSize::zero();
- new_offsets.push(length_so_far);
- (0..array.len()).for_each(|i| {
- // the length of this entry
- let length_i: OffsetSize = offsets[i + 1] - offsets[i];
- // compute where we should start slicing this entry
- let start = offsets[i]
- + if start >= OffsetSize::zero() {
- start
- } else {
- length_i + start
- };
-
- let start = start.max(offsets[i]).min(offsets[i + 1]);
- // compute the length of the slice
- let length: OffsetSize = length
- .unwrap_or(length_i)
Review comment:
Same reason! we don't need to `unwrap` `length` in each loop. So move this outside the loop.
--
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
[GitHub] [arrow-rs] Dandandan commented on a change in pull request #1512: Speed up the `substring` kernel
Posted by GitBox <gi...@apache.org>.
Dandandan commented on a change in pull request #1512:
URL: https://github.com/apache/arrow-rs/pull/1512#discussion_r839775068
##########
File path: arrow/src/compute/kernels/substring.rs
##########
@@ -24,56 +24,74 @@ use crate::{
error::{ArrowError, Result},
};
-#[allow(clippy::unnecessary_wraps)]
fn generic_substring<OffsetSize: StringOffsetSizeTrait>(
array: &GenericStringArray<OffsetSize>,
start: OffsetSize,
length: &Option<OffsetSize>,
) -> Result<ArrayRef> {
- // compute current offsets
- let offsets = array.data_ref().clone().buffers()[0].clone();
- let offsets: &[OffsetSize] = unsafe { offsets.typed_data::<OffsetSize>() };
-
- // compute null bitmap (copy)
+ let offsets = array.value_offsets();
let null_bit_buffer = array.data_ref().null_buffer().cloned();
-
- // compute values
- let values = &array.data_ref().buffers()[1];
+ let values = array.value_data();
let data = values.as_slice();
+ let zero = OffsetSize::zero();
- let mut new_values = MutableBuffer::new(0); // we have no way to estimate how much this will be.
- let mut new_offsets: Vec<OffsetSize> = Vec::with_capacity(array.len() + 1);
-
- let mut length_so_far = OffsetSize::zero();
- new_offsets.push(length_so_far);
- (0..array.len()).for_each(|i| {
- // the length of this entry
- let length_i: OffsetSize = offsets[i + 1] - offsets[i];
- // compute where we should start slicing this entry
- let start = offsets[i]
- + if start >= OffsetSize::zero() {
- start
- } else {
- length_i + start
- };
-
- let start = start.max(offsets[i]).min(offsets[i + 1]);
- // compute the length of the slice
- let length: OffsetSize = length
- .unwrap_or(length_i)
- // .max(0) is not needed as it is guaranteed
- .min(offsets[i + 1] - start); // so we do not go beyond this entry
-
- length_so_far += length;
+ // calculate the start offset for each substring
+ // if `start` >= 0
+ // then, count from the start of each string
+ // else, count from the end of each string
+ let new_starts: Vec<OffsetSize> = if start >= zero {
+ offsets
+ .windows(2)
+ .map(|pair| (pair[0] + start).min(pair[1]))
+ .collect()
+ } else {
+ offsets
+ .windows(2)
+ .map(|pair| (pair[1] + start).max(pair[0]))
+ .collect()
Review comment:
Yes, that is not possible in Rust (I think only by Boxing or manually inlining / macros).
Calculating the length in two places with something like `let length = *end - *start` within both the `new_offsets` `new_values` doesn´t seem too bad in terms of duplication?
--
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
[GitHub] [arrow-rs] HaoYang670 edited a comment on pull request #1512: Speed up the `substring` kernel
Posted by GitBox <gi...@apache.org>.
HaoYang670 edited a comment on pull request #1512:
URL: https://github.com/apache/arrow-rs/pull/1512#issuecomment-1085574499
Hi @Dandandan ! These are some changes since your last review:
1. Use dynamic `Fn` trait with `Box`, so that there is no repeated code.
2. Give up using purely functional way. Because it is not suitable in this context. `mut vec` and `for each` are more straightforward.
3. We have to materialize `new_offset`, `new_length`(`new_end` now) and `new_start` before calculating `new_value`. Because we need `new_offset` to estimate the size of array. And `new_offset` depends on `new_length` which depends on `new_start`.
4. `dyn Fn` may introduce just a little performance penalty. I have updated the benchmark.
--
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
[GitHub] [arrow-rs] HaoYang670 commented on a change in pull request #1512: Speed up the `substring` kernel
Posted by GitBox <gi...@apache.org>.
HaoYang670 commented on a change in pull request #1512:
URL: https://github.com/apache/arrow-rs/pull/1512#discussion_r840139836
##########
File path: arrow/src/compute/kernels/substring.rs
##########
@@ -24,56 +24,74 @@ use crate::{
error::{ArrowError, Result},
};
-#[allow(clippy::unnecessary_wraps)]
fn generic_substring<OffsetSize: StringOffsetSizeTrait>(
array: &GenericStringArray<OffsetSize>,
start: OffsetSize,
length: &Option<OffsetSize>,
) -> Result<ArrayRef> {
- // compute current offsets
- let offsets = array.data_ref().clone().buffers()[0].clone();
- let offsets: &[OffsetSize] = unsafe { offsets.typed_data::<OffsetSize>() };
-
- // compute null bitmap (copy)
+ let offsets = array.value_offsets();
let null_bit_buffer = array.data_ref().null_buffer().cloned();
-
- // compute values
- let values = &array.data_ref().buffers()[1];
+ let values = array.value_data();
let data = values.as_slice();
+ let zero = OffsetSize::zero();
- let mut new_values = MutableBuffer::new(0); // we have no way to estimate how much this will be.
- let mut new_offsets: Vec<OffsetSize> = Vec::with_capacity(array.len() + 1);
-
- let mut length_so_far = OffsetSize::zero();
- new_offsets.push(length_so_far);
- (0..array.len()).for_each(|i| {
- // the length of this entry
- let length_i: OffsetSize = offsets[i + 1] - offsets[i];
- // compute where we should start slicing this entry
- let start = offsets[i]
- + if start >= OffsetSize::zero() {
- start
- } else {
- length_i + start
- };
-
- let start = start.max(offsets[i]).min(offsets[i + 1]);
- // compute the length of the slice
- let length: OffsetSize = length
- .unwrap_or(length_i)
- // .max(0) is not needed as it is guaranteed
- .min(offsets[i + 1] - start); // so we do not go beyond this entry
-
- length_so_far += length;
+ // calculate the start offset for each substring
+ // if `start` >= 0
+ // then, count from the start of each string
+ // else, count from the end of each string
+ let new_starts: Vec<OffsetSize> = if start >= zero {
+ offsets
+ .windows(2)
+ .map(|pair| (pair[0] + start).min(pair[1]))
+ .collect()
+ } else {
+ offsets
+ .windows(2)
+ .map(|pair| (pair[1] + start).max(pair[0]))
+ .collect()
Review comment:
> Might be better to do `new_starts`/`new_length` in one iteration over `offsets` and use `unzip` to materialize into two Vecs?
I guess it will not make the code simple. Because there are 4 branches that has to be considered:
```rust
let (new_starts, new_length): (Vec, Vec) = match (start>=0, length) {
(true, Some(length)) => ...,
(true, None) => ...,
(false, Some(length)) =>... ,
(false, None) =>...,
};
```
Also, after doing some benchmark tests, iterating on `offsets` for multi times will not make the function slower, because `MutableBuffer::extend_from_slice` is the hotspot of the code.
--
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
[GitHub] [arrow-rs] HaoYang670 commented on a change in pull request #1512: Speed up the `substring` kernel
Posted by GitBox <gi...@apache.org>.
HaoYang670 commented on a change in pull request #1512:
URL: https://github.com/apache/arrow-rs/pull/1512#discussion_r839625876
##########
File path: arrow/src/compute/kernels/substring.rs
##########
@@ -24,56 +24,74 @@ use crate::{
error::{ArrowError, Result},
};
-#[allow(clippy::unnecessary_wraps)]
fn generic_substring<OffsetSize: StringOffsetSizeTrait>(
array: &GenericStringArray<OffsetSize>,
start: OffsetSize,
length: &Option<OffsetSize>,
) -> Result<ArrayRef> {
- // compute current offsets
- let offsets = array.data_ref().clone().buffers()[0].clone();
- let offsets: &[OffsetSize] = unsafe { offsets.typed_data::<OffsetSize>() };
-
- // compute null bitmap (copy)
+ let offsets = array.value_offsets();
let null_bit_buffer = array.data_ref().null_buffer().cloned();
-
- // compute values
- let values = &array.data_ref().buffers()[1];
+ let values = array.value_data();
let data = values.as_slice();
+ let zero = OffsetSize::zero();
- let mut new_values = MutableBuffer::new(0); // we have no way to estimate how much this will be.
- let mut new_offsets: Vec<OffsetSize> = Vec::with_capacity(array.len() + 1);
-
- let mut length_so_far = OffsetSize::zero();
- new_offsets.push(length_so_far);
- (0..array.len()).for_each(|i| {
- // the length of this entry
- let length_i: OffsetSize = offsets[i + 1] - offsets[i];
- // compute where we should start slicing this entry
- let start = offsets[i]
- + if start >= OffsetSize::zero() {
- start
- } else {
- length_i + start
- };
-
- let start = start.max(offsets[i]).min(offsets[i + 1]);
- // compute the length of the slice
- let length: OffsetSize = length
- .unwrap_or(length_i)
- // .max(0) is not needed as it is guaranteed
- .min(offsets[i + 1] - start); // so we do not go beyond this entry
-
- length_so_far += length;
+ // calculate the start offset for each substring
+ // if `start` >= 0
+ // then, count from the start of each string
+ // else, count from the end of each string
+ let new_starts: Vec<OffsetSize> = if start >= zero {
+ offsets
+ .windows(2)
+ .map(|pair| (pair[0] + start).min(pair[1]))
+ .collect()
+ } else {
+ offsets
+ .windows(2)
+ .map(|pair| (pair[1] + start).max(pair[0]))
+ .collect()
Review comment:
I tried to remove `.collect`, actually. But you know, closure values with generic type in `if-else` branch can get `no two closures, even if identical, have the same type` error. And I did not find a good solution except adding `.collect`
--
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