alamb commented on code in PR #12347:
URL: https://github.com/apache/arrow-rs/pull/12347#discussion_r4652231139


##########
arrow-buffer/src/buffer/boolean.rs:
##########
@@ -620,6 +622,23 @@ impl BooleanBuffer {
         BitSliceIterator::new(self.values(), self.bit_offset, self.bit_len)
     }
 
+    /// Returns a [`SetBitCounter`] that counts the set bits before positions 
in
+    /// this [`BooleanBuffer`]
+    ///
+    /// ```
+    /// # use arrow_buffer::BooleanBuffer;
+    /// // Validity of the elements of a list with rows of 3, 0, and 2 elements
+    /// let valid = BooleanBuffer::from(&[true, false, true, true, true][..]);

Review Comment:
   why do we need the `[..]` ?



##########
arrow-buffer/src/buffer/boolean.rs:
##########
@@ -620,6 +622,23 @@ impl BooleanBuffer {
         BitSliceIterator::new(self.values(), self.bit_offset, self.bit_len)
     }
 
+    /// Returns a [`SetBitCounter`] that counts the set bits before positions 
in
+    /// this [`BooleanBuffer`]
+    ///
+    /// ```
+    /// # use arrow_buffer::BooleanBuffer;
+    /// // Validity of the elements of a list with rows of 3, 0, and 2 elements
+    /// let valid = BooleanBuffer::from(&[true, false, true, true, true][..]);
+    /// let mut counter = valid.set_bit_counter();
+    /// // Count the valid elements of each row, in row order

Review Comment:
   I found this example super confusing -- the input is a single 
`BooleanBuffer` and then the counter can count how many bits are set in each 
range
   
   I get that counting list validity is the usecase, but this API doesn't have 
anything specifically to do with lists, so I think talking about list validity 
just makes the whole thing more confusing



##########
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? It seems like there is a single counter 
and that it is used to determine the set count for each range?



##########
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 found this pretty hard to understand how to use it
   
   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?
   
   Maybe it would help to separate out the API contract from what is going on 
in the implementation -- e.g the API is "count bits in a specified arbitrary 
range", and then add a section on "optimization" that explains the pattern it 
is optimized for (basically forward scans over ranges)?



##########
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)



##########
arrow-buffer/src/buffer/boolean.rs:
##########
@@ -620,6 +622,23 @@ impl BooleanBuffer {
         BitSliceIterator::new(self.values(), self.bit_offset, self.bit_len)
     }
 
+    /// Returns a [`SetBitCounter`] that counts the set bits before positions 
in
+    /// this [`BooleanBuffer`]
+    ///
+    /// ```
+    /// # use arrow_buffer::BooleanBuffer;
+    /// // Validity of the elements of a list with rows of 3, 0, and 2 elements
+    /// let valid = BooleanBuffer::from(&[true, false, true, true, true][..]);
+    /// let mut counter = valid.set_bit_counter();
+    /// // Count the valid elements of each row, in row order

Review Comment:
   I recommend changing the example to be more generic about just counting bits 
over sub ranges



##########
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
+/// // 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

Review Comment:
   👍 



-- 
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]

Reply via email to