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 2021/04/28 17:18:33 UTC
[GitHub] [arrow-rs] medwards opened a new pull request #236: sort_primitive result is capped to the min of limit or values.len
medwards opened a new pull request #236:
URL: https://github.com/apache/arrow-rs/pull/236
Closes #235
# What changes are included in this PR?
The result slice in `sort_primitive` is the size of all the values being sorted even when a limit is provided. Change the size to be the maximum possible result (thus avoiding the panic in #235)
# Are there any user-facing changes?
No
### Notes
I've provided a reproducing test, but skipped other variants of limits /w nulls. Those should be easy so let me know if they're of interest. Additionally it is possible that `result` is intentionally over-large in which case I can try alternative fixes.
--
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.
For queries about this service, please contact Infrastructure at:
users@infra.apache.org
[GitHub] [arrow-rs] medwards commented on a change in pull request #236: sort_primitive result is capped to the min of limit or values.len
Posted by GitBox <gi...@apache.org>.
medwards commented on a change in pull request #236:
URL: https://github.com/apache/arrow-rs/pull/236#discussion_r623297164
##########
File path: arrow/src/compute/kernels/sort.rs
##########
@@ -487,24 +487,27 @@ where
len = limit.min(len);
}
if !descending {
- sort_by(&mut valids, len - nulls_len, |a, b| cmp(a.1, b.1));
+ sort_by(&mut valids, len.saturating_sub(nulls_len), |a, b| {
Review comment:
Looking at your diff I think one of us has misunderstood the expected behaviour. I think the result should be `ArrayData` truncated to the limit as if the full input was sorted, with some control over whether nulls are ordered before or after real 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.
For queries about this service, please contact Infrastructure at:
users@infra.apache.org
[GitHub] [arrow-rs] medwards commented on a change in pull request #236: sort_primitive result is capped to the min of limit or values.len
Posted by GitBox <gi...@apache.org>.
medwards commented on a change in pull request #236:
URL: https://github.com/apache/arrow-rs/pull/236#discussion_r623875155
##########
File path: arrow/src/compute/kernels/sort.rs
##########
@@ -487,24 +487,27 @@ where
len = limit.min(len);
}
if !descending {
- sort_by(&mut valids, len - nulls_len, |a, b| cmp(a.1, b.1));
+ sort_by(&mut valids, len.saturating_sub(nulls_len), |a, b| {
+ cmp(a.1, b.1)
+ });
} else {
- sort_by(&mut valids, len - nulls_len, |a, b| cmp(a.1, b.1).reverse());
+ sort_by(&mut valids, len.saturating_sub(nulls_len), |a, b| {
+ cmp(a.1, b.1).reverse()
+ });
// reverse to keep a stable ordering
nulls.reverse();
}
// collect results directly into a buffer instead of a vec to avoid another aligned allocation
- let mut result = MutableBuffer::new(values.len() * std::mem::size_of::<u32>());
+ let result_capacity = len * std::mem::size_of::<u32>();
+ let mut result = MutableBuffer::new(result_capacity);
// sets len to capacity so we can access the whole buffer as a typed slice
- result.resize(values.len() * std::mem::size_of::<u32>(), 0);
+ result.resize(result_capacity, 0);
let result_slice: &mut [u32] = result.typed_data_mut();
- debug_assert_eq!(result_slice.len(), nulls_len + valids_len);
Review comment:
I'm having difficulty imagining an alternative here, what did you have in mind?
`result_slice.len()` can now equal two values potentially: `values.len()` or `limit`. If it is the former then the old debug assert applies, but if it is the latter, it does not apply.
Alternatively we can make the size of `result_slice` always equal `values.len()`, this requires some changing some ranges further down (have to more carefully define start/end indices) and will result in an unnecessarily large result. I don't know if that's a big deal, I might have prematurely optimized by limiting the size of `result`.
--
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.
For queries about this service, please contact Infrastructure at:
users@infra.apache.org
[GitHub] [arrow-rs] codecov-commenter edited a comment on pull request #236: sort_primitive result is capped to the min of limit or values.len
Posted by GitBox <gi...@apache.org>.
codecov-commenter edited a comment on pull request #236:
URL: https://github.com/apache/arrow-rs/pull/236#issuecomment-829792438
# [Codecov](https://codecov.io/gh/apache/arrow-rs/pull/236?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 [#236](https://codecov.io/gh/apache/arrow-rs/pull/236?src=pr&el=desc&utm_medium=referral&utm_source=github&utm_content=comment&utm_campaign=pr+comments&utm_term=The+Apache+Software+Foundation) (e5840d7) into [master](https://codecov.io/gh/apache/arrow-rs/commit/d008f31b107c1030a1f5144c164e8ca8bf543576?el=desc&utm_medium=referral&utm_source=github&utm_content=comment&utm_campaign=pr+comments&utm_term=The+Apache+Software+Foundation) (d008f31) will **increase** coverage by `0.00%`.
> The diff coverage is `100.00%`.
[](https://codecov.io/gh/apache/arrow-rs/pull/236?src=pr&el=tree&utm_medium=referral&utm_source=github&utm_content=comment&utm_campaign=pr+comments&utm_term=The+Apache+Software+Foundation)
```diff
@@ Coverage Diff @@
## master #236 +/- ##
=======================================
Coverage 82.51% 82.52%
=======================================
Files 162 162
Lines 43655 43672 +17
=======================================
+ Hits 36022 36039 +17
Misses 7633 7633
```
| [Impacted Files](https://codecov.io/gh/apache/arrow-rs/pull/236?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/sort.rs](https://codecov.io/gh/apache/arrow-rs/pull/236/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-YXJyb3cvc3JjL2NvbXB1dGUva2VybmVscy9zb3J0LnJz) | `94.41% <100.00%> (+0.08%)` | :arrow_up: |
| [parquet/src/encodings/encoding.rs](https://codecov.io/gh/apache/arrow-rs/pull/236/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) | `94.86% <0.00%> (-0.20%)` | :arrow_down: |
| [arrow/src/array/transform/fixed\_binary.rs](https://codecov.io/gh/apache/arrow-rs/pull/236/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-YXJyb3cvc3JjL2FycmF5L3RyYW5zZm9ybS9maXhlZF9iaW5hcnkucnM=) | `84.21% <0.00%> (+5.26%)` | :arrow_up: |
------
[Continue to review full report at Codecov](https://codecov.io/gh/apache/arrow-rs/pull/236?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/236?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 [d008f31...e5840d7](https://codecov.io/gh/apache/arrow-rs/pull/236?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.
For queries about this service, please contact Infrastructure at:
users@infra.apache.org
[GitHub] [arrow-rs] alamb commented on a change in pull request #236: sort_primitive result is capped to the min of limit or values.len
Posted by GitBox <gi...@apache.org>.
alamb commented on a change in pull request #236:
URL: https://github.com/apache/arrow-rs/pull/236#discussion_r623248741
##########
File path: arrow/src/compute/kernels/sort.rs
##########
@@ -487,24 +487,27 @@ where
len = limit.min(len);
}
if !descending {
- sort_by(&mut valids, len - nulls_len, |a, b| cmp(a.1, b.1));
+ sort_by(&mut valids, len.saturating_sub(nulls_len), |a, b| {
Review comment:
Silently ignoring the case where ` nulls_len`is greater than the total length being sorted seems wrong to me.
It seems like the issue may be that `nulls_len` is not being updated correctly to take the limit into account. In other words if there is a limit the code should only look at the first `limit` rows to see if there are any nulls present.
I figured it might be easier to try this out myself than to try and explain it; Here is my proposed fix (to your fix) for your consideration: https://github.com/medwards/arrow-rs/pull/1
--
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.
For queries about this service, please contact Infrastructure at:
users@infra.apache.org
[GitHub] [arrow-rs] alamb commented on pull request #236: sort_primitive result is capped to the min of limit or values.len
Posted by GitBox <gi...@apache.org>.
alamb commented on pull request #236:
URL: https://github.com/apache/arrow-rs/pull/236#issuecomment-830606878
Thanks again @medwards !
--
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.
For queries about this service, please contact Infrastructure at:
users@infra.apache.org
[GitHub] [arrow-rs] jorgecarleitao commented on a change in pull request #236: sort_primitive result is capped to the min of limit or values.len
Posted by GitBox <gi...@apache.org>.
jorgecarleitao commented on a change in pull request #236:
URL: https://github.com/apache/arrow-rs/pull/236#discussion_r623568928
##########
File path: arrow/src/compute/kernels/sort.rs
##########
@@ -1556,6 +1559,28 @@ mod tests {
Some(3),
vec![Some(1.0), Some(2.0), Some(3.0)],
);
+
+ // limit that includes some extra nulls
+ test_sort_primitive_arrays::<Float64Type>(
Review comment:
I would try to test the 4 branches:
* `(len < null.count(), null_first)`
* `(len < null.count(), null_last)`
* `(len > null.count(), null_first)`
* `(len > null.count(), null_last)`
just to make sure we cover all of them correctly.
##########
File path: arrow/src/compute/kernels/sort.rs
##########
@@ -487,24 +487,27 @@ where
len = limit.min(len);
}
if !descending {
- sort_by(&mut valids, len - nulls_len, |a, b| cmp(a.1, b.1));
+ sort_by(&mut valids, len.saturating_sub(nulls_len), |a, b| {
+ cmp(a.1, b.1)
+ });
} else {
- sort_by(&mut valids, len - nulls_len, |a, b| cmp(a.1, b.1).reverse());
+ sort_by(&mut valids, len.saturating_sub(nulls_len), |a, b| {
+ cmp(a.1, b.1).reverse()
+ });
// reverse to keep a stable ordering
nulls.reverse();
}
// collect results directly into a buffer instead of a vec to avoid another aligned allocation
- let mut result = MutableBuffer::new(values.len() * std::mem::size_of::<u32>());
+ let result_capacity = len * std::mem::size_of::<u32>();
+ let mut result = MutableBuffer::new(result_capacity);
// sets len to capacity so we can access the whole buffer as a typed slice
- result.resize(values.len() * std::mem::size_of::<u32>(), 0);
+ result.resize(result_capacity, 0);
let result_slice: &mut [u32] = result.typed_data_mut();
- debug_assert_eq!(result_slice.len(), nulls_len + valids_len);
Review comment:
There is still some invariant around here (may not exactly this one). Should we still try to assert it, for readability purposes?
--
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.
For queries about this service, please contact Infrastructure at:
users@infra.apache.org
[GitHub] [arrow-rs] jorgecarleitao commented on a change in pull request #236: sort_primitive result is capped to the min of limit or values.len
Posted by GitBox <gi...@apache.org>.
jorgecarleitao commented on a change in pull request #236:
URL: https://github.com/apache/arrow-rs/pull/236#discussion_r624471262
##########
File path: arrow/src/compute/kernels/sort.rs
##########
@@ -487,24 +487,27 @@ where
len = limit.min(len);
}
if !descending {
- sort_by(&mut valids, len - nulls_len, |a, b| cmp(a.1, b.1));
+ sort_by(&mut valids, len.saturating_sub(nulls_len), |a, b| {
+ cmp(a.1, b.1)
+ });
} else {
- sort_by(&mut valids, len - nulls_len, |a, b| cmp(a.1, b.1).reverse());
+ sort_by(&mut valids, len.saturating_sub(nulls_len), |a, b| {
+ cmp(a.1, b.1).reverse()
+ });
// reverse to keep a stable ordering
nulls.reverse();
}
// collect results directly into a buffer instead of a vec to avoid another aligned allocation
- let mut result = MutableBuffer::new(values.len() * std::mem::size_of::<u32>());
+ let result_capacity = len * std::mem::size_of::<u32>();
+ let mut result = MutableBuffer::new(result_capacity);
// sets len to capacity so we can access the whole buffer as a typed slice
- result.resize(values.len() * std::mem::size_of::<u32>(), 0);
+ result.resize(result_capacity, 0);
let result_slice: &mut [u32] = result.typed_data_mut();
- debug_assert_eq!(result_slice.len(), nulls_len + valids_len);
Review comment:
You are right, sorry for the confusion.
--
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.
For queries about this service, please contact Infrastructure at:
users@infra.apache.org
[GitHub] [arrow-rs] codecov-commenter commented on pull request #236: sort_primitive result is capped to the min of limit or values.len
Posted by GitBox <gi...@apache.org>.
codecov-commenter commented on pull request #236:
URL: https://github.com/apache/arrow-rs/pull/236#issuecomment-829792438
# [Codecov](https://codecov.io/gh/apache/arrow-rs/pull/236?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 [#236](https://codecov.io/gh/apache/arrow-rs/pull/236?src=pr&el=desc&utm_medium=referral&utm_source=github&utm_content=comment&utm_campaign=pr+comments&utm_term=The+Apache+Software+Foundation) (7bc3523) into [master](https://codecov.io/gh/apache/arrow-rs/commit/d008f31b107c1030a1f5144c164e8ca8bf543576?el=desc&utm_medium=referral&utm_source=github&utm_content=comment&utm_campaign=pr+comments&utm_term=The+Apache+Software+Foundation) (d008f31) will **increase** coverage by `0.00%`.
> The diff coverage is `100.00%`.
[](https://codecov.io/gh/apache/arrow-rs/pull/236?src=pr&el=tree&utm_medium=referral&utm_source=github&utm_content=comment&utm_campaign=pr+comments&utm_term=The+Apache+Software+Foundation)
```diff
@@ Coverage Diff @@
## master #236 +/- ##
=======================================
Coverage 82.51% 82.51%
=======================================
Files 162 162
Lines 43655 43664 +9
=======================================
+ Hits 36022 36030 +8
- Misses 7633 7634 +1
```
| [Impacted Files](https://codecov.io/gh/apache/arrow-rs/pull/236?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/sort.rs](https://codecov.io/gh/apache/arrow-rs/pull/236/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-YXJyb3cvc3JjL2NvbXB1dGUva2VybmVscy9zb3J0LnJz) | `94.37% <100.00%> (+0.04%)` | :arrow_up: |
| [parquet/src/encodings/encoding.rs](https://codecov.io/gh/apache/arrow-rs/pull/236/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) | `94.86% <0.00%> (-0.20%)` | :arrow_down: |
------
[Continue to review full report at Codecov](https://codecov.io/gh/apache/arrow-rs/pull/236?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/236?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 [d008f31...7bc3523](https://codecov.io/gh/apache/arrow-rs/pull/236?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.
For queries about this service, please contact Infrastructure at:
users@infra.apache.org
[GitHub] [arrow-rs] alamb merged pull request #236: sort_primitive result is capped to the min of limit or values.len
Posted by GitBox <gi...@apache.org>.
alamb merged pull request #236:
URL: https://github.com/apache/arrow-rs/pull/236
--
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.
For queries about this service, please contact Infrastructure at:
users@infra.apache.org
[GitHub] [arrow-rs] alamb commented on a change in pull request #236: sort_primitive result is capped to the min of limit or values.len
Posted by GitBox <gi...@apache.org>.
alamb commented on a change in pull request #236:
URL: https://github.com/apache/arrow-rs/pull/236#discussion_r623307282
##########
File path: arrow/src/compute/kernels/sort.rs
##########
@@ -487,24 +487,27 @@ where
len = limit.min(len);
}
if !descending {
- sort_by(&mut valids, len - nulls_len, |a, b| cmp(a.1, b.1));
+ sort_by(&mut valids, len.saturating_sub(nulls_len), |a, b| {
Review comment:
🤔 I think you are right.... Let me take a closer look
--
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.
For queries about this service, please contact Infrastructure at:
users@infra.apache.org
[GitHub] [arrow-rs] medwards commented on a change in pull request #236: sort_primitive result is capped to the min of limit or values.len
Posted by GitBox <gi...@apache.org>.
medwards commented on a change in pull request #236:
URL: https://github.com/apache/arrow-rs/pull/236#discussion_r623871342
##########
File path: arrow/src/compute/kernels/sort.rs
##########
@@ -1556,6 +1559,28 @@ mod tests {
Some(3),
vec![Some(1.0), Some(2.0), Some(3.0)],
);
+
+ // limit that includes some extra nulls
+ test_sort_primitive_arrays::<Float64Type>(
Review comment:
Added
```
(len < null.count(), null_last)
(len > null.count(), null_first)
```
I believe the other new tests cover the remaining cases you mentioned.
--
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.
For queries about this service, please contact Infrastructure at:
users@infra.apache.org
[GitHub] [arrow-rs] alamb commented on pull request #236: sort_primitive result is capped to the min of limit or values.len
Posted by GitBox <gi...@apache.org>.
alamb commented on pull request #236:
URL: https://github.com/apache/arrow-rs/pull/236#issuecomment-829997007
BTW we are working on the `Dev PR / Process` failing check in #242
--
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.
For queries about this service, please contact Infrastructure at:
users@infra.apache.org