You are viewing a plain text version of this content. The canonical link for it is here.
Posted to github@arrow.apache.org by "haohuaijin (via GitHub)" <gi...@apache.org> on 2026/07/27 04:35:09 UTC

[PR] perf(parquet): single-allocation intersect_masks/union_masks for unequal lengths [arrow-rs]

haohuaijin opened a new pull request, #10446:
URL: https://github.com/apache/arrow-rs/pull/10446

   # Which issue does this PR close?
   
   - Closes #10425.
   
   > [!IMPORTANT]
   > **Draft: stacked on #10444.** This branch is based on that PR, so the diff here currently shows both commits. The optimization depends on the fix in #10444 — without it the mask tail gets corrupted and the tests below fail. Once #10444 merges I'll rebase onto `main` and this reduces to the single `algebra.rs` commit.
   
   # Rationale for this change
   
   When two mask-backed `RowSelection`s have different lengths, `intersect_masks`/`union_masks` allocate twice: once for the bitwise result over the common prefix, then again for a `BooleanBufferBuilder` that appends the prefix and the longer side's tail — copying both.
   
   # What changes are included in this PR?
   
   Copy the longer mask once into a `MutableBuffer` and apply `&=`/`|=` in place over the common prefix via `bit_util::apply_bitwise_binary_op`. The tail is already in the right place, so it needs no copy at all.
   
   Neither the mask offsets nor the prefix length are assumed to be byte aligned — masks reaching this path may carry a non-zero bit offset from `BooleanBuffer::slice`, and the prefix may end mid byte. The copy keeps the longer mask's sub-byte offset instead of re-aligning it, so it stays a plain byte copy, and that offset is carried over to the result.
   
   # Are these changes tested?
   
   Yes — `test_uneven_masks_with_offsets` sweeps offsets `{0,1,5,8,13,64,67}` × `{0,1,3,8,60,64,70}` against several length pairs, and `test_uneven_masks_fuzz` runs 200 randomized rounds. Both compare against a bit-by-bit reference implementation. `cargo test -p parquet --all-features` passes (1284 tests); clippy and fmt clean.
   
   Criterion over mask-backed `RowSelection::intersection`/`union` at ~1/3 density:
   
   | case | before | after | change |
   | --- | --- | --- | --- |
   | intersect 3M / 2M | 16.60 µs | 12.96 µs | −21.9% |
   | union 3M / 2M | 16.57 µs | 13.12 µs | −20.8% |
   | intersect 3M / 3M−1 | 20.22 µs | 16.51 µs | −18.3% |
   | union 3M / 3M−1 | 20.19 µs | 16.66 µs | −17.5% |
   | intersect 100K / 1K | 509 ns | 278 ns | −45.4% |
   | union 100K / 1K | 525 ns | 270 ns | −48.6% |
   
   Measured with an ad-hoc bench harness rather than a committed one, since there's no existing bench covering mask-backed selections — `row_selector.rs` builds its inputs with `from_filters`, which is selector-backed and doesn't reach this path. Happy to add a permanent bench if you'd like one.
   
   The gain grows with the tail, which the old code copied through the builder for no reason.
   
   # Are there any user-facing changes?
   
   No API changes. `intersect_masks`/`union_masks` are `pub(super)`; the observable behaviour of `RowSelection::intersection`/`union` is unchanged.
   


-- 
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: github-unsubscribe@arrow.apache.org

For queries about this service, please contact Infrastructure at:
users@infra.apache.org


Re: [PR] perf(parquet): avoid redundant copies in mask-backed intersection/union [arrow-rs]

Posted by "alamb (via GitHub)" <gi...@apache.org>.
alamb commented on PR #10446:
URL: https://github.com/apache/arrow-rs/pull/10446#issuecomment-5208866997

   run benchmark mask_intersection


-- 
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: github-unsubscribe@arrow.apache.org

For queries about this service, please contact Infrastructure at:
users@infra.apache.org


Re: [PR] perf(parquet): avoid redundant copies in mask-backed intersection/union [arrow-rs]

Posted by "haohuaijin (via GitHub)" <gi...@apache.org>.
haohuaijin commented on PR #10446:
URL: https://github.com/apache/arrow-rs/pull/10446#issuecomment-5225311392

   run benchmark row_selector


-- 
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: github-unsubscribe@arrow.apache.org

For queries about this service, please contact Infrastructure at:
users@infra.apache.org


Re: [PR] perf(parquet): avoid redundant copies in mask-backed intersection/union [arrow-rs]

