Lots of code duplication in array_functions (array_replace_all, array_replace_n, array_replace, etc)

[alamb]

Describe the bug

There is a significant amount of code generated for array functions.

This both bloats binaries built with DataFusion as well as makes compile times slow.

To Reproduce

cd datafusion/datafusion-cli
cargo bloat

 File  .text     Size                    Crate Name
 0.1%   0.2% 151.2KiB datafusion_physical_expr datafusion_physical_expr::array_expressions::array_replace_all
 0.1%   0.2% 151.2KiB datafusion_physical_expr datafusion_physical_expr::array_expressions::array_replace_n
 0.1%   0.2% 151.2KiB datafusion_physical_expr datafusion_physical_expr::array_expressions::array_replace
 0.1%   0.2% 150.3KiB                  parquet brotli::enc::prior_eval::PriorEval<Alloc>::update_cost_base
 0.1%   0.2% 124.6KiB datafusion_physical_expr datafusion_physical_expr::array_expressions::array_repeat
 0.1%   0.2% 121.5KiB                   blake2 blake2::Blake2bVarCore::compress
 0.0%   0.1%  81.5KiB                   blake2 blake2::Blake2sVarCore::compress
 0.0%   0.1%  73.2KiB                   blake3 blake3::portable::compress_in_place
 0.0%   0.1%  65.2KiB                chrono_tz <chrono_tz::timezones::Tz as chrono_tz::timezone_impl::TimeSpans>::timespans
 0.0%   0.1%  61.1KiB                sqlparser <sqlparser::ast::Statement as core::fmt::Display>::fmt
 0.0%   0.1%  61.0KiB datafusion_physical_expr datafusion_physical_expr::array_expressions::array_append
 0.0%   0.1%  61.0KiB datafusion_physical_expr datafusion_physical_expr::array_expressions::array_prepend
 0.0%   0.1%  60.5KiB                       h2 h2::codec::framed_read::decode_frame
 0.0%   0.1%  59.3KiB               datafusion datafusion::physical_planner::DefaultPhysicalPlanner::create_initial_plan::{{closure}}
 0.0%   0.1%  56.4KiB datafusion_physical_expr datafusion_physical_expr::array_expressions::array_remove_all
 0.0%   0.1%  56.4KiB datafusion_physical_expr datafusion_physical_expr::array_expressions::array_remove_n
 0.0%   0.1%  56.4KiB datafusion_physical_expr datafusion_physical_expr::array_expressions::array_remove
 0.0%   0.1%  52.4KiB                       h2 h2::frame::headers::HeaderBlock::load::{{closure}}
 0.0%   0.1%  51.4KiB     datafusion_optimizer <datafusion_optimizer::simplify_expressions::expr_simplifier::Simplifier<S> as datafusion_common::tree_node::...
 0.0%   0.1%  48.9KiB datafusion_physical_expr datafusion_physical_expr::datetime_expressions::date_part
35.4%  97.6%  67.1MiB                          And 290367 smaller methods. Use -n N to show more.
36.3% 100.0%  68.7MiB                          .text section size, the file size is 189.3MiB

Expected behavior

I would like the array_replace_all, array_replace_n, array_replace functions to be implemented in terms of arrow kernels (such as eq, and take) and manipulations of offset buffers rather than directly creating new lists.

For example, the large macro expansion here:
https://github.com/apache/arrow-datafusion/blob/bb1d7f9343532d5fa8df871ff42000fbe836d7d7/datafusion/physical-expr/src/array_expressions.rs#L1431-L1437

I believe generates a bunch of specialized code for each different list element data type 😢

Additional context

No response

[alamb]

@jayzhan211 here is another one for you to consider

[jayzhan211]

Since this issue is not closed maybe we can extend this to all others array_function, lazy to open issue for each one :)

• array_replace Minor: Support nulls in array_replace, avoid a copy #8054
• array_repeat Replace macro with function for array_repeat #8071
• array_append/prepend rewrite array_append/array_prepend to remove deplicate codes  #8108
• array_remove Replace macro with function for array_remove #8106
• array_positions Replace macro with function for array_position and array_positions #8170

sorted by the size of cargo bloat

[Veeupup]

