mbutrovich opened a new issue, #12346:
URL: https://github.com/apache/arrow-rs/issues/12346

   ### Is your feature request related to a problem or challenge?
   
   Kernels over list arrays often need one count per row from a single bitmap, 
such as the valid elements in each row or the child values that match a 
predicate. arrow-buffer answers one range per call. 
[`Buffer::count_set_bits_offset`](https://github.com/apache/arrow-rs/blob/31ac909a640aad8a4e62f59e8a3607461597388d/arrow-buffer/src/buffer/immutable.rs#L369-L373)
 builds a new `UnalignedBitChunk` on every call, and the common pattern 
`nulls.slice(start, len).null_count()` also clones the buffer's `Arc` per row 
([`NullBuffer::slice`](https://github.com/apache/arrow-rs/blob/31ac909a640aad8a4e62f59e8a3607461597388d/arrow-buffer/src/buffer/null.rs#L277-L279)
 calls 
[`NullBuffer::new`](https://github.com/apache/arrow-rs/blob/31ac909a640aad8a4e62f59e8a3607461597388d/arrow-buffer/src/buffer/null.rs#L29-L32),
 which counts the slice). For short rows that fixed cost dominates.
   
   apache/datafusion#26507 added a 
[`SetBitCounter`](https://github.com/apache/datafusion/blob/6225dfc43b1d43c9c599ee994a611875a483f368/datafusion/common/src/utils/mod.rs#L1269-L1331)
 to DataFusion for this and used it in seven list functions, with benchmarks in 
the PR description. Reviewers there agreed it belongs in arrow-rs 
(https://github.com/apache/datafusion/pull/26507#discussion_r4417832570). Its 
callers now live in two repos (apache/datafusion and apache/datafusion-spark), 
so keeping it in DataFusion means each would carry a copy.
   
   ### Describe the solution you'd like
   
   A `SetBitCounter` in `arrow_buffer::bit_iterator`, next to 
`BitIndexIterator` and `BitSliceIterator`, created with 
`BooleanBuffer::set_bit_counter()` (like 
[`set_indices`](https://github.com/apache/arrow-rs/blob/31ac909a640aad8a4e62f59e8a3607461597388d/arrow-buffer/src/buffer/boolean.rs#L609)
 and 
[`set_slices`](https://github.com/apache/arrow-rs/blob/31ac909a640aad8a4e62f59e8a3607461597388d/arrow-buffer/src/buffer/boolean.rs#L619))
 or `SetBitCounter::new(buffer, offset, len)`:
   
   ```rust
   let mut counter = valid.set_bit_counter();
   let valid_per_row = offsets
       .windows(2)
       .map(|w| counter.count_range(w[0] as usize..w[1] as usize));
   ```
   
   It has two methods. `count_before(end)` returns the set bits before `end`, 
and `count_range(range)` returns the set bits in `range`. When positions don't 
decrease, each 64-bit word is read once, and a call within the current word 
costs a mask and a popcount. A position before the current word restarts the 
scan from the start, so the result is correct for positions in any order. A 
position past the length panics, as 
[`BooleanBuffer::value`](https://github.com/apache/arrow-rs/blob/31ac909a640aad8a4e62f59e8a3607461597388d/arrow-buffer/src/buffer/boolean.rs#L479)
 does.
   
   ### Describe alternatives you've considered
   
   A kernel that takes an `OffsetBuffer` and returns per-row counts would cover 
`ListArray`, but not list views, callers that skip rows (for example under NULL 
parent rows), or callers that count at row boundaries they find while building 
a result, as DataFusion's `prepare_list_filter` does.
   
   The DataFusion version takes an iterator of 64-bit words. A caller that 
passes `bit_chunks().iter()` instead of `iter_padded()` gets counts that are 
silently low in the final partial word 
(https://github.com/apache/datafusion/pull/26507#discussion_r4318870146). 
Taking the bitmap itself removes that mistake.
   
   ### Additional context
   
   The DataFusion version loops forever in release builds when a position 
decreases past the current word 
(https://github.com/apache/datafusion/pull/26507#discussion_r4360495918). The 
restart described above defines that case.
   
   ### Willingness to contribute
   
   I plan to contribute to this feature independently
   


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