You are viewing a plain text version of this content. The canonical link for it is here.
Posted to github@arrow.apache.org by "HuaHuaY (via GitHub)" <gi...@apache.org> on 2026/06/29 11:58:33 UTC
[PR] GH-50280: [C++] Implement VisitTwoBitRuns and VisitTwoSetBitRuns methods [arrow]
HuaHuaY opened a new pull request, #50281:
URL: https://github.com/apache/arrow/pull/50281
### Rationale for this change
We already have `VisitTwoBitBlocks` which can iterate over two bitmaps simultaneously. But there is no mirror code about `BitRunReader` and `SetBitRunReader`.
### What changes are included in this PR?
Implement `VisitTwoBitRuns` and `VisitTwoSetBitRuns` methods and refactor `VisitTwoBitBlocks` in `GroupedPivotAccumulator` as examples.
### Are these changes tested?
Yes.
### Are there any user-facing changes?
No.
--
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-50280: [C++] Implement VisitTwoBitRuns and VisitTwoSetBitRuns methods [arrow]
Posted by "rok (via GitHub)" <gi...@apache.org>.
rok commented on PR #50281:
URL: https://github.com/apache/arrow/pull/50281#issuecomment-4858109509
Benchmark runs are scheduled for commit b026a7d9c1bfb46b6726db95e25b2e55026c7221. Watch https://buildkite.com/apache-arrow and https://conbench.arrow-dev.org for updates. A comment will be posted here when the runs are complete.
--
This is an automated message from the Apache Git Service.
To respond to the message, please log on to GitHub and use the
URL above to go to the specific comment.
To unsubscribe, e-mail: github-unsubscribe@arrow.apache.org
For queries about this service, please contact Infrastructure at:
users@infra.apache.org
Re: [PR] GH-50280: [C++] Implement VisitTwoBitRuns and VisitTwoSetBitRuns methods [arrow]
Posted by "rok (via GitHub)" <gi...@apache.org>.
rok commented on PR #50281:
URL: https://github.com/apache/arrow/pull/50281#issuecomment-4861665540
Commit b026a7d9c1bfb46b6726db95e25b2e55026c7221 already has scheduled benchmark runs.
--
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-50280: [C++] Implement VisitTwoBitRuns and VisitTwoSetBitRuns methods [arrow]
Posted by "HuaHuaY (via GitHub)" <gi...@apache.org>.
HuaHuaY commented on code in PR #50281:
URL: https://github.com/apache/arrow/pull/50281#discussion_r3545519578
##########
cpp/src/arrow/util/bit_run_reader.h:
##########
@@ -536,5 +542,79 @@ inline void VisitSetBitRunsVoid(const std::shared_ptr<Buffer>& bitmap, int64_t o
std::forward<Visit>(visit));
}
+template <typename Visit>
+inline Status VisitTwoSetBitRuns(const uint8_t* left_bitmap, int64_t left_offset,
+ const uint8_t* right_bitmap, int64_t right_offset,
+ int64_t length, Visit&& visit,
+ MemoryPool* pool = default_memory_pool()) {
+ if (length == 0) {
+ return Status::OK();
+ }
+ if (left_bitmap == NULLPTR) {
+ return VisitSetBitRuns(right_bitmap, right_offset, length,
+ std::forward<Visit>(visit));
+ }
+ if (right_bitmap == NULLPTR) {
+ return VisitSetBitRuns(left_bitmap, left_offset, length, std::forward<Visit>(visit));
+ }
+
+ ARROW_ASSIGN_OR_RAISE(auto bitmap_and,
+ BitmapAnd(pool, left_bitmap, left_offset, right_bitmap,
+ right_offset, length, /*out_offset=*/0));
+ return VisitSetBitRuns(bitmap_and->data(), /*offset=*/0, length,
+ std::forward<Visit>(visit));
+}
+
+template <typename Visit>
+inline Status VisitTwoBitRuns(const uint8_t* left_bitmap, int64_t left_offset,
+ const uint8_t* right_bitmap, int64_t right_offset,
+ int64_t length, Visit&& visit,
+ MemoryPool* pool = default_memory_pool()) {
+ int64_t output_position = 0;
+ ARROW_RETURN_NOT_OK(VisitTwoSetBitRuns(
+ left_bitmap, left_offset, right_bitmap, right_offset, length,
+ [&](int64_t position, int64_t run_length) {
+ if (output_position < position) {
+ ARROW_RETURN_NOT_OK(visit(output_position, position - output_position, false));
+ }
+ ARROW_RETURN_NOT_OK(visit(position, run_length, true));
+ output_position = position + run_length;
+ return Status::OK();
+ },
+ pool));
+ if (output_position < length) {
+ return visit(output_position, length - output_position, false);
+ }
+ return Status::OK();
+}
+
+template <typename Visit>
+inline void VisitTwoBitRunsVoid(const uint8_t* left_bitmap, int64_t left_offset,
+ const uint8_t* right_bitmap, int64_t right_offset,
+ int64_t length, Visit&& visit,
+ MemoryPool* pool = default_memory_pool()) {
+ ARROW_IGNORE_EXPR(VisitTwoBitRuns(
Review Comment:
Have used `ARROW_CHECK_OK` instead.
--
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-50280: [C++] Implement VisitTwoBitRuns and VisitTwoSetBitRuns methods [arrow]
Posted by "pitrou (via GitHub)" <gi...@apache.org>.
pitrou commented on code in PR #50281:
URL: https://github.com/apache/arrow/pull/50281#discussion_r3636443247
##########
cpp/src/arrow/util/nested_bitmap_traversal_benchmark.cc:
##########
Review Comment:
I'm still not convinced that this benchmark is useful to track Arrow C++ performance. Do you really want to keep 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-50280: [C++] Implement VisitTwoBitRuns and VisitTwoSetBitRuns methods [arrow]
Posted by "HuaHuaY (via GitHub)" <gi...@apache.org>.
HuaHuaY commented on PR #50281:
URL: https://github.com/apache/arrow/pull/50281#issuecomment-4852100741
Yeah, my goal was to make `BitRunReader`'s performance match `SetBitRunReader`, and removing the `NOINLINE` from `SetBitRunReader::NextRun` wasn't what I needed.
I submitted a new commit that made some optimizations to `BitRunReader`:
1. The assignment `word_ = 0` only needs to occur when reading a portion of the word.
2. Removed redundant calculations of `bit_util::IsMultipleOf64`.
3. Prioritized checking `position_ + 128 <= length_` to avoid performing two boolean checks in the `AdvanceUntilChange` and `LoadWord` functions when null values are rare.
> what matters is actual users of this function (for example in the compute library), not the bitmap traversal micro-benchmarks :-)
As you said, user performance is more important than benchmark performance. These changes not only improved my local benchmark but also, I believe, semantically optimized the execution process.
--
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-50280: [C++] Implement VisitTwoBitRuns and VisitTwoSetBitRuns methods [arrow]
Posted by "HuaHuaY (via GitHub)" <gi...@apache.org>.
HuaHuaY commented on code in PR #50281:
URL: https://github.com/apache/arrow/pull/50281#discussion_r3518026950
##########
cpp/src/arrow/util/nested_bitmap_traversal_benchmark.cc:
##########
@@ -0,0 +1,154 @@
+// Licensed to the Apache Software Foundation (ASF) under one
+// or more contributor license agreements. See the NOTICE file
+// distributed with this work for additional information
+// regarding copyright ownership. The ASF licenses this file
+// to you under the Apache License, Version 2.0 (the
+// "License"); you may not use this file except in compliance
+// with the License. You may obtain a copy of the License at
+//
+// http://www.apache.org/licenses/LICENSE-2.0
+//
+// Unless required by applicable law or agreed to in writing,
+// software distributed under the License is distributed on an
+// "AS IS" BASIS, WITHOUT WARRANTIES OR CONDITIONS OF ANY
+// KIND, either express or implied. See the License for the
+// specific language governing permissions and limitations
+// under the License.
+
+#include "benchmark/benchmark.h"
+
+#include <cstdint>
+#include <cstdlib>
+#include <memory>
+
+#include "arrow/array/array_base.h"
+#include "arrow/array/array_nested.h"
+#include "arrow/array/array_primitive.h"
+#include "arrow/testing/gtest_util.h"
+#include "arrow/testing/random.h"
+#include "arrow/type.h"
+#include "arrow/util/bit_block_counter.h"
+#include "arrow/util/bit_run_reader.h"
+#include "arrow/util/bitmap_ops.h"
+
+namespace arrow::internal {
+
+struct NestedBitmapTraversalBenchmark {
Review Comment:
I modified this benchmark to count the number of valid values in a `list<int8>` given an outer bitmap.
--
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-50280: [C++] Implement VisitTwoBitRuns and VisitTwoSetBitRuns methods [arrow]
Posted by "HuaHuaY (via GitHub)" <gi...@apache.org>.
HuaHuaY commented on PR #50281:
URL: https://github.com/apache/arrow/pull/50281#issuecomment-4841482539
@pitrou How to run benchmark in `conbench-apache-arrow`? Please help to call the bot.
--
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-50280: [C++] Implement VisitTwoBitRuns and VisitTwoSetBitRuns methods [arrow]
Posted by "pitrou (via GitHub)" <gi...@apache.org>.
pitrou commented on PR #50281:
URL: https://github.com/apache/arrow/pull/50281#issuecomment-4841849879
@ursabot please benchmark lang=C++
--
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-50280: [C++] Implement VisitTwoBitRuns and VisitTwoSetBitRuns methods [arrow]
Posted by "HuaHuaY (via GitHub)" <gi...@apache.org>.
HuaHuaY commented on code in PR #50281:
URL: https://github.com/apache/arrow/pull/50281#discussion_r3518026950
##########
cpp/src/arrow/util/nested_bitmap_traversal_benchmark.cc:
##########
@@ -0,0 +1,154 @@
+// Licensed to the Apache Software Foundation (ASF) under one
+// or more contributor license agreements. See the NOTICE file
+// distributed with this work for additional information
+// regarding copyright ownership. The ASF licenses this file
+// to you under the Apache License, Version 2.0 (the
+// "License"); you may not use this file except in compliance
+// with the License. You may obtain a copy of the License at
+//
+// http://www.apache.org/licenses/LICENSE-2.0
+//
+// Unless required by applicable law or agreed to in writing,
+// software distributed under the License is distributed on an
+// "AS IS" BASIS, WITHOUT WARRANTIES OR CONDITIONS OF ANY
+// KIND, either express or implied. See the License for the
+// specific language governing permissions and limitations
+// under the License.
+
+#include "benchmark/benchmark.h"
+
+#include <cstdint>
+#include <cstdlib>
+#include <memory>
+
+#include "arrow/array/array_base.h"
+#include "arrow/array/array_nested.h"
+#include "arrow/array/array_primitive.h"
+#include "arrow/testing/gtest_util.h"
+#include "arrow/testing/random.h"
+#include "arrow/type.h"
+#include "arrow/util/bit_block_counter.h"
+#include "arrow/util/bit_run_reader.h"
+#include "arrow/util/bitmap_ops.h"
+
+namespace arrow::internal {
+
+struct NestedBitmapTraversalBenchmark {
Review Comment:
I modified this benchmark to count the number of valid values in a `list<int8>` given an outer bitmap. But after testing the new benchmark, I discovered something unexpected: the baseline approach—`bitmapand` combined with `VisitSetBitRunsVoid`—actually turned out to be the fastest. I attribute this to the bitmap's minimal memory footprint, where the performance gains from `bitmapand`'s vectorization outweigh the overhead of materializing the bitmap. Consequently, I have decided to close this PR and simply materialize the bitmap directly when needed.
--
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-50280: [C++] Implement VisitTwoBitRuns and VisitTwoSetBitRuns methods [arrow]
Posted by "pitrou (via GitHub)" <gi...@apache.org>.
pitrou commented on PR #50281:
URL: https://github.com/apache/arrow/pull/50281#issuecomment-4855513967
The [benchmarks above](https://github.com/apache/arrow/pull/50281#issuecomment-4854732760) don't seem to show significant wins from the BitRunReader improvements. Actually, there is a number of small-ish regressions.
--
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-50280: [C++] Implement VisitTwoBitRuns and VisitTwoSetBitRuns methods [arrow]
Posted by "HuaHuaY (via GitHub)" <gi...@apache.org>.
HuaHuaY commented on PR #50281:
URL: https://github.com/apache/arrow/pull/50281#issuecomment-4874846654
Currently, `VisitTwoSetBitRuns` materializes the bitmap first and then iterates over it using `VisitSetBitRuns`. The reason I called `BitmapAnd` directly on the full bitmap length is that the bitmap is small, so segmentation seemed unnecessary; furthermore, the performance impact of segmentation is unknown. The performance gap observed in the new benchmarks compared to `BitmapAdd` is due to differences in the extent of automatic compiler inlining. @pitrou Please take a look again.
--
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-50280: [C++] Implement VisitTwoBitRuns and VisitTwoSetBitRuns methods [arrow]
Posted by "rok (via GitHub)" <gi...@apache.org>.
rok commented on PR #50281:
URL: https://github.com/apache/arrow/pull/50281#issuecomment-4841850730
Benchmark runs are scheduled for commit c0d6bf7f428e8417efad2e675331b26d98e23a0f. Watch https://buildkite.com/apache-arrow and https://conbench.arrow-dev.org for updates. A comment will be posted here when the runs are complete.
--
This is an automated message from the Apache Git Service.
To respond to the message, please log on to GitHub and use the
URL above to go to the specific comment.
To unsubscribe, e-mail: github-unsubscribe@arrow.apache.org
For queries about this service, please contact Infrastructure at:
users@infra.apache.org
Re: [PR] GH-50280: [C++] Implement VisitTwoBitRuns and VisitTwoSetBitRuns methods [arrow]
Posted by "rok (via GitHub)" <gi...@apache.org>.
rok commented on PR #50281:
URL: https://github.com/apache/arrow/pull/50281#issuecomment-4844561380
@wgtmac That's a current workaround for not having a conbench user. :)
--
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-50280: [C++] Implement VisitTwoBitRuns and VisitTwoSetBitRuns methods [arrow]
Posted by "HuaHuaY (via GitHub)" <gi...@apache.org>.
HuaHuaY commented on PR #50281:
URL: https://github.com/apache/arrow/pull/50281#issuecomment-4841477542
@pitrou How to run benchmark in `conbench-apache-arrow`? Please help to call the bot.
--
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-50280: [C++] Implement VisitTwoBitRuns and VisitTwoSetBitRuns methods [arrow]
Posted by "HuaHuaY (via GitHub)" <gi...@apache.org>.
HuaHuaY commented on PR #50281:
URL: https://github.com/apache/arrow/pull/50281#issuecomment-4858175714
I've only modified `BitRunReader` and not modified `SetBitRunReader`. And I hope to narrow the performance gap between `BitRunReader` and `SetBitRunReader`. Therefore, I think the change in the performance ratio of `VisitBitRunsSum` and `VisitSetBitRunsSum` is more indicative of the effectiveness of the modifications. I've reorganized the data and listed the ratio differences in the last column.
## Group 1
A: 4ab7d672 / amd64-c6a-4xlarge-linux / c0d6bf7
B: d164bbbe / amd64-c6a-4xlarge-linux / 3b5b2d0
Ratio: `VisitBitRunsSum` / `VisitSetBitRunsSum`
| params | A `VisitBitRunsSum` | A `VisitSetBitRunsSum` | A ratio | B `VisitBitRunsSum` | B `VisitSetBitRunsSum` | B ratio | Δ ratio (B-A) |
|---:|---:|---:|---:|---:|---:|---:|---:|
| 2 | 3.10e+8 | 3.59e+8 | 0.8643 | 3.13e+8 | 3.39e+8 | 0.9232 | +0.0589 |
| 8 | 5.70e+8 | 6.40e+8 | 0.8903 | 5.75e+8 | 6.07e+8 | 0.9471 | +0.0568 |
| 64 | 2.07e+9 | 2.20e+9 | 0.9415 | 2.10e+9 | 2.17e+9 | 0.9672 | +0.0257 |
| 512 | 4.30e+9 | 4.58e+9 | 0.9384 | 4.38e+9 | 4.50e+9 | 0.9729 | +0.0345 |
| 4096 | 4.68e+9 | 4.88e+9 | 0.9582 | 4.70e+9 | 4.80e+9 | 0.9797 | +0.0214 |
| 32768 | 4.73e+9 | 4.93e+9 | 0.9579 | 4.76e+9 | 4.86e+9 | 0.9809 | +0.0230 |
| 65536 | 4.73e+9 | 4.94e+9 | 0.9584 | 4.76e+9 | 4.87e+9 | 0.9768 | +0.0184 |
## Group 2
A: fd5a984c / amd64-m5-4xlarge-linux / c0d6bf7
B: e74c6927 / amd64-m5-4xlarge-linux / 3b5b2d0
Ratio: `VisitBitRunsSum` / `VisitSetBitRunsSum`
| params | A `VisitBitRunsSum` | A `VisitSetBitRunsSum` | A ratio | B `VisitBitRunsSum` | B `VisitSetBitRunsSum` | B ratio | Δ ratio (B-A) |
|---:|---:|---:|---:|---:|---:|---:|---:|
| 2 | 2.07e+8 | 2.34e+8 | 0.8871 | 2.18e+8 | 2.30e+8 | 0.9494 | +0.0624 |
| 8 | 3.73e+8 | 4.01e+8 | 0.9297 | 3.84e+8 | 3.99e+8 | 0.9608 | +0.0311 |
| 64 | 1.15e+9 | 1.15e+9 | 1.0013 | 1.15e+9 | 1.15e+9 | 1.0049 | +0.0035 |
| 512 | 1.98e+9 | 2.03e+9 | 0.9734 | 1.97e+9 | 2.03e+9 | 0.9715 | -0.0019 |
| 4096 | 2.17e+9 | 2.24e+9 | 0.9706 | 2.15e+9 | 2.24e+9 | 0.9604 | -0.0102 |
| 32768 | 2.19e+9 | 2.26e+9 | 0.9693 | 2.17e+9 | 2.26e+9 | 0.9594 | -0.0099 |
| 65536 | 2.19e+9 | 2.26e+9 | 0.9694 | 2.17e+9 | 2.26e+9 | 0.9592 | -0.0102 |
## Group 3
A: 457fe991 / test-mac-arm / c0d6bf7
B: 6701543e / test-mac-arm / 3b5b2d0
Ratio: `VisitBitRunsSum` / `VisitSetBitRunsSum`
| params | A `VisitBitRunsSum` | A `VisitSetBitRunsSum` | A ratio | B `VisitBitRunsSum` | B `VisitSetBitRunsSum` | B ratio | Δ ratio (B-A) |
|---:|---:|---:|---:|---:|---:|---:|---:|
| 2 | 3.41e+8 | 4.00e+8 | 0.8526 | 3.58e+8 | 4.07e+8 | 0.8812 | +0.0286 |
| 8 | 6.44e+8 | 6.36e+8 | 1.0130 | 5.84e+8 | 6.49e+8 | 0.8995 | -0.1135 |
| 64 | 1.57e+9 | 2.64e+9 | 0.5946 | 2.27e+9 | 2.59e+9 | 0.8757 | +0.2810 |
| 512 | 2.33e+9 | 9.07e+9 | 0.2571 | 8.53e+9 | 9.00e+9 | 0.9473 | +0.6902 |
| 4096 | 2.57e+9 | 1.22e+10 | 0.2110 | 1.23e+10 | 1.22e+10 | 1.0099 | +0.7988 |
| 32768 | 2.59e+9 | 1.29e+10 | 0.2014 | 1.31e+10 | 1.28e+10 | 1.0180 | +0.8165 |
| 65536 | 2.59e+9 | 1.29e+10 | 0.2012 | 1.31e+10 | 1.29e+10 | 1.0176 | +0.8164 |
However, even if the bitmap benchmark results improve, it doesn't necessarily mean there will be improvements in other benchmark cases. I looked at the three test cases in the benchmark report above. `ArrayArrayKernel` seems unrelated to the path I modified. I couldn't reproduce the remaining two tests in my own x86 environment. I rerun the benchmark, and if it still shows a performance regression, I plan to roll back the `BitRunReader` changes. Optimizing `BitRunReader` wasn't the original purpose of this PR.
--
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-50280: [C++] Implement VisitTwoBitRuns and VisitTwoSetBitRuns methods [arrow]
Posted by "pitrou (via GitHub)" <gi...@apache.org>.
pitrou commented on PR #50281:
URL: https://github.com/apache/arrow/pull/50281#issuecomment-5055859640
@ursabot please benchmark lang=C++
--
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-50280: [C++] Implement VisitTwoBitRuns and VisitTwoSetBitRuns methods [arrow]
Posted by "pitrou (via GitHub)" <gi...@apache.org>.
pitrou commented on code in PR #50281:
URL: https://github.com/apache/arrow/pull/50281#discussion_r3529779180
##########
cpp/src/arrow/util/bit_run_reader.h:
##########
@@ -536,5 +542,79 @@ inline void VisitSetBitRunsVoid(const std::shared_ptr<Buffer>& bitmap, int64_t o
std::forward<Visit>(visit));
}
+template <typename Visit>
+inline Status VisitTwoSetBitRuns(const uint8_t* left_bitmap, int64_t left_offset,
+ const uint8_t* right_bitmap, int64_t right_offset,
+ int64_t length, Visit&& visit,
+ MemoryPool* pool = default_memory_pool()) {
+ if (length == 0) {
+ return Status::OK();
+ }
+ if (left_bitmap == NULLPTR) {
+ return VisitSetBitRuns(right_bitmap, right_offset, length,
+ std::forward<Visit>(visit));
+ }
+ if (right_bitmap == NULLPTR) {
+ return VisitSetBitRuns(left_bitmap, left_offset, length, std::forward<Visit>(visit));
+ }
+
+ ARROW_ASSIGN_OR_RAISE(auto bitmap_and,
+ BitmapAnd(pool, left_bitmap, left_offset, right_bitmap,
+ right_offset, length, /*out_offset=*/0));
+ return VisitSetBitRuns(bitmap_and->data(), /*offset=*/0, length,
+ std::forward<Visit>(visit));
+}
+
+template <typename Visit>
+inline Status VisitTwoBitRuns(const uint8_t* left_bitmap, int64_t left_offset,
+ const uint8_t* right_bitmap, int64_t right_offset,
+ int64_t length, Visit&& visit,
+ MemoryPool* pool = default_memory_pool()) {
+ int64_t output_position = 0;
+ ARROW_RETURN_NOT_OK(VisitTwoSetBitRuns(
+ left_bitmap, left_offset, right_bitmap, right_offset, length,
+ [&](int64_t position, int64_t run_length) {
+ if (output_position < position) {
+ ARROW_RETURN_NOT_OK(visit(output_position, position - output_position, false));
+ }
+ ARROW_RETURN_NOT_OK(visit(position, run_length, true));
+ output_position = position + run_length;
+ return Status::OK();
+ },
+ pool));
+ if (output_position < length) {
+ return visit(output_position, length - output_position, false);
+ }
+ return Status::OK();
+}
+
+template <typename Visit>
+inline void VisitTwoBitRunsVoid(const uint8_t* left_bitmap, int64_t left_offset,
+ const uint8_t* right_bitmap, int64_t right_offset,
+ int64_t length, Visit&& visit,
+ MemoryPool* pool = default_memory_pool()) {
+ ARROW_IGNORE_EXPR(VisitTwoBitRuns(
Review Comment:
`ARROW_IGNORE_EXPR` implies that we'll ignore any failure allocating the temporary bitmap in `BitmapAnd`. We could instead abort but it wouldn't be much better.
--
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-50280: [C++] Implement VisitTwoBitRuns and VisitTwoSetBitRuns methods [arrow]
Posted by "conbench-apache-arrow[bot] (via GitHub)" <gi...@apache.org>.
conbench-apache-arrow[bot] commented on PR #50281:
URL: https://github.com/apache/arrow/pull/50281#issuecomment-5077295935
After merging your PR, Conbench analyzed the 4 benchmarking runs that have been run so far on merge-commit aa78eb89733134c4a8db8b5840960676f96df103.
There were no benchmark performance regressions. 🎉
The [full Conbench report](https://github.com/apache/arrow/runs/89651829125) has more details. It also includes information about 57 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-50280: [C++] Implement VisitTwoBitRuns and VisitTwoSetBitRuns methods [arrow]
Posted by "HuaHuaY (via GitHub)" <gi...@apache.org>.
HuaHuaY commented on PR #50281:
URL: https://github.com/apache/arrow/pull/50281#issuecomment-5053844315
Hi @pitrou, I have cherry-picked [710cedd](https://github.com/apache/arrow/pull/50392/commits/710ceddd54bcfef56a40f37aa90e19f0b004cd53). Please take a look again.
--
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-50280: [C++] Implement VisitTwoBitRuns and VisitTwoSetBitRuns methods [arrow]
Posted by "HuaHuaY (via GitHub)" <gi...@apache.org>.
HuaHuaY commented on PR #50281:
URL: https://github.com/apache/arrow/pull/50281#issuecomment-4854749792
These are the results from the last benchmark and this benchmark, grouped in pairs, with the latest results following. I think that after optimizing BitRunReader, the performance gap between VisitBitRuns and VisitSetBitRuns has indeed narrowed in most cases. @pitrou Please take a look.
## 4ab7d672 / amd64-c6a-4xlarge-linux / c0d6bf7
| Benchmark | 2 | 8 | 64 | 512 | 4096 | 32768 | 65536 |
|---|---:|---:|---:|---:|---:|---:|---:|
| `BitBlockCounterSum` | 2.59e+8 | 6.46e+8 | 1.39e+9 | 3.58e+9 | 4.90e+9 | 5.15e+9 | 5.17e+9 |
| `VisitBitRunsSum` | 3.10e+8 | 5.70e+8 | 2.07e+9 | 4.30e+9 | 4.68e+9 | 4.73e+9 | 4.73e+9 |
| `VisitSetBitRunsSum` | 3.59e+8 | 6.40e+8 | 2.20e+9 | 4.58e+9 | 4.88e+9 | 4.93e+9 | 4.94e+9 |
## d164bbbe / amd64-c6a-4xlarge-linux / 3b5b2d0
| Benchmark | 2 | 8 | 64 | 512 | 4096 | 32768 | 65536 |
|---|---:|---:|---:|---:|---:|---:|---:|
| `BitBlockCounterSum` | 2.56e+8 | 6.37e+8 | 1.37e+9 | 3.55e+9 | 4.85e+9 | 5.09e+9 | 5.11e+9 |
| `VisitBitRunsSum` | 3.13e+8 | 5.75e+8 | 2.10e+9 | 4.38e+9 | 4.70e+9 | 4.76e+9 | 4.76e+9 |
| `VisitSetBitRunsSum` | 3.39e+8 | 6.07e+8 | 2.17e+9 | 4.50e+9 | 4.80e+9 | 4.86e+9 | 4.87e+9 |
## fd5a984c / amd64-m5-4xlarge-linux / c0d6bf7
| Benchmark | 2 | 8 | 64 | 512 | 4096 | 32768 | 65536 |
|---|---:|---:|---:|---:|---:|---:|---:|
| `BitBlockCounterSum` | 2.00e+8 | 4.55e+8 | 9.33e+8 | 1.88e+9 | 2.26e+9 | 2.32e+9 | 2.32e+9 |
| `VisitBitRunsSum` | 2.07e+8 | 3.73e+8 | 1.15e+9 | 1.98e+9 | 2.17e+9 | 2.19e+9 | 2.19e+9 |
| `VisitSetBitRunsSum` | 2.34e+8 | 4.01e+8 | 1.15e+9 | 2.03e+9 | 2.24e+9 | 2.26e+9 | 2.26e+9 |
## e74c6927 / amd64-m5-4xlarge-linux / 3b5b2d0
| Benchmark | 2 | 8 | 64 | 512 | 4096 | 32768 | 65536 |
|---|---:|---:|---:|---:|---:|---:|---:|
| `BitBlockCounterSum` | 2.00e+8 | 4.55e+8 | 9.34e+8 | 1.88e+9 | 2.26e+9 | 2.32e+9 | 2.32e+9 |
| `VisitBitRunsSum` | 2.18e+8 | 3.84e+8 | 1.15e+9 | 1.97e+9 | 2.15e+9 | 2.17e+9 | 2.17e+9 |
| `VisitSetBitRunsSum` | 2.30e+8 | 3.99e+8 | 1.15e+9 | 2.03e+9 | 2.24e+9 | 2.26e+9 | 2.26e+9 |
## 457fe991 / test-mac-arm / c0d6bf7
| Benchmark | 2 | 8 | 64 | 512 | 4096 | 32768 | 65536 |
|---|---:|---:|---:|---:|---:|---:|---:|
| `BitBlockCounterSum` | 2.60e+8 | 7.22e+8 | 1.98e+9 | 5.40e+9 | 7.09e+9 | 7.29e+9 | 7.30e+9 |
| `VisitBitRunsSum` | 3.41e+8 | 6.44e+8 | 1.57e+9 | 2.33e+9 | 2.57e+9 | 2.59e+9 | 2.59e+9 |
| `VisitSetBitRunsSum` | 4.00e+8 | 6.36e+8 | 2.64e+9 | 9.07e+9 | 1.22e+10 | 1.29e+10 | 1.29e+10 |
## 6701543e / test-mac-arm / 3b5b2d0
| Benchmark | 2 | 8 | 64 | 512 | 4096 | 32768 | 65536 |
|---|---:|---:|---:|---:|---:|---:|---:|
| `BitBlockCounterSum` | 2.60e+8 | 7.16e+8 | 1.90e+9 | 5.33e+9 | 7.03e+9 | 7.27e+9 | 7.29e+9 |
| `VisitBitRunsSum` | 3.58e+8 | 5.84e+8 | 2.27e+9 | 8.53e+9 | 1.23e+10 | 1.31e+10 | 1.31e+10 |
| `VisitSetBitRunsSum` | 4.07e+8 | 6.49e+8 | 2.59e+9 | 9.00e+9 | 1.22e+10 | 1.28e+10 | 1.29e+10 |
--
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-50280: [C++] Implement VisitTwoBitRuns and VisitTwoSetBitRuns methods [arrow]
Posted by "HuaHuaY (via GitHub)" <gi...@apache.org>.
HuaHuaY commented on PR #50281:
URL: https://github.com/apache/arrow/pull/50281#issuecomment-4845192292
I've compiled the test data into three tables. `BinaryBitBlockCounterSum` is faster than `BinaryVisitTwoSetBitRunsSum` when there are many null values, which I think is expected. In this case, merging the two bitmaps results in too many consecutive intervals, making it slower than judging multiple bits at once.
However, I was somewhat surprised that in x86 tests, `BinaryBitBlockCounterSum` achieved better performance when there were almost no null values. I don't understand why.
There were also some unexpected findings. Currently, `BinaryVisitTwoSetBitRunsSum` performs better than `BinaryVisitTwoBitRunsSum`. This is partly due to function implementation, and partly because `SetBitRunReader` performs better than `BitRunReader`. I will later adjust `BinaryVisitTwoBitRunsSum` to use `SetBitRunReader` (`BinaryVisitTwoBitRunsSum` can directly wrap `BinaryVisitTwoSetBitRunsSum`). I haven't yet figured out why `SetBitRunReader` is faster.
Based on these test results, I plan to revert the changes to `cpp/src/arrow/compute/kernels/hash_aggregate_pivot.cc`. However, I think that the real value of `BinaryVisitTwoSetBitRunsSum` lies in its ability to handle data in batches rather than row-by-row, allowing the use of vector-processing functions such as `::arrow::bit_util::SetBitsTo` or `::arrow::internal::CountSetBits`. Since I plan to use it in a future PR, I'd like to add benchmark scenarios that will showcase the advantages of `BinaryVisitTwoSetBitRunsSum`.
## 4ab7d672 / amd64-c6a-4xlarge-linux / c0d6bf7
| Benchmark | 2 | 8 | 64 | 512 | 4096 | 32768 | 65536 |
|---|---:|---:|---:|---:|---:|---:|---:|
| `BitBlockCounterSum` | 2.59e+8 | 6.46e+8 | 1.39e+9 | 3.58e+9 | 4.90e+9 | 5.15e+9 | 5.17e+9 |
| `VisitBitRunsSum` | 3.10e+8 | 5.70e+8 | 2.07e+9 | 4.30e+9 | 4.68e+9 | 4.73e+9 | 4.73e+9 |
| `VisitSetBitRunsSum` | 3.59e+8 | 6.40e+8 | 2.20e+9 | 4.58e+9 | 4.88e+9 | 4.93e+9 | 4.94e+9 |
| `BinaryBitBlockCounterSum` | 1.79e+8 | 3.68e+8 | 7.40e+8 | 1.99e+9 | 3.69e+9 | 4.18e+9 | 4.22e+9 |
| `BinaryVisitTwoBitRunsSum` | 1.40e+8 | 2.42e+8 | 9.38e+8 | 2.61e+9 | 3.36e+9 | 3.49e+9 | 3.52e+9 |
| `BinaryVisitTwoSetBitRunsSum` | 1.78e+8 | 2.77e+8 | 1.03e+9 | 3.05e+9 | 3.94e+9 | 4.06e+9 | 4.08e+9 |
## fd5a984c / amd64-m5-4xlarge-linux / c0d6bf7
| Benchmark | 2 | 8 | 64 | 512 | 4096 | 32768 | 65536 |
|---|---:|---:|---:|---:|---:|---:|---:|
| `BitBlockCounterSum` | 2.00e+8 | 4.55e+8 | 9.33e+8 | 1.88e+9 | 2.26e+9 | 2.32e+9 | 2.32e+9 |
| `VisitBitRunsSum` | 2.07e+8 | 3.73e+8 | 1.15e+9 | 1.98e+9 | 2.17e+9 | 2.19e+9 | 2.19e+9 |
| `VisitSetBitRunsSum` | 2.34e+8 | 4.01e+8 | 1.15e+9 | 2.03e+9 | 2.24e+9 | 2.26e+9 | 2.26e+9 |
| `BinaryBitBlockCounterSum` | 1.20e+8 | 2.13e+8 | 4.06e+8 | 1.02e+9 | 1.79e+9 | 2.00e+9 | 2.01e+9 |
| `BinaryVisitTwoBitRunsSum` | 1.05e+8 | 1.77e+8 | 5.93e+8 | 1.34e+9 | 1.63e+9 | 1.67e+9 | 1.68e+9 |
| `BinaryVisitTwoSetBitRunsSum` | 1.16e+8 | 1.83e+8 | 6.26e+8 | 1.51e+9 | 1.87e+9 | 1.91e+9 | 1.91e+9 |
## 457fe991 / test-mac-arm / c0d6bf7
| Benchmark | 2 | 8 | 64 | 512 | 4096 | 32768 | 65536 |
|---|---:|---:|---:|---:|---:|---:|---:|
| `BitBlockCounterSum` | 2.60e+8 | 7.22e+8 | 1.98e+9 | 5.40e+9 | 7.09e+9 | 7.29e+9 | 7.30e+9 |
| `VisitBitRunsSum` | 3.41e+8 | 6.44e+8 | 1.57e+9 | 2.33e+9 | 2.57e+9 | 2.59e+9 | 2.59e+9 |
| `VisitSetBitRunsSum` | 4.00e+8 | 6.36e+8 | 2.64e+9 | 9.07e+9 | 1.22e+10 | 1.29e+10 | 1.29e+10 |
| `BinaryBitBlockCounterSum` | 1.79e+8 | 4.07e+8 | 1.00e+9 | 2.52e+9 | 4.76e+9 | 5.38e+9 | 5.44e+9 |
| `BinaryVisitTwoBitRunsSum` | 1.75e+8 | 2.99e+8 | 1.12e+9 | 3.91e+9 | 5.64e+9 | 5.90e+9 | 5.93e+9 |
| `BinaryVisitTwoSetBitRunsSum` | 2.28e+8 | 3.17e+8 | 1.21e+9 | 4.14e+9 | 6.09e+9 | 6.40e+9 | 6.42e+9 |
--
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-50280: [C++] Implement VisitTwoBitRuns and VisitTwoSetBitRuns methods [arrow]
Posted by "HuaHuaY (via GitHub)" <gi...@apache.org>.
HuaHuaY commented on PR #50281:
URL: https://github.com/apache/arrow/pull/50281#issuecomment-4862097572
A performance regression has indeed occurred on ·amd64-c6a-4xlarge-linux·. I will revert related changes soon.
--
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-50280: [C++] Implement VisitTwoBitRuns and VisitTwoSetBitRuns methods [arrow]
Posted by "HuaHuaY (via GitHub)" <gi...@apache.org>.
HuaHuaY commented on PR #50281:
URL: https://github.com/apache/arrow/pull/50281#issuecomment-4863134897
Hi @pitrou, I have reverted all code changes on existing paths; the rest are new code and should not affect existing benchmarks. Please take a look again.
--
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-50280: [C++] Implement VisitTwoBitRuns and VisitTwoSetBitRuns methods [arrow]
Posted by "pitrou (via GitHub)" <gi...@apache.org>.
pitrou commented on PR #50281:
URL: https://github.com/apache/arrow/pull/50281#issuecomment-4845340716
> I haven't yet figured out why `SetBitRunReader` is so much faster.
Because it's simpler :)
--
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-50280: [C++] Implement VisitTwoBitRuns and VisitTwoSetBitRuns methods [arrow]
Posted by "conbench-apache-arrow[bot] (via GitHub)" <gi...@apache.org>.
conbench-apache-arrow[bot] commented on PR #50281:
URL: https://github.com/apache/arrow/pull/50281#issuecomment-4844107964
Thanks for your patience. Conbench analyzed the 3 benchmarking runs that have been run so far on PR commit c0d6bf7f428e8417efad2e675331b26d98e23a0f.
There were 5 benchmark results indicating a performance regression:
- Pull Request Run on `amd64-c6a-4xlarge-linux` at [2026-06-30 10:39:17Z](https://conbench.arrow-dev.org/compare/runs/1b61ec2a2670462f8c788da25fda3ca6...4ab7d6720b8c4e698e643f35819745c7/)
- [`BenchmarkTemporalRounding` (C++) with params=<RoundTemporal, zoned, round_1_month>/524288/0, source=cpp-micro, suite=arrow-compute-scalar-temporal-benchmark](https://conbench.arrow-dev.org/compare/benchmarks/06a42fc503ba7b01800029ebddb97ef0...06a439e3e6a87bce8000d9da145470bb)
- [`BM_UnpackUint8` (C++) with params=ScalarUnaligned/1/64, source=cpp-micro, suite=arrow-bpacking-benchmark](https://conbench.arrow-dev.org/compare/benchmarks/06a42fc15f8b7a788000a4b621d5c973...06a439e036967f1e80005086fe05383b)
- and 3 more (see the report linked below)
The [full Conbench report](https://github.com/apache/arrow/runs/84305379739) has more details.
--
This is an automated message from the Apache Git Service.
To respond to the message, please log on to GitHub and use the
URL above to go to the specific comment.
To unsubscribe, e-mail: github-unsubscribe@arrow.apache.org
For queries about this service, please contact Infrastructure at:
users@infra.apache.org
Re: [PR] GH-50280: [C++] Implement VisitTwoBitRuns and VisitTwoSetBitRuns methods [arrow]
Posted by "github-actions[bot] (via GitHub)" <gi...@apache.org>.
github-actions[bot] commented on PR #50281:
URL: https://github.com/apache/arrow/pull/50281#issuecomment-4832283772
:warning: GitHub issue #50280 **has been automatically assigned in GitHub** to PR creator.
--
This is an automated message from the Apache Git Service.
To respond to the message, please log on to GitHub and use the
URL above to go to the specific comment.
To unsubscribe, e-mail: github-unsubscribe@arrow.apache.org
For queries about this service, please contact Infrastructure at:
users@infra.apache.org
Re: [PR] GH-50280: [C++] Implement VisitTwoBitRuns and VisitTwoSetBitRuns methods [arrow]
Posted by "rok (via GitHub)" <gi...@apache.org>.
rok commented on PR #50281:
URL: https://github.com/apache/arrow/pull/50281#issuecomment-4861670317
Benchmark runs are scheduled for commit 41af9ca220dfbf40cac6554b94efe8ba94cf902e. Watch https://buildkite.com/apache-arrow and https://conbench.arrow-dev.org for updates. A comment will be posted here when the runs are complete.
--
This is an automated message from the Apache Git Service.
To respond to the message, please log on to GitHub and use the
URL above to go to the specific comment.
To unsubscribe, e-mail: github-unsubscribe@arrow.apache.org
For queries about this service, please contact Infrastructure at:
users@infra.apache.org
Re: [PR] GH-50280: [C++] Implement VisitTwoBitRuns and VisitTwoSetBitRuns methods [arrow]
Posted by "HuaHuaY (via GitHub)" <gi...@apache.org>.
HuaHuaY commented on code in PR #50281:
URL: https://github.com/apache/arrow/pull/50281#discussion_r3636617001
##########
cpp/src/arrow/util/bit_run_reader.h:
##########
@@ -536,5 +544,93 @@ inline void VisitSetBitRunsVoid(const std::shared_ptr<Buffer>& bitmap, int64_t o
std::forward<Visit>(visit));
}
+template <typename Visit>
+inline Status VisitTwoSetBitRuns(const uint8_t* left_bitmap, int64_t left_offset,
+ const uint8_t* right_bitmap, int64_t right_offset,
+ int64_t length, Visit&& visit,
+ MemoryPool* pool = default_memory_pool()) {
Review Comment:
Previously, we allocated memory for bitmap using this pool. Now bitmap uses stack space. I will remove this parameter.
--
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-50280: [C++] Implement VisitTwoBitRuns and VisitTwoSetBitRuns methods [arrow]
Posted by "pitrou (via GitHub)" <gi...@apache.org>.
pitrou merged PR #50281:
URL: https://github.com/apache/arrow/pull/50281
--
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-50280: [C++] Implement VisitTwoBitRuns and VisitTwoSetBitRuns methods [arrow]
Posted by "conbench-apache-arrow[bot] (via GitHub)" <gi...@apache.org>.
conbench-apache-arrow[bot] commented on PR #50281:
URL: https://github.com/apache/arrow/pull/50281#issuecomment-4854732760
Thanks for your patience. Conbench analyzed the 4 benchmarking runs that have been run so far on PR commit 3b5b2d00dda7476a504ff7aff41234ffc2d690d3.
There were 3 benchmark results indicating a performance regression:
- Pull Request Run on `amd64-c6a-4xlarge-linux` at [2026-07-01 10:25:34Z](https://conbench.arrow-dev.org/compare/runs/1b61ec2a2670462f8c788da25fda3ca6...d164bbbeee294086b961cdb73a925ecf/)
- [`CoalesceScalarBench64` (C++) with params=2, source=cpp-micro, suite=arrow-compute-scalar-if-else-benchmark](https://conbench.arrow-dev.org/compare/benchmarks/06a42fc5a28e71b78000f71b4bc34bfb...06a44ebd92bb79708000f9dcda75fb31)
- [`CoalesceScalarBench64` (C++) with params=4, source=cpp-micro, suite=arrow-compute-scalar-if-else-benchmark](https://conbench.arrow-dev.org/compare/benchmarks/06a42fc5a2f47348800068061d6eb4b5...06a44ebd931c72d58000840f16859d17)
- and 1 more (see the report linked below)
The [full Conbench report](https://github.com/apache/arrow/runs/84531834755) has more details.
--
This is an automated message from the Apache Git Service.
To respond to the message, please log on to GitHub and use the
URL above to go to the specific comment.
To unsubscribe, e-mail: github-unsubscribe@arrow.apache.org
For queries about this service, please contact Infrastructure at:
users@infra.apache.org
Re: [PR] GH-50280: [C++] Implement VisitTwoBitRuns and VisitTwoSetBitRuns methods [arrow]
Posted by "HuaHuaY (via GitHub)" <gi...@apache.org>.
HuaHuaY commented on PR #50281:
URL: https://github.com/apache/arrow/pull/50281#issuecomment-4858108106
@ursabot please benchmark lang=C++
--
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-50280: [C++] Implement VisitTwoBitRuns and VisitTwoSetBitRuns methods [arrow]
Posted by "conbench-apache-arrow[bot] (via GitHub)" <gi...@apache.org>.
conbench-apache-arrow[bot] commented on PR #50281:
URL: https://github.com/apache/arrow/pull/50281#issuecomment-4859733109
Thanks for your patience. Conbench analyzed the 3 benchmarking runs that have been run so far on PR commit b026a7d9c1bfb46b6726db95e25b2e55026c7221.
There were no benchmark performance regressions. 🎉
The [full Conbench report](https://github.com/apache/arrow/runs/84628944869) has more details.
--
This is an automated message from the Apache Git Service.
To respond to the message, please log on to GitHub and use the
URL above to go to the specific comment.
To unsubscribe, e-mail: github-unsubscribe@arrow.apache.org
For queries about this service, please contact Infrastructure at:
users@infra.apache.org
Re: [PR] GH-50280: [C++] Implement VisitTwoBitRuns and VisitTwoSetBitRuns methods [arrow]
Posted by "HuaHuaY (via GitHub)" <gi...@apache.org>.
HuaHuaY commented on PR #50281:
URL: https://github.com/apache/arrow/pull/50281#issuecomment-4874119717
> Well, why not have VisitTwoBitRuns functions that actually do the grunt job of materializing bitmap chunks and iterating on them?
Oh, you're right. We can add a wrapper to avoid code duplication when iterating over two bitmaps simultaneously. Let's reopen this PR and I will refactor the code later.
--
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-50280: [C++] Implement VisitTwoBitRuns and VisitTwoSetBitRuns methods [arrow]
Posted by "pitrou (via GitHub)" <gi...@apache.org>.
pitrou commented on PR #50281:
URL: https://github.com/apache/arrow/pull/50281#issuecomment-4894134427
@HuaHuaY I opened https://github.com/apache/arrow/pull/50392 to measure performance when using a batched version of `VisitTwoBitRuns` (my laptop seems to give unpredictable perf results).
--
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-50280: [C++] Implement VisitTwoBitRuns and VisitTwoSetBitRuns methods [arrow]
Posted by "pitrou (via GitHub)" <gi...@apache.org>.
pitrou commented on code in PR #50281:
URL: https://github.com/apache/arrow/pull/50281#discussion_r3636431077
##########
cpp/src/arrow/util/bit_run_reader.h:
##########
@@ -536,5 +544,93 @@ inline void VisitSetBitRunsVoid(const std::shared_ptr<Buffer>& bitmap, int64_t o
std::forward<Visit>(visit));
}
+template <typename Visit>
+inline Status VisitTwoSetBitRuns(const uint8_t* left_bitmap, int64_t left_offset,
+ const uint8_t* right_bitmap, int64_t right_offset,
+ int64_t length, Visit&& visit,
+ MemoryPool* pool = default_memory_pool()) {
Review Comment:
The `MemoryPool` argument can be removed from all those functions since AFAICT it's not being used.
##########
cpp/src/arrow/util/bit_run_reader.h:
##########
@@ -17,15 +17,23 @@
#pragma once
+#include <algorithm>
+#include <array>
#include <bit>
#include <cassert>
#include <cstdint>
#include <cstring>
#include <string>
+#include <utility>
+#include "arrow/buffer.h"
+#include "arrow/memory_pool.h"
Review Comment:
These two inclusions are probably not necessary.
--
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-50280: [C++] Implement VisitTwoBitRuns and VisitTwoSetBitRuns methods [arrow]
Posted by "HuaHuaY (via GitHub)" <gi...@apache.org>.
HuaHuaY commented on PR #50281:
URL: https://github.com/apache/arrow/pull/50281#issuecomment-4853093293
I added a new benchmark to count the number of valid int8 values in a random `struct<a: struct<b: int8>>` array. Due to the use of `CountSetBits` batch interface, `VisitTwoBitRunsVoid` achieves better performance than `VisitTwoBitBlocksVoid` in most cases.
parent_null_every | value_null_every | BitBlocks ns | BitRuns ns | vs block | SetBitRuns ns | vs block
-- | -- | -- | -- | -- | -- | --
2 | 2 | 5100500 | 3247773 | 0.64x | 3272429 | 0.64x
2 | 8 | 4592000 | 3371095 | 0.73x | 3245095 | 0.71x
2 | 64 | 4338500 | 3281286 | 0.76x | 3272810 | 0.75x
8 | 2 | 4439125 | 3052261 | 0.69x | 3103000 | 0.70x
8 | 8 | 2801040 | 3075136 | 1.10x | 3090304 | 1.10x
8 | 64 | 2326967 | 3070955 | 1.32x | 3171870 | 1.36x
64 | 2 | 4132647 | 813513 | 0.20x | 848000 | 0.21x
64 | 8 | 2026114 | 835193 | 0.41x | 823469 | 0.41x
64 | 64 | 1456122 | 789952 | 0.54x | 842785 | 0.58x
512 | 2 | 3918444 | 100072 | 0.03x | 98034 | 0.03x
4096 | 2 | 3878944 | 26525 | 0.01x | 26539 | 0.01x
65536 | 65536 | 1052229 | 14449 | 0.01x | 14641 | 0.01x
--
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-50280: [C++] Implement VisitTwoBitRuns and VisitTwoSetBitRuns methods [arrow]
Posted by "HuaHuaY (via GitHub)" <gi...@apache.org>.
HuaHuaY commented on code in PR #50281:
URL: https://github.com/apache/arrow/pull/50281#discussion_r3518026950
##########
cpp/src/arrow/util/nested_bitmap_traversal_benchmark.cc:
##########
@@ -0,0 +1,154 @@
+// Licensed to the Apache Software Foundation (ASF) under one
+// or more contributor license agreements. See the NOTICE file
+// distributed with this work for additional information
+// regarding copyright ownership. The ASF licenses this file
+// to you under the Apache License, Version 2.0 (the
+// "License"); you may not use this file except in compliance
+// with the License. You may obtain a copy of the License at
+//
+// http://www.apache.org/licenses/LICENSE-2.0
+//
+// Unless required by applicable law or agreed to in writing,
+// software distributed under the License is distributed on an
+// "AS IS" BASIS, WITHOUT WARRANTIES OR CONDITIONS OF ANY
+// KIND, either express or implied. See the License for the
+// specific language governing permissions and limitations
+// under the License.
+
+#include "benchmark/benchmark.h"
+
+#include <cstdint>
+#include <cstdlib>
+#include <memory>
+
+#include "arrow/array/array_base.h"
+#include "arrow/array/array_nested.h"
+#include "arrow/array/array_primitive.h"
+#include "arrow/testing/gtest_util.h"
+#include "arrow/testing/random.h"
+#include "arrow/type.h"
+#include "arrow/util/bit_block_counter.h"
+#include "arrow/util/bit_run_reader.h"
+#include "arrow/util/bitmap_ops.h"
+
+namespace arrow::internal {
+
+struct NestedBitmapTraversalBenchmark {
Review Comment:
I modified this benchmark to count the number of valid values in a `list<int8>` given an outer bitmap. But after testing the new benchmark, I discovered something unexpected: the baseline approach—`bitmapand` combined with `VisitSetBitRunsVoid`—actually turned out to be the fastest. I attribute this to the bitmap's minimal memory footprint, where the performance gains from `bitmapand`'s vectorization outweigh the overhead of materializing the bitmap. Consequently, I have decided to close this PR and simply materialize the bitmap directly when needed.
At the same time, `VisitTwoBitBlocks` appears to offer the worst performance. I’m curious whether replacing the current usages of `VisitTwoBitBlocks` with `bitmapAnd` might actually improve 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
Re: [PR] GH-50280: [C++] Implement VisitTwoBitRuns and VisitTwoSetBitRuns methods [arrow]
Posted by "HuaHuaY (via GitHub)" <gi...@apache.org>.
HuaHuaY commented on PR #50281:
URL: https://github.com/apache/arrow/pull/50281#issuecomment-4873657051
After testing the new benchmark, I discovered something unexpected: the baseline approach—bitmapand combined with VisitSetBitRunsVoid—actually turned out to be the fastest. I attribute this to the bitmap's minimal memory footprint, where the performance gains from bitmapand's vectorization outweigh the overhead of materializing the bitmap. Consequently, I have decided to close this PR and simply materialize the bitmap directly when needed.
At the same time, VisitTwoBitBlocks appears to offer the worst performance. I’m curious whether replacing the current usages of VisitTwoBitBlocks with bitmapAnd might actually improve performance. I may look into modifying the code and running benchmarks to test this when I have the time.
--
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-50280: [C++] Implement VisitTwoBitRuns and VisitTwoSetBitRuns methods [arrow]
Posted by "pitrou (via GitHub)" <gi...@apache.org>.
pitrou commented on PR #50281:
URL: https://github.com/apache/arrow/pull/50281#issuecomment-4874095870
> After testing the new benchmark, I discovered something unexpected: the baseline approach—`BitmapAnd` combined with `VisitSetBitRunsVoid`—actually turned out to be the fastest. I attribute this to the bitmap's minimal memory footprint (A bitmap with 1 million elements occupies only 128 KB),
This is also going to vary based on memory and cache intensivity of the current workload. Micro-benchmarks generally don't hit very hard on the memory subsystem (and they are single-threaded), so temporary allocations can seem very cheap, especially if the same allocation size is repeated over and over.
> Consequently, I have decided to close this PR and simply materialize the bitmap directly when needed.
Well, why not have `VisitTwoBitRuns` functions that actually do the grunt job of materializing bitmap chunks and iterating on 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-50280: [C++] Implement VisitTwoBitRuns and VisitTwoSetBitRuns methods [arrow]
Posted by "HuaHuaY (via GitHub)" <gi...@apache.org>.
HuaHuaY commented on PR #50281:
URL: https://github.com/apache/arrow/pull/50281#issuecomment-4861665353
@ursabot please benchmark lang=C++
--
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-50280: [C++] Implement VisitTwoBitRuns and VisitTwoSetBitRuns methods [arrow]
Posted by "rok (via GitHub)" <gi...@apache.org>.
rok commented on PR #50281:
URL: https://github.com/apache/arrow/pull/50281#issuecomment-4852556455
Benchmark runs are scheduled for commit 3b5b2d00dda7476a504ff7aff41234ffc2d690d3. Watch https://buildkite.com/apache-arrow and https://conbench.arrow-dev.org for updates. A comment will be posted here when the runs are complete.
--
This is an automated message from the Apache Git Service.
To respond to the message, please log on to GitHub and use the
URL above to go to the specific comment.
To unsubscribe, e-mail: github-unsubscribe@arrow.apache.org
For queries about this service, please contact Infrastructure at:
users@infra.apache.org
Re: [PR] GH-50280: [C++] Implement VisitTwoBitRuns and VisitTwoSetBitRuns methods [arrow]
Posted by "HuaHuaY (via GitHub)" <gi...@apache.org>.
HuaHuaY commented on PR #50281:
URL: https://github.com/apache/arrow/pull/50281#issuecomment-4861669807
@ursabot please benchmark lang=C++
--
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-50280: [C++] Implement VisitTwoBitRuns and VisitTwoSetBitRuns methods [arrow]
Posted by "conbench-apache-arrow[bot] (via GitHub)" <gi...@apache.org>.
conbench-apache-arrow[bot] commented on PR #50281:
URL: https://github.com/apache/arrow/pull/50281#issuecomment-5059378071
Thanks for your patience. Conbench analyzed the 4 benchmarking runs that have been run so far on PR commit 31668092ab4e24e19a7ce0bbab313ecd0f0dc88d.
There were 47 benchmark results indicating a performance regression:
- Pull Request Run on `amd64-c6a-4xlarge-linux` at [2026-07-23 09:00:42Z](https://conbench.arrow-dev.org/compare/runs/c667cdd9dd20491da838e5f774157405...d3dd0e1e64d346af94c3c03c132c4a34/)
- [`ArrayArrayKernel` (C++) with params=<AddChecked, Int16Type>/size:524288/inverse_null_proportion:100, source=cpp-micro, suite=arrow-compute-scalar-arithmetic-benchmark](https://conbench.arrow-dev.org/compare/benchmarks/06a60dc1740a75e98000633ce1623dca...06a61daccc1b7b0a8000cfeb81b14c68)
- [`BenchmarkTemporal` (C++) with params=<ISOWeek, non_zoned>/524288/100, source=cpp-micro, suite=arrow-compute-scalar-temporal-benchmark](https://conbench.arrow-dev.org/compare/benchmarks/06a60dbf10547fe28000243bdfdb57fc...06a61daaa4d5728b8000e282b088634a)
- and 45 more (see the report linked below)
The [full Conbench report](https://github.com/apache/arrow/runs/89230218425) has more details.
--
This is an automated message from the Apache Git Service.
To respond to the message, please log on to GitHub and use the
URL above to go to the specific comment.
To unsubscribe, e-mail: github-unsubscribe@arrow.apache.org
For queries about this service, please contact Infrastructure at:
users@infra.apache.org
Re: [PR] GH-50280: [C++] Implement VisitTwoBitRuns and VisitTwoSetBitRuns methods [arrow]
Posted by "HuaHuaY (via GitHub)" <gi...@apache.org>.
HuaHuaY commented on PR #50281:
URL: https://github.com/apache/arrow/pull/50281#issuecomment-4849908388
With the help of AI, I investigated why `VisitBitRuns` is slower than `VisitSetBitRuns` by modifying benchmarks and examining the generated assembly code.
I concluded that the primary reason lies in the absence of the `NOINLINE` attribute on `BitRunReader::NextRun`; this results in a larger code size for `VisitBitRuns` compared to `VisitSetBitRuns`, making `VisitBitRuns` itself less likely to be inlined. However, adding the `NOINLINE` attribute to `BitRunReader::NextRun` actually degrades performance further, as it forces a non-inlined call to `NextRun` regardless of whether the bitmap value is true or false.
Additionally, `BitRunReader` contains some minor code duplication that can be optimized. I will upload the changes shortly.
--
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-50280: [C++] Implement VisitTwoBitRuns and VisitTwoSetBitRuns methods [arrow]
Posted by "pitrou (via GitHub)" <gi...@apache.org>.
pitrou commented on PR #50281:
URL: https://github.com/apache/arrow/pull/50281#issuecomment-4834694438
Also, `VisitTwoBitBlocksVoid` is used extensively for binary scalar kernels, see `src/arrow/compute/kernels/codegen_internal.h`.
--
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-50280: [C++] Implement VisitTwoBitRuns and VisitTwoSetBitRuns methods [arrow]
Posted by "HuaHuaY (via GitHub)" <gi...@apache.org>.
HuaHuaY commented on code in PR #50281:
URL: https://github.com/apache/arrow/pull/50281#discussion_r3518026950
##########
cpp/src/arrow/util/nested_bitmap_traversal_benchmark.cc:
##########
@@ -0,0 +1,154 @@
+// Licensed to the Apache Software Foundation (ASF) under one
+// or more contributor license agreements. See the NOTICE file
+// distributed with this work for additional information
+// regarding copyright ownership. The ASF licenses this file
+// to you under the Apache License, Version 2.0 (the
+// "License"); you may not use this file except in compliance
+// with the License. You may obtain a copy of the License at
+//
+// http://www.apache.org/licenses/LICENSE-2.0
+//
+// Unless required by applicable law or agreed to in writing,
+// software distributed under the License is distributed on an
+// "AS IS" BASIS, WITHOUT WARRANTIES OR CONDITIONS OF ANY
+// KIND, either express or implied. See the License for the
+// specific language governing permissions and limitations
+// under the License.
+
+#include "benchmark/benchmark.h"
+
+#include <cstdint>
+#include <cstdlib>
+#include <memory>
+
+#include "arrow/array/array_base.h"
+#include "arrow/array/array_nested.h"
+#include "arrow/array/array_primitive.h"
+#include "arrow/testing/gtest_util.h"
+#include "arrow/testing/random.h"
+#include "arrow/type.h"
+#include "arrow/util/bit_block_counter.h"
+#include "arrow/util/bit_run_reader.h"
+#include "arrow/util/bitmap_ops.h"
+
+namespace arrow::internal {
+
+struct NestedBitmapTraversalBenchmark {
Review Comment:
I modified this benchmark to count the number of valid values in a `list<int8>` given an outer bitmap. But after testing the new benchmark, I discovered something unexpected: the baseline approach—`BitmapAnd` combined with `VisitSetBitRunsVoid`—actually turned out to be the fastest. I attribute this to the bitmap's minimal memory footprint (A bitmap with 1 million elements occupies only 128 KB), where the performance gains from `BitmapAnd`'s vectorization outweigh the overhead of materializing the bitmap. Consequently, I have decided to close this PR and simply materialize the bitmap directly when needed.
At the same time, `VisitTwoBitBlocks` appears to offer the worst performance. I’m curious whether replacing the current usages of `VisitTwoBitBlocks` with `BitmapAnd` might actually improve 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
Re: [PR] GH-50280: [C++] Implement VisitTwoBitRuns and VisitTwoSetBitRuns methods [arrow]
Posted by "pitrou (via GitHub)" <gi...@apache.org>.
pitrou commented on PR #50281:
URL: https://github.com/apache/arrow/pull/50281#issuecomment-5060908143
The benchmarks show a mixed bag of regressions and improvements, but in general I think these new primitives will be beneficial.
--
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-50280: [C++] Implement VisitTwoBitRuns and VisitTwoSetBitRuns methods [arrow]
Posted by "HuaHuaY (via GitHub)" <gi...@apache.org>.
HuaHuaY commented on code in PR #50281:
URL: https://github.com/apache/arrow/pull/50281#discussion_r3636610209
##########
cpp/src/arrow/util/nested_bitmap_traversal_benchmark.cc:
##########
Review Comment:
I will remove this file.
--
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-50280: [C++] Implement VisitTwoBitRuns and VisitTwoSetBitRuns methods [arrow]
Posted by "pitrou (via GitHub)" <gi...@apache.org>.
pitrou commented on PR #50281:
URL: https://github.com/apache/arrow/pull/50281#issuecomment-4851715435
I think NOINLINE was added at some point because it actually made some benchmarks better (on some compiler :-)). So let's be careful and check for regressions if we undo it.
Note that, ultimately, what matters is actual users of this function (for example in the compute library), not the bitmap traversal micro-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-50280: [C++] Implement VisitTwoBitRuns and VisitTwoSetBitRuns methods [arrow]
Posted by "HuaHuaY (via GitHub)" <gi...@apache.org>.
HuaHuaY commented on PR #50281:
URL: https://github.com/apache/arrow/pull/50281#issuecomment-4840563674
I have renamed the benchmark file and added some cases use VisitXXXBitRuns. And I added two new methods `VisitTwoBitRunsVoid` and `VisitTwoSetBitRunsVoid`.
BTW I refactored the existed method `VisitSetBitRunsVoid`. I believe compiler will optimize the lambda package cost.
--
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-50280: [C++] Implement VisitTwoBitRuns and VisitTwoSetBitRuns methods [arrow]
Posted by "rok (via GitHub)" <gi...@apache.org>.
rok commented on PR #50281:
URL: https://github.com/apache/arrow/pull/50281#issuecomment-5055860627
Benchmark runs are scheduled for commit 31668092ab4e24e19a7ce0bbab313ecd0f0dc88d. Watch https://buildkite.com/apache-arrow and https://conbench.arrow-dev.org for updates. A comment will be posted here when the runs are complete.
--
This is an automated message from the Apache Git Service.
To respond to the message, please log on to GitHub and use the
URL above to go to the specific comment.
To unsubscribe, e-mail: github-unsubscribe@arrow.apache.org
For queries about this service, please contact Infrastructure at:
users@infra.apache.org
Re: [PR] GH-50280: [C++] Implement VisitTwoBitRuns and VisitTwoSetBitRuns methods [arrow]
Posted by "HuaHuaY (via GitHub)" <gi...@apache.org>.
HuaHuaY commented on code in PR #50281:
URL: https://github.com/apache/arrow/pull/50281#discussion_r3518026950
##########
cpp/src/arrow/util/nested_bitmap_traversal_benchmark.cc:
##########
@@ -0,0 +1,154 @@
+// Licensed to the Apache Software Foundation (ASF) under one
+// or more contributor license agreements. See the NOTICE file
+// distributed with this work for additional information
+// regarding copyright ownership. The ASF licenses this file
+// to you under the Apache License, Version 2.0 (the
+// "License"); you may not use this file except in compliance
+// with the License. You may obtain a copy of the License at
+//
+// http://www.apache.org/licenses/LICENSE-2.0
+//
+// Unless required by applicable law or agreed to in writing,
+// software distributed under the License is distributed on an
+// "AS IS" BASIS, WITHOUT WARRANTIES OR CONDITIONS OF ANY
+// KIND, either express or implied. See the License for the
+// specific language governing permissions and limitations
+// under the License.
+
+#include "benchmark/benchmark.h"
+
+#include <cstdint>
+#include <cstdlib>
+#include <memory>
+
+#include "arrow/array/array_base.h"
+#include "arrow/array/array_nested.h"
+#include "arrow/array/array_primitive.h"
+#include "arrow/testing/gtest_util.h"
+#include "arrow/testing/random.h"
+#include "arrow/type.h"
+#include "arrow/util/bit_block_counter.h"
+#include "arrow/util/bit_run_reader.h"
+#include "arrow/util/bitmap_ops.h"
+
+namespace arrow::internal {
+
+struct NestedBitmapTraversalBenchmark {
Review Comment:
I modified this benchmark to count the number of valid values in a `list<int8>` given an outer bitmap. But after testing the new benchmark, I discovered something unexpected: the baseline approach—`BitmapAnd` combined with `VisitSetBitRunsVoid`—actually turned out to be the fastest. I attribute this to the bitmap's minimal memory footprint, where the performance gains from `BitmapAnd`'s vectorization outweigh the overhead of materializing the bitmap. Consequently, I have decided to close this PR and simply materialize the bitmap directly when needed.
At the same time, `VisitTwoBitBlocks` appears to offer the worst performance. I’m curious whether replacing the current usages of `VisitTwoBitBlocks` with `bitmapAnd` might actually improve performance.
##########
cpp/src/arrow/util/nested_bitmap_traversal_benchmark.cc:
##########
@@ -0,0 +1,154 @@
+// Licensed to the Apache Software Foundation (ASF) under one
+// or more contributor license agreements. See the NOTICE file
+// distributed with this work for additional information
+// regarding copyright ownership. The ASF licenses this file
+// to you under the Apache License, Version 2.0 (the
+// "License"); you may not use this file except in compliance
+// with the License. You may obtain a copy of the License at
+//
+// http://www.apache.org/licenses/LICENSE-2.0
+//
+// Unless required by applicable law or agreed to in writing,
+// software distributed under the License is distributed on an
+// "AS IS" BASIS, WITHOUT WARRANTIES OR CONDITIONS OF ANY
+// KIND, either express or implied. See the License for the
+// specific language governing permissions and limitations
+// under the License.
+
+#include "benchmark/benchmark.h"
+
+#include <cstdint>
+#include <cstdlib>
+#include <memory>
+
+#include "arrow/array/array_base.h"
+#include "arrow/array/array_nested.h"
+#include "arrow/array/array_primitive.h"
+#include "arrow/testing/gtest_util.h"
+#include "arrow/testing/random.h"
+#include "arrow/type.h"
+#include "arrow/util/bit_block_counter.h"
+#include "arrow/util/bit_run_reader.h"
+#include "arrow/util/bitmap_ops.h"
+
+namespace arrow::internal {
+
+struct NestedBitmapTraversalBenchmark {
Review Comment:
I modified this benchmark to count the number of valid values in a `list<int8>` given an outer bitmap. But after testing the new benchmark, I discovered something unexpected: the baseline approach—`BitmapAnd` combined with `VisitSetBitRunsVoid`—actually turned out to be the fastest. I attribute this to the bitmap's minimal memory footprint, where the performance gains from `BitmapAnd`'s vectorization outweigh the overhead of materializing the bitmap. Consequently, I have decided to close this PR and simply materialize the bitmap directly when needed.
At the same time, `VisitTwoBitBlocks` appears to offer the worst performance. I’m curious whether replacing the current usages of `VisitTwoBitBlocks` with `BitmapAnd` might actually improve 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
Re: [PR] GH-50280: [C++] Implement VisitTwoBitRuns and VisitTwoSetBitRuns methods [arrow]
Posted by "HuaHuaY (via GitHub)" <gi...@apache.org>.
HuaHuaY closed pull request #50281: GH-50280: [C++] Implement VisitTwoBitRuns and VisitTwoSetBitRuns methods
URL: https://github.com/apache/arrow/pull/50281
--
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-50280: [C++] Implement VisitTwoBitRuns and VisitTwoSetBitRuns methods [arrow]
Posted by "pitrou (via GitHub)" <gi...@apache.org>.
pitrou commented on PR #50281:
URL: https://github.com/apache/arrow/pull/50281#issuecomment-4852555554
@ursabot please benchmark lang=C++
--
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-50280: [C++] Implement VisitTwoBitRuns and VisitTwoSetBitRuns methods [arrow]
Posted by "pitrou (via GitHub)" <gi...@apache.org>.
pitrou commented on PR #50281:
URL: https://github.com/apache/arrow/pull/50281#issuecomment-4834656518
We have toy element-wise summation benchmarks in `bit_block_counter_benchmark.cc` (see `BinaryBitBlockBenchmark`), can you add one that uses these new primitives?
--
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-50280: [C++] Implement VisitTwoBitRuns and VisitTwoSetBitRuns methods [arrow]
Posted by "wgtmac (via GitHub)" <gi...@apache.org>.
wgtmac commented on PR #50281:
URL: https://github.com/apache/arrow/pull/50281#issuecomment-4844495589
Interesting that benchmark was run of behalf of @rok
--
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-50280: [C++] Implement VisitTwoBitRuns and VisitTwoSetBitRuns methods [arrow]
Posted by "HuaHuaY (via GitHub)" <gi...@apache.org>.
HuaHuaY commented on PR #50281:
URL: https://github.com/apache/arrow/pull/50281#issuecomment-4840934824
Now benchmarks about new method `VisitTwoBitRunsVoid` are much slower. It seems that llvm doesn't vectorize the sum operation in benchmark function. I will optimize the benchmark and push a new commit soon.
--
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