[GitHub] [arrow] wesm commented on a change in pull request #7346: ARROW-9029: [C++] Implement BitBlockCounter for much faster block popcounts of bitmaps

[GitBox <gi...@apache.org>]

wesm commented on a change in pull request #7346:
URL: https://github.com/apache/arrow/pull/7346#discussion_r435253518



##########
File path: cpp/src/arrow/util/bit_util_benchmark.cc
##########
@@ -387,6 +389,114 @@ static void BitmapEquals(benchmark::State& state) {
   state.SetBytesProcessed(state.iterations() * buffer_size);
 }
 
+template <int64_t Offset = 0>
+static void BitBlockCounterSumNotNull(benchmark::State& state) {
+  using internal::BitBlockCounter;
+
+  random::RandomArrayGenerator rng(/*seed=*/0);
+
+  const int64_t bitmap_length = 1 << 20;
+
+  // State parameter is the average number of total values for each false
+  // value. So 100 means that 1 out of 100 on average are false.
+  double true_probability = 1. - 1. / state.range(0);
+  auto arr = rng.Int8(bitmap_length, 0, 100, true_probability);
+
+  const uint8_t* bitmap = arr->null_bitmap_data();
+
+  // Compute the expected result
+  int64_t expected = 0;
+  const auto& int8_arr = static_cast<const Int8Array&>(*arr);
+  for (int64_t i = Offset; i < bitmap_length; ++i) {
+    if (int8_arr.IsValid(i)) {
+      expected += int8_arr.Value(i);
+    }
+  }
+  for (auto _ : state) {
+    BitBlockCounter scanner(bitmap, Offset, bitmap_length - Offset);
+    int64_t result = 0;
+    int64_t position = Offset;
+    while (true) {
+      BitBlockCounter::Block block = scanner.NextBlock();
+      if (block.length == 0) {
+        break;
+      }
+      if (block.length == block.popcount) {

Review comment:
       I need the popcount in order to [calculate the number of "on" elements for filters](https://github.com/apache/arrow/blob/master/cpp/src/arrow/compute/kernels/vector_filter.cc#L75), but yes for this particular optimization between "all-on" and "not-all-on" you don't need the popcount. 




----------------------------------------------------------------
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