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]
