andygrove commented on code in PR #12347:
URL: https://github.com/apache/arrow-rs/pull/12347#discussion_r4646514771
##########
arrow-buffer/src/util/bit_iterator.rs:
##########
@@ -363,6 +366,162 @@ 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.
+///
+/// A position before the word of the previous position restarts the scan from
+/// the start of the bitmask, so the counts are correct for positions in any
+/// order.
+///
+/// # 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
+/// // of `valid` is read once.
+/// let mut counter = valid.set_bit_counter();
+/// // Each pair of adjacent offsets is the start and end of a row
+/// let valid_per_row: Vec<usize> = offsets
+/// .windows(2)
+/// .map(|w| counter.count_range(w[0] as usize..w[1] as usize))
+/// .collect();
+/// assert_eq!(valid_per_row, [2, 0, 2]);
+/// ```
+///
+/// [`Buffer::count_set_bits_offset`]: crate::Buffer::count_set_bits_offset
+#[derive(Debug)]
+pub struct SetBitCounter<'a> {
+ chunks: BitChunks<'a>,
+ iter: BitChunkIterator<'a>,
+ /// The bitmask's final partial word, zero padded, until it is read
+ remainder: u64,
+ /// The word containing the most recent position
+ word: u64,
+ /// Position of the first bit of `word`
+ word_start: usize,
+ /// Set bits before `word_start`
+ count_before_word: usize,
+ len: usize,
+}
+
+impl<'a> SetBitCounter<'a> {
+ /// Create a new [`SetBitCounter`] from the provided `buffer`,
+ /// and `offset` and `len` in bits
+ ///
+ /// ```
+ /// # use arrow_buffer::bit_iterator::SetBitCounter;
+ /// // Bits 3..9 are 0, 1, 1, 0, 1, 1
+ /// let mut counter = SetBitCounter::new(&[0b1011_0101, 0b0000_0001], 3,
6);
+ /// assert_eq!(counter.count_before(3), 2);
+ /// assert_eq!(counter.count_range(3..6), 2);
+ /// ```
+ ///
+ /// # Panics
+ ///
+ /// Panics if `buffer` is too short for the provided offset and length
+ pub fn new(buffer: &'a [u8], offset: usize, len: usize) -> Self {
+ let chunks = BitChunks::new(buffer, offset, len);
+ let mut counter = Self {
+ iter: chunks.iter(),
+ chunks,
+ remainder: 0,
+ word: 0,
+ word_start: 0,
+ count_before_word: 0,
+ len,
+ };
+ counter.restart();
+ counter
+ }
+
+ // Cold and out of line because after `new`, only a position before the
+ // current word calls it, and inlining would copy it into every caller of
+ // the inlined `count_before`.
+ #[cold]
+ fn restart(&mut self) {
+ self.iter = self.chunks.iter();
+ self.remainder = self.chunks.remainder_bits();
+ self.word = self.next_word();
+ self.word_start = 0;
+ self.count_before_word = 0;
+ }
+
+ #[inline]
+ fn next_word(&mut self) -> u64 {
+ self.iter
+ .next()
+ .unwrap_or_else(|| std::mem::take(&mut self.remainder))
+ }
+
+ /// Returns the number of set bits before position `end`
+ ///
+ /// ```
+ /// # use arrow_buffer::BooleanBuffer;
+ /// let bits = BooleanBuffer::from(&[true, false, true, true][..]);
+ /// let mut counter = bits.set_bit_counter();
+ /// assert_eq!(counter.count_before(0), 0);
+ /// assert_eq!(counter.count_before(3), 2);
+ /// assert_eq!(counter.count_before(4), 3);
+ /// ```
+ ///
+ /// # Panics
+ ///
+ /// Panics if `end` is greater than the length of the bitmask
+ #[inline]
+ pub fn count_before(&mut self, end: usize) -> usize {
+ assert!(
+ end <= self.len,
+ "position {end} out of bounds for length {}",
+ self.len
+ );
+ if end < self.word_start {
+ self.restart();
Review Comment:
I had a question about the restart path. The issue mentions list views as
one reason to prefer a general counter over an `OffsetBuffer` kernel, but list
view offsets can be in any order. When rows are visited out of order, most
calls would restart and rescan from word 0. For 8192 rows of width 4 in reverse
order, that is roughly 2M word steps, which I think would be much slower than
the per-row `count_set_bits_offset` loop this replaces.
`BitChunks::chunk(index)` already gives direct access to any full word.
Would it work to track a word index and step backwards by subtracting
`chunk(i).count_ones()`? Backward moves would then cost the distance moved,
just like forward moves, and I think `restart`, the `#[cold]` path, and the
`mem::take` on the remainder could all go away. If the bounds check in `chunk`
costs too much on the forward path, keeping the iterator for forward moves and
using `chunk` only going backwards would also work. Could you add a
reverse-order or shuffled-rows case to the `set_bit_counter` benchmark so we
can see both patterns?
--
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]