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/09/04 15:04:31 UTC
[PR] [C++] [arrow]
felipecrv opened a new pull request, #43954:
URL: https://github.com/apache/arrow/pull/43954
### Rationale for this change
Improve tests and add benchmarks. I wrote the tests and benchmarks while trying to improve the performance of `ResolveMany` and failing at it.
### What changes are included in this PR?
Tests, benchmarks, and changes that don't really affect performance but might unlock more optimization opportunities in the future.
### Are these changes tested?
Yes.
--
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-43953: [C++] Add tests based on random data and benchmarks to ChunkResolver::ResolveMany [arrow]
Posted by "felipecrv (via GitHub)" <gi...@apache.org>.
felipecrv commented on PR #43954:
URL: https://github.com/apache/arrow/pull/43954#issuecomment-2329612449
> There are a number of CI failures that need fixing.
TIL `uniform_int_distribution` can't take `(u)int8_t` as type parameter on MSVC builds.
--
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-43953: [C++] Add tests based on random data and benchmarks to ChunkResolver::ResolveMany [arrow]
Posted by "pitrou (via GitHub)" <gi...@apache.org>.
pitrou commented on PR #43954:
URL: https://github.com/apache/arrow/pull/43954#issuecomment-2371262208
Just a question: do you mean to keep the 64-bit to 32-bit chunk index 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
Re: [PR] GH-43953: [C++] Add tests based on random data and benchmarks to ChunkResolver::ResolveMany [arrow]
Posted by "github-actions[bot] (via GitHub)" <gi...@apache.org>.
github-actions[bot] commented on PR #43954:
URL: https://github.com/apache/arrow/pull/43954#issuecomment-2329317109
:warning: GitHub issue #43953 **has been automatically assigned in GitHub** to PR creator.
--
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-43953: [C++] Add tests based on random data and benchmarks to ChunkResolver::ResolveMany [arrow]
Posted by "felipecrv (via GitHub)" <gi...@apache.org>.
felipecrv commented on code in PR #43954:
URL: https://github.com/apache/arrow/pull/43954#discussion_r1744106248
##########
cpp/src/arrow/chunked_array_test.cc:
##########
@@ -373,10 +374,27 @@ TEST(TestChunkResolver, Resolve) {
ASSERT_EQ(resolver.Resolve(10).chunk_index, 3);
}
+template <class RNG>
+std::vector<int64_t> GenChunkedArrayOffsets(RNG& rng, int32_t num_chunks,
+ int64_t chunked_array_len) {
+ std::uniform_int_distribution<int64_t> offset_gen(1, chunked_array_len - 1);
+ std::vector<int64_t> offsets;
+ offsets.reserve(num_chunks + 1);
+ offsets.push_back(0);
+ while (offsets.size() < static_cast<size_t>(num_chunks)) {
+ offsets.push_back(offset_gen(rng));
+ }
+ offsets.push_back(chunked_array_len);
+ std::sort(offsets.begin() + 1, offsets.end());
+ return offsets;
+}
+
template <typename T>
class TestChunkResolverMany : public ::testing::Test {
public:
using IndexType = T;
+ static constexpr int32_t kMaxInt32 = std::numeric_limits<int32_t>::max();
+ static constexpr size_t kMaxValidIndex = std::numeric_limits<IndexType>::max();
Review Comment:
True. Let me fix this.
--
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-43953: [C++] Add tests based on random data and benchmarks to ChunkResolver::ResolveMany [arrow]
Posted by "pitrou (via GitHub)" <gi...@apache.org>.
pitrou merged PR #43954:
URL: https://github.com/apache/arrow/pull/43954
--
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-43953: [C++] Add tests based on random data and benchmarks to ChunkResolver::ResolveMany [arrow]
Posted by "felipecrv (via GitHub)" <gi...@apache.org>.
felipecrv commented on PR #43954:
URL: https://github.com/apache/arrow/pull/43954#issuecomment-2369722907
@pitrou now it's all green. The only failure is unrelated.
--
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-43953: [C++] Add tests based on random data and benchmarks to ChunkResolver::ResolveMany [arrow]
Posted by "pitrou (via GitHub)" <gi...@apache.org>.
pitrou commented on PR #43954:
URL: https://github.com/apache/arrow/pull/43954#issuecomment-2329388308
Ironically, uint32 seems slightly slower than both uint16 and uint64. Not sure that's due to the compiler or to the CPU.
--
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-43953: [C++] Add tests based on random data and benchmarks to ChunkResolver::ResolveMany [arrow]
Posted by "pitrou (via GitHub)" <gi...@apache.org>.
pitrou commented on PR #43954:
URL: https://github.com/apache/arrow/pull/43954#issuecomment-2346281570
> The `chunk_hint` stuff really works. I forgot to plot it, but without it the throughput gains don't exist when indices are sorted.
Yes, it's also quite dramatic for the actual Sort implementation :-)
--
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-43953: [C++] Add tests based on random data and benchmarks to ChunkResolver::ResolveMany [arrow]
Posted by "felipecrv (via GitHub)" <gi...@apache.org>.
felipecrv commented on PR #43954:
URL: https://github.com/apache/arrow/pull/43954#issuecomment-2371844257
> Just a question: do you mean to keep the 64-bit to 32-bit chunk index change?
Yes I do.
--
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-43953: [C++] Add tests based on random data and benchmarks to ChunkResolver::ResolveMany [arrow]
Posted by "conbench-apache-arrow[bot] (via GitHub)" <gi...@apache.org>.
conbench-apache-arrow[bot] commented on PR #43954:
URL: https://github.com/apache/arrow/pull/43954#issuecomment-2372491212
After merging your PR, Conbench analyzed the 3 benchmarking runs that have been run so far on merge-commit 83f35de2ebe4672d0d57290840d0153ac8a016e8.
There were no benchmark performance regressions. 🎉
The [full Conbench report](https://github.com/apache/arrow/runs/30612872044) has more details. It also includes information about 16 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-43953: [C++] Add tests based on random data and benchmarks to ChunkResolver::ResolveMany [arrow]
Posted by "felipecrv (via GitHub)" <gi...@apache.org>.
felipecrv commented on PR #43954:
URL: https://github.com/apache/arrow/pull/43954#issuecomment-2329562976
> Ironically, uint32 seems slightly slower than both uint16 and uint64. Not sure that's due to the compiler or to the CPU.
Same on `12th Gen Intel(R) Core(TM) i7-12800H`. This is the reason I changed `lo` and `hi` to `uint32_t` and nothing changed in the benchmarks.
Things are saner on the Apple M1 Pro with 32-bit being the fastest.
```
Run on (8 X 24 MHz CPU s)
CPU Caches:
L1 Data 64 KiB
L1 Instruction 128 KiB
L2 Unified 4096 KiB (x8)
Load Average: 14.23, 6.75, 4.28
------------------------------------------------------------------------------------------------
Benchmark Time CPU Iterations UserCounters...
------------------------------------------------------------------------------------------------
ResolveManyUInt16Random/65535/100/508 2769 ns 2747 ns 252543 items_per_second=184.959M/s logical_len=65.535k num_chunks=100
ResolveManyUInt32Random/65535/100/508 2715 ns 2689 ns 257431 items_per_second=188.93M/s logical_len=65.535k num_chunks=100
ResolveManyUInt64Random/65535/100/508 2928 ns 2757 ns 252188 items_per_second=184.281M/s logical_len=65.535k num_chunks=100
ResolveManyUInt16Sorted/65535/100/508 1023 ns 1012 ns 693694 items_per_second=501.751M/s logical_len=65.535k num_chunks=100
ResolveManyUInt32Sorted/65535/100/508 929 ns 920 ns 761052 items_per_second=551.881M/s logical_len=65.535k num_chunks=100
ResolveManyUInt64Sorted/65535/100/508 933 ns 926 ns 759878 items_per_second=548.86M/s logical_len=65.535k num_chunks=100
```
--
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-43953: [C++] Add tests based on random data and benchmarks to ChunkResolver::ResolveMany [arrow]
Posted by "felipecrv (via GitHub)" <gi...@apache.org>.
felipecrv commented on code in PR #43954:
URL: https://github.com/apache/arrow/pull/43954#discussion_r1744110158
##########
cpp/src/arrow/chunk_resolver_benchmark.cc:
##########
@@ -0,0 +1,166 @@
+// Licensed to the Apache Software Foundation (ASF) under one
+// or more contributor license agreements. See the NOTICE file
+// distributed with this work for additional information
+// regarding copyright ownership. The ASF licenses this file
+// to you under the Apache License, Version 2.0 (the
+// "License"); you may not use this file except in compliance
+// with the License. You may obtain a copy of the License at
+//
+// http://www.apache.org/licenses/LICENSE-2.0
+//
+// Unless required by applicable law or agreed to in writing,
+// software distributed under the License is distributed on an
+// "AS IS" BASIS, WITHOUT WARRANTIES OR CONDITIONS OF ANY
+// KIND, either express or implied. See the License for the
+// specific language governing permissions and limitations
+// under the License.
+
+#include "benchmark/benchmark.h"
+
+#include <algorithm>
+#include <cstdint>
+#include <random>
+#include <vector>
+
+#include "arrow/chunk_resolver.h"
+#include "arrow/util/benchmark_util.h"
+#include "arrow/util/pcg_random.h"
+
+namespace arrow {
+
+using internal::ChunkResolver;
+using internal::TypedChunkLocation;
+
+namespace {
+
+int64_t constexpr kChunkedArrayLength = std::numeric_limits<uint16_t>::max();
+
+struct ResolveManyBenchmark {
+ benchmark::State& state;
+ random::pcg64 rng;
+ // Values from the state.range(i)
+ int64_t chunked_array_length;
+ int32_t num_chunks;
+ int64_t num_logical_indices;
+
+ explicit ResolveManyBenchmark(benchmark::State& state)
+ : state(state),
+ rng(42),
+ chunked_array_length(state.range(0)),
+ num_chunks(static_cast<int32_t>(state.range(1))),
+ num_logical_indices(state.range(2)) {}
+
+ std::vector<int64_t> GenChunkedArrayOffsets() {
+ std::uniform_int_distribution<int64_t> offset_gen(1, chunked_array_length);
+ std::vector<int64_t> offsets;
+ offsets.reserve(num_chunks + 1);
+ offsets.push_back(0);
+ while (offsets.size() < static_cast<size_t>(num_chunks)) {
+ offsets.push_back(offset_gen(rng));
+ }
+ offsets.push_back(chunked_array_length);
+ std::sort(offsets.begin() + 1, offsets.end());
+ return offsets;
+ }
+
+ template <typename IndexType>
+ std::vector<IndexType> GenRandomIndices(IndexType max_index, bool sorted) {
+ std::uniform_int_distribution<IndexType> index_gen(0, max_index);
+ std::vector<IndexType> indices;
+ indices.reserve(num_logical_indices);
+ while (indices.size() < static_cast<size_t>(num_logical_indices)) {
+ indices.push_back(index_gen(rng));
+ }
+ if (sorted) {
+ std::sort(indices.begin(), indices.end());
+ }
+ return indices;
+ }
+
+ template <typename IndexType>
+ void Bench(bool sorted) {
+ if constexpr (sizeof(IndexType) < 8) {
+ constexpr uint64_t kLimitIndex = std::numeric_limits<IndexType>::max();
+ ARROW_CHECK_LE(static_cast<uint64_t>(chunked_array_length), kLimitIndex);
+ }
+ const auto max_random_index = static_cast<IndexType>(chunked_array_length);
+ auto offsets = GenChunkedArrayOffsets();
+ auto logical_indices = GenRandomIndices<IndexType>(max_random_index, sorted);
+ ChunkResolver resolver(std::move(offsets));
+ std::vector<TypedChunkLocation<IndexType>> chunk_location_vec(num_logical_indices);
+ BENCHMARK_UNUSED bool all_succeeded = true;
+ for (auto _ : state) {
+ const bool success = resolver.ResolveMany<IndexType>(
+ num_logical_indices, logical_indices.data(), chunk_location_vec.data());
+ all_succeeded &= success;
+ }
+ ARROW_CHECK(all_succeeded);
+ state.counters["logical_len"] = static_cast<double>(chunked_array_length);
+ state.counters["num_chunks"] = static_cast<double>(num_chunks);
+ state.SetItemsProcessed(state.iterations() * num_logical_indices);
+ }
+};
+
+template <typename IndexType>
+void ResolveManySetArgs(benchmark::internal::Benchmark* bench) {
+ constexpr int32_t kNonAligned = 3;
+ const int64_t kNumIndicesFew = (kChunkedArrayLength >> 7) - kNonAligned;
+ const int64_t kNumIndicesMany = (kChunkedArrayLength >> 1) - kNonAligned;
+
+ switch (sizeof(IndexType)) {
+ case 1:
+ // Unexpected. See comments below.
+ case 2:
+ case 4:
+ case 8:
+ bench->Args({kChunkedArrayLength, /*num_chunks*/ 10000, kNumIndicesFew});
Review Comment:
The huge number is necessary (even though it's a bit unrealistic) to measure how effective the binary search is at reducing the search space (proportional to the number of chunks).
--
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-43953: [C++] Add tests based on random data and benchmarks to ChunkResolver::ResolveMany [arrow]
Posted by "felipecrv (via GitHub)" <gi...@apache.org>.
felipecrv commented on code in PR #43954:
URL: https://github.com/apache/arrow/pull/43954#discussion_r1744101619
##########
cpp/src/arrow/chunked_array.cc:
##########
@@ -55,7 +55,7 @@ ChunkedArray::ChunkedArray(ArrayVector chunks, std::shared_ptr<DataType> type)
<< "cannot construct ChunkedArray from empty vector and omitted type";
type_ = chunks_[0]->type();
}
-
+ ARROW_CHECK_LE(chunks.size(), std::numeric_limits<int>::max());
Review Comment:
This is useful in ensuring we are not generating more chunks than can be addressed by the index type.
--
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] [C++] [arrow]
Posted by "github-actions[bot] (via GitHub)" <gi...@apache.org>.
github-actions[bot] commented on PR #43954:
URL: https://github.com/apache/arrow/pull/43954#issuecomment-2329314781
<!--
Licensed to the Apache Software Foundation (ASF) under one
or more contributor license agreements. See the NOTICE file
distributed with this work for additional information
regarding copyright ownership. The ASF licenses this file
to you under the Apache License, Version 2.0 (the
"License"); you may not use this file except in compliance
with the License. You may obtain a copy of the License at
http://www.apache.org/licenses/LICENSE-2.0
Unless required by applicable law or agreed to in writing,
software distributed under the License is distributed on an
"AS IS" BASIS, WITHOUT WARRANTIES OR CONDITIONS OF ANY
KIND, either express or implied. See the License for the
specific language governing permissions and limitations
under the License.
-->
Thanks for opening a pull request!
If this is not a [minor PR](https://github.com/apache/arrow/blob/main/CONTRIBUTING.md#Minor-Fixes). Could you open an issue for this pull request on GitHub? https://github.com/apache/arrow/issues/new/choose
Opening GitHub issues ahead of time contributes to the [Openness](http://theapacheway.com/open/#:~:text=Openness%20allows%20new%20users%20the,must%20happen%20in%20the%20open.) of the Apache Arrow project.
Then could you also rename the pull request title in the following format?
GH-${GITHUB_ISSUE_ID}: [${COMPONENT}] ${SUMMARY}
or
MINOR: [${COMPONENT}] ${SUMMARY}
In the case of PARQUET issues on JIRA the title also supports:
PARQUET-${JIRA_ISSUE_ID}: [${COMPONENT}] ${SUMMARY}
See also:
* [Other pull requests](https://github.com/apache/arrow/pulls/)
* [Contribution Guidelines - Contributing Overview](https://arrow.apache.org/docs/developers/overview.html)
--
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-43953: [C++] Add tests based on random data and benchmarks to ChunkResolver::ResolveMany [arrow]
Posted by "felipecrv (via GitHub)" <gi...@apache.org>.
felipecrv commented on code in PR #43954:
URL: https://github.com/apache/arrow/pull/43954#discussion_r1744100466
##########
cpp/src/arrow/chunk_resolver_benchmark.cc:
##########
@@ -0,0 +1,166 @@
+// Licensed to the Apache Software Foundation (ASF) under one
+// or more contributor license agreements. See the NOTICE file
+// distributed with this work for additional information
+// regarding copyright ownership. The ASF licenses this file
+// to you under the Apache License, Version 2.0 (the
+// "License"); you may not use this file except in compliance
+// with the License. You may obtain a copy of the License at
+//
+// http://www.apache.org/licenses/LICENSE-2.0
+//
+// Unless required by applicable law or agreed to in writing,
+// software distributed under the License is distributed on an
+// "AS IS" BASIS, WITHOUT WARRANTIES OR CONDITIONS OF ANY
+// KIND, either express or implied. See the License for the
+// specific language governing permissions and limitations
+// under the License.
+
+#include "benchmark/benchmark.h"
+
+#include <algorithm>
+#include <cstdint>
+#include <random>
+#include <vector>
+
+#include "arrow/chunk_resolver.h"
+#include "arrow/util/benchmark_util.h"
+#include "arrow/util/pcg_random.h"
+
+namespace arrow {
+
+using internal::ChunkResolver;
+using internal::TypedChunkLocation;
+
+namespace {
+
+int64_t constexpr kChunkedArrayLength = std::numeric_limits<uint16_t>::max();
+
+struct ResolveManyBenchmark {
+ benchmark::State& state;
+ random::pcg64 rng;
+ // Values from the state.range(i)
+ int64_t chunked_array_length;
+ int32_t num_chunks;
+ int64_t num_logical_indices;
+
+ explicit ResolveManyBenchmark(benchmark::State& state)
+ : state(state),
+ rng(42),
+ chunked_array_length(state.range(0)),
+ num_chunks(static_cast<int32_t>(state.range(1))),
+ num_logical_indices(state.range(2)) {}
+
+ std::vector<int64_t> GenChunkedArrayOffsets() {
+ std::uniform_int_distribution<int64_t> offset_gen(1, chunked_array_length);
+ std::vector<int64_t> offsets;
+ offsets.reserve(num_chunks + 1);
+ offsets.push_back(0);
+ while (offsets.size() < static_cast<size_t>(num_chunks)) {
+ offsets.push_back(offset_gen(rng));
+ }
+ offsets.push_back(chunked_array_length);
+ std::sort(offsets.begin() + 1, offsets.end());
+ return offsets;
+ }
+
+ template <typename IndexType>
+ std::vector<IndexType> GenRandomIndices(IndexType max_index, bool sorted) {
+ std::uniform_int_distribution<IndexType> index_gen(0, max_index);
+ std::vector<IndexType> indices;
+ indices.reserve(num_logical_indices);
+ while (indices.size() < static_cast<size_t>(num_logical_indices)) {
+ indices.push_back(index_gen(rng));
+ }
+ if (sorted) {
+ std::sort(indices.begin(), indices.end());
+ }
+ return indices;
+ }
+
+ template <typename IndexType>
+ void Bench(bool sorted) {
+ if constexpr (sizeof(IndexType) < 8) {
+ constexpr uint64_t kLimitIndex = std::numeric_limits<IndexType>::max();
+ ARROW_CHECK_LE(static_cast<uint64_t>(chunked_array_length), kLimitIndex);
+ }
+ const auto max_random_index = static_cast<IndexType>(chunked_array_length);
+ auto offsets = GenChunkedArrayOffsets();
+ auto logical_indices = GenRandomIndices<IndexType>(max_random_index, sorted);
+ ChunkResolver resolver(std::move(offsets));
+ std::vector<TypedChunkLocation<IndexType>> chunk_location_vec(num_logical_indices);
+ BENCHMARK_UNUSED bool all_succeeded = true;
+ for (auto _ : state) {
+ const bool success = resolver.ResolveMany<IndexType>(
+ num_logical_indices, logical_indices.data(), chunk_location_vec.data());
+ all_succeeded &= success;
+ }
+ ARROW_CHECK(all_succeeded);
+ state.counters["logical_len"] = static_cast<double>(chunked_array_length);
+ state.counters["num_chunks"] = static_cast<double>(num_chunks);
+ state.SetItemsProcessed(state.iterations() * num_logical_indices);
+ }
+};
+
+template <typename IndexType>
+void ResolveManySetArgs(benchmark::internal::Benchmark* bench) {
+ constexpr int32_t kNonAligned = 3;
Review Comment:
The optimizations I was experimenting with involved some unrolling so I didn't want input values to neatly align to powers of 2.
--
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-43953: [C++] Add tests based on random data and benchmarks to ChunkResolver::ResolveMany [arrow]
Posted by "felipecrv (via GitHub)" <gi...@apache.org>.
felipecrv commented on PR #43954:
URL: https://github.com/apache/arrow/pull/43954#issuecomment-2329329142
The `chunk_hint` stuff really works. I forgot to plot it, but without it the throughput gains don't exist when indices are sorted.
--
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-43953: [C++] Add tests based on random data and benchmarks to ChunkResolver::ResolveMany [arrow]
Posted by "pitrou (via GitHub)" <gi...@apache.org>.
pitrou commented on code in PR #43954:
URL: https://github.com/apache/arrow/pull/43954#discussion_r1744018656
##########
cpp/src/arrow/chunk_resolver_benchmark.cc:
##########
@@ -0,0 +1,166 @@
+// Licensed to the Apache Software Foundation (ASF) under one
+// or more contributor license agreements. See the NOTICE file
+// distributed with this work for additional information
+// regarding copyright ownership. The ASF licenses this file
+// to you under the Apache License, Version 2.0 (the
+// "License"); you may not use this file except in compliance
+// with the License. You may obtain a copy of the License at
+//
+// http://www.apache.org/licenses/LICENSE-2.0
+//
+// Unless required by applicable law or agreed to in writing,
+// software distributed under the License is distributed on an
+// "AS IS" BASIS, WITHOUT WARRANTIES OR CONDITIONS OF ANY
+// KIND, either express or implied. See the License for the
+// specific language governing permissions and limitations
+// under the License.
+
+#include "benchmark/benchmark.h"
+
+#include <algorithm>
+#include <cstdint>
+#include <random>
+#include <vector>
+
+#include "arrow/chunk_resolver.h"
+#include "arrow/util/benchmark_util.h"
+#include "arrow/util/pcg_random.h"
+
+namespace arrow {
+
+using internal::ChunkResolver;
+using internal::TypedChunkLocation;
+
+namespace {
+
+int64_t constexpr kChunkedArrayLength = std::numeric_limits<uint16_t>::max();
+
+struct ResolveManyBenchmark {
+ benchmark::State& state;
+ random::pcg64 rng;
+ // Values from the state.range(i)
+ int64_t chunked_array_length;
+ int32_t num_chunks;
+ int64_t num_logical_indices;
+
+ explicit ResolveManyBenchmark(benchmark::State& state)
+ : state(state),
+ rng(42),
+ chunked_array_length(state.range(0)),
+ num_chunks(static_cast<int32_t>(state.range(1))),
+ num_logical_indices(state.range(2)) {}
+
+ std::vector<int64_t> GenChunkedArrayOffsets() {
+ std::uniform_int_distribution<int64_t> offset_gen(1, chunked_array_length);
+ std::vector<int64_t> offsets;
+ offsets.reserve(num_chunks + 1);
+ offsets.push_back(0);
+ while (offsets.size() < static_cast<size_t>(num_chunks)) {
+ offsets.push_back(offset_gen(rng));
+ }
+ offsets.push_back(chunked_array_length);
+ std::sort(offsets.begin() + 1, offsets.end());
+ return offsets;
+ }
+
+ template <typename IndexType>
+ std::vector<IndexType> GenRandomIndices(IndexType max_index, bool sorted) {
+ std::uniform_int_distribution<IndexType> index_gen(0, max_index);
+ std::vector<IndexType> indices;
+ indices.reserve(num_logical_indices);
+ while (indices.size() < static_cast<size_t>(num_logical_indices)) {
+ indices.push_back(index_gen(rng));
+ }
+ if (sorted) {
+ std::sort(indices.begin(), indices.end());
+ }
+ return indices;
+ }
+
+ template <typename IndexType>
+ void Bench(bool sorted) {
+ if constexpr (sizeof(IndexType) < 8) {
+ constexpr uint64_t kLimitIndex = std::numeric_limits<IndexType>::max();
+ ARROW_CHECK_LE(static_cast<uint64_t>(chunked_array_length), kLimitIndex);
+ }
+ const auto max_random_index = static_cast<IndexType>(chunked_array_length);
+ auto offsets = GenChunkedArrayOffsets();
+ auto logical_indices = GenRandomIndices<IndexType>(max_random_index, sorted);
+ ChunkResolver resolver(std::move(offsets));
+ std::vector<TypedChunkLocation<IndexType>> chunk_location_vec(num_logical_indices);
+ BENCHMARK_UNUSED bool all_succeeded = true;
+ for (auto _ : state) {
+ const bool success = resolver.ResolveMany<IndexType>(
+ num_logical_indices, logical_indices.data(), chunk_location_vec.data());
+ all_succeeded &= success;
+ }
+ ARROW_CHECK(all_succeeded);
+ state.counters["logical_len"] = static_cast<double>(chunked_array_length);
+ state.counters["num_chunks"] = static_cast<double>(num_chunks);
+ state.SetItemsProcessed(state.iterations() * num_logical_indices);
+ }
+};
+
+template <typename IndexType>
+void ResolveManySetArgs(benchmark::internal::Benchmark* bench) {
+ constexpr int32_t kNonAligned = 3;
Review Comment:
Can you explain what this is for?
##########
cpp/src/arrow/chunk_resolver_benchmark.cc:
##########
@@ -0,0 +1,166 @@
+// Licensed to the Apache Software Foundation (ASF) under one
+// or more contributor license agreements. See the NOTICE file
+// distributed with this work for additional information
+// regarding copyright ownership. The ASF licenses this file
+// to you under the Apache License, Version 2.0 (the
+// "License"); you may not use this file except in compliance
+// with the License. You may obtain a copy of the License at
+//
+// http://www.apache.org/licenses/LICENSE-2.0
+//
+// Unless required by applicable law or agreed to in writing,
+// software distributed under the License is distributed on an
+// "AS IS" BASIS, WITHOUT WARRANTIES OR CONDITIONS OF ANY
+// KIND, either express or implied. See the License for the
+// specific language governing permissions and limitations
+// under the License.
+
+#include "benchmark/benchmark.h"
+
+#include <algorithm>
+#include <cstdint>
+#include <random>
+#include <vector>
+
+#include "arrow/chunk_resolver.h"
+#include "arrow/util/benchmark_util.h"
+#include "arrow/util/pcg_random.h"
+
+namespace arrow {
+
+using internal::ChunkResolver;
+using internal::TypedChunkLocation;
+
+namespace {
+
+int64_t constexpr kChunkedArrayLength = std::numeric_limits<uint16_t>::max();
+
+struct ResolveManyBenchmark {
+ benchmark::State& state;
+ random::pcg64 rng;
+ // Values from the state.range(i)
+ int64_t chunked_array_length;
+ int32_t num_chunks;
+ int64_t num_logical_indices;
+
+ explicit ResolveManyBenchmark(benchmark::State& state)
+ : state(state),
+ rng(42),
+ chunked_array_length(state.range(0)),
+ num_chunks(static_cast<int32_t>(state.range(1))),
+ num_logical_indices(state.range(2)) {}
+
+ std::vector<int64_t> GenChunkedArrayOffsets() {
+ std::uniform_int_distribution<int64_t> offset_gen(1, chunked_array_length);
+ std::vector<int64_t> offsets;
+ offsets.reserve(num_chunks + 1);
+ offsets.push_back(0);
+ while (offsets.size() < static_cast<size_t>(num_chunks)) {
+ offsets.push_back(offset_gen(rng));
+ }
+ offsets.push_back(chunked_array_length);
+ std::sort(offsets.begin() + 1, offsets.end());
+ return offsets;
+ }
+
+ template <typename IndexType>
+ std::vector<IndexType> GenRandomIndices(IndexType max_index, bool sorted) {
+ std::uniform_int_distribution<IndexType> index_gen(0, max_index);
+ std::vector<IndexType> indices;
+ indices.reserve(num_logical_indices);
+ while (indices.size() < static_cast<size_t>(num_logical_indices)) {
+ indices.push_back(index_gen(rng));
+ }
+ if (sorted) {
+ std::sort(indices.begin(), indices.end());
+ }
+ return indices;
+ }
+
+ template <typename IndexType>
+ void Bench(bool sorted) {
+ if constexpr (sizeof(IndexType) < 8) {
+ constexpr uint64_t kLimitIndex = std::numeric_limits<IndexType>::max();
+ ARROW_CHECK_LE(static_cast<uint64_t>(chunked_array_length), kLimitIndex);
+ }
+ const auto max_random_index = static_cast<IndexType>(chunked_array_length);
+ auto offsets = GenChunkedArrayOffsets();
+ auto logical_indices = GenRandomIndices<IndexType>(max_random_index, sorted);
+ ChunkResolver resolver(std::move(offsets));
+ std::vector<TypedChunkLocation<IndexType>> chunk_location_vec(num_logical_indices);
+ BENCHMARK_UNUSED bool all_succeeded = true;
+ for (auto _ : state) {
+ const bool success = resolver.ResolveMany<IndexType>(
+ num_logical_indices, logical_indices.data(), chunk_location_vec.data());
+ all_succeeded &= success;
+ }
+ ARROW_CHECK(all_succeeded);
+ state.counters["logical_len"] = static_cast<double>(chunked_array_length);
+ state.counters["num_chunks"] = static_cast<double>(num_chunks);
+ state.SetItemsProcessed(state.iterations() * num_logical_indices);
+ }
+};
+
+template <typename IndexType>
+void ResolveManySetArgs(benchmark::internal::Benchmark* bench) {
+ constexpr int32_t kNonAligned = 3;
+ const int64_t kNumIndicesFew = (kChunkedArrayLength >> 7) - kNonAligned;
+ const int64_t kNumIndicesMany = (kChunkedArrayLength >> 1) - kNonAligned;
+
+ switch (sizeof(IndexType)) {
+ case 1:
+ // Unexpected. See comments below.
+ case 2:
+ case 4:
+ case 8:
+ bench->Args({kChunkedArrayLength, /*num_chunks*/ 10000, kNumIndicesFew});
Review Comment:
10000 chunks is really a lot and I'm not sure it's really useful to test different numbers of chunks. By accumulating different combinations of parameters we make the benchmark results less immediately readable.
##########
cpp/src/arrow/chunked_array_test.cc:
##########
@@ -373,10 +374,27 @@ TEST(TestChunkResolver, Resolve) {
ASSERT_EQ(resolver.Resolve(10).chunk_index, 3);
}
+template <class RNG>
+std::vector<int64_t> GenChunkedArrayOffsets(RNG& rng, int32_t num_chunks,
+ int64_t chunked_array_len) {
+ std::uniform_int_distribution<int64_t> offset_gen(1, chunked_array_len - 1);
+ std::vector<int64_t> offsets;
+ offsets.reserve(num_chunks + 1);
+ offsets.push_back(0);
+ while (offsets.size() < static_cast<size_t>(num_chunks)) {
+ offsets.push_back(offset_gen(rng));
+ }
+ offsets.push_back(chunked_array_len);
+ std::sort(offsets.begin() + 1, offsets.end());
+ return offsets;
+}
+
template <typename T>
class TestChunkResolverMany : public ::testing::Test {
public:
using IndexType = T;
+ static constexpr int32_t kMaxInt32 = std::numeric_limits<int32_t>::max();
+ static constexpr size_t kMaxValidIndex = std::numeric_limits<IndexType>::max();
Review Comment:
Shouldn't this be `uint64_t`? Especially for 32-bit platforms.
##########
cpp/src/arrow/chunked_array.cc:
##########
@@ -55,7 +55,7 @@ ChunkedArray::ChunkedArray(ArrayVector chunks, std::shared_ptr<DataType> type)
<< "cannot construct ChunkedArray from empty vector and omitted type";
type_ = chunks_[0]->type();
}
-
+ ARROW_CHECK_LE(chunks.size(), std::numeric_limits<int>::max());
Review Comment:
Is this limit useful if it ends up not making performance better anyway?
--
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-43953: [C++] Add tests based on random data and benchmarks to ChunkResolver::ResolveMany [arrow]
Posted by "pitrou (via GitHub)" <gi...@apache.org>.
pitrou commented on PR #43954:
URL: https://github.com/apache/arrow/pull/43954#issuecomment-2329385204
Results here (AMD Zen 2 CPU, gcc):
```
ResolveManyUInt16Random/65535/10000/508 7072 ns 7071 ns 98917 items_per_second=71.8471M/s logical_len=65.535k num_chunks=10k
ResolveManyUInt16Random/65535/100/508 4098 ns 4097 ns 170804 items_per_second=123.986M/s logical_len=65.535k num_chunks=100
ResolveManyUInt16Random/65535/10000/32764 1812677 ns 1812178 ns 393 items_per_second=18.0799M/s logical_len=65.535k num_chunks=10k
ResolveManyUInt16Random/65535/100/32764 723697 ns 723335 ns 876 items_per_second=45.2958M/s logical_len=65.535k num_chunks=100
ResolveManyUInt32Random/65535/10000/508 7796 ns 7795 ns 88954 items_per_second=65.1731M/s logical_len=65.535k num_chunks=10k
ResolveManyUInt32Random/65535/100/508 4397 ns 4396 ns 157489 items_per_second=115.566M/s logical_len=65.535k num_chunks=100
ResolveManyUInt32Random/65535/10000/32764 1848926 ns 1848181 ns 379 items_per_second=17.7277M/s logical_len=65.535k num_chunks=10k
ResolveManyUInt32Random/65535/100/32764 752273 ns 752045 ns 917 items_per_second=43.5665M/s logical_len=65.535k num_chunks=100
ResolveManyUInt64Random/65535/10000/508 6731 ns 6730 ns 103505 items_per_second=75.4878M/s logical_len=65.535k num_chunks=10k
ResolveManyUInt64Random/65535/100/508 4042 ns 4041 ns 172940 items_per_second=125.717M/s logical_len=65.535k num_chunks=100
ResolveManyUInt64Random/65535/10000/32764 1809563 ns 1809068 ns 387 items_per_second=18.111M/s logical_len=65.535k num_chunks=10k
ResolveManyUInt64Random/65535/100/32764 731165 ns 730968 ns 953 items_per_second=44.8227M/s logical_len=65.535k num_chunks=100
ResolveManyUInt16Sorted/65535/10000/508 6233 ns 6231 ns 111713 items_per_second=81.5236M/s logical_len=65.535k num_chunks=10k
ResolveManyUInt16Sorted/65535/100/508 955 ns 955 ns 728588 items_per_second=532.031M/s logical_len=65.535k num_chunks=100
ResolveManyUInt16Sorted/65535/10000/32764 314016 ns 313931 ns 2221 items_per_second=104.367M/s logical_len=65.535k num_chunks=10k
ResolveManyUInt16Sorted/65535/100/32764 41365 ns 41356 ns 17068 items_per_second=792.247M/s logical_len=65.535k num_chunks=100
ResolveManyUInt32Sorted/65535/10000/508 7176 ns 7174 ns 91879 items_per_second=70.8084M/s logical_len=65.535k num_chunks=10k
ResolveManyUInt32Sorted/65535/100/508 928 ns 928 ns 749739 items_per_second=547.568M/s logical_len=65.535k num_chunks=100
ResolveManyUInt32Sorted/65535/10000/32764 326595 ns 326507 ns 2145 items_per_second=100.347M/s logical_len=65.535k num_chunks=10k
ResolveManyUInt32Sorted/65535/100/32764 34162 ns 34154 ns 20518 items_per_second=959.309M/s logical_len=65.535k num_chunks=100
ResolveManyUInt64Sorted/65535/10000/508 6057 ns 6055 ns 113029 items_per_second=83.8968M/s logical_len=65.535k num_chunks=10k
ResolveManyUInt64Sorted/65535/100/508 994 ns 993 ns 700153 items_per_second=511.41M/s logical_len=65.535k num_chunks=100
ResolveManyUInt64Sorted/65535/10000/32764 316107 ns 316023 ns 2212 items_per_second=103.676M/s logical_len=65.535k num_chunks=10k
ResolveManyUInt64Sorted/65535/100/32764 38441 ns 38427 ns 20599 items_per_second=852.64M/s logical_len=65.535k num_chunks=100
```
--
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-43953: [C++] Add tests based on random data and benchmarks to ChunkResolver::ResolveMany [arrow]
Posted by "pitrou (via GitHub)" <gi...@apache.org>.
pitrou commented on PR #43954:
URL: https://github.com/apache/arrow/pull/43954#issuecomment-2355881165
There are still a couple compilation errors on CI it seems :-)
--
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-43953: [C++] Add tests based on random data and benchmarks to ChunkResolver::ResolveMany [arrow]
Posted by "pitrou (via GitHub)" <gi...@apache.org>.
pitrou commented on PR #43954:
URL: https://github.com/apache/arrow/pull/43954#issuecomment-2329593768
There are a number of CI failures that need fixing.
--
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-43953: [C++] Add tests based on random data and benchmarks to ChunkResolver::ResolveMany [arrow]
Posted by "pitrou (via GitHub)" <gi...@apache.org>.
pitrou commented on PR #43954:
URL: https://github.com/apache/arrow/pull/43954#issuecomment-2346346123
There are still a couple CI failures that need fixing.
--
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