MCPcopy Create free account
hub / github.com/apache/arrow / CountSetBits

Function CountSetBits

cpp/src/arrow/util/bitmap_ops.cc:41–92  ·  view source on GitHub ↗

Source from the content-addressed store, hash-verified

39namespace arrow::internal {
40
41int64_t CountSetBits(const uint8_t* data, int64_t bit_offset, int64_t length) {
42 constexpr int64_t pop_len = sizeof(uint64_t) * 8;
43 DCHECK_GE(bit_offset, 0);
44 int64_t count = 0;
45
46 const auto p = BitmapWordAlign<pop_len / 8>(data, bit_offset, length);
47 for (int64_t i = bit_offset; i < bit_offset + p.leading_bits; ++i) {
48 if (bit_util::GetBit(data, i)) {
49 ++count;
50 }
51 }
52
53 if (p.aligned_words > 0) {
54 // popcount as much as possible with the widest possible count
55 const uint64_t* u64_data = reinterpret_cast<const uint64_t*>(p.aligned_start);
56 DCHECK_EQ(reinterpret_cast<size_t>(u64_data) & 7, 0);
57 const uint64_t* end = u64_data + p.aligned_words;
58
59 constexpr int64_t kCountUnrollFactor = 4;
60 const int64_t words_rounded =
61 bit_util::RoundDown(p.aligned_words, kCountUnrollFactor);
62 std::array<int64_t, kCountUnrollFactor> count_unroll{};
63
64 // Unroll the loop for better performance
65 for (int64_t i = 0; i < words_rounded; i += kCountUnrollFactor) {
66 // (hand-unrolled as some gcc versions would unnest a nested `for` loop)
67 count_unroll[0] += std::popcount(u64_data[0]);
68 count_unroll[1] += std::popcount(u64_data[1]);
69 count_unroll[2] += std::popcount(u64_data[2]);
70 count_unroll[3] += std::popcount(u64_data[3]);
71 u64_data += kCountUnrollFactor;
72 }
73 for (int64_t k = 0; k < kCountUnrollFactor; k++) {
74 count += count_unroll[k];
75 }
76
77 // The trailing part
78 for (; u64_data < end; ++u64_data) {
79 count += std::popcount(*u64_data);
80 }
81 }
82
83 // Account for left over bits (in theory we could fall back to smaller
84 // versions of popcount but the code complexity is likely not worth it)
85 for (int64_t i = p.trailing_bit_offset; i < bit_offset + length; ++i) {
86 if (bit_util::GetBit(data, i)) {
87 ++count;
88 }
89 }
90
91 return count;
92}
93
94int64_t CountAndSetBits(const uint8_t* left_bitmap, int64_t left_offset,
95 const uint8_t* right_bitmap, int64_t right_offset,

Callers 15

GetBlockSlowMethod · 0.70
TEST_FFunction · 0.70
OptionalBitmapEqualsFunction · 0.70
TESTFunction · 0.70
ArrayHashMethod · 0.50
UnsafeAppendMethod · 0.50
FoldMethod · 0.50
NumBitsSetMethod · 0.50
FilterSingleBatchMethod · 0.50
GetNullCountMethod · 0.50
ListViewArrayMethod · 0.50
true_countMethod · 0.50

Calls 2

RoundDownFunction · 0.85
GetBitFunction · 0.70

Tested by 8

TEST_FFunction · 0.56
TESTFunction · 0.56
ListViewArrayMethod · 0.40
ExecComputedBitmapFunction · 0.40
AssertMinMaxAreFunction · 0.40
AssertUnsetMinMaxFunction · 0.40
CheckDecodeArrowMethod · 0.40