mbutrovich commented on PR #11732: URL: https://github.com/apache/arrow-rs/pull/11732#issuecomment-6325226430
What about replacing the per-bit path and both cutoffs with a kernel that filters values and validity straight into the builders, 64 bits at a time? As I read it, the per-bit path wins because of what it skips, not because appending one bit at a time is cheap. On the kernel path, [`filter_boolean`](https://github.com/apache/arrow-rs/blob/01a9917658fecd639991e92a5a5810be710b539c/arrow-select/src/filter.rs#L884-L890) allocates a filtered values buffer. [`filter_nulls`](https://github.com/apache/arrow-rs/blob/01a9917658fecd639991e92a5a5810be710b539c/arrow-select/src/filter.rs#L564-L594) then scans the whole filter a second time and allocates a null buffer, and `append_array` copies both into the builders. The per-bit path does none of that, but it pays per selected row: two bit reads and two appends that each [branch on the bit](https://github.com/apache/arrow-rs/blob/4c23338354a4735af9add56879c01e820532aabb/arrow-select/src/coalesce/boolean.rs#L109-L118). Without nulls, the kernel's extra cost is mostly fixed per batch, so the crossover is a row count rather than a fraction. With nulls, the second scan grows with the batch lengt h. That fits the two cutoffs you found. Both cutoffs also depend on inputs the benchmark holds fixed: - The kernel's cost tracks the 64-bit filter words that contain at least one selected row, not the selected rows. `coalesce_kernels` draws each filter bit [independently](https://github.com/apache/arrow-rs/blob/01a9917658fecd639991e92a5a5810be710b539c/arrow/src/util/bench_util.rs#L156-L171), so at 0.001 about 6% of words have a selected row. If the same rows arrive in runs, the kernel runs `compress` on up to 64x fewer words, while the per-bit path does the same work. - [`compress`](https://github.com/apache/arrow-rs/blob/01a9917658fecd639991e92a5a5810be710b539c/arrow-buffer/src/util/bit_util.rs#L66-L78) is a single `pext` instruction (extract the bits selected by a mask) only when `bmi2` is enabled at build time. Default x86_64 builds and all aarch64 builds use the portable fallback, and the bot and my runs are both aarch64. In #11776 the same portable popcount change is 28% faster on aarch64 and about 80% slower on Zen 5 ([numbers](https://github.com/apache/arrow-rs/issues/11776#issuecomment-6324648800)), so a cutoff measured on one architecture may not carry over. - A single-column Boolean batch never gets an optimized predicate ([coalesce.rs](https://github.com/apache/arrow-rs/blob/01a9917658fecd639991e92a5a5810be710b539c/arrow-select/src/coalesce.rs#L693-L704)), so `single_boolean` only measures the lazy index iterator. Batches with more than one column get precomputed `Indices`, which none of these numbers cover. The fused loop would look roughly like this, plus the trailing partial word: ```rust for (i, m) in filter_words.enumerate() { if m == 0 { continue; } let k = m.count_ones() as usize; values.append_word(compress(value_words.chunk(i), m), k); if let Some(validity) = &validity_words { nulls.append_word(compress(validity.chunk(i), m), k); } } ``` This needs no intermediate array or copy, and it scans the filter once for values and validity together. Its cost is per filter word, with no branch on the values. For precomputed `Indices` at or below `len / 64`, gathering one index at a time would stay, which is the cutoff [`filter_bits`](https://github.com/apache/arrow-rs/blob/01a9917658fecd639991e92a5a5810be710b539c/arrow-select/src/filter.rs#L743-L757) already uses. That cutoff follows from the word size (fewer than one kept bit per word), not from a benchmark. At 0.001 with independent bits, almost every non-empty word holds one selected row, so I'd expect this to tie the per-bit path there rather than beat it. [`BooleanBufferBuilder::append_word`](https://github.com/apache/arrow-rs/blob/01a9917658fecd639991e92a5a5810be710b539c/arrow-buffer/src/builder/boolean.rs#L203-L241) exists, and the Parquet reader already builds validity bitmaps with `compress` followed by `append_word` ([definition_levels.rs](https://github.com/apache/arrow-rs/blob/01a9917658fecd639991e92a5a5810be710b539c/parquet/src/arrow/record_reader/definition_levels.rs#L183-L185)). `NullBufferBuilder` has no equivalent. An `append_word` there that calls `append_n_non_nulls` while every bit is valid would keep its [lazy allocation](https://github.com/apache/arrow-rs/blob/01a9917658fecd639991e92a5a5810be710b539c/arrow-buffer/src/builder/null.rs#L26-L34). The primitive sparse path filters nulls the same way, [`filter_nulls` followed by `append_buffer`](https://github.com/apache/arrow-rs/blob/01a9917658fecd639991e92a5a5810be710b539c/arrow-select/src/coalesce/primitive.rs#L135-L145), so the validity half could be a shared helper for both. Would you be open to trying this in place of the per-bit path? If the prototype holds up on both x86_64 and aarch64, `NullBufferBuilder::append_word` could go in a separate PR first. A benchmark PR with runs of selected rows and a multi-column Boolean case would show whether it holds beyond these inputs. -- 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]
