[C++] Improve kernel performance on small batches

[asfimport]

It seems that invoking some kernels on smallish batches has quite an overhead:

ArrayArrayKernel<Add, Int32Type>/32768/100                      2860 ns         2859 ns       245195 bytes_per_second=10.6727G/s items_per_second=2.86494G/s null_percent=1 size=32.768k
ArrayArrayKernel<Add, Int32Type>/32768/0                        2752 ns         2751 ns       249316 bytes_per_second=11.093G/s items_per_second=2.97775G/s null_percent=0 size=32.768k
ArrayArrayKernel<Add, Int32Type>/524288/100                    18633 ns        18630 ns        36548 bytes_per_second=26.2097G/s items_per_second=7.03561G/s null_percent=1 size=524.288k
ArrayArrayKernel<Add, Int32Type>/524288/0                      18260 ns        18257 ns        38245 bytes_per_second=26.7451G/s items_per_second=7.17933G/s null_percent=0 size=524.288k

We should investigate and try to lighten the overhead.

Reporter: Antoine Pitrou / @pitrou

Related issues:

• [C++] Improve array expression and kernel evaluation performance on small inputs (relates to)

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

[asfimport]

Antoine Pitrou / @pitrou:
cc [~frank.du]

[asfimport]

Wes McKinney / @wesm:
I haven't spent much time looking at microperformance in the kernel execution machinery. There is a separate JIRA about adding benchmarks for a no-op / no-allocation kernel so that we can measure the execution overhead more precisely.

[asfimport]

Frank Du / @JianXinD:
Hotspot for L1 size:

  48.92%  libarrow.so.200.0.0                        [.] arrow::compute::internal::applicator::ScalarBinary<arrow::Int64Type, arrow::Int64Type, arrow::Int64Type, arrow::compute::internal
   2.81%  arrow-compute-scalar-arithmetic-benchmark  [.] mpark::detail::visitation::base::make_fmatrix_impl<mpark::detail::dtor&&, mpark::detail::base<(mpark::detail::Trait)1, decltype(n
   2.66%  libc-2.31.so                               [.] malloc
   2.54%  libpthread-2.31.so                         [.] __pthread_mutex_trylock
   2.28%  libarrow.so.200.0.0                        [.] arrow::ArrayData::Slice
   1.55%  libarrow.so.200.0.0                        [.] mpark::detail::visitation::base::make_fdiagonal_impl<mpark::detail::assignment<mpark::detail::traits<decltype(nullptr), std::shar
   1.48%  libarrow.so.200.0.0                        [.] arrow::compute::KernelSignature::MatchesInputs
   1.39%  libpthread-2.31.so                         [.] __pthread_mutex_unlock
   1.33%  libarrow.so.200.0.0                        [.] arrow::compute::detail::ScalarExecutor::Execute
   1.23%  libarrow_testing.so.200.0.0                [.] std::vector<std::shared_ptr<arrow::Buffer>, std::allocator<std::shared_ptr<arrow::Buffer> > >::~vector

Hotspot for L2 size:

  78.21%  libarrow.so.200.0.0                        [.] arrow::compute::internal::applicator::ScalarBinary<arrow::Int64Type, arrow::Int64Type, arrow::Int64Type, arrow::compute::internal
   0.93%  libarrow.so.200.0.0                        [.] arrow::internal::(anonymous namespace)::BitmapOp<std::bit_and>
   0.87%  [kernel]                                   [k] mwait_idle_with_hints.constprop.0
   0.82%  libpthread-2.31.so                         [.] __pthread_mutex_trylock
   0.80%  arrow-compute-scalar-arithmetic-benchmark  [.] mpark::detail::visitation::base::make_fmatrix_impl<mpark::detail::dtor&&, mpark::detail::base<(mpark::detail::Trait)1, decltype(n
   0.73%  libc-2.31.so                               [.] malloc
   0.69%  [kernel]                                   [k] io_serial_out
   0.64%  [kernel]                                   [k] io_serial_in
   0.56%  libarrow.so.200.0.0                        [.] arrow::compute::KernelSignature::MatchesInputs
   0.54%  libarrow.so.200.0.0                        [.] arrow::compute::detail::ScalarExecutor::Execute
   0.43%  libarrow.so.200.0.0                        [.] arrow::ArrayData::Slice

Many additional overhead on benchmark itself for small batch.

 

[asfimport]

Wes McKinney / @wesm:
IMHO we should consider a slimmed down data structure for the implementation of ExecBatch that does not use arrow::util::variant, considering that we only ever will have either ArrayData or Scalar as value types. The overhead of slicing ArrayData objects is also non-trivial

[asfimport]

Frank Du / @JianXinD:
Seems most batch for ArrayData now is exactly a copy of current, worth to add a check before Slice? 

Per perf, no Slice anymore for scalar-arithmetic-benchmark, and the data improved slightly(3%)

diff --git a/cpp/src/arrow/compute/exec.cc b/cpp/src/arrow/compute/exec.cc
index 435d7dd74..7c33a7198 100644
--- a/cpp/src/arrow/compute/exec.cc
+++ b/cpp/src/arrow/compute/exec.cc
@@ -171,7 +171,12 @@ bool ExecBatchIterator::Next(ExecBatch* batch) {
     if (args_[i].is_scalar()) {
       batch->values[i] = args_[i].scalar();
     } else if (args_[i].is_array()) {
-      batch->values[i] = args_[i].array()->Slice(position_, iteration_size);
+      if (position_ || iteration_size != length_) {
+        batch->values[i] = args_[i].array()->Slice(position_, iteration_size);
+      } else {
+        batch->values[i] = args_[i].array();
+      }
     } else {
       const ChunkedArray& carr = *args_[i].chunked_array();
       const auto& chunk = carr.chunk(chunk_indexes_[i]);

[asfimport]

Wes McKinney / @wesm:
That seems like a good start. I'd like to look at writing a patch to use a simpler data structure that doesn't involve a variant nor heap-allocating ArrayData objects. See for example the PrimitiveArg data structure that is being used in the selection kernels

arrow/cpp/src/arrow/compute/kernels/util_internal.h

Line 30 in d0f3b5f

struct PrimitiveArg {

It seems like some evolved version of that which satisfies the needs of kernels would make sense.

[asfimport]

Antoine Pitrou / @pitrou:
So, on ArrayArrayKernel<Add, Int64Type>/32768/100, we've got roughly:

• 50% CPU time spent on the kernel execution itself
• 8% on FunctionExecutorImpl::BindArgs
• 13% on ScalarExecutor::SetupPreallocation (including 12% for FunctionExecutorImpl::PrepareOutput)
• 3.5% on PropagateNulls
• 2.75% on ExecBatchIterator::Next
• 8% on ~Datum (including 5% in the jemalloc deallocator)
• a ton of other smaller things