You are viewing a plain text version of this content. The canonical link for it is here.
Posted to github@arrow.apache.org by GitBox <gi...@apache.org> on 2020/08/14 01:44:49 UTC
[GitHub] [arrow] cyb70289 opened a new pull request #7963: ARROW-9699: [C++][Compute] Optimize mode kernel for small integer types
cyb70289 opened a new pull request #7963:
URL: https://github.com/apache/arrow/pull/7963
For small integers(bool, int8, uint8), instead of general hash table,
using a value indexed array improves performance about 2x ~ 6x.
Get another 15% improvement by reading array raw_values[] directly.
----------------------------------------------------------------
This is an automated message from the Apache Git Service.
To respond to the message, please log on to GitHub and use the
URL above to go to the specific comment.
For queries about this service, please contact Infrastructure at:
users@infra.apache.org
[GitHub] [arrow] github-actions[bot] commented on pull request #7963: ARROW-9699: [C++][Compute] Optimize mode kernel for small integer types
Posted by GitBox <gi...@apache.org>.
github-actions[bot] commented on pull request #7963:
URL: https://github.com/apache/arrow/pull/7963#issuecomment-673830331
https://issues.apache.org/jira/browse/ARROW-9699
----------------------------------------------------------------
This is an automated message from the Apache Git Service.
To respond to the message, please log on to GitHub and use the
URL above to go to the specific comment.
For queries about this service, please contact Infrastructure at:
users@infra.apache.org
[GitHub] [arrow] pitrou commented on a change in pull request #7963: ARROW-9699: [C++][Compute] Optimize mode kernel for small integer types
Posted by GitBox <gi...@apache.org>.
pitrou commented on a change in pull request #7963:
URL: https://github.com/apache/arrow/pull/7963#discussion_r476395265
##########
File path: cpp/src/arrow/compute/kernels/aggregate_test.cc
##########
@@ -685,5 +687,10 @@ TYPED_TEST(TestFloatingModeKernel, Floats) {
this->AssertModeIsNull("[]");
}
+TEST_F(TestInt8ModeKernelValueRange, Basics) {
Review comment:
Good, 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.
For queries about this service, please contact Infrastructure at:
users@infra.apache.org
[GitHub] [arrow] cyb70289 commented on pull request #7963: ARROW-9699: [C++][Compute] Optimize mode kernel for small integer types
Posted by GitBox <gi...@apache.org>.
cyb70289 commented on pull request #7963:
URL: https://github.com/apache/arrow/pull/7963#issuecomment-673834858
**Removed unrelated tests for clarity.
100% null benchmark is not stable, can be ignored.**
```
$ archery benchmark diff --suite-filter="arrow-compute-aggregate-benchmark" --cc=clang-9 --cxx=clang++-9
benchmark baseline contender change %
ModeKernelInt8/1048576/10000 60.196 MiB/sec 477.048 MiB/sec 692.487 'null_percent': 0.01
ModeKernelInt8/1048576/100 60.548 MiB/sec 470.066 MiB/sec 676.351, 'null_percent': 1.0
ModeKernelInt8/1048576/0 63.520 MiB/sec 472.362 MiB/sec 643.638, 'null_percent': 0.0
ModeKernelInt8/1048576/10 62.997 MiB/sec 420.059 MiB/sec 566.788 'null_percent': 10.0
ModeKernelBoolean/1048576/10 7.640 MiB/sec 28.329 MiB/sec 270.793 'null_percent': 10.0
ModeKernelBoolean/1048576/10000 7.332 MiB/sec 26.496 MiB/sec 261.362 'null_percent': 0.01
ModeKernelBoolean/1048576/100 7.415 MiB/sec 26.710 MiB/sec 260.212, 'null_percent': 1.0
ModeKernelBoolean/1048576/0 8.079 MiB/sec 28.428 MiB/sec 251.895, 'null_percent': 0.0
ModeKernelInt8/1048576/2 80.291 MiB/sec 265.673 MiB/sec 230.887 'null_percent': 50.0
ModeKernelBoolean/1048576/2 12.449 MiB/sec 27.915 MiB/sec 124.235 'null_percent': 50.0
ModeKernelInt8/1048576/1 864.966 MiB/sec 1.313 GiB/sec 55.455'null_percent': 100.0
ModeKernelBoolean/1048576/1 115.581 MiB/sec 153.801 MiB/sec 33.067'null_percent': 100.0
ModeKernelInt32/1048576/10000 228.572 MiB/sec 263.524 MiB/sec 15.292 'null_percent': 0.01
ModeKernelInt32/1048576/100 230.087 MiB/sec 265.102 MiB/sec 15.218, 'null_percent': 1.0
ModeKernelInt16/1048576/10000 115.973 MiB/sec 132.465 MiB/sec 14.221 'null_percent': 0.01
ModeKernelInt16/1048576/100 116.657 MiB/sec 132.673 MiB/sec 13.729, 'null_percent': 1.0
ModeKernelInt32/1048576/10 241.338 MiB/sec 270.446 MiB/sec 12.061 'null_percent': 10.0
ModeKernelInt16/1048576/10 122.426 MiB/sec 135.675 MiB/sec 10.822 'null_percent': 10.0
ModeKernelInt64/1048576/10000 481.018 MiB/sec 523.582 MiB/sec 8.849 'null_percent': 0.01
ModeKernelInt64/1048576/100 485.800 MiB/sec 527.232 MiB/sec 8.529, 'null_percent': 1.0
ModeKernelInt64/1048576/10 526.491 MiB/sec 569.412 MiB/sec 8.152 'null_percent': 10.0
ModeKernelInt64/1048576/1 6.671 GiB/sec 7.180 GiB/sec 7.623'null_percent': 100.0
ModeKernelInt64/1048576/2 783.253 MiB/sec 813.436 MiB/sec 3.854 'null_percent': 50.0
ModeKernelInt32/1048576/0 257.627 MiB/sec 265.602 MiB/sec 3.096, 'null_percent': 0.0
ModeKernelInt16/1048576/0 128.580 MiB/sec 132.340 MiB/sec 2.924, 'null_percent': 0.0
ModeKernelInt16/1048576/2 160.189 MiB/sec 164.776 MiB/sec 2.863 'null_percent': 50.0
ModeKernelInt64/1048576/0 514.855 MiB/sec 528.897 MiB/sec 2.727, 'null_percent': 0.0
ModeKernelInt32/1048576/2 321.334 MiB/sec 324.092 MiB/sec 0.858 'null_percent': 50.0
ModeKernelInt16/1048576/1 1.860 GiB/sec 1.653 GiB/sec -11.109'null_percent': 100.0
ModeKernelInt32/1048576/1 5.728 GiB/sec 3.263 GiB/sec -43.038'null_percent': 100.0
```
----------------------------------------------------------------
This is an automated message from the Apache Git Service.
To respond to the message, please log on to GitHub and use the
URL above to go to the specific comment.
For queries about this service, please contact Infrastructure at:
users@infra.apache.org
[GitHub] [arrow] cyb70289 commented on a change in pull request #7963: ARROW-9699: [C++][Compute] Optimize mode kernel for small integer types
Posted by GitBox <gi...@apache.org>.
cyb70289 commented on a change in pull request #7963:
URL: https://github.com/apache/arrow/pull/7963#discussion_r474658427
##########
File path: cpp/src/arrow/compute/kernels/aggregate_mode.cc
##########
@@ -69,28 +72,83 @@ struct ModeState {
std::unordered_map<T, int64_t> value_counts{};
};
+// Use array to count small integers(bool, int8, uint8), improves performance 2x ~ 6x
+template <typename ArrowType>
+struct ModeState<ArrowType, enable_if_t<(sizeof(typename ArrowType::c_type) == 1)>> {
+ using ThisType = ModeState<ArrowType>;
+ using T = typename ArrowType::c_type;
+ using Limits = std::numeric_limits<T>;
+
+ ModeState() : value_counts(Limits::max() - Limits::min() + 1) {}
+
+ void MergeFrom(const ThisType& state) {
+ std::transform(this->value_counts.cbegin(), this->value_counts.cend(),
+ state.value_counts.cbegin(), this->value_counts.begin(),
+ std::plus<int64_t>{});
+ }
+
+ void MergeOne(T value) { ++this->value_counts[value - Limits::min()]; }
+
+ std::pair<T, int64_t> Finalize() {
+ T mode = Limits::min();
+ int64_t count = 0;
+
+ for (int i = 0; i <= Limits::max() - Limits::min(); ++i) {
+ T this_value = static_cast<T>(i + Limits::min());
+ int64_t this_count = this->value_counts[i];
+ if (this_count > count || (this_count == count && this_value < mode)) {
+ count = this_count;
+ mode = this_value;
+ }
+ }
+ return std::make_pair(mode, count);
+ }
+
+ std::vector<int64_t> value_counts;
+};
+
+// read raw_values[] directly improves performance ~15%
Review comment:
Agreed. Will remove 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.
For queries about this service, please contact Infrastructure at:
users@infra.apache.org
[GitHub] [arrow] pitrou commented on a change in pull request #7963: ARROW-9699: [C++][Compute] Optimize mode kernel for small integer types
Posted by GitBox <gi...@apache.org>.
pitrou commented on a change in pull request #7963:
URL: https://github.com/apache/arrow/pull/7963#discussion_r474146349
##########
File path: cpp/src/arrow/compute/kernels/aggregate_mode.cc
##########
@@ -69,28 +72,83 @@ struct ModeState {
std::unordered_map<T, int64_t> value_counts{};
};
+// Use array to count small integers(bool, int8, uint8), improves performance 2x ~ 6x
+template <typename ArrowType>
+struct ModeState<ArrowType, enable_if_t<(sizeof(typename ArrowType::c_type) == 1)>> {
+ using ThisType = ModeState<ArrowType>;
+ using T = typename ArrowType::c_type;
+ using Limits = std::numeric_limits<T>;
+
+ ModeState() : value_counts(Limits::max() - Limits::min() + 1) {}
+
+ void MergeFrom(const ThisType& state) {
+ std::transform(this->value_counts.cbegin(), this->value_counts.cend(),
+ state.value_counts.cbegin(), this->value_counts.begin(),
+ std::plus<int64_t>{});
+ }
+
+ void MergeOne(T value) { ++this->value_counts[value - Limits::min()]; }
+
+ std::pair<T, int64_t> Finalize() {
+ T mode = Limits::min();
+ int64_t count = 0;
+
+ for (int i = 0; i <= Limits::max() - Limits::min(); ++i) {
+ T this_value = static_cast<T>(i + Limits::min());
+ int64_t this_count = this->value_counts[i];
+ if (this_count > count || (this_count == count && this_value < mode)) {
+ count = this_count;
+ mode = this_value;
+ }
+ }
+ return std::make_pair(mode, count);
+ }
+
+ std::vector<int64_t> value_counts;
+};
+
+// read raw_values[] directly improves performance ~15%
Review comment:
This is probably heavily compiler-dependent. In any case, such micro-optimizations mostly complicate the code for no real benefit.
##########
File path: cpp/src/arrow/compute/kernels/aggregate_test.cc
##########
@@ -685,5 +687,10 @@ TYPED_TEST(TestFloatingModeKernel, Floats) {
this->AssertModeIsNull("[]");
}
+TEST_F(TestInt8ModeKernelValueRange, Basics) {
Review comment:
Are these tests useful? `int8` should already be tested in `TestIntegerModeKernel`, 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.
For queries about this service, please contact Infrastructure at:
users@infra.apache.org
[GitHub] [arrow] cyb70289 commented on a change in pull request #7963: ARROW-9699: [C++][Compute] Optimize mode kernel for small integer types
Posted by GitBox <gi...@apache.org>.
cyb70289 commented on a change in pull request #7963:
URL: https://github.com/apache/arrow/pull/7963#discussion_r474660357
##########
File path: cpp/src/arrow/compute/kernels/aggregate_test.cc
##########
@@ -685,5 +687,10 @@ TYPED_TEST(TestFloatingModeKernel, Floats) {
this->AssertModeIsNull("[]");
}
+TEST_F(TestInt8ModeKernelValueRange, Basics) {
Review comment:
Old code uses std::unordered_map, new code uses an vector with calculated size. Just to make sure boundary condition is correctly handled, so test with the minimal(-128) and maximal(127) value.
----------------------------------------------------------------
This is an automated message from the Apache Git Service.
To respond to the message, please log on to GitHub and use the
URL above to go to the specific comment.
For queries about this service, please contact Infrastructure at:
users@infra.apache.org
[GitHub] [arrow] pitrou closed pull request #7963: ARROW-9699: [C++][Compute] Optimize mode kernel for small integer types
Posted by GitBox <gi...@apache.org>.
pitrou closed pull request #7963:
URL: https://github.com/apache/arrow/pull/7963
----------------------------------------------------------------
This is an automated message from the Apache Git Service.
To respond to the message, please log on to GitHub and use the
URL above to go to the specific comment.
For queries about this service, please contact Infrastructure at:
users@infra.apache.org