Posted by "adriangbot (via GitHub)" <gi...@apache.org>.
adriangbot commented on PR #10446:
URL: https://github.com/apache/arrow-rs/pull/10446#issuecomment-5218529620

   🤖 Arrow criterion benchmark running (GKE) | [trigger](https://github.com/apache/arrow-rs/pull/10446#issuecomment-5218498440)
   **Instance:** `c4a-highmem-16` (12 vCPU / 65 GiB) | `Linux bench-c5218498440-1499-mt2br 6.12.85+ #1 SMP Wed Jun 17 20:31:55 UTC 2026 aarch64 GNU/Linux`
   <details><summary>CPU Details (lscpu)</summary>
   
   ```
   Architecture:                            aarch64
   CPU op-mode(s):                          64-bit
   Byte Order:                              Little Endian
   CPU(s):                                  16
   On-line CPU(s) list:                     0-15
   Vendor ID:                               ARM
   Model name:                              Neoverse-V2
   Model:                                   1
   Thread(s) per core:                      1
   Core(s) per cluster:                     16
   Socket(s):                               -
   Cluster(s):                              1
   Stepping:                                r0p1
   BogoMIPS:                                2000.00
   Flags:                                   fp asimd evtstrm aes pmull sha1 sha2 crc32 atomics fphp asimdhp cpuid asimdrdm jscvt fcma lrcpc dcpop sha3 sm3 sm4 asimddp sha512 sve asimdfhm dit uscat ilrcpc flagm sb paca pacg dcpodp sve2 sveaes svepmull svebitperm svesha3 svesm4 flagm2 frint svei8mm svebf16 i8mm bf16 dgh rng bti
   L1d cache:                               1 MiB (16 instances)
   L1i cache:                               1 MiB (16 instances)
   L2 cache:                                32 MiB (16 instances)
   L3 cache:                                80 MiB (1 instance)
   NUMA node(s):                            1
   NUMA node0 CPU(s):                       0-15
   Vulnerability Gather data sampling:      Not affected
   Vulnerability Indirect target selection: Not affected
   Vulnerability Itlb multihit:             Not affected
   Vulnerability L1tf:                      Not affected
   Vulnerability Mds:                       Not affected
   Vulnerability Meltdown:                  Not affected
   Vulnerability Mmio stale data:           Not affected
   Vulnerability Reg file data sampling:    Not affected
   Vulnerability Retbleed:                  Not affected
   Vulnerability Spec rstack overflow:      Not affected
   Vulnerability Spec store bypass:         Mitigation; Speculative Store Bypass disabled via prctl
   Vulnerability Spectre v1:                Mitigation; __user pointer sanitization
   Vulnerability Spectre v2:                Mitigation; CSV2, BHB
   Vulnerability Srbds:                     Not affected
   Vulnerability Tsa:                       Not affected
   Vulnerability Tsx async abort:           Not affected
   Vulnerability Vmscape:                   Not affected
   ```
   
   </details>
   
   Comparing perf-uneven-mask-intersect-union (635c740cbe789a483a2659d74f75a3892b22f39d) to 3e6bd62 (merge-base) [diff](https://github.com/apache/arrow-rs/compare/3e6bd627c7b6d0dcda8aeb0a6efc829508177d4f..635c740cbe789a483a2659d74f75a3892b22f39d)
   
   <details><summary>Run configuration</summary>
   
   ```yaml
   run benchmark row_selector
   ```
   
   </details>
   
   BENCH_COMMAND=cargo bench --features=arrow,async,test_common,experimental,object_store --bench row_selector
   Results will be posted here when complete
   
   ---
   [File an issue](https://github.com/adriangb/datafusion-benchmarking/issues) against this benchmark runner


-- 
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: github-unsubscribe@arrow.apache.org

For queries about this service, please contact Infrastructure at:
users@infra.apache.org


Re: [PR] perf(parquet): avoid redundant copies in mask-backed intersection/union [arrow-rs]

Posted by "adriangbot (via GitHub)" <gi...@apache.org>.
adriangbot commented on PR #10446:
URL: https://github.com/apache/arrow-rs/pull/10446#issuecomment-5208879776

   Benchmark for [this request](https://github.com/apache/arrow-rs/pull/10446#issuecomment-5208866997) failed.
   
   <details><summary>Run configuration</summary>
   
   ```yaml
   run benchmark mask_intersection
   ```
   
   </details>
   
   Last 20 lines of output:
   <details><summary>Click to expand</summary>
   
   ```
       regexp_kernels
       row_format
       row_group_index_reader
       row_selection_cursor
       row_selector
       row_selector_boolean_buffer
       serde
       sort_kernel
       string_dictionary_builder
       string_run_builder
       string_run_iterator
       substring_kernels
       take_kernels
       union_array
       variant_builder
       variant_kernels
       variant_validation
       view_types
       writer_overhead
       zip_kernels
   ```
   
   </details>
   
   ---
   [File an issue](https://github.com/adriangb/datafusion-benchmarking/issues) against this benchmark runner


-- 
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: github-unsubscribe@arrow.apache.org

For queries about this service, please contact Infrastructure at:
users@infra.apache.org


Re: [PR] perf(parquet): avoid redundant copies in mask-backed intersection/union [arrow-rs]

Posted by "haohuaijin (via GitHub)" <gi...@apache.org>.
haohuaijin commented on PR #10446:
URL: https://github.com/apache/arrow-rs/pull/10446#issuecomment-5191355453

   thanks for your reviews @hhhizzz , i apply the suggestion in [5fe3cb7](https://github.com/apache/arrow-rs/pull/10446/commits/5fe3cb7c221692027ede6c3eda57bb0c66f575ce), this is benchmark result
   <img width="912" height="560" alt="image" src="https://github.com/user-attachments/assets/c8fd7fdd-ff14-42e3-9468-dace4c96172d" />
   


-- 
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: github-unsubscribe@arrow.apache.org

For queries about this service, please contact Infrastructure at:
users@infra.apache.org


Re: [PR] perf(parquet): avoid redundant copies in mask-backed intersection/union [arrow-rs]

Posted by "adriangbot (via GitHub)" <gi...@apache.org>.
adriangbot commented on PR #10446:
URL: https://github.com/apache/arrow-rs/pull/10446#issuecomment-5218734866

   🤖 Arrow criterion benchmark completed (GKE) | [trigger](https://github.com/apache/arrow-rs/pull/10446#issuecomment-5218498440)
   
   **Instance:** `c4a-highmem-16` (12 vCPU / 65 GiB)
   
   Comparing perf-uneven-mask-intersect-union (635c740cbe789a483a2659d74f75a3892b22f39d) to 3e6bd62 (merge-base) [diff](https://github.com/apache/arrow-rs/compare/3e6bd627c7b6d0dcda8aeb0a6efc829508177d4f..635c740cbe789a483a2659d74f75a3892b22f39d)
   
   <details><summary>Run configuration</summary>
   
   ```yaml
   run benchmark row_selector
   ```
   
   </details>
   
   <details><summary>CPU Details (lscpu)</summary>
   
   ```
   Architecture:                            aarch64
   CPU op-mode(s):                          64-bit
   Byte Order:                              Little Endian
   CPU(s):                                  16
   On-line CPU(s) list:                     0-15
   Vendor ID:                               ARM
   Model name:                              Neoverse-V2
   Model:                                   1
   Thread(s) per core:                      1
   Core(s) per cluster:                     16
   Socket(s):                               -
   Cluster(s):                              1
   Stepping:                                r0p1
   BogoMIPS:                                2000.00
   Flags:                                   fp asimd evtstrm aes pmull sha1 sha2 crc32 atomics fphp asimdhp cpuid asimdrdm jscvt fcma lrcpc dcpop sha3 sm3 sm4 asimddp sha512 sve asimdfhm dit uscat ilrcpc flagm sb paca pacg dcpodp sve2 sveaes svepmull svebitperm svesha3 svesm4 flagm2 frint svei8mm svebf16 i8mm bf16 dgh rng bti
   L1d cache:                               1 MiB (16 instances)
   L1i cache:                               1 MiB (16 instances)
   L2 cache:                                32 MiB (16 instances)
   L3 cache:                                80 MiB (1 instance)
   NUMA node(s):                            1
   NUMA node0 CPU(s):                       0-15
   Vulnerability Gather data sampling:      Not affected
   Vulnerability Indirect target selection: Not affected
   Vulnerability Itlb multihit:             Not affected
   Vulnerability L1tf:                      Not affected
   Vulnerability Mds:                       Not affected
   Vulnerability Meltdown:                  Not affected
   Vulnerability Mmio stale data:           Not affected
   Vulnerability Reg file data sampling:    Not affected
   Vulnerability Retbleed:                  Not affected
   Vulnerability Spec rstack overflow:      Not affected
   Vulnerability Spec store bypass:         Mitigation; Speculative Store Bypass disabled via prctl
   Vulnerability Spectre v1:                Mitigation; __user pointer sanitization
   Vulnerability Spectre v2:                Mitigation; CSV2, BHB
   Vulnerability Srbds:                     Not affected
   Vulnerability Tsa:                       Not affected
   Vulnerability Tsx async abort:           Not affected
   Vulnerability Vmscape:                   Not affected
   ```
   
   </details>
   
   <details><summary>Details</summary>
   <p>
   
   ```
   group                                         main                                   perf-uneven-mask-intersect-union
   -----                                         ----                                   --------------------------------
   and_then                                      1.00    590.2±1.93µs        ? ?/sec    1.01    595.2±2.20µs        ? ?/sec
   from_filters                                  1.00    370.3±1.76µs        ? ?/sec    1.00    370.8±1.95µs        ? ?/sec
   intersection                                  1.00   1300.6±1.55µs        ? ?/sec    1.00   1301.6±2.29µs        ? ?/sec
   mask_consume/random                           1.00    402.2±2.88µs        ? ?/sec    1.00    402.5±3.54µs        ? ?/sec
   mask_consume/run01                            1.00   777.0±31.47µs        ? ?/sec    1.01   782.4±26.32µs        ? ?/sec
   mask_consume/run04                            1.00   178.5±12.64µs        ? ?/sec    1.00   177.7±11.55µs        ? ?/sec
   mask_consume/run128                           1.00      7.9±0.01µs        ? ?/sec    1.11      8.8±0.01µs        ? ?/sec
   mask_consume/run16                            1.00     46.1±4.84µs        ? ?/sec    1.00     46.0±4.99µs        ? ?/sec
   mask_consume/run32                            1.00     22.4±2.04µs        ? ?/sec    1.00     22.4±1.88µs        ? ?/sec
   mask_consume/run48                            1.00     15.5±0.77µs        ? ?/sec    1.04     16.2±0.53µs        ? ?/sec
   mask_consume/run64                            1.00     12.6±0.07µs        ? ?/sec    1.04     13.1±0.15µs        ? ?/sec
   mask_consume/run96                            1.00      8.8±0.04µs        ? ?/sec    1.11      9.8±0.00µs        ? ?/sec
   mask_intersection/equal/both_zero             1.03      9.4±0.01µs        ? ?/sec    1.00      9.1±0.02µs        ? ?/sec
   mask_intersection/equal/diff_mod64            2.48    110.1±0.03µs        ? ?/sec    1.00     44.5±0.04µs        ? ?/sec
   mask_intersection/equal/same_mod64            1.72     87.0±0.64µs        ? ?/sec    1.00     50.6±0.69µs        ? ?/sec
   mask_intersection/equal/same_mod64_far        1.83     86.8±0.43µs        ? ?/sec    1.00     47.5±0.04µs        ? ?/sec
   mask_intersection/tail1/both_zero             1.00     17.8±0.12µs        ? ?/sec    1.08     19.3±0.07µs        ? ?/sec
   mask_intersection/tail1/diff_mod64            3.47    117.9±0.05µs        ? ?/sec    1.00     34.0±0.04µs        ? ?/sec
   mask_intersection/tail1/same_mod64            3.71     87.5±0.11µs        ? ?/sec    1.00     23.6±0.03µs        ? ?/sec
   mask_intersection/tail1/same_mod64_far        4.02     95.4±0.45µs        ? ?/sec    1.00     23.7±0.03µs        ? ?/sec
   mask_intersection/tail1of3/both_zero          1.01     14.6±0.11µs        ? ?/sec    1.00     14.5±0.02µs        ? ?/sec
   mask_intersection/tail1of3/diff_mod64         3.62     88.3±0.05µs        ? ?/sec    1.00     24.4±0.02µs        ? ?/sec
   mask_intersection/tail1of3/same_mod64         4.26     74.0±0.85µs        ? ?/sec    1.00     17.4±0.02µs        ? ?/sec
   mask_intersection/tail1of3/same_mod64_far     3.89     68.0±0.08µs        ? ?/sec    1.00     17.5±0.02µs        ? ?/sec
   mask_intersection/tail_most/both_zero         1.49      7.7±0.16µs        ? ?/sec    1.00      5.1±0.01µs        ? ?/sec
   mask_intersection/tail_most/diff_mod64        5.52     28.3±0.02µs        ? ?/sec    1.00      5.1±0.00µs        ? ?/sec
   mask_intersection/tail_most/same_mod64        5.54     28.3±0.03µs        ? ?/sec    1.00      5.1±0.01µs        ? ?/sec
   mask_intersection/tail_most/same_mod64_far    5.52     28.4±0.10µs        ? ?/sec    1.00      5.1±0.02µs        ? ?/sec
   mask_iterate_then_consume/random              1.00    448.1±3.24µs        ? ?/sec    1.00    447.0±3.51µs        ? ?/sec
   mask_iterate_then_consume/run01               1.00   863.7±30.50µs        ? ?/sec    1.06   911.7±27.96µs        ? ?/sec
   mask_iterate_then_consume/run04               1.00   197.2±12.29µs        ? ?/sec    1.00   196.2±12.28µs        ? ?/sec
   mask_iterate_then_consume/run128              1.00      8.4±0.01µs        ? ?/sec    1.10      9.2±0.01µs        ? ?/sec
   mask_iterate_then_consume/run16               1.00     49.1±4.52µs        ? ?/sec    1.00     49.1±4.62µs        ? ?/sec
   mask_iterate_then_consume/run32               1.00     24.0±1.83µs        ? ?/sec    1.00     24.0±1.74µs        ? ?/sec
   mask_iterate_then_consume/run48               1.00     16.6±0.75µs        ? ?/sec    1.04     17.3±0.50µs        ? ?/sec
   mask_iterate_then_consume/run64               1.00     13.6±0.08µs        ? ?/sec    1.03     13.9±0.13µs        ? ?/sec
   mask_iterate_then_consume/run96               1.00      9.5±0.03µs        ? ?/sec    1.10     10.4±0.00µs        ? ?/sec
   mask_union/equal/both_zero                    1.03      9.4±0.01µs        ? ?/sec    1.00      9.1±0.02µs        ? ?/sec
   mask_union/equal/diff_mod64                   2.67    110.7±0.05µs        ? ?/sec    1.00     41.5±0.04µs        ? ?/sec
   mask_union/equal/same_mod64                   1.67     79.6±0.04µs        ? ?/sec    1.00     47.6±0.04µs        ? ?/sec
   mask_union/equal/same_mod64_far               1.68     79.9±0.06µs        ? ?/sec    1.00     47.5±0.03µs        ? ?/sec
   mask_union/tail1/both_zero                    1.00     17.9±0.05µs        ? ?/sec    1.07     19.2±0.03µs        ? ?/sec
   mask_union/tail1/diff_mod64                   3.62    118.2±0.27µs        ? ?/sec    1.00     32.6±0.15µs        ? ?/sec
   mask_union/tail1/same_mod64                   3.69     87.6±0.10µs        ? ?/sec    1.00     23.8±0.02µs        ? ?/sec
   mask_union/tail1/same_mod64_far               3.69     87.5±0.11µs        ? ?/sec    1.00     23.7±0.04µs        ? ?/sec
   mask_union/tail1of3/both_zero                 1.01     14.6±0.11µs        ? ?/sec    1.00     14.5±0.03µs        ? ?/sec
   mask_union/tail1of3/diff_mod64                3.79     88.3±0.06µs        ? ?/sec    1.00     23.3±0.03µs        ? ?/sec
   mask_union/tail1of3/same_mod64                3.91     67.6±0.05µs        ? ?/sec    1.00     17.3±0.03µs        ? ?/sec
   mask_union/tail1of3/same_mod64_far            3.88     67.8±0.05µs        ? ?/sec    1.00     17.5±0.02µs        ? ?/sec
   mask_union/tail_most/both_zero                1.50      7.7±0.16µs        ? ?/sec    1.00      5.1±0.01µs        ? ?/sec
   mask_union/tail_most/diff_mod64               5.51     28.3±0.02µs        ? ?/sec    1.00      5.1±0.00µs        ? ?/sec
   mask_union/tail_most/same_mod64               5.55     28.3±0.03µs        ? ?/sec    1.00      5.1±0.01µs        ? ?/sec
   mask_union/tail_most/same_mod64_far           5.51     28.3±0.03µs        ? ?/sec    1.00      5.1±0.00µs        ? ?/sec
   union                                         1.00   1310.5±1.28µs        ? ?/sec    1.00   1316.4±1.51µs        ? ?/sec
   ```
   
   </p>
   </details>
   
   <details><summary>Resource Usage</summary>
   
   **base (merge-base)**
   | Metric | Value |
   |--------|-------|
   | Wall time | 545.1s |
   | Peak memory | 18.7 MiB |
   | Avg memory | 16.5 MiB |
   | CPU user | 542.4s |
   | CPU sys | 0.0s |
   | Peak spill | 0 B |
   
   **branch**
   | Metric | Value |
   |--------|-------|
   | Wall time | 540.1s |
   | Peak memory | 16.9 MiB |
   | Avg memory | 15.4 MiB |
   | CPU user | 534.6s |
   | CPU sys | 0.0s |
   | Peak spill | 0 B |
   </details>
   
   
   ---
   [File an issue](https://github.com/adriangb/datafusion-benchmarking/issues) against this benchmark runner


-- 
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: github-unsubscribe@arrow.apache.org

For queries about this service, please contact Infrastructure at:
users@infra.apache.org


Re: [PR] perf(parquet): avoid redundant copies in mask-backed intersection/union [arrow-rs]

Posted by "haohuaijin (via GitHub)" <gi...@apache.org>.
haohuaijin commented on PR #10446:
URL: https://github.com/apache/arrow-rs/pull/10446#issuecomment-5207283084

   > So the improvement looks real, but it does not appear to come from the redundant-copy removal described in the PR. Could you clarify whether this is a cross-crate inlining/codegen effect? One useful way to isolate it would be to benchmark &left & &right against a direct from_bitwise_binary_op call on the same commit and with the same inputs.
   
   Thanks for the suggestion — I ran the isolation, then took it further with LTO. All on `upstream/main`, both variants in one binary, same inputs, `codegen-units=1`:
   
   | offsets | variant | no LTO | fat LTO |
   | --- | --- | --- | --- |
   | `(3, 5)` | `&l & &r` | 97.0 µs | 97.3 µs |
   | `(3, 5)` | direct | **25.6 µs** | **97.4 µs** |
   
   At `(3, 5)` both produce byte-identical buffers, and the gap disappears under LTO. Thus `equal/diff_mod64` is an artifact of cross-crate codegen, not related to this change. (LTO slowing the direct call😂.)
   


-- 
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: github-unsubscribe@arrow.apache.org

For queries about this service, please contact Infrastructure at:
users@infra.apache.org


Re: [PR] perf(parquet): avoid redundant copies in mask-backed intersection/union [arrow-rs]

Posted by "adriangbot (via GitHub)" <gi...@apache.org>.
adriangbot commented on PR #10446:
URL: https://github.com/apache/arrow-rs/pull/10446#issuecomment-5208879541

   🤖 Arrow criterion benchmark running (GKE) | [trigger](https://github.com/apache/arrow-rs/pull/10446#issuecomment-5208866997)
   **Instance:** `c4a-highmem-16` (12 vCPU / 65 GiB) | `Linux bench-c5208866997-1491-98jjq 6.12.85+ #1 SMP Wed Jun 17 20:31:55 UTC 2026 aarch64 GNU/Linux`
   <details><summary>CPU Details (lscpu)</summary>
   
   ```
   Architecture:                            aarch64
   CPU op-mode(s):                          64-bit
   Byte Order:                              Little Endian
   CPU(s):                                  16
   On-line CPU(s) list:                     0-15
   Vendor ID:                               ARM
   Model name:                              Neoverse-V2
   Model:                                   1
   Thread(s) per core:                      1
   Core(s) per cluster:                     16
   Socket(s):                               -
   Cluster(s):                              1
   Stepping:                                r0p1
   BogoMIPS:                                2000.00
   Flags:                                   fp asimd evtstrm aes pmull sha1 sha2 crc32 atomics fphp asimdhp cpuid asimdrdm jscvt fcma lrcpc dcpop sha3 sm3 sm4 asimddp sha512 sve asimdfhm dit uscat ilrcpc flagm sb paca pacg dcpodp sve2 sveaes svepmull svebitperm svesha3 svesm4 flagm2 frint svei8mm svebf16 i8mm bf16 dgh rng bti
   L1d cache:                               1 MiB (16 instances)
   L1i cache:                               1 MiB (16 instances)
   L2 cache:                                32 MiB (16 instances)
   L3 cache:                                80 MiB (1 instance)
   NUMA node(s):                            1
   NUMA node0 CPU(s):                       0-15
   Vulnerability Gather data sampling:      Not affected
   Vulnerability Indirect target selection: Not affected
   Vulnerability Itlb multihit:             Not affected
   Vulnerability L1tf:                      Not affected
   Vulnerability Mds:                       Not affected
   Vulnerability Meltdown:                  Not affected
   Vulnerability Mmio stale data:           Not affected
   Vulnerability Reg file data sampling:    Not affected
   Vulnerability Retbleed:                  Not affected
   Vulnerability Spec rstack overflow:      Not affected
   Vulnerability Spec store bypass:         Mitigation; Speculative Store Bypass disabled via prctl
   Vulnerability Spectre v1:                Mitigation; __user pointer sanitization
   Vulnerability Spectre v2:                Mitigation; CSV2, BHB
   Vulnerability Srbds:                     Not affected
   Vulnerability Tsa:                       Not affected
   Vulnerability Tsx async abort:           Not affected
   Vulnerability Vmscape:                   Not affected
   ```
   
   </details>
   
   Comparing perf-uneven-mask-intersect-union (004bf28557f12708aa8509eef729d9e941ccce6d) to 3df22cd (merge-base) [diff](https://github.com/apache/arrow-rs/compare/3df22cd7c664e213ab3058d1b98db358467560d4..004bf28557f12708aa8509eef729d9e941ccce6d)
   
   <details><summary>Run configuration</summary>
   
   ```yaml
   run benchmark mask_intersection
   ```
   
   </details>
   
   BENCH_COMMAND=cargo bench --features=arrow,async,test_common,experimental,object_store --bench mask_intersection
   Results will be posted here when complete
   
   ---
   [File an issue](https://github.com/adriangb/datafusion-benchmarking/issues) against this benchmark runner


-- 
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: github-unsubscribe@arrow.apache.org

For queries about this service, please contact Infrastructure at:
users@infra.apache.org


Re: [PR] perf(parquet): avoid redundant copies in mask-backed intersection/union [arrow-rs]

Posted by "adriangbot (via GitHub)" <gi...@apache.org>.
adriangbot commented on PR #10446:
URL: https://github.com/apache/arrow-rs/pull/10446#issuecomment-5225320572

   🤖 Arrow criterion benchmark running (GKE) | [trigger](https://github.com/apache/arrow-rs/pull/10446#issuecomment-5225311392)
   **Instance:** `c4a-highmem-16` (12 vCPU / 65 GiB) | `Linux bench-c5225311392-1501-72hjv 6.12.85+ #1 SMP Wed Jun 17 20:31:55 UTC 2026 aarch64 GNU/Linux`
   <details><summary>CPU Details (lscpu)</summary>
   
   ```
   Architecture:                            aarch64
   CPU op-mode(s):                          64-bit
   Byte Order:                              Little Endian
   CPU(s):                                  16
   On-line CPU(s) list:                     0-15
   Vendor ID:                               ARM
   Model name:                              Neoverse-V2
   Model:                                   1
   Thread(s) per core:                      1
   Core(s) per cluster:                     16
   Socket(s):                               -
   Cluster(s):                              1
   Stepping:                                r0p1
   BogoMIPS:                                2000.00
   Flags:                                   fp asimd evtstrm aes pmull sha1 sha2 crc32 atomics fphp asimdhp cpuid asimdrdm jscvt fcma lrcpc dcpop sha3 sm3 sm4 asimddp sha512 sve asimdfhm dit uscat ilrcpc flagm sb paca pacg dcpodp sve2 sveaes svepmull svebitperm svesha3 svesm4 flagm2 frint svei8mm svebf16 i8mm bf16 dgh rng bti
   L1d cache:                               1 MiB (16 instances)
   L1i cache:                               1 MiB (16 instances)
   L2 cache:                                32 MiB (16 instances)
   L3 cache:                                80 MiB (1 instance)
   NUMA node(s):                            1
   NUMA node0 CPU(s):                       0-15
   Vulnerability Gather data sampling:      Not affected
   Vulnerability Indirect target selection: Not affected
   Vulnerability Itlb multihit:             Not affected
   Vulnerability L1tf:                      Not affected
   Vulnerability Mds:                       Not affected
   Vulnerability Meltdown:                  Not affected
   Vulnerability Mmio stale data:           Not affected
   Vulnerability Reg file data sampling:    Not affected
   Vulnerability Retbleed:                  Not affected
   Vulnerability Spec rstack overflow:      Not affected
   Vulnerability Spec store bypass:         Mitigation; Speculative Store Bypass disabled via prctl
   Vulnerability Spectre v1:                Mitigation; __user pointer sanitization
   Vulnerability Spectre v2:                Mitigation; CSV2, BHB
   Vulnerability Srbds:                     Not affected
   Vulnerability Tsa:                       Not affected
   Vulnerability Tsx async abort:           Not affected
   Vulnerability Vmscape:                   Not affected
   ```
   
   </details>
   
   Comparing perf-uneven-mask-intersect-union (635c740cbe789a483a2659d74f75a3892b22f39d) to 3e6bd62 (merge-base) [diff](https://github.com/apache/arrow-rs/compare/3e6bd627c7b6d0dcda8aeb0a6efc829508177d4f..635c740cbe789a483a2659d74f75a3892b22f39d)
   
   <details><summary>Run configuration</summary>
   
   ```yaml
   run benchmark row_selector
   ```
   
   </details>
   
   BENCH_COMMAND=cargo bench --features=arrow,async,test_common,experimental,object_store --bench row_selector
   Results will be posted here when complete
   
   ---
   [File an issue](https://github.com/adriangb/datafusion-benchmarking/issues) against this benchmark runner


-- 
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: github-unsubscribe@arrow.apache.org

For queries about this service, please contact Infrastructure at:
users@infra.apache.org


Re: [PR] perf(parquet): avoid redundant copies in mask-backed intersection/union [arrow-rs]

Posted by "haohuaijin (via GitHub)" <gi...@apache.org>.
haohuaijin commented on PR #10446:
URL: https://github.com/apache/arrow-rs/pull/10446#issuecomment-5226097864

   the benchmark is match the pr body (1.7-5.6x speed up), and the `mask_consume / mask_iterate_then_consume` movement looks unrelated, this pr do not touch the related path.
   
   


-- 
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: github-unsubscribe@arrow.apache.org

For queries about this service, please contact Infrastructure at:
users@infra.apache.org


Re: [PR] perf(parquet): avoid redundant copies in mask-backed intersection/union [arrow-rs]

Posted by "alamb (via GitHub)" <gi...@apache.org>.
alamb commented on PR #10446:
URL: https://github.com/apache/arrow-rs/pull/10446#issuecomment-5208868263

   merging up from main to try and get a clean CI run


-- 
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: github-unsubscribe@arrow.apache.org

For queries about this service, please contact Infrastructure at:
users@infra.apache.org


Re: [PR] perf(parquet): avoid redundant copies in mask-backed intersection/union [arrow-rs]

Posted by "haohuaijin (via GitHub)" <gi...@apache.org>.
haohuaijin commented on PR #10446:
URL: https://github.com/apache/arrow-rs/pull/10446#issuecomment-5212137957

   split the benchmark to https://github.com/apache/arrow-rs/pull/10574 cc @alamb 


-- 
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: github-unsubscribe@arrow.apache.org

For queries about this service, please contact Infrastructure at:
users@infra.apache.org


Re: [PR] perf(parquet): avoid redundant copies in mask-backed intersection/union [arrow-rs]

Posted by "hhhizzz (via GitHub)" <gi...@apache.org>.
hhhizzz commented on code in PR #10446:
URL: https://github.com/apache/arrow-rs/pull/10446#discussion_r3718326685


##########
parquet/src/arrow/arrow_reader/selection/algebra.rs:
##########
@@ -269,39 +269,77 @@ pub(super) fn union_row_selections(left: &[RowSelector], right: &[RowSelector])
 /// Bitwise AND of two mask-backed selections. Longer side's tail passes through.
 pub(super) fn intersect_masks(l: &BooleanBuffer, r: &BooleanBuffer) -> BooleanBuffer {
     if l.len() == r.len() {
-        return l & r;
-    }
-    let common = l.len().min(r.len());
-    let head = &l.slice(0, common) & &r.slice(0, common);
-    let (longer, longer_len) = if l.len() > r.len() {
-        (l, l.len())
-    } else {
-        (r, r.len())
-    };
-    let tail = longer.slice(common, longer_len - common);
-    let mut builder = BooleanBufferBuilder::new(longer_len);
-    builder.append_buffer(&head);
-    builder.append_buffer(&tail);
-    builder.finish()
+        return combine_equal_masks(l, r, |a, b| a & b);
+    }
+    combine_uneven_masks(l, r, |a, b| a & b)
 }
 
 /// Bitwise OR of two mask-backed selections. Longer side's tail passes through.
 pub(super) fn union_masks(l: &BooleanBuffer, r: &BooleanBuffer) -> BooleanBuffer {
     if l.len() == r.len() {
-        return l | r;
-    }
-    let common = l.len().min(r.len());
-    let head = &l.slice(0, common) | &r.slice(0, common);
-    let (longer, longer_len) = if l.len() > r.len() {
-        (l, l.len())
-    } else {
-        (r, r.len())
-    };
-    let tail = longer.slice(common, longer_len - common);
-    let mut builder = BooleanBufferBuilder::new(longer_len);
-    builder.append_buffer(&head);
-    builder.append_buffer(&tail);
-    builder.finish()
+        return combine_equal_masks(l, r, |a, b| a | b);

Review Comment:
   The logical semantics are unchanged, but I think we still have “user-facing changes” here.
   
   `RowSelection::as_mask()` is public, so callers can observe that equal-length intersection/union previously returned an offset-zero `BooleanBuffer`, while this implementation may preserve a non-zero offset. This also changes the observable `values()`, `inner()`, and `ptr_eq()` representation.
   
   I don't think this is a breaking API change because `as_mask()` does not promise normalization and consumers must already honor `BooleanBuffer::offset()`. Could we clarify the PR wording to say that there are no public signature or logical-selection changes, while the underlying mask layout may differ?
   



##########
parquet/benches/row_selector.rs:
##########
@@ -26,6 +26,21 @@ use std::hint;
 /// [`RowSelector`]s per row, so the RLE encoding dominates.
 const MASK_RUN_LENGTHS: &[usize] = &[1, 4, 16, 32, 48, 64, 96, 128];
 
+const MASK_ALGEBRA_ROWS: usize = 3_000_000;
+
+/// Operand length pairs. Unequal lengths pass the longer side's tail through unchanged,
+/// so the ratio decides how much of the work is the bitwise combine versus the tail.
+const MASK_ALGEBRA_LENGTHS: &[(&str, usize, usize)] = &[
+    ("equal", MASK_ALGEBRA_ROWS, MASK_ALGEBRA_ROWS),
+    ("tail1", MASK_ALGEBRA_ROWS, MASK_ALGEBRA_ROWS - 1),
+    ("tail1of3", MASK_ALGEBRA_ROWS, MASK_ALGEBRA_ROWS * 2 / 3),
+    ("tail_most", MASK_ALGEBRA_ROWS, 1_000),
+];
+
+/// Bit offsets applied to both operands. Masks come from [`BooleanBuffer::slice`], so a
+/// non-zero offset is normal, and one that is not byte aligned is the expensive case.
+const MASK_ALGEBRA_OFFSETS: &[(&str, usize)] = &[("aligned", 0), ("unaligned", 3)];

Review Comment:
   Could we include more case where the operands have different relative offsets?
   
   At the moment both operands use the same offset, so the unaligned case only exercises the `left_offset % 64 == right_offset % 64` fast path in `BooleanBuffer::from_bitwise_binary_op`. When the offsets differ, for example `(3, 5)`, the helper takes the shifting fallback and returns a zero-offset buffer, so the old implementation does not necessarily pay the extra normalization copy described in the PR.
   
   Something like `(0, 0)`, `(3, 3)`, `(3, 5)`, and `(3, 67)` would make the benchmark coverage and the performance claim more precise. Alternatively, the PR description could narrow “non-byte-aligned operands” to “operands sharing a non-zero sub-64-bit alignment”.



##########
parquet/src/arrow/arrow_reader/selection/algebra.rs:
##########
@@ -269,39 +269,77 @@ pub(super) fn union_row_selections(left: &[RowSelector], right: &[RowSelector])
 /// Bitwise AND of two mask-backed selections. Longer side's tail passes through.
 pub(super) fn intersect_masks(l: &BooleanBuffer, r: &BooleanBuffer) -> BooleanBuffer {
     if l.len() == r.len() {
-        return l & r;
-    }
-    let common = l.len().min(r.len());
-    let head = &l.slice(0, common) & &r.slice(0, common);
-    let (longer, longer_len) = if l.len() > r.len() {
-        (l, l.len())
-    } else {
-        (r, r.len())
-    };
-    let tail = longer.slice(common, longer_len - common);
-    let mut builder = BooleanBufferBuilder::new(longer_len);
-    builder.append_buffer(&head);
-    builder.append_buffer(&tail);
-    builder.finish()
+        return combine_equal_masks(l, r, |a, b| a & b);
+    }
+    combine_uneven_masks(l, r, |a, b| a & b)
 }
 
 /// Bitwise OR of two mask-backed selections. Longer side's tail passes through.
 pub(super) fn union_masks(l: &BooleanBuffer, r: &BooleanBuffer) -> BooleanBuffer {
     if l.len() == r.len() {
-        return l | r;
-    }
-    let common = l.len().min(r.len());
-    let head = &l.slice(0, common) | &r.slice(0, common);
-    let (longer, longer_len) = if l.len() > r.len() {
-        (l, l.len())
-    } else {
-        (r, r.len())
-    };
-    let tail = longer.slice(common, longer_len - common);
-    let mut builder = BooleanBufferBuilder::new(longer_len);
-    builder.append_buffer(&head);
-    builder.append_buffer(&tail);
-    builder.finish()
+        return combine_equal_masks(l, r, |a, b| a | b);
+    }
+    combine_uneven_masks(l, r, |a, b| a | b)
+}
+
+/// Combines two masks of equal length with the bitwise operation `op`.
+///
+/// `BitAnd`/`BitOr` on `&BooleanBuffer` normalise the result to a zero bit offset,
+/// which costs a second allocation and a shifting copy of the whole mask when the
+/// operands are not byte aligned. Building the buffer directly keeps the offset,
+/// as the uneven path does.
+fn combine_equal_masks<F>(l: &BooleanBuffer, r: &BooleanBuffer, op: F) -> BooleanBuffer
+where
+    F: FnMut(u64, u64) -> u64,
+{
+    BooleanBuffer::from_bitwise_binary_op(
+        l.values(),
+        l.offset(),
+        r.values(),
+        r.offset(),
+        l.len(),
+        op,
+    )
+}
+
+/// Combines two masks of differing lengths with the bitwise operation `op`,
+/// passing the longer side's tail through unchanged.
+///
+/// The longer mask is copied once into a [`MutableBuffer`] and `op` is then
+/// applied in place over the common prefix. This avoids materialising the
+/// prefix into its own buffer and copying both prefix and tail again through a
+/// [`BooleanBufferBuilder`].
+///
+/// Neither the mask offsets nor the prefix length are assumed to be byte
+/// aligned: the copy keeps the longer mask's sub-byte offset so it stays a
+/// plain byte copy, and the offset is carried over to the returned buffer.
+fn combine_uneven_masks<F>(l: &BooleanBuffer, r: &BooleanBuffer, op: F) -> BooleanBuffer

Review Comment:
   Nit: a few names could make the offset arithmetic easier to follow:
   
   - `combine_uneven_masks` -> `combine_unequal_length_masks`
   - `bit_offset` -> `offset_within_byte` or `sub_byte_offset`
   - `start` / `end` -> `start_byte` / `end_byte`
   
   In particular, `bit_offset` currently looks like the full `BooleanBuffer::offset()`, but it is specifically `longer.offset() % 8`, which is an important distinction in this code.



##########
parquet/src/arrow/arrow_reader/selection/algebra.rs:
##########
@@ -269,39 +269,77 @@ pub(super) fn union_row_selections(left: &[RowSelector], right: &[RowSelector])
 /// Bitwise AND of two mask-backed selections. Longer side's tail passes through.
 pub(super) fn intersect_masks(l: &BooleanBuffer, r: &BooleanBuffer) -> BooleanBuffer {
     if l.len() == r.len() {
-        return l & r;
-    }
-    let common = l.len().min(r.len());
-    let head = &l.slice(0, common) & &r.slice(0, common);
-    let (longer, longer_len) = if l.len() > r.len() {
-        (l, l.len())
-    } else {
-        (r, r.len())
-    };
-    let tail = longer.slice(common, longer_len - common);
-    let mut builder = BooleanBufferBuilder::new(longer_len);
-    builder.append_buffer(&head);
-    builder.append_buffer(&tail);
-    builder.finish()
+        return combine_equal_masks(l, r, |a, b| a & b);
+    }
+    combine_uneven_masks(l, r, |a, b| a & b)
 }
 
 /// Bitwise OR of two mask-backed selections. Longer side's tail passes through.
 pub(super) fn union_masks(l: &BooleanBuffer, r: &BooleanBuffer) -> BooleanBuffer {
     if l.len() == r.len() {
-        return l | r;
-    }
-    let common = l.len().min(r.len());
-    let head = &l.slice(0, common) | &r.slice(0, common);
-    let (longer, longer_len) = if l.len() > r.len() {
-        (l, l.len())
-    } else {
-        (r, r.len())
-    };
-    let tail = longer.slice(common, longer_len - common);
-    let mut builder = BooleanBufferBuilder::new(longer_len);
-    builder.append_buffer(&head);
-    builder.append_buffer(&tail);
-    builder.finish()
+        return combine_equal_masks(l, r, |a, b| a | b);
+    }
+    combine_uneven_masks(l, r, |a, b| a | b)
+}
+
+/// Combines two masks of equal length with the bitwise operation `op`.
+///
+/// `BitAnd`/`BitOr` on `&BooleanBuffer` normalise the result to a zero bit offset,
+/// which costs a second allocation and a shifting copy of the whole mask when the
+/// operands are not byte aligned. Building the buffer directly keeps the offset,
+/// as the uneven path does.
+fn combine_equal_masks<F>(l: &BooleanBuffer, r: &BooleanBuffer, op: F) -> BooleanBuffer
+where
+    F: FnMut(u64, u64) -> u64,
+{
+    BooleanBuffer::from_bitwise_binary_op(
+        l.values(),
+        l.offset(),
+        r.values(),
+        r.offset(),
+        l.len(),
+        op,
+    )
+}
+
+/// Combines two masks of differing lengths with the bitwise operation `op`,
+/// passing the longer side's tail through unchanged.
+///
+/// The longer mask is copied once into a [`MutableBuffer`] and `op` is then
+/// applied in place over the common prefix. This avoids materialising the
+/// prefix into its own buffer and copying both prefix and tail again through a
+/// [`BooleanBufferBuilder`].
+///
+/// Neither the mask offsets nor the prefix length are assumed to be byte
+/// aligned: the copy keeps the longer mask's sub-byte offset so it stays a
+/// plain byte copy, and the offset is carried over to the returned buffer.
+fn combine_uneven_masks<F>(l: &BooleanBuffer, r: &BooleanBuffer, op: F) -> BooleanBuffer
+where
+    F: FnMut(u64, u64) -> u64,
+{
+    let (longer, shorter) = if l.len() > r.len() { (l, r) } else { (r, l) };
+    let common = shorter.len();
+    if common == 0 {

Review Comment:
   Is retaining the original backing allocation intentional for the empty-common-prefix case?
   
   `BooleanBuffer::clone()` is shallow, so if `longer` is a small slice of a much larger buffer, the result will continue to retain the entire original allocation. The previous builder path produced a compact copy of the logical mask.
   
   Avoiding the copy is attractive, but this changes the memory-retention behavior and could be surprising when the result outlives the input selection. Could we either document this tradeoff, add a test covering a small slice of a large buffer, or copy only the logical byte range here?



-- 
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: github-unsubscribe@arrow.apache.org

For queries about this service, please contact Infrastructure at:
users@infra.apache.org


Re: [PR] perf(parquet): single-allocation intersect_masks/union_masks for unequal lengths [arrow-rs]

Posted by "haohuaijin (via GitHub)" <gi...@apache.org>.
haohuaijin commented on PR #10446:
URL: https://github.com/apache/arrow-rs/pull/10446#issuecomment-5179823238

   Hi @alamb @hhhizzz , this pr makes the uneven-length intersection/union copy once instead of twice — 18–34% faster, or 61–83% when the masks aren't byte aligned. Also adds a benchmark for the path. ready for reviews.


-- 
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: github-unsubscribe@arrow.apache.org

For queries about this service, please contact Infrastructure at:
users@infra.apache.org


Re: [PR] perf(parquet): avoid redundant copies in mask-backed intersection/union [arrow-rs]

Posted by "alamb (via GitHub)" <gi...@apache.org>.
alamb commented on PR #10446:
URL: https://github.com/apache/arrow-rs/pull/10446#issuecomment-5297059180

   > > Looks good to me @haohuaijin
   > > Thank you
   > > @hhhizzz does this PR look ready to merge to you too?
   > 
   > Sorry I just found I missed the message, the PR looks good to me, thank you!
   
   No problem -- thank you for checking. I totally relate to not seeing all git hub alerts (I find it close to impossible to keep up)


-- 
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: github-unsubscribe@arrow.apache.org

For queries about this service, please contact Infrastructure at:
users@infra.apache.org


Re: [PR] perf(parquet): avoid redundant copies in mask-backed intersection/union [arrow-rs]

Posted by "adriangbot (via GitHub)" <gi...@apache.org>.
adriangbot commented on PR #10446:
URL: https://github.com/apache/arrow-rs/pull/10446#issuecomment-5225378225

   🤖 Arrow criterion benchmark completed (GKE) | [trigger](https://github.com/apache/arrow-rs/pull/10446#issuecomment-5225311392)
   
   **Instance:** `c4a-highmem-16` (12 vCPU / 65 GiB)
   
   Comparing perf-uneven-mask-intersect-union (635c740cbe789a483a2659d74f75a3892b22f39d) to 3e6bd62 (merge-base) [diff](https://github.com/apache/arrow-rs/compare/3e6bd627c7b6d0dcda8aeb0a6efc829508177d4f..635c740cbe789a483a2659d74f75a3892b22f39d)
   
   <details><summary>Run configuration</summary>
   
   ```yaml
   run benchmark row_selector
   ```
   
   </details>
   
   <details><summary>CPU Details (lscpu)</summary>
   
   ```
   Architecture:                            aarch64
   CPU op-mode(s):                          64-bit
   Byte Order:                              Little Endian
   CPU(s):                                  16
   On-line CPU(s) list:                     0-15
   Vendor ID:                               ARM
   Model name:                              Neoverse-V2
   Model:                                   1
   Thread(s) per core:                      1
   Core(s) per cluster:                     16
   Socket(s):                               -
   Cluster(s):                              1
   Stepping:                                r0p1
   BogoMIPS:                                2000.00
   Flags:                                   fp asimd evtstrm aes pmull sha1 sha2 crc32 atomics fphp asimdhp cpuid asimdrdm jscvt fcma lrcpc dcpop sha3 sm3 sm4 asimddp sha512 sve asimdfhm dit uscat ilrcpc flagm sb paca pacg dcpodp sve2 sveaes svepmull svebitperm svesha3 svesm4 flagm2 frint svei8mm svebf16 i8mm bf16 dgh rng bti
   L1d cache:                               1 MiB (16 instances)
   L1i cache:                               1 MiB (16 instances)
   L2 cache:                                32 MiB (16 instances)
   L3 cache:                                80 MiB (1 instance)
   NUMA node(s):                            1
   NUMA node0 CPU(s):                       0-15
   Vulnerability Gather data sampling:      Not affected
   Vulnerability Indirect target selection: Not affected
   Vulnerability Itlb multihit:             Not affected
   Vulnerability L1tf:                      Not affected
   Vulnerability Mds:                       Not affected
   Vulnerability Meltdown:                  Not affected
   Vulnerability Mmio stale data:           Not affected
   Vulnerability Reg file data sampling:    Not affected
   Vulnerability Retbleed:                  Not affected
   Vulnerability Spec rstack overflow:      Not affected
   Vulnerability Spec store bypass:         Mitigation; Speculative Store Bypass disabled via prctl
   Vulnerability Spectre v1:                Mitigation; __user pointer sanitization
   Vulnerability Spectre v2:                Mitigation; CSV2, BHB
   Vulnerability Srbds:                     Not affected
   Vulnerability Tsa:                       Not affected
   Vulnerability Tsx async abort:           Not affected
   Vulnerability Vmscape:                   Not affected
   ```
   
   </details>
   
   <details><summary>Details</summary>
   <p>
   
   ```
   group                                         main                                   perf-uneven-mask-intersect-union
   -----                                         ----                                   --------------------------------
   and_then                                      1.00    590.7±2.57µs        ? ?/sec    1.00    591.6±2.17µs        ? ?/sec
   from_filters                                  1.00    371.8±2.05µs        ? ?/sec    1.00    371.0±2.32µs        ? ?/sec
   intersection                                  1.00   1300.9±1.89µs        ? ?/sec    1.01   1308.4±3.08µs        ? ?/sec
   mask_consume/random                           1.01    404.8±3.35µs        ? ?/sec    1.00    402.6±3.58µs        ? ?/sec
   mask_consume/run01                            1.00   775.7±30.89µs        ? ?/sec    1.00   775.7±31.73µs        ? ?/sec
   mask_consume/run04                            1.00   177.6±11.94µs        ? ?/sec    1.00   177.0±11.67µs        ? ?/sec
   mask_consume/run128                           1.00      7.9±0.01µs        ? ?/sec    1.11      8.7±0.01µs        ? ?/sec
   mask_consume/run16                            1.00     45.9±4.52µs        ? ?/sec    1.00     45.9±4.99µs        ? ?/sec
   mask_consume/run32                            1.00     22.2±1.77µs        ? ?/sec    1.00     22.3±1.88µs        ? ?/sec
   mask_consume/run48                            1.00     15.5±0.70µs        ? ?/sec    1.04     16.1±0.57µs        ? ?/sec
   mask_consume/run64                            1.00     12.6±0.07µs        ? ?/sec    1.04     13.1±0.11µs        ? ?/sec
   mask_consume/run96                            1.00      8.9±0.06µs        ? ?/sec    1.10      9.8±0.01µs        ? ?/sec
   mask_intersection/equal/both_zero             1.05      9.3±0.02µs        ? ?/sec    1.00      8.9±0.01µs        ? ?/sec
   mask_intersection/equal/diff_mod64            2.48    110.2±0.07µs        ? ?/sec    1.00     44.5±0.04µs        ? ?/sec
   mask_intersection/equal/same_mod64            1.76     83.8±0.60µs        ? ?/sec    1.00     47.6±0.08µs        ? ?/sec
   mask_intersection/equal/same_mod64_far        1.55     80.0±0.05µs        ? ?/sec    1.00     51.5±0.35µs        ? ?/sec
   mask_intersection/tail1/both_zero             1.01     18.6±0.06µs        ? ?/sec    1.00     18.4±0.01µs        ? ?/sec
   mask_intersection/tail1/diff_mod64            3.49    118.0±0.10µs        ? ?/sec    1.00     33.8±0.03µs        ? ?/sec
   mask_intersection/tail1/same_mod64            3.70     87.7±0.08µs        ? ?/sec    1.00     23.7±0.03µs        ? ?/sec
   mask_intersection/tail1/same_mod64_far        3.72     87.9±0.08µs        ? ?/sec    1.00     23.7±0.05µs        ? ?/sec
   mask_intersection/tail1of3/both_zero          1.08     15.0±0.05µs        ? ?/sec    1.00     13.9±0.01µs        ? ?/sec
   mask_intersection/tail1of3/diff_mod64         3.66     88.5±0.05µs        ? ?/sec    1.00     24.2±0.02µs        ? ?/sec
   mask_intersection/tail1of3/same_mod64         3.90     67.7±0.06µs        ? ?/sec    1.00     17.3±0.03µs        ? ?/sec
   mask_intersection/tail1of3/same_mod64_far     3.96     68.2±0.08µs        ? ?/sec    1.00     17.2±0.02µs        ? ?/sec
   mask_intersection/tail_most/both_zero         1.50      7.7±0.06µs        ? ?/sec    1.00      5.1±0.01µs        ? ?/sec
   mask_intersection/tail_most/diff_mod64        5.58     28.4±0.03µs        ? ?/sec    1.00      5.1±0.00µs        ? ?/sec
   mask_intersection/tail_most/same_mod64        5.61     28.5±0.07µs        ? ?/sec    1.00      5.1±0.00µs        ? ?/sec
   mask_intersection/tail_most/same_mod64_far    5.48     28.4±0.02µs        ? ?/sec    1.00      5.2±0.01µs        ? ?/sec
   mask_iterate_then_consume/random              1.01    441.7±3.59µs        ? ?/sec    1.00    439.5±3.75µs        ? ?/sec
   mask_iterate_then_consume/run01               1.00   866.6±31.59µs        ? ?/sec    1.00   867.5±31.38µs        ? ?/sec
   mask_iterate_then_consume/run04               1.00   196.5±11.51µs        ? ?/sec    1.00   195.8±12.07µs        ? ?/sec
   mask_iterate_then_consume/run128              1.00      8.4±0.01µs        ? ?/sec    1.10      9.2±0.01µs        ? ?/sec
   mask_iterate_then_consume/run16               1.00     49.7±4.86µs        ? ?/sec    1.00     49.6±4.99µs        ? ?/sec
   mask_iterate_then_consume/run32               1.01     24.4±2.11µs        ? ?/sec    1.00     24.2±1.93µs        ? ?/sec
   mask_iterate_then_consume/run48               1.00     16.7±0.81µs        ? ?/sec    1.04     17.4±0.56µs        ? ?/sec
   mask_iterate_then_consume/run64               1.00     13.6±0.08µs        ? ?/sec    1.02     13.9±0.15µs        ? ?/sec
   mask_iterate_then_consume/run96               1.00      9.5±0.04µs        ? ?/sec    1.10     10.4±0.01µs        ? ?/sec
   mask_union/equal/both_zero                    1.05      9.3±0.02µs        ? ?/sec    1.00      8.9±0.01µs        ? ?/sec
   mask_union/equal/diff_mod64                   2.66    110.2±0.03µs        ? ?/sec    1.00     41.5±0.02µs        ? ?/sec
   mask_union/equal/same_mod64                   1.78     85.0±0.48µs        ? ?/sec    1.00     47.6±0.05µs        ? ?/sec
   mask_union/equal/same_mod64_far               1.65     85.4±2.23µs        ? ?/sec    1.00     51.8±0.48µs        ? ?/sec
   mask_union/tail1/both_zero                    1.02     18.7±0.04µs        ? ?/sec    1.00     18.4±0.01µs        ? ?/sec
   mask_union/tail1/diff_mod64                   3.65    117.9±0.11µs        ? ?/sec    1.00     32.3±0.03µs        ? ?/sec
   mask_union/tail1/same_mod64                   3.95     93.9±0.66µs        ? ?/sec    1.00     23.8±0.03µs        ? ?/sec
   mask_union/tail1/same_mod64_far               3.70     87.5±0.15µs        ? ?/sec    1.00     23.7±0.04µs        ? ?/sec
   mask_union/tail1of3/both_zero                 1.07     15.0±0.05µs        ? ?/sec    1.00     13.9±0.02µs        ? ?/sec
   mask_union/tail1of3/diff_mod64                3.84     88.5±0.04µs        ? ?/sec    1.00     23.0±0.01µs        ? ?/sec
   mask_union/tail1of3/same_mod64                3.95     68.2±0.18µs        ? ?/sec    1.00     17.3±0.01µs        ? ?/sec
   mask_union/tail1of3/same_mod64_far            3.96     68.2±0.08µs        ? ?/sec    1.00     17.2±0.01µs        ? ?/sec
   mask_union/tail_most/both_zero                1.50      7.7±0.06µs        ? ?/sec    1.00      5.1±0.01µs        ? ?/sec
   mask_union/tail_most/diff_mod64               5.58     28.4±0.03µs        ? ?/sec    1.00      5.1±0.00µs        ? ?/sec
   mask_union/tail_most/same_mod64               5.59     28.4±0.04µs        ? ?/sec    1.00      5.1±0.01µs        ? ?/sec
   mask_union/tail_most/same_mod64_far           5.58     28.4±0.02µs        ? ?/sec    1.00      5.1±0.00µs        ? ?/sec
   union                                         1.00   1314.5±1.99µs        ? ?/sec    1.00   1318.5±1.44µs        ? ?/sec
   ```
   
   </p>
   </details>
   
   <details><summary>Resource Usage</summary>
   
   **base (merge-base)**
   | Metric | Value |
   |--------|-------|
   | Wall time | 545.1s |
   | Peak memory | 18.7 MiB |
   | Avg memory | 16.5 MiB |
   | CPU user | 539.4s |
   | CPU sys | 0.0s |
   | Peak spill | 0 B |
   
   **branch**
   | Metric | Value |
   |--------|-------|
   | Wall time | 540.1s |
   | Peak memory | 16.9 MiB |
   | Avg memory | 15.4 MiB |
   | CPU user | 534.6s |
   | CPU sys | 0.0s |
   | Peak spill | 0 B |
   </details>
   
   
   ---
   [File an issue](https://github.com/adriangb/datafusion-benchmarking/issues) against this benchmark runner


-- 
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: github-unsubscribe@arrow.apache.org

For queries about this service, please contact Infrastructure at:
users@infra.apache.org


Re: [PR] perf(parquet): avoid redundant copies in mask-backed intersection/union [arrow-rs]

Posted by "hhhizzz (via GitHub)" <gi...@apache.org>.
hhhizzz commented on PR #10446:
URL: https://github.com/apache/arrow-rs/pull/10446#issuecomment-5199761952

   > thanks for your reviews @hhhizzz , i apply the suggestion in [5fe3cb7](https://github.com/apache/arrow-rs/pull/10446/commits/5fe3cb7c221692027ede6c3eda57bb0c66f575ce).
   > 
   > this is benchmark result after added the suggestion benchmark
   
   Thanks for providing the full `critcmp` output. The raw timings look stable, and the `equal/both_zero` result being flat is a useful sanity check.
   
   The remaining result I find surprising is `equal/diff_mod64`:
   
   - intersection: 98.8 µs -> 27.8 µs (3.55x)
   - union: 90.3 µs -> 27.7 µs (3.26x)
   
   With different mod-64 alignments, `BooleanBuffer::from_bitwise_binary_op` takes the shifting fallback and returns an offset-zero buffer. The old `buffer_bin_and` / `buffer_bin_or` wrappers should therefore use `into_inner()` without performing the additional normalization copy. The new path calls the same underlying helper directly.
   
   So the improvement looks real, but it does not appear to come from the redundant-copy removal described in the PR. Could you clarify whether this is a cross-crate inlining/codegen effect? One useful way to isolate it would be to benchmark `&left & &right` against a direct `from_bitwise_binary_op` call on the same commit and with the same 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: github-unsubscribe@arrow.apache.org

For queries about this service, please contact Infrastructure at:
users@infra.apache.org


Re: [PR] perf(parquet): avoid redundant copies in mask-backed intersection/union [arrow-rs]

Posted by "adriangbot (via GitHub)" <gi...@apache.org>.
adriangbot commented on PR #10446:
URL: https://github.com/apache/arrow-rs/pull/10446#issuecomment-5225257959

   🤖 Arrow criterion benchmark completed (GKE) | [trigger](https://github.com/apache/arrow-rs/pull/10446#issuecomment-5225185097)
   
   **Instance:** `c4a-highmem-16` (12 vCPU / 65 GiB)
   
   Comparing perf-uneven-mask-intersect-union (635c740cbe789a483a2659d74f75a3892b22f39d) to 3e6bd62 (merge-base) [diff](https://github.com/apache/arrow-rs/compare/3e6bd627c7b6d0dcda8aeb0a6efc829508177d4f..635c740cbe789a483a2659d74f75a3892b22f39d)
   
   <details><summary>Run configuration</summary>
   
   ```yaml
   run benchmark row_selector
   ```
   
   </details>
   
   <details><summary>CPU Details (lscpu)</summary>
   
   ```
   Architecture:                            aarch64
   CPU op-mode(s):                          64-bit
   Byte Order:                              Little Endian
   CPU(s):                                  16
   On-line CPU(s) list:                     0-15
   Vendor ID:                               ARM
   Model name:                              Neoverse-V2
   Model:                                   1
   Thread(s) per core:                      1
   Core(s) per cluster:                     16
   Socket(s):                               -
   Cluster(s):                              1
   Stepping:                                r0p1
   BogoMIPS:                                2000.00
   Flags:                                   fp asimd evtstrm aes pmull sha1 sha2 crc32 atomics fphp asimdhp cpuid asimdrdm jscvt fcma lrcpc dcpop sha3 sm3 sm4 asimddp sha512 sve asimdfhm dit uscat ilrcpc flagm sb paca pacg dcpodp sve2 sveaes svepmull svebitperm svesha3 svesm4 flagm2 frint svei8mm svebf16 i8mm bf16 dgh rng bti
   L1d cache:                               1 MiB (16 instances)
   L1i cache:                               1 MiB (16 instances)
   L2 cache:                                32 MiB (16 instances)
   L3 cache:                                80 MiB (1 instance)
   NUMA node(s):                            1
   NUMA node0 CPU(s):                       0-15
   Vulnerability Gather data sampling:      Not affected
   Vulnerability Indirect target selection: Not affected
   Vulnerability Itlb multihit:             Not affected
   Vulnerability L1tf:                      Not affected
   Vulnerability Mds:                       Not affected
   Vulnerability Meltdown:                  Not affected
   Vulnerability Mmio stale data:           Not affected
   Vulnerability Reg file data sampling:    Not affected
   Vulnerability Retbleed:                  Not affected
   Vulnerability Spec rstack overflow:      Not affected
   Vulnerability Spec store bypass:         Mitigation; Speculative Store Bypass disabled via prctl
   Vulnerability Spectre v1:                Mitigation; __user pointer sanitization
   Vulnerability Spectre v2:                Mitigation; CSV2, BHB
   Vulnerability Srbds:                     Not affected
   Vulnerability Tsa:                       Not affected
   Vulnerability Tsx async abort:           Not affected
   Vulnerability Vmscape:                   Not affected
   ```
   
   </details>
   
   <details><summary>Details</summary>
   <p>
   
   ```
   group                                         main                                   perf-uneven-mask-intersect-union
   -----                                         ----                                   --------------------------------
   and_then                                      1.00    587.5±2.65µs        ? ?/sec    1.00    587.3±2.07µs        ? ?/sec
   from_filters                                  1.00    370.8±1.95µs        ? ?/sec    1.00    371.4±2.21µs        ? ?/sec
   intersection                                  1.00   1300.9±2.24µs        ? ?/sec    1.00   1296.2±1.31µs        ? ?/sec
   mask_consume/random                           1.00    398.1±3.25µs        ? ?/sec    1.02    404.9±5.39µs        ? ?/sec
   mask_consume/run01                            1.00   776.4±31.17µs        ? ?/sec    1.01   784.5±29.52µs        ? ?/sec
   mask_consume/run04                            1.00   177.6±12.85µs        ? ?/sec    1.04   183.9±14.31µs        ? ?/sec
   mask_consume/run128                           1.00      7.9±0.01µs        ? ?/sec    1.41     11.2±5.60µs        ? ?/sec
   mask_consume/run16                            1.00     45.8±4.53µs        ? ?/sec    1.07     49.0±6.73µs        ? ?/sec
   mask_consume/run32                            1.00     22.2±1.77µs        ? ?/sec    1.08     24.0±3.71µs        ? ?/sec
   mask_consume/run48                            1.00     15.4±0.75µs        ? ?/sec    1.18     18.2±4.71µs        ? ?/sec
   mask_consume/run64                            1.00     12.7±0.08µs        ? ?/sec    1.24     15.7±6.14µs        ? ?/sec
   mask_consume/run96                            1.00      8.8±0.04µs        ? ?/sec    1.40     12.3±5.87µs        ? ?/sec
   mask_intersection/equal/both_zero             1.00      9.0±0.02µs        ? ?/sec    1.03      9.2±0.02µs        ? ?/sec
   mask_intersection/equal/diff_mod64            2.47    110.2±0.04µs        ? ?/sec    1.00     44.6±0.16µs        ? ?/sec
   mask_intersection/equal/same_mod64            1.68     79.5±0.08µs        ? ?/sec    1.00     47.4±0.03µs        ? ?/sec
   mask_intersection/equal/same_mod64_far        1.82     86.3±0.72µs        ? ?/sec    1.00     47.5±0.02µs        ? ?/sec
   mask_intersection/tail1/both_zero             1.00     18.0±0.10µs        ? ?/sec    1.03     18.6±0.02µs        ? ?/sec
   mask_intersection/tail1/diff_mod64            3.48    118.2±0.15µs        ? ?/sec    1.00     33.9±0.02µs        ? ?/sec
   mask_intersection/tail1/same_mod64            3.67     87.3±0.10µs        ? ?/sec    1.00     23.8±0.03µs        ? ?/sec
   mask_intersection/tail1/same_mod64_far        3.64     87.1±0.09µs        ? ?/sec    1.00     23.9±0.09µs        ? ?/sec
   mask_intersection/tail1of3/both_zero          1.03     14.5±0.07µs        ? ?/sec    1.00     14.1±0.02µs        ? ?/sec
   mask_intersection/tail1of3/diff_mod64         3.64     88.4±0.07µs        ? ?/sec    1.00     24.3±0.01µs        ? ?/sec
   mask_intersection/tail1of3/same_mod64         4.13     71.5±3.62µs        ? ?/sec    1.00     17.3±0.02µs        ? ?/sec
   mask_intersection/tail1of3/same_mod64_far     3.88     68.1±0.05µs        ? ?/sec    1.00     17.6±0.02µs        ? ?/sec
   mask_intersection/tail_most/both_zero         1.44      7.3±0.01µs        ? ?/sec    1.00      5.0±0.01µs        ? ?/sec
   mask_intersection/tail_most/diff_mod64        5.56     28.3±0.02µs        ? ?/sec    1.00      5.1±0.01µs        ? ?/sec
   mask_intersection/tail_most/same_mod64        5.56     28.3±0.04µs        ? ?/sec    1.00      5.1±0.00µs        ? ?/sec
   mask_intersection/tail_most/same_mod64_far    5.57     28.4±0.08µs        ? ?/sec    1.00      5.1±0.01µs        ? ?/sec
   mask_iterate_then_consume/random              1.00    435.4±4.09µs        ? ?/sec    1.01    437.9±3.73µs        ? ?/sec
   mask_iterate_then_consume/run01               1.01   867.6±33.58µs        ? ?/sec    1.00   860.2±30.67µs        ? ?/sec
   mask_iterate_then_consume/run04               1.00   196.1±12.65µs        ? ?/sec    1.00   196.2±11.89µs        ? ?/sec
   mask_iterate_then_consume/run128              1.00      8.4±0.01µs        ? ?/sec    1.10      9.2±0.01µs        ? ?/sec
   mask_iterate_then_consume/run16               1.00     49.5±4.91µs        ? ?/sec    1.00     49.6±4.98µs        ? ?/sec
   mask_iterate_then_consume/run32               1.01     24.4±2.05µs        ? ?/sec    1.00     24.2±1.91µs        ? ?/sec
   mask_iterate_then_consume/run48               1.00     16.7±0.81µs        ? ?/sec    1.04     17.4±0.61µs        ? ?/sec
   mask_iterate_then_consume/run64               1.00     13.6±0.09µs        ? ?/sec    1.03     14.0±0.12µs        ? ?/sec
   mask_iterate_then_consume/run96               1.00      9.5±0.06µs        ? ?/sec    1.10     10.4±0.01µs        ? ?/sec
   mask_union/equal/both_zero                    1.00      9.0±0.02µs        ? ?/sec    1.03      9.3±0.02µs        ? ?/sec
   mask_union/equal/diff_mod64                   2.63    110.2±0.07µs        ? ?/sec    1.00     41.9±0.03µs        ? ?/sec
   mask_union/equal/same_mod64                   1.67     79.5±0.06µs        ? ?/sec    1.00     47.5±0.04µs        ? ?/sec
   mask_union/equal/same_mod64_far               1.65     79.8±0.10µs        ? ?/sec    1.00     48.3±1.57µs        ? ?/sec
   mask_union/tail1/both_zero                    1.00     18.0±0.09µs        ? ?/sec    1.03     18.6±0.02µs        ? ?/sec
   mask_union/tail1/diff_mod64                   3.63    117.8±0.07µs        ? ?/sec    1.00     32.5±0.10µs        ? ?/sec
   mask_union/tail1/same_mod64                   4.05     96.8±0.36µs        ? ?/sec    1.00     23.9±0.02µs        ? ?/sec
   mask_union/tail1/same_mod64_far               3.64     87.1±0.12µs        ? ?/sec    1.00     24.0±0.03µs        ? ?/sec
   mask_union/tail1of3/both_zero                 1.01     14.3±0.06µs        ? ?/sec    1.00     14.1±0.04µs        ? ?/sec
   mask_union/tail1of3/diff_mod64                3.76     88.4±0.10µs        ? ?/sec    1.00     23.5±0.02µs        ? ?/sec
   mask_union/tail1of3/same_mod64                3.91     67.5±0.06µs        ? ?/sec    1.00     17.3±0.02µs        ? ?/sec
   mask_union/tail1of3/same_mod64_far            4.08     71.4±0.84µs        ? ?/sec    1.00     17.5±0.02µs        ? ?/sec
   mask_union/tail_most/both_zero                1.44      7.3±0.03µs        ? ?/sec    1.00      5.0±0.01µs        ? ?/sec
   mask_union/tail_most/diff_mod64               5.57     28.3±0.02µs        ? ?/sec    1.00      5.1±0.01µs        ? ?/sec
   mask_union/tail_most/same_mod64               5.56     28.3±0.04µs        ? ?/sec    1.00      5.1±0.01µs        ? ?/sec
   mask_union/tail_most/same_mod64_far           5.57     28.4±0.05µs        ? ?/sec    1.00      5.1±0.01µs        ? ?/sec
   union                                         1.00   1311.6±1.42µs        ? ?/sec    1.00   1309.2±1.00µs        ? ?/sec
   ```
   
   </p>
   </details>
   
   <details><summary>Resource Usage</summary>
   
   **base (merge-base)**
   | Metric | Value |
   |--------|-------|
   | Wall time | 545.1s |
   | Peak memory | 18.7 MiB |
   | Avg memory | 16.5 MiB |
   | CPU user | 540.4s |
   | CPU sys | 0.1s |
   | Peak spill | 0 B |
   
   **branch**
   | Metric | Value |
   |--------|-------|
   | Wall time | 535.1s |
   | Peak memory | 16.9 MiB |
   | Avg memory | 15.4 MiB |
   | CPU user | 532.6s |
   | CPU sys | 0.0s |
   | Peak spill | 0 B |
   </details>
   
   
   ---
   [File an issue](https://github.com/adriangb/datafusion-benchmarking/issues) against this benchmark runner


-- 
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: github-unsubscribe@arrow.apache.org

For queries about this service, please contact Infrastructure at:
users@infra.apache.org


Re: [PR] perf(parquet): avoid redundant copies in mask-backed intersection/union [arrow-rs]

Posted by "alamb (via GitHub)" <gi...@apache.org>.
alamb commented on PR #10446:
URL: https://github.com/apache/arrow-rs/pull/10446#issuecomment-5218498440

   
   run benchmark row_selector
   
   


-- 
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: github-unsubscribe@arrow.apache.org

For queries about this service, please contact Infrastructure at:
users@infra.apache.org


Re: [PR] perf(parquet): avoid redundant copies in mask-backed intersection/union [arrow-rs]

Posted by "alamb (via GitHub)" <gi...@apache.org>.
alamb merged PR #10446:
URL: https://github.com/apache/arrow-rs/pull/10446


-- 
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: github-unsubscribe@arrow.apache.org

For queries about this service, please contact Infrastructure at:
users@infra.apache.org


Re: [PR] perf(parquet): avoid redundant copies in mask-backed intersection/union [arrow-rs]

Posted by "adriangbot (via GitHub)" <gi...@apache.org>.
adriangbot commented on PR #10446:
URL: https://github.com/apache/arrow-rs/pull/10446#issuecomment-5209030281

   🤖 Arrow criterion benchmark completed (GKE) | [trigger](https://github.com/apache/arrow-rs/pull/10446#issuecomment-5208939378)
   
   **Instance:** `c4a-highmem-16` (12 vCPU / 65 GiB)
   
   Comparing perf-uneven-mask-intersect-union (004bf28557f12708aa8509eef729d9e941ccce6d) to 3df22cd (merge-base) [diff](https://github.com/apache/arrow-rs/compare/3df22cd7c664e213ab3058d1b98db358467560d4..004bf28557f12708aa8509eef729d9e941ccce6d)
   
   <details><summary>Run configuration</summary>
   
   ```yaml
   run benchmark row_selector
   ```
   
   </details>
   
   <details><summary>CPU Details (lscpu)</summary>
   
   ```
   Architecture:                            aarch64
   CPU op-mode(s):                          64-bit
   Byte Order:                              Little Endian
   CPU(s):                                  16
   On-line CPU(s) list:                     0-15
   Vendor ID:                               ARM
   Model name:                              Neoverse-V2
   Model:                                   1
   Thread(s) per core:                      1
   Core(s) per cluster:                     16
   Socket(s):                               -
   Cluster(s):                              1
   Stepping:                                r0p1
   BogoMIPS:                                2000.00
   Flags:                                   fp asimd evtstrm aes pmull sha1 sha2 crc32 atomics fphp asimdhp cpuid asimdrdm jscvt fcma lrcpc dcpop sha3 sm3 sm4 asimddp sha512 sve asimdfhm dit uscat ilrcpc flagm sb paca pacg dcpodp sve2 sveaes svepmull svebitperm svesha3 svesm4 flagm2 frint svei8mm svebf16 i8mm bf16 dgh rng bti
   L1d cache:                               1 MiB (16 instances)
   L1i cache:                               1 MiB (16 instances)
   L2 cache:                                32 MiB (16 instances)
   L3 cache:                                80 MiB (1 instance)
   NUMA node(s):                            1
   NUMA node0 CPU(s):                       0-15
   Vulnerability Gather data sampling:      Not affected
   Vulnerability Indirect target selection: Not affected
   Vulnerability Itlb multihit:             Not affected
   Vulnerability L1tf:                      Not affected
   Vulnerability Mds:                       Not affected
   Vulnerability Meltdown:                  Not affected
   Vulnerability Mmio stale data:           Not affected
   Vulnerability Reg file data sampling:    Not affected
   Vulnerability Retbleed:                  Not affected
   Vulnerability Spec rstack overflow:      Not affected
   Vulnerability Spec store bypass:         Mitigation; Speculative Store Bypass disabled via prctl
   Vulnerability Spectre v1:                Mitigation; __user pointer sanitization
   Vulnerability Spectre v2:                Mitigation; CSV2, BHB
   Vulnerability Srbds:                     Not affected
   Vulnerability Tsa:                       Not affected
   Vulnerability Tsx async abort:           Not affected
   Vulnerability Vmscape:                   Not affected
   ```
   
   </details>
   
   <details><summary>Details</summary>
   <p>
   
   ```
   group                                         main                                   perf-uneven-mask-intersect-union
   -----                                         ----                                   --------------------------------
   and_then                                      1.02    604.2±2.69µs        ? ?/sec    1.00    592.2±2.99µs        ? ?/sec
   from_filters                                  1.00    369.0±3.46µs        ? ?/sec    1.01    371.7±4.56µs        ? ?/sec
   intersection                                  1.03   1338.0±2.50µs        ? ?/sec    1.00   1305.1±2.62µs        ? ?/sec
   mask_consume/random                           1.00    352.2±2.29µs        ? ?/sec    1.16    408.6±2.48µs        ? ?/sec
   mask_consume/run01                            1.00    684.9±4.13µs        ? ?/sec    1.14   777.9±27.37µs        ? ?/sec
   mask_consume/run04                            1.00   166.9±14.77µs        ? ?/sec    1.07   178.4±11.89µs        ? ?/sec
   mask_consume/run128                           1.07      8.5±0.02µs        ? ?/sec    1.00      7.9±0.13µs        ? ?/sec
   mask_consume/run16                            1.00     44.9±5.07µs        ? ?/sec    1.03     46.0±4.98µs        ? ?/sec
   mask_consume/run32                            1.02     22.8±1.82µs        ? ?/sec    1.00     22.5±1.92µs        ? ?/sec
   mask_consume/run48                            1.03     16.3±1.00µs        ? ?/sec    1.00     15.8±0.95µs        ? ?/sec
   mask_consume/run64                            1.01     13.0±0.28µs        ? ?/sec    1.00     12.9±0.45µs        ? ?/sec
   mask_consume/run96                            1.05      9.5±0.03µs        ? ?/sec    1.00      9.0±0.03µs        ? ?/sec
   mask_intersection/equal/both_zero                                                    1.00      9.1±0.05µs        ? ?/sec
   mask_intersection/equal/diff_mod64                                                   1.00     44.9±0.11µs        ? ?/sec
   mask_intersection/equal/same_mod64                                                   1.00     47.8±1.05µs        ? ?/sec
   mask_intersection/equal/same_mod64_far                                               1.00     47.8±0.15µs        ? ?/sec
   mask_intersection/tail1/both_zero                                                    1.00     18.9±0.03µs        ? ?/sec
   mask_intersection/tail1/diff_mod64                                                   1.00     34.4±0.04µs        ? ?/sec
   mask_intersection/tail1/same_mod64                                                   1.00     24.1±0.04µs        ? ?/sec
   mask_intersection/tail1/same_mod64_far                                               1.00     24.1±0.03µs        ? ?/sec
   mask_intersection/tail1of3/both_zero                                                 1.00     14.2±0.02µs        ? ?/sec
   mask_intersection/tail1of3/diff_mod64                                                1.00     24.4±0.02µs        ? ?/sec
   mask_intersection/tail1of3/same_mod64                                                1.00     17.4±0.02µs        ? ?/sec
   mask_intersection/tail1of3/same_mod64_far                                            1.00     17.6±0.74µs        ? ?/sec
   mask_intersection/tail_most/both_zero                                                1.00      5.1±0.01µs        ? ?/sec
   mask_intersection/tail_most/diff_mod64                                               1.00      5.2±0.01µs        ? ?/sec
   mask_intersection/tail_most/same_mod64                                               1.00      5.1±0.01µs        ? ?/sec
   mask_intersection/tail_most/same_mod64_far                                           1.00      5.2±0.01µs        ? ?/sec
   mask_iterate_then_consume/random              1.00    389.0±2.38µs        ? ?/sec    1.17    456.0±2.56µs        ? ?/sec
   mask_iterate_then_consume/run01               1.00   783.6±15.31µs        ? ?/sec    1.14   896.5±29.69µs        ? ?/sec
   mask_iterate_then_consume/run04               1.00   184.8±15.56µs        ? ?/sec    1.07   196.8±11.18µs        ? ?/sec
   mask_iterate_then_consume/run128              1.07      9.0±0.03µs        ? ?/sec    1.00      8.4±0.12µs        ? ?/sec
   mask_iterate_then_consume/run16               1.00     48.6±5.11µs        ? ?/sec    1.01     49.1±4.60µs        ? ?/sec
   mask_iterate_then_consume/run32               1.02     24.7±1.95µs        ? ?/sec    1.00     24.1±1.77µs        ? ?/sec
   mask_iterate_then_consume/run48               1.03     17.5±1.03µs        ? ?/sec    1.00     17.0±0.93µs        ? ?/sec
   mask_iterate_then_consume/run64               1.03     14.1±0.33µs        ? ?/sec    1.00     13.7±0.26µs        ? ?/sec
   mask_iterate_then_consume/run96               1.05     10.1±0.02µs        ? ?/sec    1.00      9.6±0.11µs        ? ?/sec
   mask_union/equal/both_zero                                                           1.00      9.2±0.03µs        ? ?/sec
   mask_union/equal/diff_mod64                                                          1.00     41.9±0.05µs        ? ?/sec
   mask_union/equal/same_mod64                                                          1.00     48.5±3.90µs        ? ?/sec
   mask_union/equal/same_mod64_far                                                      1.00     47.8±0.14µs        ? ?/sec
   mask_union/tail1/both_zero                                                           1.00     18.9±0.03µs        ? ?/sec
   mask_union/tail1/diff_mod64                                                          1.00     33.2±1.25µs        ? ?/sec
   mask_union/tail1/same_mod64                                                          1.00     24.0±0.06µs        ? ?/sec
   mask_union/tail1/same_mod64_far                                                      1.00     24.1±0.03µs        ? ?/sec
   mask_union/tail1of3/both_zero                                                        1.00     14.1±0.03µs        ? ?/sec
   mask_union/tail1of3/diff_mod64                                                       1.00     23.5±0.03µs        ? ?/sec
   mask_union/tail1of3/same_mod64                                                       1.00     17.3±0.02µs        ? ?/sec
   mask_union/tail1of3/same_mod64_far                                                   1.00     17.5±0.02µs        ? ?/sec
   mask_union/tail_most/both_zero                                                       1.00      5.1±0.01µs        ? ?/sec
   mask_union/tail_most/diff_mod64                                                      1.00      5.2±0.02µs        ? ?/sec
   mask_union/tail_most/same_mod64                                                      1.00      5.2±0.01µs        ? ?/sec
   mask_union/tail_most/same_mod64_far                                                  1.00      5.2±0.01µs        ? ?/sec
   union                                         1.08   1420.0±2.45µs        ? ?/sec    1.00   1314.8±1.72µs        ? ?/sec
   ```
   
   </p>
   </details>
   
   <details><summary>Resource Usage</summary>
   
   **base (merge-base)**
   | Metric | Value |
   |--------|-------|
   | Wall time | 235.1s |
   | Peak memory | 14.6 MiB |
   | Avg memory | 13.7 MiB |
   | CPU user | 230.0s |
   | CPU sys | 0.0s |
   | Peak spill | 0 B |
   
   **branch**
   | Metric | Value |
   |--------|-------|
   | Wall time | 535.1s |
   | Peak memory | 16.9 MiB |
   | Avg memory | 15.5 MiB |
   | CPU user | 532.6s |
   | CPU sys | 0.1s |
   | Peak spill | 0 B |
   </details>
   
   
   ---
   [File an issue](https://github.com/adriangb/datafusion-benchmarking/issues) against this benchmark runner


-- 
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: github-unsubscribe@arrow.apache.org

For queries about this service, please contact Infrastructure at:
users@infra.apache.org


Re: [PR] perf(parquet): avoid redundant copies in mask-backed intersection/union [arrow-rs]

Posted by "hhhizzz (via GitHub)" <gi...@apache.org>.
hhhizzz commented on code in PR #10446:
URL: https://github.com/apache/arrow-rs/pull/10446#discussion_r3725499778


##########
parquet/src/arrow/arrow_reader/selection/algebra.rs:
##########
@@ -825,4 +861,129 @@ mod tests {
         let bits: Vec<bool> = (0..5).map(|i| r_mask.value(i)).collect();
         assert_eq!(bits, vec![true, true, false, false, true]);
     }
+
+    /// Expected result of combining two masks of possibly differing lengths:
+    /// `op` over the common prefix, then the longer side's tail unchanged.
+    fn expected_combined(l: &[bool], r: &[bool], op: fn(bool, bool) -> bool) -> Vec<bool> {
+        let common = l.len().min(r.len());
+        let longer = if l.len() > r.len() { l } else { r };
+        (0..common)
+            .map(|i| op(l[i], r[i]))
+            .chain(longer[common..].iter().copied())
+            .collect()
+    }
+
+    fn assert_mask_eq(actual: &BooleanBuffer, expected: &[bool], context: &str) {
+        assert_eq!(actual.len(), expected.len(), "{context}: length");
+        let actual: Vec<bool> = actual.iter().collect();
+        assert_eq!(actual, expected, "{context}");
+    }
+
+    #[test]
+    fn test_mask_algebra_with_offsets() {
+        // Offsets and lengths that are not byte (or word) aligned on either side,
+        // so the common prefix can start and end mid byte. Covers both the equal
+        // and uneven length paths.
+        let base: Vec<bool> = (0..600).map(|i| i % 7 == 0 || i % 3 == 1).collect();
+        let other: Vec<bool> = (0..600).map(|i| i % 5 == 2 || i % 11 == 4).collect();
+        let base = BooleanBuffer::from(base);
+        let other = BooleanBuffer::from(other);
+
+        for l_offset in [0, 1, 5, 8, 13, 64, 67] {
+            for r_offset in [0, 1, 3, 8, 60, 64, 70] {
+                for (l_len, r_len) in [
+                    (0, 9),
+                    (9, 0),
+                    (1, 200),
+                    (200, 1),
+                    (63, 130),
+                    (321, 65),
+                    (0, 0),
+                    (1, 1),
+                    (63, 63),
+                    (64, 64),
+                    (200, 200),
+                    (321, 321),
+                ] {
+                    let l = base.slice(l_offset, l_len);
+                    let r = other.slice(r_offset, r_len);
+                    let l_bits: Vec<bool> = l.iter().collect();
+                    let r_bits: Vec<bool> = r.iter().collect();
+                    let context =
+                        format!("l_offset={l_offset} r_offset={r_offset} lens=({l_len},{r_len})");
+
+                    assert_mask_eq(
+                        &intersect_masks(&l, &r),
+                        &expected_combined(&l_bits, &r_bits, |a, b| a && b),
+                        &format!("intersect {context}"),
+                    );
+                    assert_mask_eq(
+                        &union_masks(&l, &r),
+                        &expected_combined(&l_bits, &r_bits, |a, b| a || b),
+                        &format!("union {context}"),
+                    );
+                }
+            }
+        }
+    }
+
+    #[test]
+    fn test_mask_algebra_does_not_retain_backing_buffer() {
+        // A short slice of a long mask must not keep the long allocation alive,
+        // including when the other operand is empty and contributes nothing.
+        let long = BooleanBuffer::from((0..80_000).map(|i| i % 3 == 0).collect::<Vec<bool>>());
+        assert!(long.inner().len() >= 10_000);
+
+        for (l, r) in [
+            (long.slice(5, 40), BooleanBuffer::new_unset(0)),
+            (long.slice(5, 40), BooleanBuffer::new_set(7)),
+            (BooleanBuffer::new_set(7), long.slice(5, 40)),
+        ] {
+            for combined in [intersect_masks(&l, &r), union_masks(&l, &r)] {
+                assert!(
+                    combined.inner().len() <= 16,

Review Comment:
   I don't think `len()` fully verifies the property stated by this test. A shallow `Buffer::slice_with_length` can expose a small logical length while still retaining the original large allocation through its `Arc`, so that regression could pass this assertion.
   
   Could we compare the backing capacity instead, for example:
   
       assert!(
           combined.inner().capacity() < long.inner().capacity(),
           "result retained the original backing allocation"
       );
   
   The current implementation does make a compact copy; this would ensure the test actually protects that memory-retention property.



##########
parquet/src/arrow/arrow_reader/selection/algebra.rs:
##########
@@ -269,39 +269,75 @@ pub(super) fn union_row_selections(left: &[RowSelector], right: &[RowSelector])
 /// Bitwise AND of two mask-backed selections. Longer side's tail passes through.
 pub(super) fn intersect_masks(l: &BooleanBuffer, r: &BooleanBuffer) -> BooleanBuffer {
     if l.len() == r.len() {
-        return l & r;
-    }
-    let common = l.len().min(r.len());
-    let head = &l.slice(0, common) & &r.slice(0, common);
-    let (longer, longer_len) = if l.len() > r.len() {
-        (l, l.len())
-    } else {
-        (r, r.len())
-    };
-    let tail = longer.slice(common, longer_len - common);
-    let mut builder = BooleanBufferBuilder::new(longer_len);
-    builder.append_buffer(&head);
-    builder.append_buffer(&tail);
-    builder.finish()
+        return combine_equal_length_masks(l, r, |a, b| a & b);
+    }
+    combine_unequal_length_masks(l, r, |a, b| a & b)
 }
 
 /// Bitwise OR of two mask-backed selections. Longer side's tail passes through.
 pub(super) fn union_masks(l: &BooleanBuffer, r: &BooleanBuffer) -> BooleanBuffer {
     if l.len() == r.len() {
-        return l | r;
-    }
-    let common = l.len().min(r.len());
-    let head = &l.slice(0, common) | &r.slice(0, common);
-    let (longer, longer_len) = if l.len() > r.len() {
-        (l, l.len())
-    } else {
-        (r, r.len())
-    };
-    let tail = longer.slice(common, longer_len - common);
-    let mut builder = BooleanBufferBuilder::new(longer_len);
-    builder.append_buffer(&head);
-    builder.append_buffer(&tail);
-    builder.finish()
+        return combine_equal_length_masks(l, r, |a, b| a | b);
+    }
+    combine_unequal_length_masks(l, r, |a, b| a | b)
+}
+
+/// Combines two masks of equal length with the bitwise operation `op`.
+///
+/// `BitAnd`/`BitOr` on `&BooleanBuffer` normalise the result to a zero bit offset,
+/// which costs a second allocation and a shifting copy of the whole mask when the
+/// operands are not byte aligned. Building the buffer directly keeps the offset,

Review Comment:
   Could we narrow this condition? “When the operands are not byte aligned” is too broad: `(3,5)` is also non-byte-aligned, but because the operands have different mod-64 alignments, `from_bitwise_binary_op` takes the shifting fallback and returns an offset-zero result, so the old wrapper does not perform an additional normalization copy.
   
   Perhaps:
   
       which costs a second allocation and a shifting copy when both operands
       share the same non-zero sub-64-bit alignment, causing
       `from_bitwise_binary_op` to return a non-zero-offset result.



-- 
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: github-unsubscribe@arrow.apache.org

For queries about this service, please contact Infrastructure at:
users@infra.apache.org


Re: [PR] perf(parquet): avoid redundant copies in mask-backed intersection/union [arrow-rs]

Posted by "haohuaijin (via GitHub)" <gi...@apache.org>.
haohuaijin commented on PR #10446:
URL: https://github.com/apache/arrow-rs/pull/10446#issuecomment-5225185097

   run benchmark row_selector


-- 
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: github-unsubscribe@arrow.apache.org

For queries about this service, please contact Infrastructure at:
users@infra.apache.org


Re: [PR] perf(parquet): avoid redundant copies in mask-backed intersection/union [arrow-rs]

Posted by "alamb (via GitHub)" <gi...@apache.org>.
alamb commented on PR #10446:
URL: https://github.com/apache/arrow-rs/pull/10446#issuecomment-5295585329

   Thanks @haohuaijin and @hhhizzz 


-- 
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: github-unsubscribe@arrow.apache.org

For queries about this service, please contact Infrastructure at:
users@infra.apache.org


Re: [PR] perf(parquet): avoid redundant copies in mask-backed intersection/union [arrow-rs]

Posted by "haohuaijin (via GitHub)" <gi...@apache.org>.
haohuaijin commented on code in PR #10446:
URL: https://github.com/apache/arrow-rs/pull/10446#discussion_r3730182266


##########
parquet/src/arrow/arrow_reader/selection/algebra.rs:
##########
@@ -825,4 +861,129 @@ mod tests {
         let bits: Vec<bool> = (0..5).map(|i| r_mask.value(i)).collect();
         assert_eq!(bits, vec![true, true, false, false, true]);
     }
+
+    /// Expected result of combining two masks of possibly differing lengths:
+    /// `op` over the common prefix, then the longer side's tail unchanged.
+    fn expected_combined(l: &[bool], r: &[bool], op: fn(bool, bool) -> bool) -> Vec<bool> {
+        let common = l.len().min(r.len());
+        let longer = if l.len() > r.len() { l } else { r };
+        (0..common)
+            .map(|i| op(l[i], r[i]))
+            .chain(longer[common..].iter().copied())
+            .collect()
+    }
+
+    fn assert_mask_eq(actual: &BooleanBuffer, expected: &[bool], context: &str) {
+        assert_eq!(actual.len(), expected.len(), "{context}: length");
+        let actual: Vec<bool> = actual.iter().collect();
+        assert_eq!(actual, expected, "{context}");
+    }
+
+    #[test]
+    fn test_mask_algebra_with_offsets() {
+        // Offsets and lengths that are not byte (or word) aligned on either side,
+        // so the common prefix can start and end mid byte. Covers both the equal
+        // and uneven length paths.
+        let base: Vec<bool> = (0..600).map(|i| i % 7 == 0 || i % 3 == 1).collect();
+        let other: Vec<bool> = (0..600).map(|i| i % 5 == 2 || i % 11 == 4).collect();
+        let base = BooleanBuffer::from(base);
+        let other = BooleanBuffer::from(other);
+
+        for l_offset in [0, 1, 5, 8, 13, 64, 67] {
+            for r_offset in [0, 1, 3, 8, 60, 64, 70] {
+                for (l_len, r_len) in [
+                    (0, 9),
+                    (9, 0),
+                    (1, 200),
+                    (200, 1),
+                    (63, 130),
+                    (321, 65),
+                    (0, 0),
+                    (1, 1),
+                    (63, 63),
+                    (64, 64),
+                    (200, 200),
+                    (321, 321),
+                ] {
+                    let l = base.slice(l_offset, l_len);
+                    let r = other.slice(r_offset, r_len);
+                    let l_bits: Vec<bool> = l.iter().collect();
+                    let r_bits: Vec<bool> = r.iter().collect();
+                    let context =
+                        format!("l_offset={l_offset} r_offset={r_offset} lens=({l_len},{r_len})");
+
+                    assert_mask_eq(
+                        &intersect_masks(&l, &r),
+                        &expected_combined(&l_bits, &r_bits, |a, b| a && b),
+                        &format!("intersect {context}"),
+                    );
+                    assert_mask_eq(
+                        &union_masks(&l, &r),
+                        &expected_combined(&l_bits, &r_bits, |a, b| a || b),
+                        &format!("union {context}"),
+                    );
+                }
+            }
+        }
+    }
+
+    #[test]
+    fn test_mask_algebra_does_not_retain_backing_buffer() {
+        // A short slice of a long mask must not keep the long allocation alive,
+        // including when the other operand is empty and contributes nothing.
+        let long = BooleanBuffer::from((0..80_000).map(|i| i % 3 == 0).collect::<Vec<bool>>());
+        assert!(long.inner().len() >= 10_000);
+
+        for (l, r) in [
+            (long.slice(5, 40), BooleanBuffer::new_unset(0)),
+            (long.slice(5, 40), BooleanBuffer::new_set(7)),
+            (BooleanBuffer::new_set(7), long.slice(5, 40)),
+        ] {
+            for combined in [intersect_masks(&l, &r), union_masks(&l, &r)] {
+                assert!(
+                    combined.inner().len() <= 16,

Review Comment:
   apply in [fae46dd](https://github.com/apache/arrow-rs/pull/10446/commits/fae46dde05e81859d0b40623d54623ce95107217)



##########
parquet/src/arrow/arrow_reader/selection/algebra.rs:
##########
@@ -269,39 +269,75 @@ pub(super) fn union_row_selections(left: &[RowSelector], right: &[RowSelector])
 /// Bitwise AND of two mask-backed selections. Longer side's tail passes through.
 pub(super) fn intersect_masks(l: &BooleanBuffer, r: &BooleanBuffer) -> BooleanBuffer {
     if l.len() == r.len() {
-        return l & r;
-    }
-    let common = l.len().min(r.len());
-    let head = &l.slice(0, common) & &r.slice(0, common);
-    let (longer, longer_len) = if l.len() > r.len() {
-        (l, l.len())
-    } else {
-        (r, r.len())
-    };
-    let tail = longer.slice(common, longer_len - common);
-    let mut builder = BooleanBufferBuilder::new(longer_len);
-    builder.append_buffer(&head);
-    builder.append_buffer(&tail);
-    builder.finish()
+        return combine_equal_length_masks(l, r, |a, b| a & b);
+    }
+    combine_unequal_length_masks(l, r, |a, b| a & b)
 }
 
 /// Bitwise OR of two mask-backed selections. Longer side's tail passes through.
 pub(super) fn union_masks(l: &BooleanBuffer, r: &BooleanBuffer) -> BooleanBuffer {
     if l.len() == r.len() {
-        return l | r;
-    }
-    let common = l.len().min(r.len());
-    let head = &l.slice(0, common) | &r.slice(0, common);
-    let (longer, longer_len) = if l.len() > r.len() {
-        (l, l.len())
-    } else {
-        (r, r.len())
-    };
-    let tail = longer.slice(common, longer_len - common);
-    let mut builder = BooleanBufferBuilder::new(longer_len);
-    builder.append_buffer(&head);
-    builder.append_buffer(&tail);
-    builder.finish()
+        return combine_equal_length_masks(l, r, |a, b| a | b);
+    }
+    combine_unequal_length_masks(l, r, |a, b| a | b)
+}
+
+/// Combines two masks of equal length with the bitwise operation `op`.
+///
+/// `BitAnd`/`BitOr` on `&BooleanBuffer` normalise the result to a zero bit offset,
+/// which costs a second allocation and a shifting copy of the whole mask when the
+/// operands are not byte aligned. Building the buffer directly keeps the offset,

Review Comment:
   apply in [fae46dd](https://github.com/apache/arrow-rs/pull/10446/commits/fae46dde05e81859d0b40623d54623ce95107217)



-- 
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: github-unsubscribe@arrow.apache.org

For queries about this service, please contact Infrastructure at:
users@infra.apache.org


Re: [PR] perf(parquet): avoid redundant copies in mask-backed intersection/union [arrow-rs]

Posted by "alamb (via GitHub)" <gi...@apache.org>.
alamb commented on PR #10446:
URL: https://github.com/apache/arrow-rs/pull/10446#issuecomment-5218496827

   > split the benchmark to #10574 for easy compare in ci, cc @alamb
   
   Thank you -- I merged it in and merged this PR up from main Rerunning tests now


-- 
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: github-unsubscribe@arrow.apache.org

For queries about this service, please contact Infrastructure at:
users@infra.apache.org


Re: [PR] perf(parquet): avoid redundant copies in mask-backed intersection/union [arrow-rs]

Posted by "hhhizzz (via GitHub)" <gi...@apache.org>.
hhhizzz commented on PR #10446:
URL: https://github.com/apache/arrow-rs/pull/10446#issuecomment-5296017303

   > Looks good to me @haohuaijin
   > 
   > Thank you
   > 
   > @hhhizzz does this PR look ready to merge to you too?
   
   Sorry I just found I missed the message, the PR looks good to me, thank you! 


-- 
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: github-unsubscribe@arrow.apache.org

For queries about this service, please contact Infrastructure at:
users@infra.apache.org


Re: [PR] perf(parquet): avoid redundant copies in mask-backed intersection/union [arrow-rs]

Posted by "adriangbot (via GitHub)" <gi...@apache.org>.
adriangbot commented on PR #10446:
URL: https://github.com/apache/arrow-rs/pull/10446#issuecomment-5225192606

   🤖 Arrow criterion benchmark running (GKE) | [trigger](https://github.com/apache/arrow-rs/pull/10446#issuecomment-5225185097)
   **Instance:** `c4a-highmem-16` (12 vCPU / 65 GiB) | `Linux bench-c5225185097-1500-gdw9g 6.12.85+ #1 SMP Wed Jun 17 20:31:55 UTC 2026 aarch64 GNU/Linux`
   <details><summary>CPU Details (lscpu)</summary>
   
   ```
   Architecture:                            aarch64
   CPU op-mode(s):                          64-bit
   Byte Order:                              Little Endian
   CPU(s):                                  16
   On-line CPU(s) list:                     0-15
   Vendor ID:                               ARM
   Model name:                              Neoverse-V2
   Model:                                   1
   Thread(s) per core:                      1
   Core(s) per cluster:                     16
   Socket(s):                               -
   Cluster(s):                              1
   Stepping:                                r0p1
   BogoMIPS:                                2000.00
   Flags:                                   fp asimd evtstrm aes pmull sha1 sha2 crc32 atomics fphp asimdhp cpuid asimdrdm jscvt fcma lrcpc dcpop sha3 sm3 sm4 asimddp sha512 sve asimdfhm dit uscat ilrcpc flagm sb paca pacg dcpodp sve2 sveaes svepmull svebitperm svesha3 svesm4 flagm2 frint svei8mm svebf16 i8mm bf16 dgh rng bti
   L1d cache:                               1 MiB (16 instances)
   L1i cache:                               1 MiB (16 instances)
   L2 cache:                                32 MiB (16 instances)
   L3 cache:                                80 MiB (1 instance)
   NUMA node(s):                            1
   NUMA node0 CPU(s):                       0-15
   Vulnerability Gather data sampling:      Not affected
   Vulnerability Indirect target selection: Not affected
   Vulnerability Itlb multihit:             Not affected
   Vulnerability L1tf:                      Not affected
   Vulnerability Mds:                       Not affected
   Vulnerability Meltdown:                  Not affected
   Vulnerability Mmio stale data:           Not affected
   Vulnerability Reg file data sampling:    Not affected
   Vulnerability Retbleed:                  Not affected
   Vulnerability Spec rstack overflow:      Not affected
   Vulnerability Spec store bypass:         Mitigation; Speculative Store Bypass disabled via prctl
   Vulnerability Spectre v1:                Mitigation; __user pointer sanitization
   Vulnerability Spectre v2:                Mitigation; CSV2, BHB
   Vulnerability Srbds:                     Not affected
   Vulnerability Tsa:                       Not affected
   Vulnerability Tsx async abort:           Not affected
   Vulnerability Vmscape:                   Not affected
   ```
   
   </details>
   
   Comparing perf-uneven-mask-intersect-union (635c740cbe789a483a2659d74f75a3892b22f39d) to 3e6bd62 (merge-base) [diff](https://github.com/apache/arrow-rs/compare/3e6bd627c7b6d0dcda8aeb0a6efc829508177d4f..635c740cbe789a483a2659d74f75a3892b22f39d)
   
   <details><summary>Run configuration</summary>
   
   ```yaml
   run benchmark row_selector
   ```
   
   </details>
   
   BENCH_COMMAND=cargo bench --features=arrow,async,test_common,experimental,object_store --bench row_selector
   Results will be posted here when complete
   
   ---
   [File an issue](https://github.com/adriangb/datafusion-benchmarking/issues) against this benchmark runner


-- 
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: github-unsubscribe@arrow.apache.org

For queries about this service, please contact Infrastructure at:
users@infra.apache.org


Re: [PR] perf(parquet): avoid redundant copies in mask-backed intersection/union [arrow-rs]

Posted by "adriangbot (via GitHub)" <gi...@apache.org>.
adriangbot commented on PR #10446:
URL: https://github.com/apache/arrow-rs/pull/10446#issuecomment-5208951714

   🤖 Arrow criterion benchmark running (GKE) | [trigger](https://github.com/apache/arrow-rs/pull/10446#issuecomment-5208939378)
   **Instance:** `c4a-highmem-16` (12 vCPU / 65 GiB) | `Linux bench-c5208939378-1492-rjxhc 6.12.85+ #1 SMP Wed Jun 17 20:31:55 UTC 2026 aarch64 GNU/Linux`
   <details><summary>CPU Details (lscpu)</summary>
   
   ```
   Architecture:                            aarch64
   CPU op-mode(s):                          64-bit
   Byte Order:                              Little Endian
   CPU(s):                                  16
   On-line CPU(s) list:                     0-15
   Vendor ID:                               ARM
   Model name:                              Neoverse-V2
   Model:                                   1
   Thread(s) per core:                      1
   Core(s) per cluster:                     16
   Socket(s):                               -
   Cluster(s):                              1
   Stepping:                                r0p1
   BogoMIPS:                                2000.00
   Flags:                                   fp asimd evtstrm aes pmull sha1 sha2 crc32 atomics fphp asimdhp cpuid asimdrdm jscvt fcma lrcpc dcpop sha3 sm3 sm4 asimddp sha512 sve asimdfhm dit uscat ilrcpc flagm sb paca pacg dcpodp sve2 sveaes svepmull svebitperm svesha3 svesm4 flagm2 frint svei8mm svebf16 i8mm bf16 dgh rng bti
   L1d cache:                               1 MiB (16 instances)
   L1i cache:                               1 MiB (16 instances)
   L2 cache:                                32 MiB (16 instances)
   L3 cache:                                80 MiB (1 instance)
   NUMA node(s):                            1
   NUMA node0 CPU(s):                       0-15
   Vulnerability Gather data sampling:      Not affected
   Vulnerability Indirect target selection: Not affected
   Vulnerability Itlb multihit:             Not affected
   Vulnerability L1tf:                      Not affected
   Vulnerability Mds:                       Not affected
   Vulnerability Meltdown:                  Not affected
   Vulnerability Mmio stale data:           Not affected
   Vulnerability Reg file data sampling:    Not affected
   Vulnerability Retbleed:                  Not affected
   Vulnerability Spec rstack overflow:      Not affected
   Vulnerability Spec store bypass:         Mitigation; Speculative Store Bypass disabled via prctl
   Vulnerability Spectre v1:                Mitigation; __user pointer sanitization
   Vulnerability Spectre v2:                Mitigation; CSV2, BHB
   Vulnerability Srbds:                     Not affected
   Vulnerability Tsa:                       Not affected
   Vulnerability Tsx async abort:           Not affected
   Vulnerability Vmscape:                   Not affected
   ```
   
   </details>
   
   Comparing perf-uneven-mask-intersect-union (004bf28557f12708aa8509eef729d9e941ccce6d) to 3df22cd (merge-base) [diff](https://github.com/apache/arrow-rs/compare/3df22cd7c664e213ab3058d1b98db358467560d4..004bf28557f12708aa8509eef729d9e941ccce6d)
   
   <details><summary>Run configuration</summary>
   
   ```yaml
   run benchmark row_selector
   ```
   
   </details>
   
   BENCH_COMMAND=cargo bench --features=arrow,async,test_common,experimental,object_store --bench row_selector
   Results will be posted here when complete
   
   ---
   [File an issue](https://github.com/adriangb/datafusion-benchmarking/issues) against this benchmark runner


-- 
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: github-unsubscribe@arrow.apache.org

For queries about this service, please contact Infrastructure at:
users@infra.apache.org


Re: [PR] perf(parquet): avoid redundant copies in mask-backed intersection/union [arrow-rs]

Posted by "alamb (via GitHub)" <gi...@apache.org>.
alamb commented on PR #10446:
URL: https://github.com/apache/arrow-rs/pull/10446#issuecomment-5208939378

   run benchmark row_selector


-- 
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: github-unsubscribe@arrow.apache.org

For queries about this service, please contact Infrastructure at:
users@infra.apache.org