mbutrovich commented on code in PR #12347:
URL: https://github.com/apache/arrow-rs/pull/12347#discussion_r4653550981
##########
arrow-buffer/src/util/bit_iterator.rs:
##########
@@ -363,6 +366,166 @@ impl Iterator for BitIndexU32Iterator<'_> {
}
}
+/// Counts the set bits before positions in a packed bitmask, for many
positions
+///
+/// When positions do not decrease from one call to the next, each 64-bit word
+/// of the bitmask is read once, and a call within the current word costs a
mask
+/// and a popcount. This suits a pass over the rows of a list array, such as
+/// counting the valid elements of each row, where calling
+/// [`Buffer::count_set_bits_offset`] for each row rescans from the row's
start.
+///
+/// Positions can come in any order. A call reads each word between the
+/// previous position and the new one, in either direction. When positions jump
+/// across the bitmask, such as the rows of a list view in random order,
calling
+/// [`Buffer::count_set_bits_offset`] for each row reads fewer words.
+///
+/// # Example: Count the valid elements of each row of a list
Review Comment:
> I suggest starting with a simpler example of just counting bits in ranges.
And then show the example of list offsets (the use case this is optimized for)
Done. The ranges-only example comes first, and the list offsets example
follows the `# Performance` section.
--
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: [email protected]
For queries about this service, please contact Infrastructure at:
[email protected]