[C++][Compute] Extract preallocation logic from KernelExecutor

[asfimport]

Currently KernelExecutor handles preallocation of null bitmaps and other buffers based on simple flags on each Kernel. This is not very flexible and we end up leaving a lot of performance on the table in cases where we can preallocate but the behavior can't be captured in the available flags. For example, in the case of binary_string_join_element_wise, it would be possible to preallocate all buffers (even the character buffer) and write output into slices.

Having this as a public function would enable us to unit test it directly (currently Executors are only tested indirectly through calling of compute::Functions) and reuse it, for example to correctly preallocate a small temporary for pipelined execution

One way this could be added is as a new method on each Kernel:

// Output preallocated Datums sufficient for execution of the kernel on each ExecBatch.
// The output Datums may not be identically chunked to the input batches, for example
// kernels which support contiguous output preallocation will preallocate a single Datum
// (and can then output into slices of that Datum).
Result<std::vector<Datum>> Kernel::prepare_output(
  const Kernel*,
  KernelContext*,
  const std::vector<ExecBatch>& inputs)

Reporter: Ben Kietzman / @bkietz

Related issues:

• [C++] C++ array kernels framework and execution buildout (umbrella issue) (is a child of)
• [C++] Improve array expression and kernel evaluation performance on small inputs (relates to)
• [C++][Compute] CastFromNull does not use preallocated buffers (relates to)
• [C++] Rewrite ExecuteScalarExpression to not use ScalarExecutor (is related to)

_{Note: This issue was originally created as ARROW-13121. Please see the migration documentation for further details.}

[asfimport]

Ben Kietzman / @bkietz:
@wesm

[asfimport]

Antoine Pitrou / @pitrou:
I'd also mention that when I worked on ARROW-13042, I spent a lot of time trying to figure out which code paths exactly got executed in exec.cc and I never fully figured it out (one particularly case was implicit casting and broadcasting with a NullScalar LHS and a ChunkedArray RHS on a scalar kernel). I ended up trying to find clues in other places instead.

[asfimport]

Ben Kietzman / @bkietz:
Another point which we might like to optimize: #10550 (comment)

[github-actions]

This issue has been marked as stale because it has had no activity in the past 365 days. Please remove the stale label or comment below, or this issue will be closed in 14 days. If this improvement is still desired but has no current owner, please add the 'Status: needs champion' label.