mbutrovich commented on code in PR #12347:
URL: https://github.com/apache/arrow-rs/pull/12347#discussion_r4653549440
##########
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
Review Comment:
> I was a bit confused about if it were an iterator (aka if I call
`count_before` twice will I always get the same answer)? I tink the answer is
yes, but the first time it would be faster?
Yes, you get the same answer. A result depends only on the arguments, and
the counter's state only changes how many words a call reads. A repeated call
reads no new words, so it costs a mask and a popcount. The struct docs now open
with that contract and an example that repeats a call, and the forward-scan
optimization has its own `# Performance` section.
##########
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
+/// ```
+/// # use arrow_buffer::{BooleanBuffer, OffsetBuffer};
+/// // A list with rows of 3, 0, and 2 elements, and the validity of its
elements
+/// let offsets = OffsetBuffer::<i32>::from_lengths([3, 0, 2]);
+/// let valid = BooleanBuffer::from(&[true, false, true, true, true][..]);
+///
+/// // One counter for every row. The rows are visited in order, so each word
Review Comment:
> Why is it one counter for every row?
That was a wording mistake. It now says "One counter for all rows".
--
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]