You are viewing a plain text version of this content. The canonical link for it is here.
Posted to github@arrow.apache.org by "felipecrv (via GitHub)" <gi...@apache.org> on 2024/01/27 02:34:17 UTC
[PR] GH-39815: [C++] Document and micro-optimize ChunkResolver::Resolve() [arrow]
felipecrv opened a new pull request, #39817:
URL: https://github.com/apache/arrow/pull/39817
### Rationale for this change
There has been interest in improving operations on chunked-arrays and even though `ChunkResolver::Resolve()` is not a big contributor in most kernels, the fact that it can be used from tight loops warrants careful attention to branch prediction and memory effects of its implementation.
### What changes are included in this PR?
- Documentation of invariants and behavior of functions
- Multiple optimizations justified by microbenchmarks
- Addition of a variation of `Resolve` that takes a hint as parameter
- Fix of an out-of-bounds memory access that doesn't affect correctness (it can only reduce effectiveness of cache in very rare situations, but is nevertheless an issue)
### Are these changes tested?
Yes, by existing tests.
### Are there any user-facing changes?
- The `arrow::internal::ChunkResolver::Bisect()` function was `protected` and is now `private` with a different signature
--
This is an automated message from the Apache Git Service.
To respond to the message, please log on to GitHub and use the
URL above to go to the specific comment.
To unsubscribe, e-mail: github-unsubscribe@arrow.apache.org
For queries about this service, please contact Infrastructure at:
users@infra.apache.org
Re: [PR] GH-39815: [C++] Document and micro-optimize ChunkResolver::Resolve() [arrow]
Posted by "ursabot (via GitHub)" <gi...@apache.org>.
ursabot commented on PR #39817:
URL: https://github.com/apache/arrow/pull/39817#issuecomment-1913538237
Benchmark runs are scheduled for commit a3923536046581ce9b1413b0a889ed50787db55d. Watch https://buildkite.com/apache-arrow and https://conbench.ursa.dev for updates. A comment will be posted here when the runs are complete.
--
This is an automated message from the Apache Git Service.
To respond to the message, please log on to GitHub and use the
URL above to go to the specific comment.
To unsubscribe, e-mail: github-unsubscribe@arrow.apache.org
For queries about this service, please contact Infrastructure at:
users@infra.apache.org
Re: [PR] GH-39815: [C++] Document and micro-optimize ChunkResolver::Resolve() [arrow]
Posted by "pitrou (via GitHub)" <gi...@apache.org>.
pitrou commented on code in PR #39817:
URL: https://github.com/apache/arrow/pull/39817#discussion_r1468807136
##########
cpp/src/arrow/compute/kernels/vector_sort.cc:
##########
@@ -748,11 +749,15 @@ class TableSorter {
auto& comparator = comparator_;
const auto& first_sort_key = sort_keys_[0];
+ ChunkLocation left_loc{0, 0};
+ ChunkLocation right_loc{0, 0};
std::merge(nulls_begin, nulls_middle, nulls_middle, nulls_end, temp_indices,
[&](uint64_t left, uint64_t right) {
// First column is either null or nan
- const auto left_loc = left_resolver_.Resolve(left);
- const auto right_loc = right_resolver_.Resolve(right);
+ left_loc =
+ left_resolver_.ResolveWithChunkIndexHint(left, left_loc.chunk_index);
Review Comment:
The point of this is to avoid all atomic accesses, right?
--
This is an automated message from the Apache Git Service.
To respond to the message, please log on to GitHub and use the
URL above to go to the specific comment.
To unsubscribe, e-mail: github-unsubscribe@arrow.apache.org
For queries about this service, please contact Infrastructure at:
users@infra.apache.org
Re: [PR] GH-39815: [C++] Document and micro-optimize ChunkResolver::Resolve() [arrow]
Posted by "felipecrv (via GitHub)" <gi...@apache.org>.
felipecrv commented on PR #39817:
URL: https://github.com/apache/arrow/pull/39817#issuecomment-1914768598
> There are nice chunked Sort and Rank performance improvements on the ARM64 benchmark machines. Thank you!
Nice numbers indeed! 🚀
<img width="1350" alt="Screenshot 2024-01-29 at 11 05 10" src="https://github.com/apache/arrow/assets/207795/e751c797-dc5d-4f47-9cdb-d810d9686bb8">
https://conbench.ursa.dev/compare/runs/1d47651f96e0468283cec3367674f7a4...5c59b6b2d4fe4a5ea599d5685fb5102b/
--
This is an automated message from the Apache Git Service.
To respond to the message, please log on to GitHub and use the
URL above to go to the specific comment.
To unsubscribe, e-mail: github-unsubscribe@arrow.apache.org
For queries about this service, please contact Infrastructure at:
users@infra.apache.org
Re: [PR] GH-39815: [C++] Document and micro-optimize ChunkResolver::Resolve() [arrow]
Posted by "felipecrv (via GitHub)" <gi...@apache.org>.
felipecrv commented on PR #39817:
URL: https://github.com/apache/arrow/pull/39817#issuecomment-1912926168
@amol- @pitrou @js8544
--
This is an automated message from the Apache Git Service.
To respond to the message, please log on to GitHub and use the
URL above to go to the specific comment.
To unsubscribe, e-mail: github-unsubscribe@arrow.apache.org
For queries about this service, please contact Infrastructure at:
users@infra.apache.org
Re: [PR] GH-39815: [C++] Document and micro-optimize ChunkResolver::Resolve() [arrow]
Posted by "pitrou (via GitHub)" <gi...@apache.org>.
pitrou commented on PR #39817:
URL: https://github.com/apache/arrow/pull/39817#issuecomment-1913538216
@ursabot please 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
Re: [PR] GH-39815: [C++] Document and micro-optimize ChunkResolver::Resolve() [arrow]
Posted by "felipecrv (via GitHub)" <gi...@apache.org>.
felipecrv commented on PR #39817:
URL: https://github.com/apache/arrow/pull/39817#issuecomment-1912925883
Benchmarks of `sort` and `rank` on chunked arrays -- heavy users of `ChunkResolver`. 3 measurements after roughly every change to give an idea of level of noise. The purple group (`bounds-check-fix`) is when I fixed the out-of-bounds access bug that exists on `main` (not introduced by me in the optimizations). After that, the other two groups bring improvements that bring the throughput back to what was achieved before the bounds check.

Ideas that were tried and didn't make a difference or made throughput worse:
- Removing the use of `std::atomic` completely, relaxed atomic operations are enough (which is good because that could introduce bugs)
- Starting the `Bisect` on different ranges depending on the results of the branches
[1] `ninja arrow-compute-vector-sort-benchmark && ./**/arrow-compute-vector-sort-benchmark --benchmark_filter="ChunkedArray(Sort|Rank).*Int64.*65536/100(/tiebreaker:2|$)" --benchmark_out_format=csv`
--
This is an automated message from the Apache Git Service.
To respond to the message, please log on to GitHub and use the
URL above to go to the specific comment.
To unsubscribe, e-mail: github-unsubscribe@arrow.apache.org
For queries about this service, please contact Infrastructure at:
users@infra.apache.org
Re: [PR] GH-39815: [C++] Document and micro-optimize ChunkResolver::Resolve() [arrow]
Posted by "felipecrv (via GitHub)" <gi...@apache.org>.
felipecrv merged PR #39817:
URL: https://github.com/apache/arrow/pull/39817
--
This is an automated message from the Apache Git Service.
To respond to the message, please log on to GitHub and use the
URL above to go to the specific comment.
To unsubscribe, e-mail: github-unsubscribe@arrow.apache.org
For queries about this service, please contact Infrastructure at:
users@infra.apache.org
Re: [PR] GH-39815: [C++] Document and micro-optimize ChunkResolver::Resolve() [arrow]
Posted by "conbench-apache-arrow[bot] (via GitHub)" <gi...@apache.org>.
conbench-apache-arrow[bot] commented on PR #39817:
URL: https://github.com/apache/arrow/pull/39817#issuecomment-1913578559
Thanks for your patience. Conbench analyzed the 5 benchmarking runs that have been run so far on PR commit a3923536046581ce9b1413b0a889ed50787db55d.
There was 1 benchmark result indicating a performance regression:
- Pull Request Run on `ursa-i9-9960x` at [2024-01-28 10:03:30Z](https://conbench.ursa.dev/compare/runs/85ea0563c38a40d8b9ac47a521a10972...df2d305078464b599d9a45e17d079dd9/)
- [`tpch` (R) with engine=arrow, format=native, language=R, memory_map=False, query_id=TPCH-16, scale_factor=1](https://conbench.ursa.dev/compare/benchmarks/065aec70414a716180002a29f77f5855...065b63eca760728a80003847b5a406bb)
The [full Conbench report](https://github.com/apache/arrow/runs/20943699540) has more details.
--
This is an automated message from the Apache Git Service.
To respond to the message, please log on to GitHub and use the
URL above to go to the specific comment.
To unsubscribe, e-mail: github-unsubscribe@arrow.apache.org
For queries about this service, please contact Infrastructure at:
users@infra.apache.org
Re: [PR] GH-39815: [C++] Document and micro-optimize ChunkResolver::Resolve() [arrow]
Posted by "felipecrv (via GitHub)" <gi...@apache.org>.
felipecrv commented on code in PR #39817:
URL: https://github.com/apache/arrow/pull/39817#discussion_r1468892601
##########
cpp/src/arrow/compute/kernels/vector_sort.cc:
##########
@@ -748,11 +749,15 @@ class TableSorter {
auto& comparator = comparator_;
const auto& first_sort_key = sort_keys_[0];
+ ChunkLocation left_loc{0, 0};
+ ChunkLocation right_loc{0, 0};
std::merge(nulls_begin, nulls_middle, nulls_middle, nulls_end, temp_indices,
[&](uint64_t left, uint64_t right) {
// First column is either null or nan
- const auto left_loc = left_resolver_.Resolve(left);
- const auto right_loc = right_resolver_.Resolve(right);
+ left_loc =
+ left_resolver_.ResolveWithChunkIndexHint(left, left_loc.chunk_index);
Review Comment:
Memory access really: keeping the `ChunkLocation::chunk_index` in registers throughout the loop -- of course it depends on the register allocation and inlining of `ResolveWithChunkIndexHint`. It improved the sort benchmarks slightly.
--
This is an automated message from the Apache Git Service.
To respond to the message, please log on to GitHub and use the
URL above to go to the specific comment.
To unsubscribe, e-mail: github-unsubscribe@arrow.apache.org
For queries about this service, please contact Infrastructure at:
users@infra.apache.org
Re: [PR] GH-39815: [C++] Document and micro-optimize ChunkResolver::Resolve() [arrow]
Posted by "conbench-apache-arrow[bot] (via GitHub)" <gi...@apache.org>.
conbench-apache-arrow[bot] commented on PR #39817:
URL: https://github.com/apache/arrow/pull/39817#issuecomment-1915086023
After merging your PR, Conbench analyzed the 5 benchmarking runs that have been run so far on merge-commit 2fa095c8393a9ff54fcf84c52f47f75152243b1e.
There were no benchmark performance regressions. 🎉
The [full Conbench report](https://github.com/apache/arrow/runs/20980726428) has more details. It also includes information about 132 possible false positives for unstable benchmarks that are known to sometimes produce them.
--
This is an automated message from the Apache Git Service.
To respond to the message, please log on to GitHub and use the
URL above to go to the specific comment.
To unsubscribe, e-mail: github-unsubscribe@arrow.apache.org
For queries about this service, please contact Infrastructure at:
users@infra.apache.org
Re: [PR] GH-39815: [C++] Document and micro-optimize ChunkResolver::Resolve() [arrow]
Posted by "pitrou (via GitHub)" <gi...@apache.org>.
pitrou commented on PR #39817:
URL: https://github.com/apache/arrow/pull/39817#issuecomment-1913538163
+1 on the principle, looks like a nice improvement.
--
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