You are viewing a plain text version of this content. The canonical link for it is here.
Posted to github@arrow.apache.org by "alamb (via GitHub)" <gi...@apache.org> on 2023/07/13 14:49:30 UTC
[GitHub] [arrow-datafusion] alamb opened a new pull request, #6954: Allow better vectorization in accumulate functions
alamb opened a new pull request, #6954:
URL: https://github.com/apache/arrow-datafusion/pull/6954
Draft as I am running performance tests and will clean up the code a bit if possible.
# Which issue does this PR close?
Part of https://github.com/apache/arrow-datafusion/issues/6889
This is a follow on to https://github.com/apache/arrow-datafusion/pull/6904 where some last minute changes (to track null state correctly) decreased performance slightly -- I am trying to get some back
# Rationale for this change
I am trying to help the compiler to vectorize the inner loops of the accumulators. Let's do this by doing the minimal work as possible
# What changes are included in this PR?
Update null state with a separate loop
<!--
There is no need to duplicate the description in the issue here but it is sometimes worth providing a summary of the individual changes in this PR.
-->
# Are these changes tested?
covered by existing tests
<!--
We typically require tests for all PRs in order to:
1. Prevent the code from being accidentally broken by subsequent changes
2. Serve as another way to document the expected behavior of the code
If tests are not included in your PR, please explain why (for example, are they covered by existing tests)?
-->
# Are there any user-facing changes?
<!--
If there are user-facing changes then we may require documentation to be updated before approving the PR.
-->
<!--
If there are any breaking changes to public APIs, please add the `api change` label.
-->
--
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-datafusion] alamb commented on a diff in pull request #6954: Allow better vectorization in accumulate functions
Posted by "alamb (via GitHub)" <gi...@apache.org>.
alamb commented on code in PR #6954:
URL: https://github.com/apache/arrow-datafusion/pull/6954#discussion_r1262676664
##########
datafusion/physical-expr/src/aggregate/groups_accumulator/accumulate.rs:
##########
@@ -139,10 +139,14 @@ impl NullState {
// no nulls, no filter,
(false, None) => {
let iter = group_indices.iter().zip(data.iter());
+
for (&group_index, &new_value) in iter {
- seen_values.set_bit(group_index, true);
value_fn(group_index, new_value);
}
+ // update seen values in separate loop
Review Comment:
the idea is to use a separate loop
Note we can skip this update entirely once all the groups have been seen -- I will explore if I can figure out how to do that next.
--
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-datafusion] alamb commented on pull request #6954: Improve grouping performance via better vectorization in accumulate functions
Posted by "alamb (via GitHub)" <gi...@apache.org>.
alamb commented on PR #6954:
URL: https://github.com/apache/arrow-datafusion/pull/6954#issuecomment-1647697329
Tracking this basic idea in https://github.com/apache/arrow-datafusion/issues/7066 , I don't plan ti pursue this PR anymore for now
--
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-datafusion] alamb commented on pull request #6954: Improve grouping performance via better vectorization in accumulate functions
Posted by "alamb (via GitHub)" <gi...@apache.org>.
alamb commented on PR #6954:
URL: https://github.com/apache/arrow-datafusion/pull/6954#issuecomment-1635876295
> Noise maybe? Your previous run seems to have some noisy results as well.
> I only get relatively relatively stable perf results by closing all browsers / IDEs etc.
Yeah, I am trying to control for noise by running these experiments on a GCP machine (not my laptop) ๐ค
--
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-datafusion] alamb commented on a diff in pull request #6954: Allow better vectorization in accumulate functions
Posted by "alamb (via GitHub)" <gi...@apache.org>.
alamb commented on code in PR #6954:
URL: https://github.com/apache/arrow-datafusion/pull/6954#discussion_r1262835648
##########
datafusion/physical-expr/src/aggregate/groups_accumulator/accumulate.rs:
##########
@@ -139,10 +139,14 @@ impl NullState {
// no nulls, no filter,
(false, None) => {
let iter = group_indices.iter().zip(data.iter());
+
for (&group_index, &new_value) in iter {
- seen_values.set_bit(group_index, true);
value_fn(group_index, new_value);
}
+ // update seen values in separate loop
+ for &group_index in group_indices.iter() {
+ seen_values.set_bit(group_index, true);
Review Comment:
That is an excellent point. I will try and take that into account
--
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-datafusion] alamb closed pull request #6954: Improve grouping performance via better vectorization in accumulate functions
Posted by "alamb (via GitHub)" <gi...@apache.org>.
alamb closed pull request #6954: Improve grouping performance via better vectorization in accumulate functions
URL: https://github.com/apache/arrow-datafusion/pull/6954
--
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-datafusion] alamb commented on pull request #6954: Allow better vectorization in accumulate functions
Posted by "alamb (via GitHub)" <gi...@apache.org>.
alamb commented on PR #6954:
URL: https://github.com/apache/arrow-datafusion/pull/6954#issuecomment-1634591961
This shows a little benefit bit maybe in the noise range
```
โโโโโโโโโโโโโโโโณโโโโโโโโโโโโณโโโโโโโโโโโโโโโโโโโโโโโโณโโโโโโโโโโโโโโโโ
โ Query โ main_base โ alamb_faster_grouping โ Change โ
โกโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโฉ
โ QQuery 1 โ 560.29ms โ 533.10ms โ no change โ
โ QQuery 2 โ 174.72ms โ 162.55ms โ +1.07x faster โ
โ QQuery 3 โ 167.44ms โ 161.30ms โ no change โ
โ QQuery 4 โ 119.56ms โ 117.52ms โ no change โ
โ QQuery 5 โ 394.33ms โ 400.22ms โ no change โ
โ QQuery 6 โ 45.54ms โ 40.08ms โ +1.14x faster โ
โ QQuery 7 โ 849.06ms โ 837.12ms โ no change โ
โ QQuery 8 โ 258.03ms โ 247.16ms โ no change โ
โ QQuery 9 โ 595.82ms โ 566.07ms โ no change โ
โ QQuery 10 โ 341.31ms โ 337.04ms โ no change โ
โ QQuery 11 โ 170.28ms โ 159.25ms โ +1.07x faster โ
โ QQuery 12 โ 175.19ms โ 173.80ms โ no change โ
โ QQuery 13 โ 331.46ms โ 315.21ms โ no change โ
โ QQuery 14 โ 48.67ms โ 49.25ms โ no change โ
โ QQuery 15 โ 59.04ms โ 50.88ms โ +1.16x faster โ
โ QQuery 16 โ 164.45ms โ 164.20ms โ no change โ
โ QQuery 17 โ 966.84ms โ 873.41ms โ +1.11x faster โ
โ QQuery 18 โ 1676.43ms โ 1637.90ms โ no change โ
โ QQuery 19 โ 166.95ms โ 167.24ms โ no change โ
โ QQuery 20 โ 313.92ms โ 313.73ms โ no change โ
โ QQuery 21 โ 1062.69ms โ 1060.65ms โ no change โ
โ QQuery 22 โ 88.17ms โ 93.33ms โ 1.06x slower โ
โโโโโโโโโโโโโโโโดโโโโโโโโโโโโดโโโโโโโโโโโโโโโโโโโโโโโโดโโโโโโโโโโโโโโโโ
```
--
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-datafusion] alamb commented on pull request #6954: Allow better vectorization in accumulate functions
Posted by "alamb (via GitHub)" <gi...@apache.org>.
alamb commented on PR #6954:
URL: https://github.com/apache/arrow-datafusion/pull/6954#issuecomment-1634767978
I am now benchmarking the special case of "don't track nulls they can't possibly be present
--
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-datafusion] Dandandan commented on a diff in pull request #6954: Allow better vectorization in accumulate functions
Posted by "Dandandan (via GitHub)" <gi...@apache.org>.
Dandandan commented on code in PR #6954:
URL: https://github.com/apache/arrow-datafusion/pull/6954#discussion_r1262819183
##########
datafusion/physical-expr/src/aggregate/groups_accumulator/accumulate.rs:
##########
@@ -139,10 +139,14 @@ impl NullState {
// no nulls, no filter,
(false, None) => {
let iter = group_indices.iter().zip(data.iter());
+
for (&group_index, &new_value) in iter {
- seen_values.set_bit(group_index, true);
value_fn(group_index, new_value);
}
+ // update seen values in separate loop
+ for &group_index in group_indices.iter() {
+ seen_values.set_bit(group_index, true);
Review Comment:
Can't we assume `seen_values` is true for every group_index for "no nulls, no filter" until we observed a first null-value?
--
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-datafusion] Dandandan commented on a diff in pull request #6954: Allow better vectorization in accumulate functions
Posted by "Dandandan (via GitHub)" <gi...@apache.org>.
Dandandan commented on code in PR #6954:
URL: https://github.com/apache/arrow-datafusion/pull/6954#discussion_r1262819183
##########
datafusion/physical-expr/src/aggregate/groups_accumulator/accumulate.rs:
##########
@@ -139,10 +139,14 @@ impl NullState {
// no nulls, no filter,
(false, None) => {
let iter = group_indices.iter().zip(data.iter());
+
for (&group_index, &new_value) in iter {
- seen_values.set_bit(group_index, true);
value_fn(group_index, new_value);
}
+ // update seen values in separate loop
+ for &group_index in group_indices.iter() {
+ seen_values.set_bit(group_index, true);
Review Comment:
Can't we assume `seen_values` is true for "no nulls, no filter" until we observed a first null-value?
--
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-datafusion] alamb commented on pull request #6954: Improve grouping performance via better vectorization in accumulate functions
Posted by "alamb (via GitHub)" <gi...@apache.org>.
alamb commented on PR #6954:
URL: https://github.com/apache/arrow-datafusion/pull/6954#issuecomment-1635709082
Special casing the nulls seems to have helped a little, though the fact that some queries now report slower is surprising to me
```
โโโโโโโโโโโโโโโโณโโโโโโโโโโโโณโโโโโโโโโโโโโโโโโโโโโโโโณโโโโโโโโโโโโโโโโ
โ Query โ main_base โ alamb_faster_grouping โ Change โ
โกโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโฉ
โ QQuery 1 โ 574.53ms โ 522.95ms โ +1.10x faster โ
โ QQuery 2 โ 168.33ms โ 152.40ms โ +1.10x faster โ
โ QQuery 3 โ 173.45ms โ 182.54ms โ 1.05x slower โ
โ QQuery 4 โ 116.60ms โ 116.16ms โ no change โ
โ QQuery 5 โ 402.46ms โ 405.81ms โ no change โ
โ QQuery 6 โ 45.04ms โ 41.94ms โ +1.07x faster โ
โ QQuery 7 โ 922.93ms โ 916.25ms โ no change โ
โ QQuery 8 โ 255.73ms โ 240.93ms โ +1.06x faster โ
โ QQuery 9 โ 577.15ms โ 554.53ms โ no change โ
โ QQuery 10 โ 318.40ms โ 330.10ms โ no change โ
โ QQuery 11 โ 167.56ms โ 172.50ms โ no change โ
โ QQuery 12 โ 174.26ms โ 177.85ms โ no change โ
โ QQuery 13 โ 324.26ms โ 320.80ms โ no change โ
โ QQuery 14 โ 48.11ms โ 48.24ms โ no change โ
โ QQuery 15 โ 54.18ms โ 57.05ms โ 1.05x slower โ
โ QQuery 16 โ 164.83ms โ 168.32ms โ no change โ
โ QQuery 17 โ 897.29ms โ 877.01ms โ no change โ
โ QQuery 18 โ 1672.32ms โ 1675.61ms โ no change โ
โ QQuery 19 โ 179.13ms โ 166.64ms โ +1.07x faster โ
โ QQuery 20 โ 324.28ms โ 324.27ms โ no change โ
โ QQuery 21 โ 1147.35ms โ 1177.47ms โ no change โ
โ QQuery 22 โ 93.86ms โ 91.11ms โ no change โ
```
--
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-datafusion] Dandandan commented on pull request #6954: Improve grouping performance via better vectorization in accumulate functions
Posted by "Dandandan (via GitHub)" <gi...@apache.org>.
Dandandan commented on PR #6954:
URL: https://github.com/apache/arrow-datafusion/pull/6954#issuecomment-1635760468
Noise maybe? Your previous run seems to have some noisy results as well.
I only get relatively relatively stable perf results by closing all browsers / IDEs etc.
--
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