jorgecarleitao opened a new pull request #8960:
URL: https://github.com/apache/arrow/pull/8960
This PR improves the filter kernel:
* made the filter benchmarks more realistic
* performance improved by 1.2-4x for all multi-filter operations
* performance decreased by 30% for a single-filter operation
* filter now supports all types supported by `MutableArrayData`
* removed 500 LOC
There are two novel ideas here:
1. it minimizes the number of memcopies when building the filtered array,
both for single filter and multi-filter operations.
2. for single filter operations, it leverages an iterator to create the new
array on the fly. For multi filter operations, it persists the iterator's
result in a vector and iterates over it per array.
This PR also improves the performance of `MutableArrayData` by avoiding some
bound checks via `unsafe` (properly documented).
Summary of the benchmarks:
| benchmark | variation (%) |
|-------------- | -------------- |
| filter u8 | 29.5 |
| filter u8 low selectivity | 7.3 |
| filter context u8 w NULLs | -17.5 |
| filter context u8 w NULLs high selectivity | -21.9 |
| filter context f32 high selectivity | -22.0 |
| filter context f32 | -26.8 |
| filter context string high selectivity | -27.5 |
| filter context string | -31.4 |
| filter context u8 | -40.3 |
| filter u8 high selectivity | -47.3 |
| filter context string low selectivity | -55.3 |
| filter context u8 w NULLs low selectivity | -57.7 |
| filter context f32 low selectivity | -64.8 |
| filter context u8 low selectivity | -66.0 |
| filter context u8 high selectivity | -77.2 |
Code used to benchmark:
```bash
git checkout 54da4378d138df12bd4e09a68b0f4c80218834c7
cargo bench --bench filter_kernels
git checkout mutable_filter2
cargo bench --bench filter_kernels
```
Benchmark result:
```
Compiling arrow v3.0.0-SNAPSHOT
(/Users/jorgecarleitao/projects/arrow/rust/arrow)
Finished bench [optimized] target(s) in 1m 01s
Running
/Users/jorgecarleitao/projects/arrow/rust/target/release/deps/filter_kernels-5208f9a404de52c9
Gnuplot not found, using plotters backend
filter u8 time: [512.54 us 513.43 us 514.37 us]
change: [+29.070% +29.548% +30.003%] (p = 0.00 <
0.05)
Performance has regressed.
Found 5 outliers among 100 measurements (5.00%)
3 (3.00%) high mild
2 (2.00%) high severe
filter u8 high selectivity
time: [11.494 us 11.513 us 11.532 us]
change: [-47.846% -47.337% -46.755%] (p = 0.00 <
0.05)
Performance has improved.
Found 7 outliers among 100 measurements (7.00%)
2 (2.00%) high mild
5 (5.00%) high severe
filter u8 low selectivity
time: [7.0342 us 7.0520 us 7.0693 us]
change: [+6.5543% +7.3409% +8.1080%] (p = 0.00 <
0.05)
Performance has regressed.
Found 5 outliers among 100 measurements (5.00%)
1 (1.00%) high mild
4 (4.00%) high severe
filter context u8 time: [233.81 us 234.31 us 234.93 us]
change: [-40.715% -40.329% -39.886%] (p = 0.00 <
0.05)
Performance has improved.
Found 8 outliers among 100 measurements (8.00%)
3 (3.00%) high mild
5 (5.00%) high severe
filter context u8 high selectivity
time: [4.5943 us 4.6100 us 4.6276 us]
change: [-77.449% -77.231% -77.022%] (p = 0.00 <
0.05)
Performance has improved.
Found 18 outliers among 100 measurements (18.00%)
10 (10.00%) high mild
8 (8.00%) high severe
filter context u8 low selectivity
time: [1.7582 us 1.7664 us 1.7742 us]
change: [-66.250% -65.989% -65.669%] (p = 0.00 <
0.05)
Performance has improved.
Found 2 outliers among 100 measurements (2.00%)
2 (2.00%) high severe
filter context u8 w NULLs
time: [476.99 us 477.71 us 478.44 us]
change: [-17.852% -17.457% -17.000%] (p = 0.00 <
0.05)
Performance has improved.
Found 6 outliers among 100 measurements (6.00%)
3 (3.00%) high mild
3 (3.00%) high severe
filter context u8 w NULLs high selectivity
time: [296.46 us 297.03 us 297.67 us]
change: [-22.297% -21.871% -21.393%] (p = 0.00 <
0.05)
Performance has improved.
Found 7 outliers among 100 measurements (7.00%)
3 (3.00%) high mild
4 (4.00%) high severe
filter context u8 w NULLs low selectivity
time: [2.5988 us 2.6124 us 2.6268 us]
change: [-58.065% -57.668% -57.237%] (p = 0.00 <
0.05)
Performance has improved.
Found 5 outliers among 100 measurements (5.00%)
4 (4.00%) high mild
1 (1.00%) high severe
filter context f32 time: [470.69 us 472.39 us 474.73 us]
change: [-29.574% -26.769% -24.242%] (p = 0.00 <
0.05)
Performance has improved.
Found 14 outliers among 100 measurements (14.00%)
9 (9.00%) high mild
5 (5.00%) high severe
filter context f32 high selectivity
time: [307.16 us 307.58 us 308.03 us]
change: [-22.472% -22.039% -21.532%] (p = 0.00 <
0.05)
Performance has improved.
Found 6 outliers among 100 measurements (6.00%)
2 (2.00%) high mild
4 (4.00%) high severe
filter context f32 low selectivity
time: [2.4266 us 2.4323 us 2.4384 us]
change: [-65.024% -64.764% -64.517%] (p = 0.00 <
0.05)
Performance has improved.
Found 7 outliers among 100 measurements (7.00%)
5 (5.00%) high mild
2 (2.00%) high severe
filter context string time: [645.82 us 647.32 us 649.04 us]
change: [-31.810% -31.427% -31.046%] (p = 0.00 <
0.05)
Performance has improved.
Found 11 outliers among 100 measurements (11.00%)
6 (6.00%) high mild
5 (5.00%) high severe
Benchmarking filter context string high selectivity: Warming up for 3.0000 s
Warning: Unable to complete 100 samples in 5.0s. You may wish to increase
target time to 5.2s, enable flat sampling, or reduce sample count to 60.
filter context string high selectivity
time: [999.11 us 1.0008 ms 1.0027 ms]
change: [-28.133% -27.524% -26.930%] (p = 0.00 <
0.05)
Performance has improved.
Found 11 outliers among 100 measurements (11.00%)
7 (7.00%) high mild
4 (4.00%) high severe
filter context string low selectivity
time: [3.6441 us 3.6623 us 3.6799 us]
change: [-55.650% -55.329% -55.013%] (p = 0.00 <
0.05)
Performance has improved.
Found 8 outliers among 100 measurements (8.00%)
6 (6.00%) low mild
2 (2.00%) high severe
```
----------------------------------------------------------------
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.
For queries about this service, please contact Infrastructure at:
[email protected]