@jayzhan211 Thanks for your kind advice! I'll try array_append/prepend first!

It seems that the above functions have been all implemented.

[alamb]

Thank you both 🙏

[jayzhan211]

@jayzhan211 Thanks for your kind advice! I'll try array_append/prepend first!

It seems that the above functions have been all implemented.

Yeah, all implemented but need to change to general type approach without downcast on each data type. See #8050 #8054 and #8071

[alamb]

I think there are still several examples of macros that could/should be functions:

• array_remove: https://github.com/apache/arrow-datafusion/blob/724bafd4de98eff8d6ffd67942d29d0f9faf2aa3/datafusion/physical-expr/src/array_expressions.rs#L1131-L1202
• array_positions: https://github.com/apache/arrow-datafusion/blob/724bafd4de98eff8d6ffd67942d29d0f9faf2aa3/datafusion/physical-expr/src/array_expressions.rs#L1066
• array_repeat: https://github.com/apache/arrow-datafusion/blob/724bafd4de98eff8d6ffd67942d29d0f9faf2aa3/datafusion/physical-expr/src/array_expressions.rs#L844-L961

In general, I think we should be aiming for the removal of macros in the array functions as the macros are unecessary, harder to maintain, and generate more code than is necessary

[Veeupup]

@alamb I'm now making code duplication in #8081 , I'll come back later to remove duplicate codes in theses functions

[jayzhan211]

Work on array_remove

[Veeupup]

I can help with array_append

[Veeupup]

and prepend seems can be done in one PR ..

[jayzhan211]

working on array_positions

[jayzhan211]

TODO:

• array_array Replace macro in array_array to remove duplicate codes #8252
• define_array_slice
• array has Replace array_has/array_has_all/array_has_any macro to remove duplicate code #8263

[alamb]

Its looking really nice @jayzhan211 -- thank you

[Veeupup]

@jayzhan211 hi, I can help with array_array

[jayzhan211]

@jayzhan211 hi, I can help with array_array

Great!

[Veeupup]

hi @jayzhan211 I'm going to work on array_has : )

[alamb]

It is great to see how we are chipping away at this project. Very nice 👍

[jayzhan211]

Work on define_array_slice

[jayzhan211]

datafusion_common::scalar::ScalarValue::iter_to_array is probably not the target function to cleanup ? Since it need to check the data types in Scalar and deal with them specifically.

[alamb]

`datafusion_common::scalar::ScalarValue::iter_to_array` is probably not the target function to cleanup ? Since it need to check the data types in Scalar and deal with them specifically.

I think macros that generate specialized for for each scalar type could potentially be replaced

https://github.com/apache/arrow-datafusion/blob/075ff3ddfc78680d5da424ed63ffea1e38a6c57d/datafusion/common/src/scalar.rs#L1371-L1468

This then makes a massive about of duplication:
https://github.com/apache/arrow-datafusion/blob/075ff3ddfc78680d5da424ed63ffea1e38a6c57d/datafusion/common/src/scalar.rs#L1544-L1765

Specifically, rather than having specialized code for each possible list element type, perhaps we could have one code that accumulated the values (perhaps recursively calling iter_to_array) and one function that computes the offsets

[alamb]

@jayzhan211 and @Weijun-H and @Veeupup your efforts appear to be paying off!

The size of the datafusion-cli binary has shrunk by 2MB (from 63MB to 61MB) since 33.0.0 🎉

Size on main after merging https://github.com/apache/arrow-datafusion/pull/8414/files

andrewlamb@Andrews-MacBook-Pro:~/Software/arrow-datafusion/datafusion-cli$ ls -l  `which datafusion-cli`
-rwxr-xr-x@ 1 andrewlamb  staff    63M Dec  5 14:07 /Users/andrewlamb/.cargo/bin/datafusion-cli*

Size of binary from 33.0.0

andrewlamb@Andrews-MacBook-Pro:~/Software/arrow-datafusion/datafusion-cli$ ls -l target/release/datafusion-cli
-rwxr-xr-x@ 1 andrewlamb  staff    61M Dec  6 16:48 target/release/datafusion-cli*

[jayzhan211]

I think we have done all the tasks in this topic