neilconway opened a new pull request, #26507: URL: https://github.com/apache/datafusion/pull/26507
## Which issue does this PR close? - Followup to #25754 ## Rationale for this change There are several places where we want to count the set bits within a certain range of indices in a bitmap: for example, to count how many non-null elements are in a given row of a list column. Previously, this was typically done by slicing the bitmap and then calling Arrow's `count_set_bits_offset`. This has a lot of per-call overhead, which can be avoided when we want to count bits repeatedly on the same bitmap (e.g., for each row in the scenario above). #25754 introduced `SetBitCounter` as a small abstraction to do this more efficiently for the `array_filter` UDF. This PR refines that API, makes it public, and uses it in several other places in DataFusion: Spark's `array_contains` and `map_from_entries` UDFs, and core's `array_compact`, `array_remove`, `inner_product`, `cosine_distance`, and `array_normalize` UDFs. Benchmarks: (x86, AMD EPYC-Milan) vector_math - inner_product/width_4/no_nulls: 1.57 ms → 175.940 µs (−88.8%) - cosine_distance/width_4/no_nulls: 1.82 ms → 390.200 µs (−78.5%) - array_normalize/width_4/no_nulls: 1.47 ms → 280.990 µs (−80.9%) - inner_product/width_4/null_elements: 2.41 ms → 451.880 µs (−81.2%) - cosine_distance/width_4/null_elements: 2.46 ms → 657.260 µs (−73.2%) - array_normalize/width_4/null_elements: 1.47 ms → 426.120 µs (−71.0%) - inner_product/width_32/no_nulls: 577.000 µs → 64.133 µs (−88.9%) - cosine_distance/width_32/no_nulls: 322.610 µs → 138.470 µs (−57.1%) - array_normalize/width_32/no_nulls: 637.830 µs → 145.690 µs (−77.2%) - inner_product/width_32/null_elements: 611.040 µs → 97.872 µs (−84.0%) - cosine_distance/width_32/null_elements: 378.080 µs → 160.790 µs (−57.5%) - array_normalize/width_32/null_elements: 598.450 µs → 157.790 µs (−73.6%) - inner_product/width_256/no_nulls: 452.730 µs → 92.799 µs (−79.5%) - cosine_distance/width_256/no_nulls: 136.570 µs → 112.350 µs (−17.7%) - array_normalize/width_256/no_nulls: 538.780 µs → 187.670 µs (−65.2%) - inner_product/width_256/null_elements: 379.930 µs → 88.551 µs (−76.7%) - cosine_distance/width_256/null_elements: 123.600 µs → 103.470 µs (−16.3%) - array_normalize/width_256/null_elements: 494.110 µs → 176.980 µs (−64.2%) array_remove (scalar needle) - array_remove_int64 size 10, rows 4000: 226.790 µs → 200.230 µs (−11.7%) - array_remove_int64 size 100, rows 10000: 1.31 ms → 1.29 ms (−2.1%) - array_remove_int64 size 500, rows 10000: 6.34 ms → 6.27 ms (−1.1%) - array_remove_n_int64 size 10, rows 4000: 244.930 µs → 208.590 µs (−14.8%) - array_remove_n_int64 size 100, rows 10000: 2.27 ms → 2.28 ms (+0.4%) - array_remove_n_int64 size 500, rows 10000: 11.34 ms → 11.30 ms (−0.3%) - array_remove_all_int64 size 10, rows 4000: 234.380 µs → 211.390 µs (−9.8%) - array_remove_all_int64 size 100, rows 10000: 3.36 ms → 3.37 ms (+0.3%) - array_remove_all_int64 size 500, rows 10000: 15.24 ms → 15.36 ms (+0.8%) - array_remove_strings size 10, rows 4000: 389.410 µs → 377.810 µs (−3.0%) - array_remove_strings size 100, rows 10000: 7.31 ms → 7.35 ms (+0.6%) - array_remove_strings size 500, rows 10000: 47.14 ms → 46.79 ms (−0.8%) - array_remove_boolean size 10, rows 4000: 314.650 µs → 274.600 µs (−12.7%) - array_remove_boolean size 100, rows 10000: 1.66 ms → 1.63 ms (−1.9%) - array_remove_boolean size 500, rows 10000: 5.13 ms → 5.10 ms (−0.5%) - array_remove_fixed_size_binary size 10, rows 4000: 391.640 µs → 346.230 µs (−11.6%) - array_remove_fixed_size_binary size 100, rows 10000: 5.80 ms → 5.71 ms (−1.5%) - array_remove_fixed_size_binary size 500, rows 10000: 68.23 ms → 68.33 ms (+0.1%) array_contains (Spark) - array_contains/list/width_4: 183.660 µs → 60.303 µs (−67.2%) - array_contains/list/width_16: 214.510 µs → 99.500 µs (−53.6%) - array_contains/list/width_128: 503.060 µs → 451.970 µs (−10.2%) - array_contains/fixed_size_list/width_16: 200.670 µs → 103.220 µs (−48.6%) map_from_entries (Spark) - map_from_entries/width_4: 2.34 ms → 2.15 ms (−8.2%) - map_from_entries/width_16: 8.58 ms → 8.31 ms (−3.1%) - map_from_entries/width_64: 34.26 ms → 33.30 ms (−2.8%) array_compact (non-primitive values) - dictionary/mixed_nulls/2048: 6.259 µs → 3.669 µs (−41.4%) - dictionary/mixed_nulls/1048576: 6.363 µs → 3.788 µs (−40.5%) - random/utf8/random_sparse: 5.977 µs → 3.324 µs (−44.4%) - random/utf8/random: 7.024 µs → 4.209 µs (−40.1%) - random/utf8/random_half: 7.049 µs → 4.276 µs (−39.3%) - random/utf8/random_dense: 4.071 µs → 1.407 µs (−65.4%) - random/utf8_view/random_sparse: 4.688 µs → 2.055 µs (−56.2%) - random/utf8_view/random: 6.596 µs → 3.954 µs (−40.1%) - random/utf8_view/random_half: 5.629 µs → 2.977 µs (−47.1%) - random/utf8_view/random_dense: 3.882 µs → 1.209 µs (−68.9%) - types/utf8/mixed: 7.634 µs → 4.906 µs (−35.7%) - nulls/utf8/clustered: 5.481 µs → 2.793 µs (−49.0%) - types/boolean/mixed: 7.367 µs → 4.714 µs (−36.0%) - types/nested/sparse: 8.943 µs → 6.175 µs (−31.0%) - types/struct_nested/sparse: 9.526 µs → 6.798 µs (−28.6%) - types/fixed_nested/sparse: 14.481 µs → 11.780 µs (−18.7%) - types/map/sparse: 12.709 µs → 10.038 µs (−21.0%) - types/run/mixed: 11.296 µs → 8.685 µs (−23.1%) - strings/utf8_long: 13.171 µs → 10.547 µs (−19.9%) - shape/utf8/width_128: 3.451 µs → 3.307 µs (−4.2%) - parent_nulls/utf8/some: 108.580 µs → 109.120 µs (+0.5%) - parent_nulls/utf8/mostly: 3.075 µs → 4.381 µs (+42.5%) - parent_nulls/nested/mostly: 12.639 µs → 13.844 µs (+9.5%) - large_list/utf8: 7.754 µs → 4.926 µs (−36.5%) - child_slice/utf8: 7.717 µs → 4.924 µs (−36.2%) - large/utf8/random_tenth: 3.77 ms → 3.12 ms (−17.1%) - large/utf8/random_half: 4.27 ms → 3.54 ms (−17.2%) - large/utf8_long/random_half: 84.19 ms → 83.72 ms (−0.6%) - binary/random_half: 10.583 µs → 7.737 µs (−26.9%) - large_binary/random_half: 10.532 µs → 8.003 µs (−24.0%) - strings/null_payload: 7.930 µs → 2.502 µs (−68.4%) - strings/null_payload_null_rows: 1.545 µs → 1.553 µs (+0.6%) array_filter (lists with NULL rows) - int32/keep50/null_rows50: 4.909 µs → 4.867 µs (−0.9%) - int32/keep50/null_rows99: 1.440 µs → 1.445 µs (+0.4%) - utf8/keep50/null_rows50: 14.942 µs → 14.110 µs (−5.6%) - utf8/keep50/null_rows99: 1.650 µs → 1.589 µs (−3.7%) - utf8_view/keep50/null_rows50: 6.849 µs → 7.428 µs (+8.5%) - utf8_view/keep50/null_rows99: 1.556 µs → 1.505 µs (−3.3%) - int32/keep50/null_rows50/hidden_storage: 7.417 µs → 7.387 µs (−0.4%) ## What changes are included in this PR? * Add benchmarks for Spark's `array_contains` and `map_from_entries` and core's `inner_product`, `cosine_distance`, and `array_normalize` * Move `SetBitCounter` to `datafusion-common`, make it public, and generalize the API * Adopt new `SetBitCounter` API in `array_remove`, `inner_product`, `cosine_distance`, and `array_normalize` core UDFs, and in `array_contains` and `map_from_entries` Spark UDFs * Build `array_compact`'s result for non-primitive values with `prepare_list_filter`, which `array_filter` already uses. This is slower when NULL list rows still store elements, which is rare but can occur (e.g., the result of `nullif`). For such inputs, `SetBitCounter` reads the validity bits for "hidden" rows, which the old loop skipped. To keep that cost down, `prepare_list_filter` now handles each run of NULL rows between two valid rows with one count and one append, instead of one per NULL row. The remaining cost shows in extreme cases: `parent_nulls/utf8/mostly` (99% of rows NULL, 256 elements each) is 42% slower and `parent_nulls/nested/mostly` is 9.5% slower. A counter that skips the words under NULL rows avoided this, but it slowed `array_filter` on lists without NULL rows by 34% on x86, so I didn't pursue it. ## What is the testing strategy for this PR? Existing tests pass; new tests added. ## Are there any user-facing changes? New public `SetBitCounter` API. -- This is an automated message from the Apache Git Service. To respond to the message, please log on to GitHub and use the URL above to go to the specific comment. To unsubscribe, e-mail: [email protected] For queries about this service, please contact Infrastructure at: [email protected] --------------------------------------------------------------------- To unsubscribe, e-mail: [email protected] For additional commands, e-mail: [email protected]
