You are viewing a plain text version of this content. The canonical link for it is here.
Posted to github@arrow.apache.org by "zanmato1984 (via GitHub)" <gi...@apache.org> on 2024/09/11 02:27:05 UTC
[PR] GH-44052: [C++][Compute] Reduce the complexity of row segmenter [arrow]
zanmato1984 opened a new pull request, #44053:
URL: https://github.com/apache/arrow/pull/44053
<!--
Thanks for opening a pull request!
If this is your first pull request you can find detailed information on how
to contribute here:
* [New Contributor's Guide](https://arrow.apache.org/docs/dev/developers/guide/step_by_step/pr_lifecycle.html#reviews-and-merge-of-the-pull-request)
* [Contributing Overview](https://arrow.apache.org/docs/dev/developers/overview.html)
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}
-->
### Rationale for this change
As described in #44052, currently `AnyKeysSegmenter::GetNextSegment` has `O(n*m)` complexity, where `n` is the number of rows in a batch, and `m` is the number of segments in this batch (a "segment" is the group of contiguous rows who have the same segment key). This is because in each invocation of the method, it computes all the group ids of the remaining rows in this batch, where it's only interested in the first group, making the rest of the computation a waste.
In this PR I introduced a new API `GetSegments` (and subsequently deprecated the old `GetNextSegment`) to compute the group ids only once and iterate all the segments outside to avoid the duplicated computation. This reduces the complexity from `O(n*m)` to `O(n)`.
<!--
Why are you proposing this change? If this is already explained clearly in the issue then this section is not needed.
Explaining clearly why changes are proposed helps reviewers understand your changes and offer better suggestions for fixes.
-->
### What changes are included in this PR?
1. Because `grouper.h` is a [public header](https://github.com/apache/arrow/blob/8556001e6a8b4c7f35d4e18c28704d7811005904/cpp/src/arrow/compute/api.h#L47), so I assume `RowSegmenter::GetNextSegment` is a public API and only deprecate it instead of removing it.
2. Implement new API `RowSegmenter::GetSegments` and update the call-sites.
3. Some code reorg of the segmenter code (mostly moving to inside a class).
4. A new benchmark for the segmented aggregation. (The benchmark result is shown in the comments below.)
<!--
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?
Legacy tests are sufficient.
<!--
We typically require tests for all PRs in order to:
1. Prevent the code from being accidentally broken by subsequent changes
5. 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?
Yes.
<!--
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 uncomment the line below and explain which changes are breaking.
-->
**This PR includes breaking changes to public APIs.**
The API `RowSegmenter::GetNextSegment` is deprecated due to its inefficiency and replaced with a more efficient one `RowSegmenter::GetSegments`.
<!--
Please uncomment the line below (and provide explanation) if the changes fix either (a) a security vulnerability, (b) a bug that caused incorrect or invalid data to be produced, or (c) a bug that causes a crash (even when the API contract is upheld). We use this to highlight fixes to issues that may affect users without their knowledge. For this reason, fixing bugs that cause errors don't count, since those are usually obvious.
-->
<!-- **This PR contains a "Critical Fix".** -->
--
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-44052: [C++][Compute] Reduce the complexity of row segmenter [arrow]
Posted by "pitrou (via GitHub)" <gi...@apache.org>.
pitrou commented on code in PR #44053:
URL: https://github.com/apache/arrow/pull/44053#discussion_r1763223991
##########
cpp/src/arrow/acero/aggregate_benchmark.cc:
##########
@@ -866,5 +887,61 @@ BENCHMARK(TDigestKernelDoubleMedian)->Apply(QuantileKernelArgs);
BENCHMARK(TDigestKernelDoubleDeciles)->Apply(QuantileKernelArgs);
BENCHMARK(TDigestKernelDoubleCentiles)->Apply(QuantileKernelArgs);
+//
+// Segmented Aggregate
+//
+
+static void BenchmarkSegmentedAggregate(
+ benchmark::State& state, int64_t num_rows, std::vector<Aggregate> aggregates,
+ const std::vector<std::shared_ptr<Array>>& arguments,
+ const std::vector<std::shared_ptr<Array>>& keys, int64_t num_segment_keys,
+ int64_t num_segments) {
+ ASSERT_GT(num_segments, 0);
+
+ auto rng = random::RandomArrayGenerator(42);
+ auto segment_key = rng.Int64(num_rows, /*min=*/0, /*max=*/num_segments - 1);
+ int64_t* values = segment_key->data()->GetMutableValues<int64_t>(1);
+ std::sort(values, values + num_rows);
+ // num_segment_keys copies of the segment key.
+ ArrayVector segment_keys(num_segment_keys, segment_key);
Review Comment:
This is not much better than before, is it? I would expect something like:
```suggestion
ArrayVector segment_keys(num_segment_keys);
for (auto& segment_key : segment_keys) {
segment_key = rng.Int64(num_rows, /*min=*/0, /*max=*/num_segments - 1);
int64_t* values = segment_key->data()->GetMutableValues<int64_t>(1);
std::sort(values, values + num_rows);
}
```
##########
cpp/src/arrow/acero/aggregate_benchmark.cc:
##########
@@ -866,5 +887,61 @@ BENCHMARK(TDigestKernelDoubleMedian)->Apply(QuantileKernelArgs);
BENCHMARK(TDigestKernelDoubleDeciles)->Apply(QuantileKernelArgs);
BENCHMARK(TDigestKernelDoubleCentiles)->Apply(QuantileKernelArgs);
+//
+// Segmented Aggregate
+//
+
+static void BenchmarkSegmentedAggregate(
+ benchmark::State& state, int64_t num_rows, std::vector<Aggregate> aggregates,
+ const std::vector<std::shared_ptr<Array>>& arguments,
+ const std::vector<std::shared_ptr<Array>>& keys, int64_t num_segment_keys,
+ int64_t num_segments) {
+ ASSERT_GT(num_segments, 0);
+
+ auto rng = random::RandomArrayGenerator(42);
+ auto segment_key = rng.Int64(num_rows, /*min=*/0, /*max=*/num_segments - 1);
+ int64_t* values = segment_key->data()->GetMutableValues<int64_t>(1);
+ std::sort(values, values + num_rows);
+ // num_segment_keys copies of the segment key.
+ ArrayVector segment_keys(num_segment_keys, segment_key);
+
+ BenchmarkAggregate(state, std::move(aggregates), arguments, keys, segment_keys);
+}
+
+template <typename... Args>
+static void CountScalarSegmentedByInts(benchmark::State& state, Args&&...) {
+ constexpr int64_t num_rows = 32 * 1024;
+
+ // A trivial column to count from.
+ auto arg = ConstantArrayGenerator::Zeroes(num_rows, int32());
+
+ BenchmarkSegmentedAggregate(state, num_rows, {{"count", ""}}, {arg}, {}, state.range(0),
+ state.range(1));
+}
+BENCHMARK(CountScalarSegmentedByInts)
+ ->ArgNames({"SegmentKeys", "Segments"})
+ ->ArgsProduct({{0, 1, 2}, benchmark::CreateRange(1, 256, 8)});
+
+template <typename... Args>
+static void CountGroupByIntsSegmentedByInts(benchmark::State& state, Args&&...) {
+ constexpr int64_t num_rows = 32 * 1024;
+
+ // A trivial column to count from.
+ auto arg = ConstantArrayGenerator::Zeroes(num_rows, int32());
+
+ auto rng = random::RandomArrayGenerator(42);
+ int64_t num_keys = state.range(0);
+ ArrayVector keys(num_keys);
+ for (auto& key : keys) {
+ key = rng.Int64(num_rows, /*min=*/0, /*max=*/64);
+ }
+
+ BenchmarkSegmentedAggregate(state, num_rows, {{"hash_count", ""}}, {arg},
+ std::move(keys), state.range(1), state.range(2));
+}
+BENCHMARK(CountGroupByIntsSegmentedByInts)
+ ->ArgNames({"Keys", "SegmentKeys", "Segments"})
+ ->ArgsProduct({{1, 2}, {0, 1, 2}, benchmark::CreateRange(1, 256, 8)});
Review Comment:
I've tried to use 1+ segment keys and 0 non-segment keys to get an idea of the purely-segmented performance, but I get:
```
Invalid: The provided function (hash_count) is a hash aggregate function. Since there are no keys to group by, a scalar aggregate function was expected (normally these do not start with hash_)
```
It's a bit of a bummer, isn't it?
--
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-44052: [C++][Compute] Reduce the complexity of row segmenter [arrow]
Posted by "zanmato1984 (via GitHub)" <gi...@apache.org>.
zanmato1984 commented on code in PR #44053:
URL: https://github.com/apache/arrow/pull/44053#discussion_r1756216686
##########
cpp/src/arrow/compute/row/grouper.cc:
##########
@@ -170,42 +169,137 @@ struct SimpleKeySegmenter : public BaseRowSegmenter {
return extends;
}
- Result<Segment> GetNextSegment(const Scalar& scalar, int64_t offset, int64_t length) {
+ ARROW_DEPRECATED("Deprecated in 18.0.0 along with GetSegments.")
+ Result<Segment> GetNextSegmentDeprecated(const Scalar& scalar, int64_t offset,
+ int64_t length) {
+ ARROW_SUPPRESS_DEPRECATION_WARNING
ARROW_RETURN_NOT_OK(CheckType(*scalar.type));
if (!scalar.is_valid) {
return Status::Invalid("segmenting an invalid scalar");
}
auto data = checked_cast<const PrimitiveScalarBase&>(scalar).data();
- bool extends = length > 0 ? Extend(data) : kEmptyExtends;
+ bool extends = length > 0 ? ExtendDeprecated(data) : kEmptyExtends;
return MakeSegment(length, offset, length, extends);
+ ARROW_UNSUPPRESS_DEPRECATION_WARNING
}
- Result<Segment> GetNextSegment(const DataType& array_type, const uint8_t* array_bytes,
- int64_t offset, int64_t length) {
+ ARROW_DEPRECATED("Deprecated in 18.0.0 along with GetSegments.")
+ Result<Segment> GetNextSegmentDeprecated(const DataType& array_type,
+ const uint8_t* array_bytes, int64_t offset,
+ int64_t length) {
+ ARROW_SUPPRESS_DEPRECATION_WARNING
RETURN_NOT_OK(CheckType(array_type));
DCHECK_LE(offset, length);
int64_t byte_width = array_type.byte_width();
int64_t match_length = GetMatchLength(array_bytes + offset * byte_width, byte_width,
array_bytes, offset, length);
- bool extends = length > 0 ? Extend(array_bytes + offset * byte_width) : kEmptyExtends;
+ bool extends =
+ length > 0 ? ExtendDeprecated(array_bytes + offset * byte_width) : kEmptyExtends;
return MakeSegment(length, offset, match_length, extends);
+ ARROW_UNSUPPRESS_DEPRECATION_WARNING
}
+ ARROW_DEPRECATED("Deprecated in 18.0.0. Use GetSegments instead.")
Review Comment:
I guess not so useful. Removed.
--
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-44052: [C++][Compute] Reduce the complexity of row segmenter [arrow]
Posted by "pitrou (via GitHub)" <gi...@apache.org>.
pitrou commented on code in PR #44053:
URL: https://github.com/apache/arrow/pull/44053#discussion_r1753658921
##########
cpp/src/arrow/compute/row/grouper.cc:
##########
@@ -170,42 +169,137 @@ struct SimpleKeySegmenter : public BaseRowSegmenter {
return extends;
}
- Result<Segment> GetNextSegment(const Scalar& scalar, int64_t offset, int64_t length) {
+ ARROW_DEPRECATED("Deprecated in 18.0.0 along with GetSegments.")
+ Result<Segment> GetNextSegmentDeprecated(const Scalar& scalar, int64_t offset,
+ int64_t length) {
+ ARROW_SUPPRESS_DEPRECATION_WARNING
ARROW_RETURN_NOT_OK(CheckType(*scalar.type));
if (!scalar.is_valid) {
return Status::Invalid("segmenting an invalid scalar");
}
auto data = checked_cast<const PrimitiveScalarBase&>(scalar).data();
- bool extends = length > 0 ? Extend(data) : kEmptyExtends;
+ bool extends = length > 0 ? ExtendDeprecated(data) : kEmptyExtends;
return MakeSegment(length, offset, length, extends);
+ ARROW_UNSUPPRESS_DEPRECATION_WARNING
}
- Result<Segment> GetNextSegment(const DataType& array_type, const uint8_t* array_bytes,
- int64_t offset, int64_t length) {
+ ARROW_DEPRECATED("Deprecated in 18.0.0 along with GetSegments.")
+ Result<Segment> GetNextSegmentDeprecated(const DataType& array_type,
+ const uint8_t* array_bytes, int64_t offset,
+ int64_t length) {
+ ARROW_SUPPRESS_DEPRECATION_WARNING
RETURN_NOT_OK(CheckType(array_type));
DCHECK_LE(offset, length);
int64_t byte_width = array_type.byte_width();
int64_t match_length = GetMatchLength(array_bytes + offset * byte_width, byte_width,
array_bytes, offset, length);
- bool extends = length > 0 ? Extend(array_bytes + offset * byte_width) : kEmptyExtends;
+ bool extends =
+ length > 0 ? ExtendDeprecated(array_bytes + offset * byte_width) : kEmptyExtends;
return MakeSegment(length, offset, match_length, extends);
+ ARROW_UNSUPPRESS_DEPRECATION_WARNING
}
+ ARROW_DEPRECATED("Deprecated in 18.0.0. Use GetSegments instead.")
Result<Segment> GetNextSegment(const ExecSpan& batch, int64_t offset) override {
+ ARROW_SUPPRESS_DEPRECATION_WARNING
ARROW_RETURN_NOT_OK(CheckForGetNextSegment(batch, offset, {key_type_}));
if (offset == batch.length) {
return MakeSegment(batch.length, offset, 0, kEmptyExtends);
}
const auto& value = batch.values[0];
if (value.is_scalar()) {
- return GetNextSegment(*value.scalar, offset, batch.length);
+ return GetNextSegmentDeprecated(*value.scalar, offset, batch.length);
}
ARROW_DCHECK(value.is_array());
const auto& array = value.array;
if (array.GetNullCount() > 0) {
return Status::NotImplemented("segmenting a nullable array");
}
- return GetNextSegment(*array.type, GetValuesAsBytes(array), offset, batch.length);
+ return GetNextSegmentDeprecated(*array.type, GetValuesAsBytes(array), offset,
+ batch.length);
+ ARROW_UNSUPPRESS_DEPRECATION_WARNING
+ }
+
+ Result<std::vector<Segment>> GetSegments(const ExecSpan& batch) override {
+ RETURN_NOT_OK(CheckForGetSegments(batch, {key_type_}));
+
+ if (batch.length == 0) {
+ return std::vector<Segment>{};
+ }
+
+ const auto& value = batch.values[0];
+ RETURN_NOT_OK(CheckType(*value.type()));
+
+ std::vector<Segment> segments;
+ const void* key_data;
+ if (value.is_scalar()) {
+ const auto& scalar = *value.scalar;
+ DCHECK(scalar.is_valid);
+ key_data = checked_cast<const PrimitiveScalarBase&>(scalar).data();
+ bool extends = Extend(key_data);
+ segments.push_back(MakeSegment(batch.length, 0, batch.length, extends));
+ } else {
+ DCHECK(value.is_array());
+ const auto& array = value.array;
+ DCHECK_EQ(array.GetNullCount(), 0);
+ auto data = GetValuesAsBytes(array);
+ int64_t byte_width = array.type->byte_width();
+ int64_t offset = 0;
+ bool extends = Extend(data);
+ while (offset < array.length) {
+ int64_t match_length = GetMatchLength(data + offset * byte_width, byte_width,
+ data, offset, array.length);
+ segments.push_back(MakeSegment(array.length, offset, match_length,
+ offset == 0 ? extends : false));
+ offset += match_length;
+ }
+ key_data = data + (array.length - 1) * byte_width;
+ }
+
+ SaveKeyData(key_data);
+
+ return segments;
+ }
+
+ private:
+ static Status CheckType(const DataType& type) {
+ if (!is_fixed_width(type)) {
+ return Status::Invalid("SimpleKeySegmenter does not support type ", type);
+ }
+ return Status::OK();
+ }
+
+ static const uint8_t* GetValuesAsBytes(const ArraySpan& data, int64_t offset = 0) {
+ DCHECK_GT(data.type->byte_width(), 0);
+ int64_t absolute_byte_offset = (data.offset + offset) * data.type->byte_width();
+ return data.GetValues<uint8_t>(1, absolute_byte_offset);
+ }
+
+ // Find the match-length of a value within a fixed-width buffer
+ static int64_t GetMatchLength(const uint8_t* match_bytes, int64_t match_width,
+ const uint8_t* array_bytes, int64_t offset,
+ int64_t length) {
+ int64_t cursor, byte_cursor;
+ for (cursor = offset, byte_cursor = match_width * cursor; cursor < length;
+ cursor++, byte_cursor += match_width) {
+ if (memcmp(match_bytes, array_bytes + byte_cursor,
+ static_cast<size_t>(match_width)) != 0) {
+ break;
+ }
+ }
+ return std::min(cursor, length) - offset;
+ }
+
+ bool Extend(const void* data) {
+ if ARROW_PREDICT_FALSE (!extend_was_called_) {
Review Comment:
Please let's put parentheses here
```suggestion
if (ARROW_PREDICT_FALSE(!extend_was_called_)) {
```
--
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-44052: [C++][Compute] Reduce the complexity of row segmenter [arrow]
Posted by "pitrou (via GitHub)" <gi...@apache.org>.
pitrou commented on code in PR #44053:
URL: https://github.com/apache/arrow/pull/44053#discussion_r1753620669
##########
cpp/src/arrow/acero/aggregate_benchmark.cc:
##########
@@ -866,5 +890,47 @@ BENCHMARK(TDigestKernelDoubleMedian)->Apply(QuantileKernelArgs);
BENCHMARK(TDigestKernelDoubleDeciles)->Apply(QuantileKernelArgs);
BENCHMARK(TDigestKernelDoubleCentiles)->Apply(QuantileKernelArgs);
+//
+// RowSegmenter
+//
+
+template <typename... Args>
+static void BenchmarkRowSegmenter(benchmark::State& state, Args&&...) {
+ int64_t num_rows = state.range(0);
+ int64_t num_segments = state.range(1);
+ ASSERT_NE(num_segments, 0);
+ ASSERT_GE(num_rows, num_segments);
+ int64_t num_segment_keys = state.range(2);
+ // Adjust num_rows to be a multiple of num_segments.
+ num_rows = num_rows / num_segments * num_segments;
+
+ // A trivial column to count from.
+ auto arg = ConstantArrayGenerator::Zeroes(num_rows, int64());
+ // num_segments segments, each having identical num_rows / num_segments rows of the
+ // associated segment id.
+ ArrayVector segments(num_segments);
+ for (int i = 0; i < num_segments; ++i) {
+ ASSERT_OK_AND_ASSIGN(
+ segments[i],
+ Constant(std::make_shared<Int64Scalar>(i))->Generate(num_rows / num_segments));
+ }
+ // Concat all segments to form the segment key.
+ ASSERT_OK_AND_ASSIGN(auto segment_key, Concatenate(segments));
+ // num_segment_keys copies of the segment key.
+ ArrayVector segment_keys(num_segment_keys, segment_key);
+
+ BenchmarkGroupBy(state, {{"count", ""}}, {arg}, /*keys=*/{}, segment_keys);
+
+ state.SetItemsProcessed(num_rows * state.iterations());
+}
+
+std::vector<std::string> row_segmenter_argnames = {"Rows", "Segments", "SegmentKeys"};
+std::vector<std::vector<int64_t>> row_segmenter_args = {
+ {32 * 1024}, benchmark::CreateRange(1, 256, 4), benchmark::CreateDenseRange(0, 3, 1)};
+
+BENCHMARK(BenchmarkRowSegmenter)
Review Comment:
This is a GroupBy benchmark, so should probably have "GroupBy" in its name like other benchmarks?
--
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-44052: [C++][Compute] Reduce the complexity of row segmenter [arrow]
Posted by "pitrou (via GitHub)" <gi...@apache.org>.
pitrou commented on code in PR #44053:
URL: https://github.com/apache/arrow/pull/44053#discussion_r1755196664
##########
cpp/src/arrow/acero/aggregate_benchmark.cc:
##########
@@ -866,5 +890,47 @@ BENCHMARK(TDigestKernelDoubleMedian)->Apply(QuantileKernelArgs);
BENCHMARK(TDigestKernelDoubleDeciles)->Apply(QuantileKernelArgs);
BENCHMARK(TDigestKernelDoubleCentiles)->Apply(QuantileKernelArgs);
+//
+// RowSegmenter
+//
+
+template <typename... Args>
+static void BenchmarkRowSegmenter(benchmark::State& state, Args&&...) {
+ int64_t num_rows = state.range(0);
+ int64_t num_segments = state.range(1);
+ ASSERT_NE(num_segments, 0);
+ ASSERT_GE(num_rows, num_segments);
+ int64_t num_segment_keys = state.range(2);
+ // Adjust num_rows to be a multiple of num_segments.
+ num_rows = num_rows / num_segments * num_segments;
+
+ // A trivial column to count from.
+ auto arg = ConstantArrayGenerator::Zeroes(num_rows, int64());
+ // num_segments segments, each having identical num_rows / num_segments rows of the
+ // associated segment id.
+ ArrayVector segments(num_segments);
+ for (int i = 0; i < num_segments; ++i) {
+ ASSERT_OK_AND_ASSIGN(
+ segments[i],
+ Constant(std::make_shared<Int64Scalar>(i))->Generate(num_rows / num_segments));
+ }
+ // Concat all segments to form the segment key.
+ ASSERT_OK_AND_ASSIGN(auto segment_key, Concatenate(segments));
+ // num_segment_keys copies of the segment key.
+ ArrayVector segment_keys(num_segment_keys, segment_key);
Review Comment:
I mean that you have the exact same segment lengths in each segment key column. By using random generation the patterns would be slightly different.
--
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-44052: [C++][Compute] Reduce the complexity of row segmenter [arrow]
Posted by "zanmato1984 (via GitHub)" <gi...@apache.org>.
zanmato1984 commented on code in PR #44053:
URL: https://github.com/apache/arrow/pull/44053#discussion_r1756557814
##########
cpp/src/arrow/acero/aggregate_benchmark.cc:
##########
@@ -34,6 +36,9 @@
namespace arrow {
+using arrow::Concatenate;
+using arrow::ConstantArrayGenerator;
Review Comment:
Removed.
--
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-44052: [C++][Compute] Reduce the complexity of row segmenter [arrow]
Posted by "pitrou (via GitHub)" <gi...@apache.org>.
pitrou commented on code in PR #44053:
URL: https://github.com/apache/arrow/pull/44053#discussion_r1763487575
##########
cpp/src/arrow/acero/aggregate_benchmark.cc:
##########
@@ -866,5 +887,61 @@ BENCHMARK(TDigestKernelDoubleMedian)->Apply(QuantileKernelArgs);
BENCHMARK(TDigestKernelDoubleDeciles)->Apply(QuantileKernelArgs);
BENCHMARK(TDigestKernelDoubleCentiles)->Apply(QuantileKernelArgs);
+//
+// Segmented Aggregate
+//
+
+static void BenchmarkSegmentedAggregate(
+ benchmark::State& state, int64_t num_rows, std::vector<Aggregate> aggregates,
+ const std::vector<std::shared_ptr<Array>>& arguments,
+ const std::vector<std::shared_ptr<Array>>& keys, int64_t num_segment_keys,
+ int64_t num_segments) {
+ ASSERT_GT(num_segments, 0);
+
+ auto rng = random::RandomArrayGenerator(42);
+ auto segment_key = rng.Int64(num_rows, /*min=*/0, /*max=*/num_segments - 1);
+ int64_t* values = segment_key->data()->GetMutableValues<int64_t>(1);
+ std::sort(values, values + num_rows);
+ // num_segment_keys copies of the segment key.
+ ArrayVector segment_keys(num_segment_keys, segment_key);
+
+ BenchmarkAggregate(state, std::move(aggregates), arguments, keys, segment_keys);
+}
+
+template <typename... Args>
+static void CountScalarSegmentedByInts(benchmark::State& state, Args&&...) {
Review Comment:
But `select count(*) from t` is not what this is doing. It's still doing a "group by", it's just not using a hash table for it.
--
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-44052: [C++][Compute] Reduce the complexity of row segmenter [arrow]
Posted by "zanmato1984 (via GitHub)" <gi...@apache.org>.
zanmato1984 commented on code in PR #44053:
URL: https://github.com/apache/arrow/pull/44053#discussion_r1755179067
##########
cpp/src/arrow/acero/aggregate_benchmark.cc:
##########
@@ -866,5 +890,47 @@ BENCHMARK(TDigestKernelDoubleMedian)->Apply(QuantileKernelArgs);
BENCHMARK(TDigestKernelDoubleDeciles)->Apply(QuantileKernelArgs);
BENCHMARK(TDigestKernelDoubleCentiles)->Apply(QuantileKernelArgs);
+//
+// RowSegmenter
+//
+
+template <typename... Args>
+static void BenchmarkRowSegmenter(benchmark::State& state, Args&&...) {
+ int64_t num_rows = state.range(0);
+ int64_t num_segments = state.range(1);
+ ASSERT_NE(num_segments, 0);
+ ASSERT_GE(num_rows, num_segments);
+ int64_t num_segment_keys = state.range(2);
+ // Adjust num_rows to be a multiple of num_segments.
+ num_rows = num_rows / num_segments * num_segments;
+
+ // A trivial column to count from.
+ auto arg = ConstantArrayGenerator::Zeroes(num_rows, int64());
+ // num_segments segments, each having identical num_rows / num_segments rows of the
+ // associated segment id.
+ ArrayVector segments(num_segments);
+ for (int i = 0; i < num_segments; ++i) {
+ ASSERT_OK_AND_ASSIGN(
+ segments[i],
+ Constant(std::make_shared<Int64Scalar>(i))->Generate(num_rows / num_segments));
+ }
+ // Concat all segments to form the segment key.
+ ASSERT_OK_AND_ASSIGN(auto segment_key, Concatenate(segments));
+ // num_segment_keys copies of the segment key.
+ ArrayVector segment_keys(num_segment_keys, segment_key);
Review Comment:
> Then the multi-column segments will not trivially map to the individual key segments.
Sorry, I don't follow this part :(
Could you elaborate a bit? Thank you.
--
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-44052: [C++][Compute] Reduce the complexity of row segmenter [arrow]
Posted by "pitrou (via GitHub)" <gi...@apache.org>.
pitrou commented on code in PR #44053:
URL: https://github.com/apache/arrow/pull/44053#discussion_r1753625090
##########
cpp/src/arrow/acero/aggregate_benchmark.cc:
##########
@@ -866,5 +890,47 @@ BENCHMARK(TDigestKernelDoubleMedian)->Apply(QuantileKernelArgs);
BENCHMARK(TDigestKernelDoubleDeciles)->Apply(QuantileKernelArgs);
BENCHMARK(TDigestKernelDoubleCentiles)->Apply(QuantileKernelArgs);
+//
+// RowSegmenter
+//
+
+template <typename... Args>
+static void BenchmarkRowSegmenter(benchmark::State& state, Args&&...) {
+ int64_t num_rows = state.range(0);
+ int64_t num_segments = state.range(1);
+ ASSERT_NE(num_segments, 0);
+ ASSERT_GE(num_rows, num_segments);
+ int64_t num_segment_keys = state.range(2);
+ // Adjust num_rows to be a multiple of num_segments.
+ num_rows = num_rows / num_segments * num_segments;
+
+ // A trivial column to count from.
+ auto arg = ConstantArrayGenerator::Zeroes(num_rows, int64());
+ // num_segments segments, each having identical num_rows / num_segments rows of the
+ // associated segment id.
+ ArrayVector segments(num_segments);
+ for (int i = 0; i < num_segments; ++i) {
+ ASSERT_OK_AND_ASSIGN(
+ segments[i],
+ Constant(std::make_shared<Int64Scalar>(i))->Generate(num_rows / num_segments));
+ }
+ // Concat all segments to form the segment key.
+ ASSERT_OK_AND_ASSIGN(auto segment_key, Concatenate(segments));
+ // num_segment_keys copies of the segment key.
+ ArrayVector segment_keys(num_segment_keys, segment_key);
+
+ BenchmarkGroupBy(state, {{"count", ""}}, {arg}, /*keys=*/{}, segment_keys);
+
+ state.SetItemsProcessed(num_rows * state.iterations());
Review Comment:
Why don't we call `SetItemsProcessed` in `BenchmarkGroupBy` instead? It should probably be relevant for the other GroupBy benchmarks.
--
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-44052: [C++][Compute] Reduce the complexity of row segmenter [arrow]
Posted by "pitrou (via GitHub)" <gi...@apache.org>.
pitrou commented on code in PR #44053:
URL: https://github.com/apache/arrow/pull/44053#discussion_r1753644708
##########
cpp/src/arrow/compute/row/grouper.cc:
##########
@@ -292,6 +372,75 @@ struct AnyKeysSegmenter : public BaseRowSegmenter {
} else {
return Status::Invalid("segmenting unsupported datum kind ", datum.kind());
}
+ ARROW_UNSUPPRESS_DEPRECATION_WARNING
+ }
+
+ Result<std::vector<Segment>> GetSegments(const ExecSpan& batch) override {
+ RETURN_NOT_OK(CheckForGetSegments(batch, {key_types_}));
+
+ if (batch.length == 0) {
+ return std::vector<Segment>{};
+ }
+
+ // determine if the first segment in this batch extends the last segment in the
+ // previous batch
+ bool extends = kDefaultExtends;
+ // the group id must be computed prior to resetting the grouper, since it is compared
+ // to save_group_id_, and after resetting the grouper produces incomparable group ids
+ ARROW_ASSIGN_OR_RAISE(auto group_id, MapGroupIdAt(batch));
+ // it "extends" unless the group id differs from the last group id
+ if (save_group_id_ != kNoGroupId && group_id != save_group_id_) {
+ extends = false;
+ }
Review Comment:
Very small suggested improvement
```suggestion
if (save_group_id_ != kNoGroupId) {
// the group id must be computed prior to resetting the grouper, since it is compared
// to save_group_id_, and after resetting the grouper produces incomparable group ids
ARROW_ASSIGN_OR_RAISE(auto group_id, MapGroupIdAt(batch));
// it "extends" unless the group id differs from the last group id
extends = (group_id == save_group_id_);
}
```
--
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-44052: [C++][Compute] Reduce the complexity of row segmenter [arrow]
Posted by "zanmato1984 (via GitHub)" <gi...@apache.org>.
zanmato1984 commented on code in PR #44053:
URL: https://github.com/apache/arrow/pull/44053#discussion_r1763350364
##########
cpp/src/arrow/acero/aggregate_benchmark.cc:
##########
@@ -866,5 +887,61 @@ BENCHMARK(TDigestKernelDoubleMedian)->Apply(QuantileKernelArgs);
BENCHMARK(TDigestKernelDoubleDeciles)->Apply(QuantileKernelArgs);
BENCHMARK(TDigestKernelDoubleCentiles)->Apply(QuantileKernelArgs);
+//
+// Segmented Aggregate
+//
+
+static void BenchmarkSegmentedAggregate(
+ benchmark::State& state, int64_t num_rows, std::vector<Aggregate> aggregates,
+ const std::vector<std::shared_ptr<Array>>& arguments,
+ const std::vector<std::shared_ptr<Array>>& keys, int64_t num_segment_keys,
+ int64_t num_segments) {
+ ASSERT_GT(num_segments, 0);
+
+ auto rng = random::RandomArrayGenerator(42);
+ auto segment_key = rng.Int64(num_rows, /*min=*/0, /*max=*/num_segments - 1);
+ int64_t* values = segment_key->data()->GetMutableValues<int64_t>(1);
+ std::sort(values, values + num_rows);
+ // num_segment_keys copies of the segment key.
+ ArrayVector segment_keys(num_segment_keys, segment_key);
+
+ BenchmarkAggregate(state, std::move(aggregates), arguments, keys, segment_keys);
+}
+
+template <typename... Args>
+static void CountScalarSegmentedByInts(benchmark::State& state, Args&&...) {
+ constexpr int64_t num_rows = 32 * 1024;
+
+ // A trivial column to count from.
+ auto arg = ConstantArrayGenerator::Zeroes(num_rows, int32());
+
+ BenchmarkSegmentedAggregate(state, num_rows, {{"count", ""}}, {arg}, {}, state.range(0),
+ state.range(1));
+}
+BENCHMARK(CountScalarSegmentedByInts)
+ ->ArgNames({"SegmentKeys", "Segments"})
+ ->ArgsProduct({{0, 1, 2}, benchmark::CreateRange(1, 256, 8)});
+
+template <typename... Args>
+static void CountGroupByIntsSegmentedByInts(benchmark::State& state, Args&&...) {
+ constexpr int64_t num_rows = 32 * 1024;
+
+ // A trivial column to count from.
+ auto arg = ConstantArrayGenerator::Zeroes(num_rows, int32());
+
+ auto rng = random::RandomArrayGenerator(42);
+ int64_t num_keys = state.range(0);
+ ArrayVector keys(num_keys);
+ for (auto& key : keys) {
+ key = rng.Int64(num_rows, /*min=*/0, /*max=*/64);
+ }
+
+ BenchmarkSegmentedAggregate(state, num_rows, {{"hash_count", ""}}, {arg},
+ std::move(keys), state.range(1), state.range(2));
+}
+BENCHMARK(CountGroupByIntsSegmentedByInts)
+ ->ArgNames({"Keys", "SegmentKeys", "Segments"})
+ ->ArgsProduct({{1, 2}, {0, 1, 2}, benchmark::CreateRange(1, 256, 8)});
Review Comment:
As my other comment explained, an aggregation w/o any group by keys (aka. non-segment keys here) is a scalar aggregation and requires "count" rather than "hash_count".
This is a "group by aggregation" benchmark (the counter-part of the subsequent "CountScalar" one) so there has to be at least one group by key.
--
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-44052: [C++][Compute] Reduce the complexity of row segmenter [arrow]
Posted by "zanmato1984 (via GitHub)" <gi...@apache.org>.
zanmato1984 commented on code in PR #44053:
URL: https://github.com/apache/arrow/pull/44053#discussion_r1763350364
##########
cpp/src/arrow/acero/aggregate_benchmark.cc:
##########
@@ -866,5 +887,61 @@ BENCHMARK(TDigestKernelDoubleMedian)->Apply(QuantileKernelArgs);
BENCHMARK(TDigestKernelDoubleDeciles)->Apply(QuantileKernelArgs);
BENCHMARK(TDigestKernelDoubleCentiles)->Apply(QuantileKernelArgs);
+//
+// Segmented Aggregate
+//
+
+static void BenchmarkSegmentedAggregate(
+ benchmark::State& state, int64_t num_rows, std::vector<Aggregate> aggregates,
+ const std::vector<std::shared_ptr<Array>>& arguments,
+ const std::vector<std::shared_ptr<Array>>& keys, int64_t num_segment_keys,
+ int64_t num_segments) {
+ ASSERT_GT(num_segments, 0);
+
+ auto rng = random::RandomArrayGenerator(42);
+ auto segment_key = rng.Int64(num_rows, /*min=*/0, /*max=*/num_segments - 1);
+ int64_t* values = segment_key->data()->GetMutableValues<int64_t>(1);
+ std::sort(values, values + num_rows);
+ // num_segment_keys copies of the segment key.
+ ArrayVector segment_keys(num_segment_keys, segment_key);
+
+ BenchmarkAggregate(state, std::move(aggregates), arguments, keys, segment_keys);
+}
+
+template <typename... Args>
+static void CountScalarSegmentedByInts(benchmark::State& state, Args&&...) {
+ constexpr int64_t num_rows = 32 * 1024;
+
+ // A trivial column to count from.
+ auto arg = ConstantArrayGenerator::Zeroes(num_rows, int32());
+
+ BenchmarkSegmentedAggregate(state, num_rows, {{"count", ""}}, {arg}, {}, state.range(0),
+ state.range(1));
+}
+BENCHMARK(CountScalarSegmentedByInts)
+ ->ArgNames({"SegmentKeys", "Segments"})
+ ->ArgsProduct({{0, 1, 2}, benchmark::CreateRange(1, 256, 8)});
+
+template <typename... Args>
+static void CountGroupByIntsSegmentedByInts(benchmark::State& state, Args&&...) {
+ constexpr int64_t num_rows = 32 * 1024;
+
+ // A trivial column to count from.
+ auto arg = ConstantArrayGenerator::Zeroes(num_rows, int32());
+
+ auto rng = random::RandomArrayGenerator(42);
+ int64_t num_keys = state.range(0);
+ ArrayVector keys(num_keys);
+ for (auto& key : keys) {
+ key = rng.Int64(num_rows, /*min=*/0, /*max=*/64);
+ }
+
+ BenchmarkSegmentedAggregate(state, num_rows, {{"hash_count", ""}}, {arg},
+ std::move(keys), state.range(1), state.range(2));
+}
+BENCHMARK(CountGroupByIntsSegmentedByInts)
+ ->ArgNames({"Keys", "SegmentKeys", "Segments"})
+ ->ArgsProduct({{1, 2}, {0, 1, 2}, benchmark::CreateRange(1, 256, 8)});
Review Comment:
As my other comment explained, an aggregation w/o any group by keys (aka. non-segment keys here) is a scalar aggregation and requires "count" rather than "hash_count".
This is a "group by aggregation" benchmark (the counter-part of the previous "CountScalar" one) so there has to be at least one group by key.
--
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-44052: [C++][Compute] Reduce the complexity of row segmenter [arrow]
Posted by "zanmato1984 (via GitHub)" <gi...@apache.org>.
zanmato1984 commented on code in PR #44053:
URL: https://github.com/apache/arrow/pull/44053#discussion_r1763379627
##########
cpp/src/arrow/acero/aggregate_benchmark.cc:
##########
@@ -866,5 +887,61 @@ BENCHMARK(TDigestKernelDoubleMedian)->Apply(QuantileKernelArgs);
BENCHMARK(TDigestKernelDoubleDeciles)->Apply(QuantileKernelArgs);
BENCHMARK(TDigestKernelDoubleCentiles)->Apply(QuantileKernelArgs);
+//
+// Segmented Aggregate
+//
+
+static void BenchmarkSegmentedAggregate(
+ benchmark::State& state, int64_t num_rows, std::vector<Aggregate> aggregates,
+ const std::vector<std::shared_ptr<Array>>& arguments,
+ const std::vector<std::shared_ptr<Array>>& keys, int64_t num_segment_keys,
+ int64_t num_segments) {
+ ASSERT_GT(num_segments, 0);
+
+ auto rng = random::RandomArrayGenerator(42);
+ auto segment_key = rng.Int64(num_rows, /*min=*/0, /*max=*/num_segments - 1);
+ int64_t* values = segment_key->data()->GetMutableValues<int64_t>(1);
+ std::sort(values, values + num_rows);
+ // num_segment_keys copies of the segment key.
+ ArrayVector segment_keys(num_segment_keys, segment_key);
+
+ BenchmarkAggregate(state, std::move(aggregates), arguments, keys, segment_keys);
+}
+
+template <typename... Args>
+static void CountScalarSegmentedByInts(benchmark::State& state, Args&&...) {
+ constexpr int64_t num_rows = 32 * 1024;
+
+ // A trivial column to count from.
+ auto arg = ConstantArrayGenerator::Zeroes(num_rows, int32());
+
+ BenchmarkSegmentedAggregate(state, num_rows, {{"count", ""}}, {arg}, {}, state.range(0),
+ state.range(1));
+}
+BENCHMARK(CountScalarSegmentedByInts)
+ ->ArgNames({"SegmentKeys", "Segments"})
+ ->ArgsProduct({{0, 1, 2}, benchmark::CreateRange(1, 256, 8)});
+
+template <typename... Args>
+static void CountGroupByIntsSegmentedByInts(benchmark::State& state, Args&&...) {
+ constexpr int64_t num_rows = 32 * 1024;
+
+ // A trivial column to count from.
+ auto arg = ConstantArrayGenerator::Zeroes(num_rows, int32());
+
+ auto rng = random::RandomArrayGenerator(42);
+ int64_t num_keys = state.range(0);
+ ArrayVector keys(num_keys);
+ for (auto& key : keys) {
+ key = rng.Int64(num_rows, /*min=*/0, /*max=*/64);
Review Comment:
Generally the cardinalities of a segment key and a group by key are relatively independent, so I chose not to use the one of segment key for group by as well. If we want to make the group by cardinality variable, we can use another independent parameter.
But my concerns is that the performance of segment keys and group by keys are also independent, that is why this benchmark uses a fixed group by key cardinality. What do you think?
--
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-44052: [C++][Compute] Reduce the complexity of row segmenter [arrow]
Posted by "pitrou (via GitHub)" <gi...@apache.org>.
pitrou commented on code in PR #44053:
URL: https://github.com/apache/arrow/pull/44053#discussion_r1753619031
##########
cpp/src/arrow/acero/aggregate_benchmark.cc:
##########
@@ -866,5 +890,47 @@ BENCHMARK(TDigestKernelDoubleMedian)->Apply(QuantileKernelArgs);
BENCHMARK(TDigestKernelDoubleDeciles)->Apply(QuantileKernelArgs);
BENCHMARK(TDigestKernelDoubleCentiles)->Apply(QuantileKernelArgs);
+//
+// RowSegmenter
+//
+
+template <typename... Args>
+static void BenchmarkRowSegmenter(benchmark::State& state, Args&&...) {
+ int64_t num_rows = state.range(0);
+ int64_t num_segments = state.range(1);
+ ASSERT_NE(num_segments, 0);
+ ASSERT_GE(num_rows, num_segments);
+ int64_t num_segment_keys = state.range(2);
+ // Adjust num_rows to be a multiple of num_segments.
+ num_rows = num_rows / num_segments * num_segments;
+
+ // A trivial column to count from.
+ auto arg = ConstantArrayGenerator::Zeroes(num_rows, int64());
+ // num_segments segments, each having identical num_rows / num_segments rows of the
+ // associated segment id.
+ ArrayVector segments(num_segments);
+ for (int i = 0; i < num_segments; ++i) {
+ ASSERT_OK_AND_ASSIGN(
+ segments[i],
+ Constant(std::make_shared<Int64Scalar>(i))->Generate(num_rows / num_segments));
+ }
+ // Concat all segments to form the segment key.
+ ASSERT_OK_AND_ASSIGN(auto segment_key, Concatenate(segments));
+ // num_segment_keys copies of the segment key.
+ ArrayVector segment_keys(num_segment_keys, segment_key);
Review Comment:
Less trivially, you can, for each segmented key, 1) generate a random Int64 array of the right cardinality (using the min and max values) 2) sort it to make it segmented. Then the multi-column segments will not trivially map to the individual key segments.
--
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-44052: [C++][Compute] Reduce the complexity of row segmenter [arrow]
Posted by "zanmato1984 (via GitHub)" <gi...@apache.org>.
zanmato1984 commented on code in PR #44053:
URL: https://github.com/apache/arrow/pull/44053#discussion_r1756557143
##########
cpp/src/arrow/acero/aggregate_benchmark.cc:
##########
@@ -866,5 +890,47 @@ BENCHMARK(TDigestKernelDoubleMedian)->Apply(QuantileKernelArgs);
BENCHMARK(TDigestKernelDoubleDeciles)->Apply(QuantileKernelArgs);
BENCHMARK(TDigestKernelDoubleCentiles)->Apply(QuantileKernelArgs);
+//
+// RowSegmenter
+//
+
+template <typename... Args>
+static void BenchmarkRowSegmenter(benchmark::State& state, Args&&...) {
Review Comment:
Updated.
##########
cpp/src/arrow/acero/aggregate_benchmark.cc:
##########
@@ -866,5 +890,47 @@ BENCHMARK(TDigestKernelDoubleMedian)->Apply(QuantileKernelArgs);
BENCHMARK(TDigestKernelDoubleDeciles)->Apply(QuantileKernelArgs);
BENCHMARK(TDigestKernelDoubleCentiles)->Apply(QuantileKernelArgs);
+//
+// RowSegmenter
+//
+
+template <typename... Args>
+static void BenchmarkRowSegmenter(benchmark::State& state, Args&&...) {
+ int64_t num_rows = state.range(0);
+ int64_t num_segments = state.range(1);
+ ASSERT_NE(num_segments, 0);
+ ASSERT_GE(num_rows, num_segments);
+ int64_t num_segment_keys = state.range(2);
+ // Adjust num_rows to be a multiple of num_segments.
+ num_rows = num_rows / num_segments * num_segments;
+
+ // A trivial column to count from.
+ auto arg = ConstantArrayGenerator::Zeroes(num_rows, int64());
+ // num_segments segments, each having identical num_rows / num_segments rows of the
+ // associated segment id.
+ ArrayVector segments(num_segments);
+ for (int i = 0; i < num_segments; ++i) {
+ ASSERT_OK_AND_ASSIGN(
+ segments[i],
+ Constant(std::make_shared<Int64Scalar>(i))->Generate(num_rows / num_segments));
+ }
+ // Concat all segments to form the segment key.
+ ASSERT_OK_AND_ASSIGN(auto segment_key, Concatenate(segments));
+ // num_segment_keys copies of the segment key.
+ ArrayVector segment_keys(num_segment_keys, segment_key);
Review Comment:
Done.
##########
cpp/src/arrow/acero/aggregate_benchmark.cc:
##########
@@ -866,5 +890,47 @@ BENCHMARK(TDigestKernelDoubleMedian)->Apply(QuantileKernelArgs);
BENCHMARK(TDigestKernelDoubleDeciles)->Apply(QuantileKernelArgs);
BENCHMARK(TDigestKernelDoubleCentiles)->Apply(QuantileKernelArgs);
+//
+// RowSegmenter
+//
+
+template <typename... Args>
+static void BenchmarkRowSegmenter(benchmark::State& state, Args&&...) {
+ int64_t num_rows = state.range(0);
+ int64_t num_segments = state.range(1);
+ ASSERT_NE(num_segments, 0);
+ ASSERT_GE(num_rows, num_segments);
+ int64_t num_segment_keys = state.range(2);
+ // Adjust num_rows to be a multiple of num_segments.
+ num_rows = num_rows / num_segments * num_segments;
+
+ // A trivial column to count from.
+ auto arg = ConstantArrayGenerator::Zeroes(num_rows, int64());
+ // num_segments segments, each having identical num_rows / num_segments rows of the
+ // associated segment id.
+ ArrayVector segments(num_segments);
+ for (int i = 0; i < num_segments; ++i) {
+ ASSERT_OK_AND_ASSIGN(
+ segments[i],
+ Constant(std::make_shared<Int64Scalar>(i))->Generate(num_rows / num_segments));
+ }
+ // Concat all segments to form the segment key.
+ ASSERT_OK_AND_ASSIGN(auto segment_key, Concatenate(segments));
+ // num_segment_keys copies of the segment key.
+ ArrayVector segment_keys(num_segment_keys, segment_key);
+
+ BenchmarkGroupBy(state, {{"count", ""}}, {arg}, /*keys=*/{}, segment_keys);
+
+ state.SetItemsProcessed(num_rows * state.iterations());
+}
+
+std::vector<std::string> row_segmenter_argnames = {"Rows", "Segments", "SegmentKeys"};
+std::vector<std::vector<int64_t>> row_segmenter_args = {
+ {32 * 1024}, benchmark::CreateRange(1, 256, 4), benchmark::CreateDenseRange(0, 3, 1)};
+
+BENCHMARK(BenchmarkRowSegmenter)
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
Re: [PR] GH-44052: [C++][Compute] Reduce the complexity of row segmenter [arrow]
Posted by "zanmato1984 (via GitHub)" <gi...@apache.org>.
zanmato1984 commented on code in PR #44053:
URL: https://github.com/apache/arrow/pull/44053#discussion_r1764372039
##########
cpp/src/arrow/acero/aggregate_benchmark.cc:
##########
@@ -866,5 +887,61 @@ BENCHMARK(TDigestKernelDoubleMedian)->Apply(QuantileKernelArgs);
BENCHMARK(TDigestKernelDoubleDeciles)->Apply(QuantileKernelArgs);
BENCHMARK(TDigestKernelDoubleCentiles)->Apply(QuantileKernelArgs);
+//
+// Segmented Aggregate
+//
+
+static void BenchmarkSegmentedAggregate(
+ benchmark::State& state, int64_t num_rows, std::vector<Aggregate> aggregates,
+ const std::vector<std::shared_ptr<Array>>& arguments,
+ const std::vector<std::shared_ptr<Array>>& keys, int64_t num_segment_keys,
+ int64_t num_segments) {
+ ASSERT_GT(num_segments, 0);
+
+ auto rng = random::RandomArrayGenerator(42);
+ auto segment_key = rng.Int64(num_rows, /*min=*/0, /*max=*/num_segments - 1);
+ int64_t* values = segment_key->data()->GetMutableValues<int64_t>(1);
+ std::sort(values, values + num_rows);
+ // num_segment_keys copies of the segment key.
+ ArrayVector segment_keys(num_segment_keys, segment_key);
+
+ BenchmarkAggregate(state, std::move(aggregates), arguments, keys, segment_keys);
+}
+
+template <typename... Args>
+static void CountScalarSegmentedByInts(benchmark::State& state, Args&&...) {
+ constexpr int64_t num_rows = 32 * 1024;
+
+ // A trivial column to count from.
+ auto arg = ConstantArrayGenerator::Zeroes(num_rows, int32());
+
+ BenchmarkSegmentedAggregate(state, num_rows, {{"count", ""}}, {arg}, {}, state.range(0),
+ state.range(1));
+}
+BENCHMARK(CountScalarSegmentedByInts)
+ ->ArgNames({"SegmentKeys", "Segments"})
+ ->ArgsProduct({{0, 1, 2}, benchmark::CreateRange(1, 256, 8)});
+
+template <typename... Args>
+static void CountGroupByIntsSegmentedByInts(benchmark::State& state, Args&&...) {
+ constexpr int64_t num_rows = 32 * 1024;
+
+ // A trivial column to count from.
+ auto arg = ConstantArrayGenerator::Zeroes(num_rows, int32());
+
+ auto rng = random::RandomArrayGenerator(42);
+ int64_t num_keys = state.range(0);
+ ArrayVector keys(num_keys);
+ for (auto& key : keys) {
+ key = rng.Int64(num_rows, /*min=*/0, /*max=*/64);
Review Comment:
In these two particular benchmarks, they are to show how the number of segment keys and the number of segments perform with a predefined group by setup. In other words, the group by portion of the benchmark is merely to make the benchmark more realistic. They are not designed for the comparison you suggested.
IIUC, an apple to apple comparison though might be: a segmented scalar agg (N segment keys and 0 group by keys) VS. a non-segmented group by agg (0 segment keys and N group by keys), with the same key distribution. In this comparison, we can answer how a group by can be done more efficiently by taking advantage of the segmented nature of the key(s) (i.e., using segmented agg). If you are suggesting such a comparison, yes that makes sense. I think I can add a new benchmark for it.
What do you think? Thanks.
--
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-44052: [C++][Compute] Reduce the complexity of row segmenter [arrow]
Posted by "pitrou (via GitHub)" <gi...@apache.org>.
pitrou commented on PR #44053:
URL: https://github.com/apache/arrow/pull/44053#issuecomment-2344291865
That said, it's quite low priority.
--
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-44052: [C++][Compute] Reduce the complexity of row segmenter [arrow]
Posted by "zanmato1984 (via GitHub)" <gi...@apache.org>.
zanmato1984 commented on PR #44053:
URL: https://github.com/apache/arrow/pull/44053#issuecomment-2342492864
The benchmark number, ran on my Intel(R) Core(TM) i9-9980HK CPU @ 2.40GHz, shows a maximum `50x` speedup, nearly `O(n^2)` to `O(n)`.
Before:
```cpp
----------------------------------------------------------------------------------------------------------------------
Benchmark Time CPU Iterations UserCounters...
----------------------------------------------------------------------------------------------------------------------
BenchmarkRowSegmenter/Rows:32768/Segments:1/SegmentKeys:0 24934 ns 24906 ns 27871 bytes_per_second=9.80236Gi/s items_per_second=1.31565G/s
BenchmarkRowSegmenter/Rows:32768/Segments:4/SegmentKeys:0 24729 ns 24687 ns 27358 bytes_per_second=9.88957Gi/s items_per_second=1.32736G/s
BenchmarkRowSegmenter/Rows:32768/Segments:16/SegmentKeys:0 24630 ns 24616 ns 28100 bytes_per_second=9.91805Gi/s items_per_second=1.33118G/s
BenchmarkRowSegmenter/Rows:32768/Segments:64/SegmentKeys:0 24633 ns 24620 ns 28112 bytes_per_second=9.91645Gi/s items_per_second=1.33096G/s
BenchmarkRowSegmenter/Rows:32768/Segments:256/SegmentKeys:0 24679 ns 24656 ns 28651 bytes_per_second=9.90192Gi/s items_per_second=1.32901G/s
BenchmarkRowSegmenter/Rows:32768/Segments:1/SegmentKeys:1 199781 ns 199339 ns 3606 bytes_per_second=2.4495Gi/s items_per_second=164.383M/s
BenchmarkRowSegmenter/Rows:32768/Segments:4/SegmentKeys:1 222783 ns 220778 ns 2905 bytes_per_second=2.21164Gi/s items_per_second=148.421M/s
BenchmarkRowSegmenter/Rows:32768/Segments:16/SegmentKeys:1 254637 ns 254545 ns 2703 bytes_per_second=1.91825Gi/s items_per_second=128.732M/s
BenchmarkRowSegmenter/Rows:32768/Segments:64/SegmentKeys:1 452659 ns 452356 ns 1550 bytes_per_second=1.07942Gi/s items_per_second=72.4385M/s
BenchmarkRowSegmenter/Rows:32768/Segments:256/SegmentKeys:1 1241185 ns 1240526 ns 572 bytes_per_second=403.055Mi/s items_per_second=26.4146M/s
BenchmarkRowSegmenter/Rows:32768/Segments:1/SegmentKeys:2 351964 ns 351202 ns 1983 bytes_per_second=1.39031Gi/s items_per_second=93.3024M/s
BenchmarkRowSegmenter/Rows:32768/Segments:4/SegmentKeys:2 1076041 ns 1010477 ns 727 bytes_per_second=494.816Mi/s items_per_second=32.4282M/s
BenchmarkRowSegmenter/Rows:32768/Segments:16/SegmentKeys:2 4587149 ns 4584191 ns 152 bytes_per_second=109.071Mi/s items_per_second=7.14804M/s
BenchmarkRowSegmenter/Rows:32768/Segments:64/SegmentKeys:2 25132123 ns 25118536 ns 28 bytes_per_second=19.9056Mi/s items_per_second=1.30453M/s
BenchmarkRowSegmenter/Rows:32768/Segments:256/SegmentKeys:2 102196767 ns 102086286 ns 7 bytes_per_second=4.89782Mi/s items_per_second=320.983k/s
BenchmarkRowSegmenter/Rows:32768/Segments:1/SegmentKeys:3 424279 ns 423836 ns 1619 bytes_per_second=1.15205Gi/s items_per_second=77.3129M/s
BenchmarkRowSegmenter/Rows:32768/Segments:4/SegmentKeys:3 1180743 ns 1157215 ns 610 bytes_per_second=432.072Mi/s items_per_second=28.3163M/s
BenchmarkRowSegmenter/Rows:32768/Segments:16/SegmentKeys:3 5738171 ns 5729356 ns 118 bytes_per_second=87.2698Mi/s items_per_second=5.71932M/s
BenchmarkRowSegmenter/Rows:32768/Segments:64/SegmentKeys:3 30695547 ns 30656783 ns 23 bytes_per_second=16.3096Mi/s items_per_second=1.06887M/s
BenchmarkRowSegmenter/Rows:32768/Segments:256/SegmentKeys:3 125980210 ns 125906333 ns 6 bytes_per_second=3.97121Mi/s items_per_second=260.257k/s
```
After:
```cpp
----------------------------------------------------------------------------------------------------------------------
Benchmark Time CPU Iterations UserCounters...
----------------------------------------------------------------------------------------------------------------------
BenchmarkRowSegmenter/Rows:32768/Segments:1/SegmentKeys:0 24717 ns 24709 ns 28098 bytes_per_second=9.8808Gi/s items_per_second=1.32618G/s
BenchmarkRowSegmenter/Rows:32768/Segments:4/SegmentKeys:0 24283 ns 24275 ns 28709 bytes_per_second=10.0574Gi/s items_per_second=1.34989G/s
BenchmarkRowSegmenter/Rows:32768/Segments:16/SegmentKeys:0 24426 ns 24413 ns 28328 bytes_per_second=10.0006Gi/s items_per_second=1.34226G/s
BenchmarkRowSegmenter/Rows:32768/Segments:64/SegmentKeys:0 24331 ns 24320 ns 28073 bytes_per_second=10.0385Gi/s items_per_second=1.34735G/s
BenchmarkRowSegmenter/Rows:32768/Segments:256/SegmentKeys:0 26190 ns 25537 ns 28471 bytes_per_second=9.56034Gi/s items_per_second=1.28317G/s
BenchmarkRowSegmenter/Rows:32768/Segments:1/SegmentKeys:1 197105 ns 196813 ns 3587 bytes_per_second=2.48093Gi/s items_per_second=166.493M/s
BenchmarkRowSegmenter/Rows:32768/Segments:4/SegmentKeys:1 207379 ns 207241 ns 3384 bytes_per_second=2.3561Gi/s items_per_second=158.115M/s
BenchmarkRowSegmenter/Rows:32768/Segments:16/SegmentKeys:1 254707 ns 254565 ns 2777 bytes_per_second=1.9181Gi/s items_per_second=128.721M/s
BenchmarkRowSegmenter/Rows:32768/Segments:64/SegmentKeys:1 439539 ns 439415 ns 1589 bytes_per_second=1.11121Gi/s items_per_second=74.5719M/s
BenchmarkRowSegmenter/Rows:32768/Segments:256/SegmentKeys:1 1225127 ns 1224517 ns 576 bytes_per_second=408.324Mi/s items_per_second=26.7599M/s
BenchmarkRowSegmenter/Rows:32768/Segments:1/SegmentKeys:2 355268 ns 355082 ns 1985 bytes_per_second=1.37512Gi/s items_per_second=92.283M/s
BenchmarkRowSegmenter/Rows:32768/Segments:4/SegmentKeys:2 410702 ns 410486 ns 1703 bytes_per_second=1.18952Gi/s items_per_second=79.8273M/s
BenchmarkRowSegmenter/Rows:32768/Segments:16/SegmentKeys:2 667262 ns 667087 ns 1035 bytes_per_second=749.527Mi/s items_per_second=49.121M/s
BenchmarkRowSegmenter/Rows:32768/Segments:64/SegmentKeys:2 1087405 ns 1086757 ns 651 bytes_per_second=460.084Mi/s items_per_second=30.1521M/s
BenchmarkRowSegmenter/Rows:32768/Segments:256/SegmentKeys:2 2133928 ns 2132308 ns 331 bytes_per_second=234.488Mi/s items_per_second=15.3674M/s
BenchmarkRowSegmenter/Rows:32768/Segments:1/SegmentKeys:3 437444 ns 437048 ns 1592 bytes_per_second=1.11722Gi/s items_per_second=74.9757M/s
BenchmarkRowSegmenter/Rows:32768/Segments:4/SegmentKeys:3 505824 ns 505355 ns 1385 bytes_per_second=989.403Mi/s items_per_second=64.8415M/s
BenchmarkRowSegmenter/Rows:32768/Segments:16/SegmentKeys:3 756347 ns 755999 ns 906 bytes_per_second=661.377Mi/s items_per_second=43.344M/s
BenchmarkRowSegmenter/Rows:32768/Segments:64/SegmentKeys:3 1294590 ns 1293676 ns 546 bytes_per_second=386.496Mi/s items_per_second=25.3294M/s
BenchmarkRowSegmenter/Rows:32768/Segments:256/SegmentKeys:3 2552917 ns 2551420 ns 274 bytes_per_second=195.969Mi/s items_per_second=12.843M/s
```
--
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-44052: [C++][Compute] Reduce the complexity of row segmenter [arrow]
Posted by "zanmato1984 (via GitHub)" <gi...@apache.org>.
zanmato1984 commented on code in PR #44053:
URL: https://github.com/apache/arrow/pull/44053#discussion_r1755206400
##########
cpp/src/arrow/acero/aggregate_benchmark.cc:
##########
@@ -866,5 +890,47 @@ BENCHMARK(TDigestKernelDoubleMedian)->Apply(QuantileKernelArgs);
BENCHMARK(TDigestKernelDoubleDeciles)->Apply(QuantileKernelArgs);
BENCHMARK(TDigestKernelDoubleCentiles)->Apply(QuantileKernelArgs);
+//
+// RowSegmenter
+//
+
+template <typename... Args>
+static void BenchmarkRowSegmenter(benchmark::State& state, Args&&...) {
+ int64_t num_rows = state.range(0);
+ int64_t num_segments = state.range(1);
+ ASSERT_NE(num_segments, 0);
+ ASSERT_GE(num_rows, num_segments);
+ int64_t num_segment_keys = state.range(2);
+ // Adjust num_rows to be a multiple of num_segments.
+ num_rows = num_rows / num_segments * num_segments;
+
+ // A trivial column to count from.
+ auto arg = ConstantArrayGenerator::Zeroes(num_rows, int64());
+ // num_segments segments, each having identical num_rows / num_segments rows of the
+ // associated segment id.
+ ArrayVector segments(num_segments);
+ for (int i = 0; i < num_segments; ++i) {
+ ASSERT_OK_AND_ASSIGN(
+ segments[i],
+ Constant(std::make_shared<Int64Scalar>(i))->Generate(num_rows / num_segments));
+ }
+ // Concat all segments to form the segment key.
+ ASSERT_OK_AND_ASSIGN(auto segment_key, Concatenate(segments));
+ // num_segment_keys copies of the segment key.
+ ArrayVector segment_keys(num_segment_keys, segment_key);
Review Comment:
Ah, you mean introducing some randomness into the individual segment lengths. That sounds good given that this particular benchmark needs to be more realistic.
Will do. Thank you for elaborating.
--
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-44052: [C++][Compute] Reduce the complexity of row segmenter [arrow]
Posted by "pitrou (via GitHub)" <gi...@apache.org>.
pitrou commented on code in PR #44053:
URL: https://github.com/apache/arrow/pull/44053#discussion_r1753626002
##########
cpp/src/arrow/acero/aggregate_benchmark.cc:
##########
@@ -34,6 +36,9 @@
namespace arrow {
+using arrow::Concatenate;
+using arrow::ConstantArrayGenerator;
Review Comment:
These look unnecessary?
--
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-44052: [C++][Compute] Reduce the complexity of row segmenter [arrow]
Posted by "pitrou (via GitHub)" <gi...@apache.org>.
pitrou commented on code in PR #44053:
URL: https://github.com/apache/arrow/pull/44053#discussion_r1763486397
##########
cpp/src/arrow/acero/aggregate_benchmark.cc:
##########
@@ -866,5 +887,61 @@ BENCHMARK(TDigestKernelDoubleMedian)->Apply(QuantileKernelArgs);
BENCHMARK(TDigestKernelDoubleDeciles)->Apply(QuantileKernelArgs);
BENCHMARK(TDigestKernelDoubleCentiles)->Apply(QuantileKernelArgs);
+//
+// Segmented Aggregate
+//
+
+static void BenchmarkSegmentedAggregate(
+ benchmark::State& state, int64_t num_rows, std::vector<Aggregate> aggregates,
+ const std::vector<std::shared_ptr<Array>>& arguments,
+ const std::vector<std::shared_ptr<Array>>& keys, int64_t num_segment_keys,
+ int64_t num_segments) {
+ ASSERT_GT(num_segments, 0);
+
+ auto rng = random::RandomArrayGenerator(42);
+ auto segment_key = rng.Int64(num_rows, /*min=*/0, /*max=*/num_segments - 1);
+ int64_t* values = segment_key->data()->GetMutableValues<int64_t>(1);
+ std::sort(values, values + num_rows);
+ // num_segment_keys copies of the segment key.
+ ArrayVector segment_keys(num_segment_keys, segment_key);
Review Comment:
But that's also much more realistic, isn't it?
##########
cpp/src/arrow/acero/aggregate_benchmark.cc:
##########
@@ -866,5 +887,61 @@ BENCHMARK(TDigestKernelDoubleMedian)->Apply(QuantileKernelArgs);
BENCHMARK(TDigestKernelDoubleDeciles)->Apply(QuantileKernelArgs);
BENCHMARK(TDigestKernelDoubleCentiles)->Apply(QuantileKernelArgs);
+//
+// Segmented Aggregate
+//
+
+static void BenchmarkSegmentedAggregate(
+ benchmark::State& state, int64_t num_rows, std::vector<Aggregate> aggregates,
+ const std::vector<std::shared_ptr<Array>>& arguments,
+ const std::vector<std::shared_ptr<Array>>& keys, int64_t num_segment_keys,
+ int64_t num_segments) {
+ ASSERT_GT(num_segments, 0);
+
+ auto rng = random::RandomArrayGenerator(42);
+ auto segment_key = rng.Int64(num_rows, /*min=*/0, /*max=*/num_segments - 1);
+ int64_t* values = segment_key->data()->GetMutableValues<int64_t>(1);
+ std::sort(values, values + num_rows);
+ // num_segment_keys copies of the segment key.
+ ArrayVector segment_keys(num_segment_keys, segment_key);
Review Comment:
That said, as you prefer.
--
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-44052: [C++][Compute] Reduce the complexity of row segmenter [arrow]
Posted by "pitrou (via GitHub)" <gi...@apache.org>.
pitrou commented on code in PR #44053:
URL: https://github.com/apache/arrow/pull/44053#discussion_r1764536748
##########
cpp/src/arrow/acero/aggregate_benchmark.cc:
##########
@@ -866,5 +887,61 @@ BENCHMARK(TDigestKernelDoubleMedian)->Apply(QuantileKernelArgs);
BENCHMARK(TDigestKernelDoubleDeciles)->Apply(QuantileKernelArgs);
BENCHMARK(TDigestKernelDoubleCentiles)->Apply(QuantileKernelArgs);
+//
+// Segmented Aggregate
+//
+
+static void BenchmarkSegmentedAggregate(
+ benchmark::State& state, int64_t num_rows, std::vector<Aggregate> aggregates,
+ const std::vector<std::shared_ptr<Array>>& arguments,
+ const std::vector<std::shared_ptr<Array>>& keys, int64_t num_segment_keys,
+ int64_t num_segments) {
+ ASSERT_GT(num_segments, 0);
+
+ auto rng = random::RandomArrayGenerator(42);
+ auto segment_key = rng.Int64(num_rows, /*min=*/0, /*max=*/num_segments - 1);
+ int64_t* values = segment_key->data()->GetMutableValues<int64_t>(1);
+ std::sort(values, values + num_rows);
+ // num_segment_keys copies of the segment key.
+ ArrayVector segment_keys(num_segment_keys, segment_key);
+
+ BenchmarkAggregate(state, std::move(aggregates), arguments, keys, segment_keys);
+}
+
+template <typename... Args>
+static void CountScalarSegmentedByInts(benchmark::State& state, Args&&...) {
+ constexpr int64_t num_rows = 32 * 1024;
+
+ // A trivial column to count from.
+ auto arg = ConstantArrayGenerator::Zeroes(num_rows, int32());
+
+ BenchmarkSegmentedAggregate(state, num_rows, {{"count", ""}}, {arg}, {}, state.range(0),
+ state.range(1));
+}
+BENCHMARK(CountScalarSegmentedByInts)
+ ->ArgNames({"SegmentKeys", "Segments"})
+ ->ArgsProduct({{0, 1, 2}, benchmark::CreateRange(1, 256, 8)});
+
+template <typename... Args>
+static void CountGroupByIntsSegmentedByInts(benchmark::State& state, Args&&...) {
+ constexpr int64_t num_rows = 32 * 1024;
+
+ // A trivial column to count from.
+ auto arg = ConstantArrayGenerator::Zeroes(num_rows, int32());
+
+ auto rng = random::RandomArrayGenerator(42);
+ int64_t num_keys = state.range(0);
+ ArrayVector keys(num_keys);
+ for (auto& key : keys) {
+ key = rng.Int64(num_rows, /*min=*/0, /*max=*/64);
Review Comment:
Ok, thanks for the explanation. A new benchmark can be added in a later PR if we want, this one is fine now that I understand the motivation.
--
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-44052: [C++][Compute] Reduce the complexity of row segmenter [arrow]
Posted by "zanmato1984 (via GitHub)" <gi...@apache.org>.
zanmato1984 commented on PR #44053:
URL: https://github.com/apache/arrow/pull/44053#issuecomment-2344193625
> I'm curious, is the `SimpleKeySegmenter` useful for performance?
If you mean if the `SimpleKeySegmenter` has better performance than using `AnyKeysSegmenter` for "simple key", then yes. The former only has to perform a linear search on the input data, as opposed to the later who uses a heavy hash table which introduces all sorts of overhead (memory alloc/insertion/lookup). In short, I think `SimpleKeySegmenter` is a worthwhile specialization for performance.
I hacked the code and got the benchmark number.
`SimpleKeySegmenter` (copied from my previous comment):
```
BenchmarkRowSegmenter/Rows:32768/Segments:1/SegmentKeys:1 197105 ns 196813 ns 3587 bytes_per_second=2.48093Gi/s items_per_second=166.493M/s
BenchmarkRowSegmenter/Rows:32768/Segments:4/SegmentKeys:1 207379 ns 207241 ns 3384 bytes_per_second=2.3561Gi/s items_per_second=158.115M/s
BenchmarkRowSegmenter/Rows:32768/Segments:16/SegmentKeys:1 254707 ns 254565 ns 2777 bytes_per_second=1.9181Gi/s items_per_second=128.721M/s
BenchmarkRowSegmenter/Rows:32768/Segments:64/SegmentKeys:1 439539 ns 439415 ns 1589 bytes_per_second=1.11121Gi/s items_per_second=74.5719M/s
BenchmarkRowSegmenter/Rows:32768/Segments:256/SegmentKeys:1 1225127 ns 1224517 ns 576 bytes_per_second=408.324Mi/s items_per_second=26.7599M/s
```
`AnyKeysSegmenter` (by hacking the code to use it for even "simple key"):
```
BenchmarkRowSegmenter/Rows:32768/Segments:1/SegmentKeys:1 271931 ns 271563 ns 2571 bytes_per_second=1.79804Gi/s items_per_second=120.664M/s
BenchmarkRowSegmenter/Rows:32768/Segments:4/SegmentKeys:1 335488 ns 330342 ns 2196 bytes_per_second=1.47811Gi/s items_per_second=99.194M/s
BenchmarkRowSegmenter/Rows:32768/Segments:16/SegmentKeys:1 510618 ns 508622 ns 1387 bytes_per_second=983.048Mi/s items_per_second=64.425M/s
BenchmarkRowSegmenter/Rows:32768/Segments:64/SegmentKeys:1 847002 ns 846245 ns 827 bytes_per_second=590.845Mi/s items_per_second=38.7216M/s
BenchmarkRowSegmenter/Rows:32768/Segments:256/SegmentKeys:1 1745628 ns 1744707 ns 409 bytes_per_second=286.581Mi/s items_per_second=18.7814M/s
```
--
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-44052: [C++][Compute] Reduce the complexity of row segmenter [arrow]
Posted by "pitrou (via GitHub)" <gi...@apache.org>.
pitrou commented on code in PR #44053:
URL: https://github.com/apache/arrow/pull/44053#discussion_r1763232596
##########
cpp/src/arrow/acero/aggregate_benchmark.cc:
##########
@@ -866,5 +887,61 @@ BENCHMARK(TDigestKernelDoubleMedian)->Apply(QuantileKernelArgs);
BENCHMARK(TDigestKernelDoubleDeciles)->Apply(QuantileKernelArgs);
BENCHMARK(TDigestKernelDoubleCentiles)->Apply(QuantileKernelArgs);
+//
+// Segmented Aggregate
+//
+
+static void BenchmarkSegmentedAggregate(
+ benchmark::State& state, int64_t num_rows, std::vector<Aggregate> aggregates,
+ const std::vector<std::shared_ptr<Array>>& arguments,
+ const std::vector<std::shared_ptr<Array>>& keys, int64_t num_segment_keys,
+ int64_t num_segments) {
+ ASSERT_GT(num_segments, 0);
+
+ auto rng = random::RandomArrayGenerator(42);
+ auto segment_key = rng.Int64(num_rows, /*min=*/0, /*max=*/num_segments - 1);
+ int64_t* values = segment_key->data()->GetMutableValues<int64_t>(1);
+ std::sort(values, values + num_rows);
+ // num_segment_keys copies of the segment key.
+ ArrayVector segment_keys(num_segment_keys, segment_key);
+
+ BenchmarkAggregate(state, std::move(aggregates), arguments, keys, segment_keys);
+}
+
+template <typename... Args>
+static void CountScalarSegmentedByInts(benchmark::State& state, Args&&...) {
+ constexpr int64_t num_rows = 32 * 1024;
+
+ // A trivial column to count from.
+ auto arg = ConstantArrayGenerator::Zeroes(num_rows, int32());
+
+ BenchmarkSegmentedAggregate(state, num_rows, {{"count", ""}}, {arg}, {}, state.range(0),
+ state.range(1));
+}
+BENCHMARK(CountScalarSegmentedByInts)
+ ->ArgNames({"SegmentKeys", "Segments"})
+ ->ArgsProduct({{0, 1, 2}, benchmark::CreateRange(1, 256, 8)});
+
+template <typename... Args>
+static void CountGroupByIntsSegmentedByInts(benchmark::State& state, Args&&...) {
+ constexpr int64_t num_rows = 32 * 1024;
+
+ // A trivial column to count from.
+ auto arg = ConstantArrayGenerator::Zeroes(num_rows, int32());
+
+ auto rng = random::RandomArrayGenerator(42);
+ int64_t num_keys = state.range(0);
+ ArrayVector keys(num_keys);
+ for (auto& key : keys) {
+ key = rng.Int64(num_rows, /*min=*/0, /*max=*/64);
Review Comment:
It's a bit weird that this doesn't use num_segments. For comparison purposes, I would expect a similar cardinality in segmented and non-segmented keys.
--
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-44052: [C++][Compute] Reduce the complexity of row segmenter [arrow]
Posted by "zanmato1984 (via GitHub)" <gi...@apache.org>.
zanmato1984 commented on code in PR #44053:
URL: https://github.com/apache/arrow/pull/44053#discussion_r1763387381
##########
cpp/src/arrow/acero/aggregate_benchmark.cc:
##########
@@ -866,5 +887,61 @@ BENCHMARK(TDigestKernelDoubleMedian)->Apply(QuantileKernelArgs);
BENCHMARK(TDigestKernelDoubleDeciles)->Apply(QuantileKernelArgs);
BENCHMARK(TDigestKernelDoubleCentiles)->Apply(QuantileKernelArgs);
+//
+// Segmented Aggregate
+//
+
+static void BenchmarkSegmentedAggregate(
+ benchmark::State& state, int64_t num_rows, std::vector<Aggregate> aggregates,
+ const std::vector<std::shared_ptr<Array>>& arguments,
+ const std::vector<std::shared_ptr<Array>>& keys, int64_t num_segment_keys,
+ int64_t num_segments) {
+ ASSERT_GT(num_segments, 0);
+
+ auto rng = random::RandomArrayGenerator(42);
+ auto segment_key = rng.Int64(num_rows, /*min=*/0, /*max=*/num_segments - 1);
+ int64_t* values = segment_key->data()->GetMutableValues<int64_t>(1);
+ std::sort(values, values + num_rows);
+ // num_segment_keys copies of the segment key.
+ ArrayVector segment_keys(num_segment_keys, segment_key);
Review Comment:
Ah, I see your point. It is only that I want to make the number of segments to be exactly as specified. Combining independently-random keys, even with the same distribution, will make the number of segments (potentially, much) bigger.
--
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-44052: [C++][Compute] Reduce the complexity of row segmenter [arrow]
Posted by "zanmato1984 (via GitHub)" <gi...@apache.org>.
zanmato1984 commented on code in PR #44053:
URL: https://github.com/apache/arrow/pull/44053#discussion_r1764354057
##########
cpp/src/arrow/acero/aggregate_benchmark.cc:
##########
@@ -866,5 +887,61 @@ BENCHMARK(TDigestKernelDoubleMedian)->Apply(QuantileKernelArgs);
BENCHMARK(TDigestKernelDoubleDeciles)->Apply(QuantileKernelArgs);
BENCHMARK(TDigestKernelDoubleCentiles)->Apply(QuantileKernelArgs);
+//
+// Segmented Aggregate
+//
+
+static void BenchmarkSegmentedAggregate(
+ benchmark::State& state, int64_t num_rows, std::vector<Aggregate> aggregates,
+ const std::vector<std::shared_ptr<Array>>& arguments,
+ const std::vector<std::shared_ptr<Array>>& keys, int64_t num_segment_keys,
+ int64_t num_segments) {
+ ASSERT_GT(num_segments, 0);
+
+ auto rng = random::RandomArrayGenerator(42);
+ auto segment_key = rng.Int64(num_rows, /*min=*/0, /*max=*/num_segments - 1);
+ int64_t* values = segment_key->data()->GetMutableValues<int64_t>(1);
+ std::sort(values, values + num_rows);
+ // num_segment_keys copies of the segment key.
+ ArrayVector segment_keys(num_segment_keys, segment_key);
Review Comment:
> But that's also much more realistic, isn't it?
I think having exact number of segments would help on diagnostics of performance issues than introducing yet another level of randomness, so I'd rather keep it as is :)
--
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-44052: [C++][Compute] Reduce the complexity of row segmenter [arrow]
Posted by "zanmato1984 (via GitHub)" <gi...@apache.org>.
zanmato1984 commented on code in PR #44053:
URL: https://github.com/apache/arrow/pull/44053#discussion_r1763342723
##########
cpp/src/arrow/acero/aggregate_benchmark.cc:
##########
@@ -866,5 +887,61 @@ BENCHMARK(TDigestKernelDoubleMedian)->Apply(QuantileKernelArgs);
BENCHMARK(TDigestKernelDoubleDeciles)->Apply(QuantileKernelArgs);
BENCHMARK(TDigestKernelDoubleCentiles)->Apply(QuantileKernelArgs);
+//
+// Segmented Aggregate
+//
+
+static void BenchmarkSegmentedAggregate(
+ benchmark::State& state, int64_t num_rows, std::vector<Aggregate> aggregates,
+ const std::vector<std::shared_ptr<Array>>& arguments,
+ const std::vector<std::shared_ptr<Array>>& keys, int64_t num_segment_keys,
+ int64_t num_segments) {
+ ASSERT_GT(num_segments, 0);
+
+ auto rng = random::RandomArrayGenerator(42);
+ auto segment_key = rng.Int64(num_rows, /*min=*/0, /*max=*/num_segments - 1);
+ int64_t* values = segment_key->data()->GetMutableValues<int64_t>(1);
+ std::sort(values, values + num_rows);
+ // num_segment_keys copies of the segment key.
+ ArrayVector segment_keys(num_segment_keys, segment_key);
+
+ BenchmarkAggregate(state, std::move(aggregates), arguments, keys, segment_keys);
+}
+
+template <typename... Args>
+static void CountScalarSegmentedByInts(benchmark::State& state, Args&&...) {
Review Comment:
Please let me explain a bit.
Though both are named "aggregation", depending on whether there are "group by" keys or not (take SQL `select count(*) from t group by c` and `select count(*) from t` for instance), most compute engines have two variants of them. Acero calls them "[scalar aggregation](https://github.com/apache/arrow/blob/main/cpp/src/arrow/acero/scalar_aggregate_node.cc)" and "[group by aggregation](https://github.com/apache/arrow/blob/main/cpp/src/arrow/acero/groupby_aggregate_node.cc)", and they work with aggregation functions "count/sum/..." and "hash_count/hash_sum/..." respectively. This is understandable because w/o a group by key, the aggregation just needs to hold one "scalar" value (e.g., current count/sum/...) during the whole computation, whereas a group by key immediately requires some structures like a hash table.
And segment keys, on the other hand, working orthogonally with group by keys, apply to both scalar and group by aggregations.
Back to your question, yes, "CountScalar" implies exactly that this is a "scalar aggregation" (i.e., w/o any group by keys) on a "count" function. "SegmentedByInts" implies that there are potential segment keys.
Hope this can clear things a bit.
--
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-44052: [C++][Compute] Reduce the complexity of row segmenter [arrow]
Posted by "zanmato1984 (via GitHub)" <gi...@apache.org>.
zanmato1984 commented on code in PR #44053:
URL: https://github.com/apache/arrow/pull/44053#discussion_r1764345867
##########
cpp/src/arrow/acero/aggregate_benchmark.cc:
##########
@@ -866,5 +887,61 @@ BENCHMARK(TDigestKernelDoubleMedian)->Apply(QuantileKernelArgs);
BENCHMARK(TDigestKernelDoubleDeciles)->Apply(QuantileKernelArgs);
BENCHMARK(TDigestKernelDoubleCentiles)->Apply(QuantileKernelArgs);
+//
+// Segmented Aggregate
+//
+
+static void BenchmarkSegmentedAggregate(
+ benchmark::State& state, int64_t num_rows, std::vector<Aggregate> aggregates,
+ const std::vector<std::shared_ptr<Array>>& arguments,
+ const std::vector<std::shared_ptr<Array>>& keys, int64_t num_segment_keys,
+ int64_t num_segments) {
+ ASSERT_GT(num_segments, 0);
+
+ auto rng = random::RandomArrayGenerator(42);
+ auto segment_key = rng.Int64(num_rows, /*min=*/0, /*max=*/num_segments - 1);
+ int64_t* values = segment_key->data()->GetMutableValues<int64_t>(1);
+ std::sort(values, values + num_rows);
+ // num_segment_keys copies of the segment key.
+ ArrayVector segment_keys(num_segment_keys, segment_key);
+
+ BenchmarkAggregate(state, std::move(aggregates), arguments, keys, segment_keys);
+}
+
+template <typename... Args>
+static void CountScalarSegmentedByInts(benchmark::State& state, Args&&...) {
Review Comment:
You are right, what this benchmark does is not simply a `select count(*) from t`. This is merely to explain the difference between a scalar agg and a group by agg. But that doesn't mean this benchmark is a group by - at least not in Acero.
Though I'm not entirely sure how the segmented non-group-by agg map to a SQL basis, in Acero, specifying segment keys doesn't actually require group-by's existence. One just specifies segment keys and group by keys (independently) within https://github.com/apache/arrow/blob/9576a41001fe883ab4b6538663647d7c602fc4df/cpp/src/arrow/acero/options.h#L332-L348 and call an "aggregate" node. The plan parsing will generate scalar agg or group by agg depending on if there are group by keys and assign segment keys to whichever of them.
So I would let the naming reflect the underlying implementation (scalar agg vs. group by agg).
(I understand the argument could be: a segment key still implies group by semantic. I agree. But that's a more end-to-end perspective and doesn't reflect how we handle the segment key).
--
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-44052: [C++][Compute] Reduce the complexity of row segmenter [arrow]
Posted by "pitrou (via GitHub)" <gi...@apache.org>.
pitrou commented on code in PR #44053:
URL: https://github.com/apache/arrow/pull/44053#discussion_r1763489117
##########
cpp/src/arrow/acero/aggregate_benchmark.cc:
##########
@@ -866,5 +887,61 @@ BENCHMARK(TDigestKernelDoubleMedian)->Apply(QuantileKernelArgs);
BENCHMARK(TDigestKernelDoubleDeciles)->Apply(QuantileKernelArgs);
BENCHMARK(TDigestKernelDoubleCentiles)->Apply(QuantileKernelArgs);
+//
+// Segmented Aggregate
+//
+
+static void BenchmarkSegmentedAggregate(
+ benchmark::State& state, int64_t num_rows, std::vector<Aggregate> aggregates,
+ const std::vector<std::shared_ptr<Array>>& arguments,
+ const std::vector<std::shared_ptr<Array>>& keys, int64_t num_segment_keys,
+ int64_t num_segments) {
+ ASSERT_GT(num_segments, 0);
+
+ auto rng = random::RandomArrayGenerator(42);
+ auto segment_key = rng.Int64(num_rows, /*min=*/0, /*max=*/num_segments - 1);
+ int64_t* values = segment_key->data()->GetMutableValues<int64_t>(1);
+ std::sort(values, values + num_rows);
+ // num_segment_keys copies of the segment key.
+ ArrayVector segment_keys(num_segment_keys, segment_key);
+
+ BenchmarkAggregate(state, std::move(aggregates), arguments, keys, segment_keys);
+}
+
+template <typename... Args>
+static void CountScalarSegmentedByInts(benchmark::State& state, Args&&...) {
+ constexpr int64_t num_rows = 32 * 1024;
+
+ // A trivial column to count from.
+ auto arg = ConstantArrayGenerator::Zeroes(num_rows, int32());
+
+ BenchmarkSegmentedAggregate(state, num_rows, {{"count", ""}}, {arg}, {}, state.range(0),
+ state.range(1));
+}
+BENCHMARK(CountScalarSegmentedByInts)
+ ->ArgNames({"SegmentKeys", "Segments"})
+ ->ArgsProduct({{0, 1, 2}, benchmark::CreateRange(1, 256, 8)});
+
+template <typename... Args>
+static void CountGroupByIntsSegmentedByInts(benchmark::State& state, Args&&...) {
+ constexpr int64_t num_rows = 32 * 1024;
+
+ // A trivial column to count from.
+ auto arg = ConstantArrayGenerator::Zeroes(num_rows, int32());
+
+ auto rng = random::RandomArrayGenerator(42);
+ int64_t num_keys = state.range(0);
+ ArrayVector keys(num_keys);
+ for (auto& key : keys) {
+ key = rng.Int64(num_rows, /*min=*/0, /*max=*/64);
Review Comment:
The point here is to compare performance of segmented vs. non-segmented keys, 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-44052: [C++][Compute] Reduce the complexity of row segmenter [arrow]
Posted by "pitrou (via GitHub)" <gi...@apache.org>.
pitrou commented on code in PR #44053:
URL: https://github.com/apache/arrow/pull/44053#discussion_r1763231118
##########
cpp/src/arrow/acero/aggregate_benchmark.cc:
##########
@@ -866,5 +887,61 @@ BENCHMARK(TDigestKernelDoubleMedian)->Apply(QuantileKernelArgs);
BENCHMARK(TDigestKernelDoubleDeciles)->Apply(QuantileKernelArgs);
BENCHMARK(TDigestKernelDoubleCentiles)->Apply(QuantileKernelArgs);
+//
+// Segmented Aggregate
+//
+
+static void BenchmarkSegmentedAggregate(
+ benchmark::State& state, int64_t num_rows, std::vector<Aggregate> aggregates,
+ const std::vector<std::shared_ptr<Array>>& arguments,
+ const std::vector<std::shared_ptr<Array>>& keys, int64_t num_segment_keys,
+ int64_t num_segments) {
+ ASSERT_GT(num_segments, 0);
+
+ auto rng = random::RandomArrayGenerator(42);
+ auto segment_key = rng.Int64(num_rows, /*min=*/0, /*max=*/num_segments - 1);
+ int64_t* values = segment_key->data()->GetMutableValues<int64_t>(1);
+ std::sort(values, values + num_rows);
+ // num_segment_keys copies of the segment key.
+ ArrayVector segment_keys(num_segment_keys, segment_key);
+
+ BenchmarkAggregate(state, std::move(aggregates), arguments, keys, segment_keys);
+}
+
+template <typename... Args>
+static void CountScalarSegmentedByInts(benchmark::State& state, Args&&...) {
Review Comment:
So "CountScalar" is actually the case where Keys=0 but there are segment keys?
This is quite misleading.
--
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-44052: [C++][Compute] Reduce the complexity of row segmenter [arrow]
Posted by "pitrou (via GitHub)" <gi...@apache.org>.
pitrou merged PR #44053:
URL: https://github.com/apache/arrow/pull/44053
--
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-44052: [C++][Compute] Reduce the complexity of row segmenter [arrow]
Posted by "pitrou (via GitHub)" <gi...@apache.org>.
pitrou commented on code in PR #44053:
URL: https://github.com/apache/arrow/pull/44053#discussion_r1753613049
##########
cpp/src/arrow/acero/aggregate_benchmark.cc:
##########
@@ -866,5 +890,47 @@ BENCHMARK(TDigestKernelDoubleMedian)->Apply(QuantileKernelArgs);
BENCHMARK(TDigestKernelDoubleDeciles)->Apply(QuantileKernelArgs);
BENCHMARK(TDigestKernelDoubleCentiles)->Apply(QuantileKernelArgs);
+//
+// RowSegmenter
+//
+
+template <typename... Args>
+static void BenchmarkRowSegmenter(benchmark::State& state, Args&&...) {
Review Comment:
Can we turn this into a more realistic GroupBy benchmark? For example:
* M=0 to 1 non-segmented keys
* N=1 to 2 segmented keys
* K=key cardinality (2,8,64)
--
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-44052: [C++][Compute] Reduce the complexity of row segmenter [arrow]
Posted by "zanmato1984 (via GitHub)" <gi...@apache.org>.
zanmato1984 commented on code in PR #44053:
URL: https://github.com/apache/arrow/pull/44053#discussion_r1755180251
##########
cpp/src/arrow/acero/aggregate_benchmark.cc:
##########
@@ -866,5 +890,47 @@ BENCHMARK(TDigestKernelDoubleMedian)->Apply(QuantileKernelArgs);
BENCHMARK(TDigestKernelDoubleDeciles)->Apply(QuantileKernelArgs);
BENCHMARK(TDigestKernelDoubleCentiles)->Apply(QuantileKernelArgs);
+//
+// RowSegmenter
+//
+
+template <typename... Args>
+static void BenchmarkRowSegmenter(benchmark::State& state, Args&&...) {
Review Comment:
Sure. Will do, and the name should be named with `GroupBy` for sure.
--
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-44052: [C++][Compute] Reduce the complexity of row segmenter [arrow]
Posted by "pitrou (via GitHub)" <gi...@apache.org>.
pitrou commented on code in PR #44053:
URL: https://github.com/apache/arrow/pull/44053#discussion_r1753662844
##########
cpp/src/arrow/compute/row/grouper.cc:
##########
@@ -170,42 +169,137 @@ struct SimpleKeySegmenter : public BaseRowSegmenter {
return extends;
}
- Result<Segment> GetNextSegment(const Scalar& scalar, int64_t offset, int64_t length) {
+ ARROW_DEPRECATED("Deprecated in 18.0.0 along with GetSegments.")
+ Result<Segment> GetNextSegmentDeprecated(const Scalar& scalar, int64_t offset,
+ int64_t length) {
+ ARROW_SUPPRESS_DEPRECATION_WARNING
ARROW_RETURN_NOT_OK(CheckType(*scalar.type));
if (!scalar.is_valid) {
return Status::Invalid("segmenting an invalid scalar");
}
auto data = checked_cast<const PrimitiveScalarBase&>(scalar).data();
- bool extends = length > 0 ? Extend(data) : kEmptyExtends;
+ bool extends = length > 0 ? ExtendDeprecated(data) : kEmptyExtends;
return MakeSegment(length, offset, length, extends);
+ ARROW_UNSUPPRESS_DEPRECATION_WARNING
}
- Result<Segment> GetNextSegment(const DataType& array_type, const uint8_t* array_bytes,
- int64_t offset, int64_t length) {
+ ARROW_DEPRECATED("Deprecated in 18.0.0 along with GetSegments.")
+ Result<Segment> GetNextSegmentDeprecated(const DataType& array_type,
+ const uint8_t* array_bytes, int64_t offset,
+ int64_t length) {
+ ARROW_SUPPRESS_DEPRECATION_WARNING
RETURN_NOT_OK(CheckType(array_type));
DCHECK_LE(offset, length);
int64_t byte_width = array_type.byte_width();
int64_t match_length = GetMatchLength(array_bytes + offset * byte_width, byte_width,
array_bytes, offset, length);
- bool extends = length > 0 ? Extend(array_bytes + offset * byte_width) : kEmptyExtends;
+ bool extends =
+ length > 0 ? ExtendDeprecated(array_bytes + offset * byte_width) : kEmptyExtends;
return MakeSegment(length, offset, match_length, extends);
+ ARROW_UNSUPPRESS_DEPRECATION_WARNING
}
+ ARROW_DEPRECATED("Deprecated in 18.0.0. Use GetSegments instead.")
Review Comment:
It's already in the declaration, is it useful to duplicate the deprecation here?
--
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-44052: [C++][Compute] Reduce the complexity of row segmenter [arrow]
Posted by "pitrou (via GitHub)" <gi...@apache.org>.
pitrou commented on PR #44053:
URL: https://github.com/apache/arrow/pull/44053#issuecomment-2344208196
I see, thanks. Are segment keys used often? If so, it might worth improving `SimpleKeySegmenter` and also making it more generic (there's no reason why it should be limited to no-nulls fixed-width types, for example).
--
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-44052: [C++][Compute] Reduce the complexity of row segmenter [arrow]
Posted by "zanmato1984 (via GitHub)" <gi...@apache.org>.
zanmato1984 commented on code in PR #44053:
URL: https://github.com/apache/arrow/pull/44053#discussion_r1756218452
##########
cpp/src/arrow/acero/aggregate_benchmark.cc:
##########
@@ -866,5 +890,47 @@ BENCHMARK(TDigestKernelDoubleMedian)->Apply(QuantileKernelArgs);
BENCHMARK(TDigestKernelDoubleDeciles)->Apply(QuantileKernelArgs);
BENCHMARK(TDigestKernelDoubleCentiles)->Apply(QuantileKernelArgs);
+//
+// RowSegmenter
+//
+
+template <typename... Args>
+static void BenchmarkRowSegmenter(benchmark::State& state, Args&&...) {
+ int64_t num_rows = state.range(0);
+ int64_t num_segments = state.range(1);
+ ASSERT_NE(num_segments, 0);
+ ASSERT_GE(num_rows, num_segments);
+ int64_t num_segment_keys = state.range(2);
+ // Adjust num_rows to be a multiple of num_segments.
+ num_rows = num_rows / num_segments * num_segments;
+
+ // A trivial column to count from.
+ auto arg = ConstantArrayGenerator::Zeroes(num_rows, int64());
+ // num_segments segments, each having identical num_rows / num_segments rows of the
+ // associated segment id.
+ ArrayVector segments(num_segments);
+ for (int i = 0; i < num_segments; ++i) {
+ ASSERT_OK_AND_ASSIGN(
+ segments[i],
+ Constant(std::make_shared<Int64Scalar>(i))->Generate(num_rows / num_segments));
+ }
+ // Concat all segments to form the segment key.
+ ASSERT_OK_AND_ASSIGN(auto segment_key, Concatenate(segments));
+ // num_segment_keys copies of the segment key.
+ ArrayVector segment_keys(num_segment_keys, segment_key);
+
+ BenchmarkGroupBy(state, {{"count", ""}}, {arg}, /*keys=*/{}, segment_keys);
+
+ state.SetItemsProcessed(num_rows * state.iterations());
Review Comment:
I guess they should.
Moved into `BenchmarkGroupBy`. Other sharing benchmarks will have items_per_second metrics 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
Re: [PR] GH-44052: [C++][Compute] Reduce the complexity of row segmenter [arrow]
Posted by "zanmato1984 (via GitHub)" <gi...@apache.org>.
zanmato1984 commented on PR #44053:
URL: https://github.com/apache/arrow/pull/44053#issuecomment-2344247544
> I see, thanks. Are segment keys used often? If so, it might worth improving `SimpleKeySegmenter` and also making it more generic (there's no reason why it should be limited to no-nulls fixed-width types, for example).
Not in traditional RDBMS-es, but could be essential in time-series scenarios. (I believe I saw the original author mentioned that somewhere, but I can't find it at the moment.)
I can help with enhancing the simple key case 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-44052: [C++][Compute] Reduce the complexity of row segmenter [arrow]
Posted by "conbench-apache-arrow[bot] (via GitHub)" <gi...@apache.org>.
conbench-apache-arrow[bot] commented on PR #44053:
URL: https://github.com/apache/arrow/pull/44053#issuecomment-2358728335
After merging your PR, Conbench analyzed the 4 benchmarking runs that have been run so far on merge-commit 3d6d5817313920abc71c854828d95b63b2562938.
There was 1 benchmark result indicating a performance regression:
- Commit Run on `amd64-m5-4xlarge-linux` at [2024-09-18 09:22:53Z](https://conbench.ursa.dev/compare/runs/fda0a58783964c4d9285434f2dc66397...4a83486ab4b346b6a1389386ce39576e/)
- [`partitioned-dataset-filter` (R) with dataset=dataset-taxi-parquet, language=R, query=vignette](https://conbench.ursa.dev/compare/benchmarks/066ea87edd99700c80006b595b529997...066eacacdbef73188000d6fd5a37c338)
The [full Conbench report](https://github.com/apache/arrow/runs/30325096020) has more details. It also includes information about 255 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-44052: [C++][Compute] Reduce the complexity of row segmenter [arrow]
Posted by "zanmato1984 (via GitHub)" <gi...@apache.org>.
zanmato1984 commented on code in PR #44053:
URL: https://github.com/apache/arrow/pull/44053#discussion_r1753032974
##########
cpp/src/arrow/acero/aggregate_internal.h:
##########
@@ -131,17 +131,14 @@ void AggregatesToString(std::stringstream* ss, const Schema& input_schema,
template <typename BatchHandler>
Status HandleSegments(RowSegmenter* segmenter, const ExecBatch& batch,
const std::vector<int>& ids, const BatchHandler& handle_batch) {
- int64_t offset = 0;
ARROW_ASSIGN_OR_RAISE(auto segment_exec_batch, batch.SelectValues(ids));
ExecSpan segment_batch(segment_exec_batch);
- while (true) {
Review Comment:
This is the only call-site in non-testing codes.
##########
cpp/src/arrow/compute/row/grouper.cc:
##########
@@ -241,24 +336,9 @@ struct AnyKeysSegmenter : public BaseRowSegmenter {
return extends;
}
- // Runs the grouper on a single row. This is used to determine the group id of the
- // first row of a new segment to see if it extends the previous segment.
- template <typename Batch>
- Result<group_id_t> MapGroupIdAt(const Batch& batch, int64_t offset) {
Review Comment:
Moved w/o touching the code inside.
##########
cpp/src/arrow/acero/hash_aggregate_test.cc:
##########
@@ -585,19 +585,12 @@ void TestGroupClassSupportedKeys(
void TestSegments(std::unique_ptr<RowSegmenter>& segmenter, const ExecSpan& batch,
std::vector<Segment> expected_segments) {
- int64_t offset = 0, segment_num = 0;
- for (auto expected_segment : expected_segments) {
- SCOPED_TRACE("segment #" + ToChars(segment_num++));
- ASSERT_OK_AND_ASSIGN(auto segment, segmenter->GetNextSegment(batch, offset));
- ASSERT_EQ(expected_segment, segment);
- offset = segment.offset + segment.length;
+ ASSERT_OK_AND_ASSIGN(auto actual_segments, segmenter->GetSegments(batch));
+ ASSERT_EQ(actual_segments.size(), expected_segments.size());
+ for (size_t i = 0; i < actual_segments.size(); ++i) {
+ SCOPED_TRACE("segment #" + ToChars(i));
+ ASSERT_EQ(actual_segments[i], expected_segments[i]);
}
- // Assert next is the last (empty) segment.
Review Comment:
The new API generates fewer segments than before - there is no meaningless (`length == 0`) tailing segment.
##########
cpp/src/arrow/compute/row/grouper.h:
##########
@@ -97,7 +97,12 @@ class ARROW_EXPORT RowSegmenter {
virtual Status Reset() = 0;
/// \brief Get the next segment for the given batch starting from the given offset
+ /// DEPRECATED: Due to its inefficiency, use GetSegments instead.
+ ARROW_DEPRECATED("Deprecated in 18.0.0. Use GetSegments instead.")
Review Comment:
Deprecate instead of removing it because I assume this is a public API (due to `grouper.h` is a public header).
##########
cpp/src/arrow/compute/row/grouper.cc:
##########
@@ -102,21 +109,6 @@ Segment MakeSegment(int64_t batch_length, int64_t offset, int64_t length, bool e
return Segment{offset, length, offset + length >= batch_length, extends};
}
-// Used by SimpleKeySegmenter::GetNextSegment to find the match-length of a value within a
-// fixed-width buffer
-int64_t GetMatchLength(const uint8_t* match_bytes, int64_t match_width,
Review Comment:
Moved w/o touching the code inside.
##########
cpp/src/arrow/acero/hash_aggregate_test.cc:
##########
@@ -629,61 +622,47 @@ TEST(RowSegmenter, Basics) {
auto batch2 = ExecBatchFromJSON(types2, "[[1, 1], [1, 2], [2, 2]]");
auto batch1 = ExecBatchFromJSON(types1, "[[1], [1], [2]]");
ExecBatch batch0({}, 3);
- {
Review Comment:
The new API doesn't accept `offset` argument so no need for such testing.
##########
cpp/src/arrow/acero/hash_aggregate_test.cc:
##########
@@ -629,61 +622,47 @@ TEST(RowSegmenter, Basics) {
auto batch2 = ExecBatchFromJSON(types2, "[[1, 1], [1, 2], [2, 2]]");
auto batch1 = ExecBatchFromJSON(types1, "[[1], [1], [2]]");
ExecBatch batch0({}, 3);
- {
- SCOPED_TRACE("offset");
- ASSERT_OK_AND_ASSIGN(auto segmenter, MakeRowSegmenter(types0));
- ExecSpan span0(batch0);
- for (int64_t offset : {-1, 4}) {
- EXPECT_RAISES_WITH_MESSAGE_THAT(Invalid,
- HasSubstr("invalid grouping segmenter offset"),
- segmenter->GetNextSegment(span0, offset));
- }
- }
{
SCOPED_TRACE("types0 segmenting of batch2");
ASSERT_OK_AND_ASSIGN(auto segmenter, MakeRowSegmenter(types0));
ExecSpan span2(batch2);
EXPECT_RAISES_WITH_MESSAGE_THAT(Invalid, HasSubstr("expected batch size 0 "),
- segmenter->GetNextSegment(span2, 0));
+ segmenter->GetSegments(span2));
ExecSpan span0(batch0);
- TestSegments(segmenter, span0, {{0, 3, true, true}, {3, 0, true, true}});
Review Comment:
Here and below are just because the new API doesn't generate the zero-length ending segment.
##########
cpp/src/arrow/compute/row/grouper.cc:
##########
@@ -147,21 +152,15 @@ struct SimpleKeySegmenter : public BaseRowSegmenter {
save_key_data_(static_cast<size_t>(key_type_.type->byte_width())),
extend_was_called_(false) {}
- Status CheckType(const DataType& type) {
Review Comment:
Moved w/o touching the code inside.
##########
cpp/src/arrow/compute/row/grouper.cc:
##########
@@ -54,13 +55,8 @@ using group_id_t = std::remove_const<decltype(kNoGroupId)>::type;
using GroupIdType = CTypeTraits<group_id_t>::ArrowType;
auto g_group_id_type = std::make_shared<GroupIdType>();
-inline const uint8_t* GetValuesAsBytes(const ArraySpan& data, int64_t offset = 0) {
Review Comment:
Moved w/o touching the code inside.
--
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-44052: [C++][Compute] Reduce the complexity of row segmenter [arrow]
Posted by "zanmato1984 (via GitHub)" <gi...@apache.org>.
zanmato1984 commented on PR #44053:
URL: https://github.com/apache/arrow/pull/44053#issuecomment-2342495642
Hi friends, @pitrou @felipecrv @mapleFU , would you like to take a look? Thanks.
--
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-44052: [C++][Compute] Reduce the complexity of row segmenter [arrow]
Posted by "pitrou (via GitHub)" <gi...@apache.org>.
pitrou commented on PR #44053:
URL: https://github.com/apache/arrow/pull/44053#issuecomment-2343053477
I'm curious, is the `SimpleKeySegmenter` useful for 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