Reduce memory of concat kernel

[ritchie46]

The concat kernel concats multiple arrays to contiguous memory. It has the potential to only allocate the required memory. However for (large)-utf8 and for (large)-list it does not do so and relies on exponential allocation to get the required memory.

Precomputing the needed capacity of buffers would be faster and less memory heavy.

[Dandandan]

@ritchie46 is this closed in your eyes by #348?

[ritchie46]

I think we can apply the same logic to arrays with child data.

• list
• large-list
• struct
• dictionary

come to mind.

[jorgecarleitao]

I agree that it would be great to have a method to specify all capacities.

The required capacity is usually dependent on the problem over which MutableArrayData is used for. Therefore, I suggest that the calculation of which capacity to use to be made by the user of MutableArrayData, and not inside MutableArrayData itself.

In this context, a way to address this is to allow something like

MutableArrayData::with_capacities(capacities: Capacities);

enum Capacities {
   Binary(usize, Option<usize>),  // Binary, Utf8
   List(usize, Option<Box<Capacities>>),
   ...
}

and let MutableArrayData panic if the capacity variant is incompatible with the arrays' DataType.

This gives users the freedom to pass other capacities.

[jhorstmann]

Support for list capacities was added in #382 and #1885, adding support for at least single-level lists in the concat kernel should be relatively easy now by extending the match statement in

arrow-rs/arrow/src/compute/kernels/concat.rs

Line 96 in a0a263f

_ => MutableArrayData::new(arrays, false, capacity),