mbutrovich commented on code in PR #12347:
URL: https://github.com/apache/arrow-rs/pull/12347#discussion_r4648646701
##########
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:
> Would it work to track a word index and step backwards by subtracting
`chunk(i).count_ones()`?
It works for backward moves. Reading every word with
[`BitChunks::chunk`](https://github.com/apache/arrow-rs/blob/1b42833a2105efdbb757108c7d15233aa35e9bf5/arrow-buffer/src/util/bit_chunk_iterator.rs#L372-L377)
in
[661a54f](https://github.com/apache/arrow-rs/pull/12347/commits/661a54f3d8508cd4f6fe14e275fa645ef9009f4a)
made rows in order slower, down to 0.70x on Neoverse-V2.
[654b9d2](https://github.com/apache/arrow-rs/pull/12347/commits/654b9d2d946980275fc9799ad0611f68f7e3b0e4)
keeps `BitChunkIterator` for forward moves, as you suggested if `chunk` cost
too much, and steps back with `chunk` in a `#[cold]` function. To reposition
the iterator after a step back, `BitChunkIterator::nth` now skips in constant
time.
Speedup over the restart version
([e97b4a3](https://github.com/apache/arrow-rs/pull/12347/commits/e97b4a38075f14507fb1075bab72a40587d015d5))
on Neoverse-V2, from the 661a54f
[default](https://github.com/apache/arrow-rs/pull/12347#issuecomment-7049852527)
and
[aligned](https://github.com/apache/arrow-rs/pull/12347#issuecomment-7049873880)
runs and the 654b9d2
[default](https://github.com/apache/arrow-rs/pull/12347#issuecomment-7051892186)
and
[aligned](https://github.com/apache/arrow-rs/pull/12347#issuecomment-7051892664)
runs:
| Case | 661a54f | 661a54f, aligned | 654b9d2 | 654b9d2, aligned |
|---|--:|--:|--:|--:|
| `width_4/random/offset_0/forward` | 0.89x | 0.87x | 0.98x | 0.97x |
| `width_32/random/offset_0/forward` | 0.71x | 0.70x | 1.11x | 0.82x |
| `width_32/random/offset_3/forward` | 0.77x | 0.73x | 1.08x | 0.92x |
| `width_4/constant/offset_0/reverse` | 11.06x | 10.99x | 9.78x | 9.92x |
| `width_32/constant/offset_0/reverse` | 331.40x | 319.33x | 250.55x |
248.91x |
| `width_256/constant/offset_0/reverse` | 824.47x | 830.43x | 714.84x |
708.46x |
With 654b9d2, no forward case is below 0.95x in both layouts. On the Xeon,
the forward cases range from 0.81x to 1.04x with 661a54f and from 0.89x to
1.12x with 654b9d2
([default](https://github.com/apache/arrow-rs/pull/12347#issuecomment-7051912316)
and
[aligned](https://github.com/apache/arrow-rs/pull/12347#issuecomment-7051912753)
runs).
> For 8192 rows of width 4 in reverse order, that is roughly 2M word steps
The restart ran only when a row crossed back over a word boundary, so it was
about 262K word steps at width 4. That still grew with the square of the row
count: in the 654b9d2 default run on Neoverse-V2, reverse order took 202 us at
width 4 and 92 ms at width 256 with the restart, against 21 us and 129 us with
654b9d2.
> Could you add a reverse-order or shuffled-rows case to the
`set_bit_counter` benchmark so we can see both patterns?
[e97b4a3](https://github.com/apache/arrow-rs/pull/12347/commits/e97b4a38075f14507fb1075bab72a40587d015d5)
runs every case with rows in forward, reverse, and shuffled order. Shuffled
order costs the distance jumped with either design (0.94x to 1.11x of the
restart version), and per-row `count_set_bits_offset` is 11x to more than 1000x
faster there. The rustdoc now points callers whose positions jump across the
bitmap, such as list views in random order, to `count_set_bits_offset`.
--
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]