You are viewing a plain text version of this content. The canonical link for it is here.
Posted to github@arrow.apache.org by "felipecrv (via GitHub)" <gi...@apache.org> on 2024/05/17 03:59:55 UTC

[PR] GH-39565: [C++] [arrow]

felipecrv opened a new pull request, #41700:
URL: https://github.com/apache/arrow/pull/41700

   ### Rationale for this change
   
   Concatenating a chunked array into a single array before running the `array_take` kernels is very inefficient and can lead to out-of-memory crashes.
   
   ### What changes are included in this PR?
   
    - Improvements in the dispatching logic of `TakeMetaFunction`(`"take"`) to make `"array_take"` able to have a `chunked_exec` kernel for some types
    - Implementation of kernels for `"array_take"` that can receive a `ChunkedArray` as `values` and produce an output without concatenating these chunks
   
   ### Are these changes tested?
   
   By existing tests. Some tests were added in previous PRs that introduced some of the infrastructure to support this.


-- 
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: github-unsubscribe@arrow.apache.org

For queries about this service, please contact Infrastructure at:
users@infra.apache.org


Re: [PR] GH-39565: [C++] Do not concatenate chunked values of fixed-width types to run "array_take" [arrow]

Posted by "felipecrv (via GitHub)" <gi...@apache.org>.
felipecrv commented on PR #41700:
URL: https://github.com/apache/arrow/pull/41700#issuecomment-2305885012

   > ...while still hurting it on random indices.
   
   The binary searches for chunk index are a costly part of the process that is avoided when value chunks are concatenated.
   
   I have ideas to make the search interleaved so that multiple binary searches can happen in parallel (i.e. likely sharing the same cache line accesses to make progress).


-- 
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: github-unsubscribe@arrow.apache.org

For queries about this service, please contact Infrastructure at:
users@infra.apache.org


Re: [PR] GH-39565: [C++] Do not concatenate chunked values of fixed-width types to run "array_take" [arrow]

Posted by "pitrou (via GitHub)" <gi...@apache.org>.
pitrou commented on PR #41700:
URL: https://github.com/apache/arrow/pull/41700#issuecomment-2230814917

   Ok, a first issue is that taking a chunked dictionary array crashes (are there no tests for this?):
   ```python
   >>> a1 = pa.array(["foo", "bar", "foo"]).dictionary_encode()
   >>> a2 = pa.array([None, "bar", "bar", "foo"]).dictionary_encode()
   >>> a = pa.chunked_array([a1, a2])
   >>> a.take([1,4])
   /home/antoine/arrow/dev/cpp/src/arrow/array/array_dict.cc:84:  Check failed: (data->dictionary) != (nullptr) 
   ```
   


-- 
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: github-unsubscribe@arrow.apache.org

For queries about this service, please contact Infrastructure at:
users@infra.apache.org


Re: [PR] GH-39565: [C++] Do not concatenate chunked values of fixed-width types to run "array_take" [arrow]

Posted by "felipecrv (via GitHub)" <gi...@apache.org>.
felipecrv commented on code in PR #41700:
URL: https://github.com/apache/arrow/pull/41700#discussion_r1723524869


##########
cpp/src/arrow/compute/kernels/vector_selection_take_internal.cc:
##########
@@ -395,10 +526,45 @@ struct FixedWidthTakeImpl {
     out_arr->null_count = out_arr->length - valid_count;
     return Status::OK();
   }
+
+  static Status ChunkedExec(KernelContext* ctx, const ChunkedArray& values,
+                            const ArraySpan& indices, ArrayData* out_arr,
+                            int64_t factor) {
+    const bool out_has_validity = values.null_count() > 0 || indices.MayHaveNulls();
+
+    ChunkedFixedWidthValuesSpan chunked_values{values};
+    ResolvedIndicesState resolved_idx;
+    RETURN_NOT_OK(resolved_idx.InitWithIndices<IndexCType>(
+        /*chunks=*/values.chunks(), /*idx_length=*/indices.length,
+        /*idx=*/indices.GetValues<IndexCType>(1), ctx->memory_pool()));
+
+    int64_t valid_count = 0;
+    arrow::internal::GatherFromChunks<kValueWidthInBits, IndexCType, WithFactor::value>

Review Comment:
   This is the kind of optimization that depends on statistical properties of the input data so gains are hard to quantify. Here I went with the assumption that if there are multiple chunks, values are gathered from multiple of them.



-- 
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: github-unsubscribe@arrow.apache.org

For queries about this service, please contact Infrastructure at:
users@infra.apache.org


Re: [PR] GH-39565: [C++] Do not concatenate chunked values of fixed-width types to run "array_take" [arrow]

Posted by "pitrou (via GitHub)" <gi...@apache.org>.
pitrou commented on PR #41700:
URL: https://github.com/apache/arrow/pull/41700#issuecomment-2535452180

   By building on this (arguably simplified) analysis:
   
   > we're trading the concatenation of the chunked values (essentially allocating a new values array) against the resolution of many chunked indices (essentially allocating two new indices arrays). This is only beneficial if the value width is quite large (say a 256-byte FSB) or the number of indices is much smaller than the number of values.
   
   and assuming the following known values:
   * `n_values`: length of the values input
   * `n_indices`: length of the indices input (governing the output length)
   * `value_width`: byte width of the individual values
   
   Then a simple heuristic could be to concatenate iff `n_indices * 16 > n_values * value_width`. This wouldn't take into account the larger computational cost associated with chunked indexing, but at least it would disable the chunked resolution approach when it doesn't make sense at all.
   
   (btw, a moderate improvement could probably be achieved by using `CompressedChunkLocation`)


-- 
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: github-unsubscribe@arrow.apache.org

For queries about this service, please contact Infrastructure at:
users@infra.apache.org


Re: [PR] GH-39565: [C++] Do not concatenate chunked values of fixed-width types to run "array_take" [arrow]

Posted by "felipecrv (via GitHub)" <gi...@apache.org>.
felipecrv commented on code in PR #41700:
URL: https://github.com/apache/arrow/pull/41700#discussion_r1685743190


##########
cpp/src/arrow/compute/kernels/vector_selection_take_internal.cc:
##########
@@ -715,12 +853,244 @@ class TakeMetaFunction : public MetaFunction {
     return Status::NotImplemented(
         "Unsupported types for take operation: "
         "values=",
-        args[0].ToString(), "indices=", args[1].ToString());
+        args[0].ToString(), ", indices=", args[1].ToString());
   }
 };
 
 // ----------------------------------------------------------------------
 
+/// \brief Prepare the output array like ExecuteArrayKernel::PrepareOutput()
+std::shared_ptr<ArrayData> PrepareOutput(const ExecBatch& batch, int64_t length) {
+  DCHECK_EQ(batch.length, length);
+  auto out = std::make_shared<ArrayData>(batch.values[0].type(), length);
+  out->buffers.resize(batch.values[0].type()->layout().buffers.size());
+  return out;
+}
+
+Result<std::shared_ptr<Array>> ChunkedArrayAsArray(
+    const std::shared_ptr<ChunkedArray>& values, MemoryPool* pool) {
+  switch (values->num_chunks()) {
+    case 0:
+      return MakeArrayOfNull(values->type(), /*length=*/0, pool);
+    case 1:
+      return values->chunk(0);
+    default:
+      return Concatenate(values->chunks(), pool);
+  }
+}
+
+Status CallAAAKernel(ArrayKernelExec take_aaa_exec, KernelContext* ctx,
+                     std::shared_ptr<ArrayData> values,
+                     std::shared_ptr<ArrayData> indices, Datum* out) {
+  int64_t batch_length = values->length;
+  std::vector<Datum> args = {std::move(values), std::move(indices)};
+  ExecBatch array_array_batch(std::move(args), batch_length);
+  DCHECK_EQ(out->kind(), Datum::ARRAY);
+  ExecSpan exec_span{array_array_batch};
+  ExecResult result;
+  result.value = out->array();
+  return take_aaa_exec(ctx, exec_span, &result);
+}
+
+Status CallCAAKernel(VectorKernel::ChunkedExec take_caa_exec, KernelContext* ctx,
+                     std::shared_ptr<ChunkedArray> values,
+                     std::shared_ptr<ArrayData> indices, Datum* out) {
+  int64_t batch_length = values->length();
+  std::vector<Datum> args = {std::move(values), std::move(indices)};
+  ExecBatch chunked_array_array_batch(std::move(args), batch_length);
+  DCHECK_EQ(out->kind(), Datum::ARRAY);
+  return take_caa_exec(ctx, chunked_array_array_batch, out);
+}
+
+Status TakeACCChunkedExec(ArrayKernelExec take_aaa_exec, KernelContext* ctx,
+                          const ExecBatch& batch, Datum* out) {
+  auto& values = batch.values[0].array();
+  auto& indices = batch.values[1].chunked_array();
+  auto num_chunks = indices->num_chunks();
+  std::vector<std::shared_ptr<Array>> new_chunks(num_chunks);
+  for (int i = 0; i < num_chunks; i++) {
+    // Take with that indices chunk
+    auto& indices_chunk = indices->chunk(i)->data();
+    Datum result = PrepareOutput(batch, values->length);
+    RETURN_NOT_OK(CallAAAKernel(take_aaa_exec, ctx, values, indices_chunk, &result));
+    new_chunks[i] = MakeArray(result.array());
+  }
+  out->value = std::make_shared<ChunkedArray>(std::move(new_chunks), values->type);
+  return Status::OK();
+}
+
+/// \brief Generic (slower) VectorKernel::exec_chunked (`CA->C`, `CC->C`, and `AC->C`).
+///
+/// This function concatenates the chunks of the values and then calls the `AA->A` take
+/// kernel to handle the `CA->C` cases. The ArrayData returned by the `AA->A` kernel is
+/// converted to a ChunkedArray with a single chunk to honor the `CA->C` contract.
+///
+/// For `CC->C` cases, it concatenates the chunks of the values and calls the `AA->A` take
+/// kernel for each chunk of the indices, producing a new chunked array with the same
+/// shape as the indices.
+///
+/// `AC->C` cases are trivially delegated to TakeACCChunkedExec without any concatenation.
+///
+/// \param take_aaa_exec The `AA->A` take kernel to use.
+Status GenericTakeChunkedExec(ArrayKernelExec take_aaa_exec, KernelContext* ctx,
+                              const ExecBatch& batch, Datum* out) {
+  const auto& args = batch.values;
+  if (args[0].kind() == Datum::CHUNKED_ARRAY) {
+    auto& values_chunked = args[0].chunked_array();
+    ARROW_ASSIGN_OR_RAISE(auto values_array,
+                          ChunkedArrayAsArray(values_chunked, ctx->memory_pool()));
+    if (args[1].kind() == Datum::ARRAY) {
+      // CA->C
+      auto& indices = args[1].array();
+      DCHECK_EQ(values_array->length(), batch.length);
+      {
+        // AA->A
+        RETURN_NOT_OK(
+            CallAAAKernel(take_aaa_exec, ctx, values_array->data(), indices, out));
+        out->value = std::make_shared<ChunkedArray>(MakeArray(out->array()));
+      }
+      return Status::OK();
+    } else if (args[1].kind() == Datum::CHUNKED_ARRAY) {
+      // CC->C
+      const auto& indices = args[1].chunked_array();
+      std::vector<std::shared_ptr<Array>> new_chunks;
+      for (int i = 0; i < indices->num_chunks(); i++) {
+        // AA->A
+        auto& indices_chunk = indices->chunk(i)->data();
+        Datum result = PrepareOutput(batch, values_array->length());
+        RETURN_NOT_OK(CallAAAKernel(take_aaa_exec, ctx, values_array->data(),
+                                    indices_chunk, &result));
+        new_chunks.push_back(MakeArray(result.array()));
+      }
+      DCHECK(out->is_array());
+      out->value =
+          std::make_shared<ChunkedArray>(std::move(new_chunks), values_chunked->type());
+      return Status::OK();
+    }
+  } else {
+    // VectorKernel::exec_chunked are only called when at least one of the inputs is
+    // chunked, so we should be able to assume that args[1] is a chunked array when
+    // everything is wired up correctly.
+    if (args[1].kind() == Datum::CHUNKED_ARRAY) {
+      // AC->C
+      return TakeACCChunkedExec(take_aaa_exec, ctx, batch, out);
+    } else {
+      DCHECK(false) << "Unexpected kind for array_take's exec_chunked kernel: values="
+                    << args[0].ToString() << ", indices=" << args[1].ToString();
+    }
+  }
+  return Status::NotImplemented(
+      "Unsupported kinds for 'array_take', try using 'take': "
+      "values=",
+      args[0].ToString(), ", indices=", args[1].ToString());
+}
+
+template <ArrayKernelExec kTakeAAAExec>
+struct GenericTakeChunkedExecFunctor {
+  static Status Exec(KernelContext* ctx, const ExecBatch& batch, Datum* out) {
+    return GenericTakeChunkedExec(kTakeAAAExec, ctx, batch, out);
+  }
+};
+
+/// \brief Specialized (faster) VectorKernel::exec_chunked (`CA->C`, `CC->C`, `AC->C`).
+///
+/// This function doesn't ever need to concatenate the chunks of the values, so it can be
+/// more efficient than GenericTakeChunkedExec that can only delegate to the `AA->A` take
+/// kernels.
+///
+/// For `CA->C` cases, it can call the `CA->A` take kernel directly [1] and trivially
+/// convert the result to a ChunkedArray of a single chunk to honor the `CA->C` contract.
+///
+/// For `CC->C` cases it can call the `CA->A` take kernel for each chunk of the indices to
+/// get each chunk that becomes the ChunkedArray output.
+///
+/// `AC->C` cases are trivially delegated to TakeACCChunkedExec.
+///
+/// \param take_aaa_exec The `AA->A` take kernel to use.
+Status SpecialTakeChunkedExec(const ArrayKernelExec take_aaa_exec,
+                              VectorKernel::ChunkedExec take_caa_exec, KernelContext* ctx,
+                              const ExecBatch& batch, Datum* out) {
+  Datum result = PrepareOutput(batch, batch.length);
+  auto* pool = ctx->memory_pool();
+  const auto& args = batch.values;
+  if (args[0].kind() == Datum::CHUNKED_ARRAY) {
+    auto& values_chunked = args[0].chunked_array();
+    std::shared_ptr<Array> single_chunk = nullptr;
+    if (values_chunked->num_chunks() == 0 || values_chunked->length() == 0) {
+      ARROW_ASSIGN_OR_RAISE(single_chunk,
+                            MakeArrayOfNull(values_chunked->type(), /*length=*/0, pool));
+    } else if (values_chunked->num_chunks() == 1) {
+      single_chunk = values_chunked->chunk(0);
+    }
+
+    if (args[1].kind() == Datum::ARRAY) {
+      // CA->C
+      auto& indices = args[1].array();
+      if (single_chunk) {
+        // AA->A
+        DCHECK_EQ(single_chunk->length(), batch.length);
+        // If the ChunkedArray was cheaply converted to a single chunk,
+        // we can use the AA->A take kernel directly.
+        RETURN_NOT_OK(
+            CallAAAKernel(take_aaa_exec, ctx, single_chunk->data(), indices, out));
+        out->value = std::make_shared<ChunkedArray>(MakeArray(out->array()));
+        return Status::OK();
+      }
+      // Instead of concatenating the chunks, we call the CA->A take kernel

Review Comment:
   Right after the comments it calls `take_caa_exec` (a function pointer).
   
   `RETURN_NOT_OK(take_caa_exec(ctx, batch, &result));`



-- 
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: github-unsubscribe@arrow.apache.org

For queries about this service, please contact Infrastructure at:
users@infra.apache.org


Re: [PR] GH-39565: [C++] Do not concatenate chunked values of fixed-width types to run "array_take" [arrow]

Posted by "pitrou (via GitHub)" <gi...@apache.org>.
pitrou commented on PR #41700:
URL: https://github.com/apache/arrow/pull/41700#issuecomment-2299060850

   It should be noted that this entails significant regression on our micro-benchmarks (when only one thread is working and there's little memory pressure):
   ```
   ---------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------
   Non-regressions: (14)
   ---------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------
                                                    benchmark           baseline          contender  change %                                                                                                                                                                                                                     counters
      TakeChunkedChunkedStringRandomIndicesWithNulls/524288/1   1.324G items/sec   1.582G items/sec    19.459 {'family_index': 7, 'per_family_instance_index': 3, 'run_name': 'TakeChunkedChunkedStringRandomIndicesWithNulls/524288/1', 'repetitions': 1, 'repetition_index': 0, 'threads': 1, 'iterations': 1766, 'null_percent': 100.0}
        TakeChunkedChunkedStringRandomIndicesNoNulls/524288/1 225.526M items/sec 239.940M items/sec     6.391    {'family_index': 6, 'per_family_instance_index': 3, 'run_name': 'TakeChunkedChunkedStringRandomIndicesNoNulls/524288/1', 'repetitions': 1, 'repetition_index': 0, 'threads': 1, 'iterations': 300, 'null_percent': 100.0}
     TakeChunkedChunkedStringRandomIndicesNoNulls/524288/1000  34.689M items/sec  36.379M items/sec     4.871    {'family_index': 6, 'per_family_instance_index': 0, 'run_name': 'TakeChunkedChunkedStringRandomIndicesNoNulls/524288/1000', 'repetitions': 1, 'repetition_index': 0, 'threads': 1, 'iterations': 45, 'null_percent': 0.1}
       TakeChunkedChunkedStringRandomIndicesNoNulls/524288/10  37.765M items/sec  39.242M items/sec     3.913     {'family_index': 6, 'per_family_instance_index': 1, 'run_name': 'TakeChunkedChunkedStringRandomIndicesNoNulls/524288/10', 'repetitions': 1, 'repetition_index': 0, 'threads': 1, 'iterations': 51, 'null_percent': 10.0}
            TakeChunkedChunkedStringMonotonicIndices/524288/1 227.141M items/sec 234.760M items/sec     3.354        {'family_index': 8, 'per_family_instance_index': 3, 'run_name': 'TakeChunkedChunkedStringMonotonicIndices/524288/1', 'repetitions': 1, 'repetition_index': 0, 'threads': 1, 'iterations': 303, 'null_percent': 100.0}
            TakeChunkedChunkedStringMonotonicIndices/524288/0  80.957M items/sec  82.842M items/sec     2.328          {'family_index': 8, 'per_family_instance_index': 4, 'run_name': 'TakeChunkedChunkedStringMonotonicIndices/524288/0', 'repetitions': 1, 'repetition_index': 0, 'threads': 1, 'iterations': 108, 'null_percent': 0.0}
        TakeChunkedChunkedStringRandomIndicesNoNulls/524288/2  55.847M items/sec  57.044M items/sec     2.143      {'family_index': 6, 'per_family_instance_index': 2, 'run_name': 'TakeChunkedChunkedStringRandomIndicesNoNulls/524288/2', 'repetitions': 1, 'repetition_index': 0, 'threads': 1, 'iterations': 74, 'null_percent': 50.0}
        TakeChunkedChunkedStringRandomIndicesNoNulls/524288/0  40.181M items/sec  40.949M items/sec     1.912       {'family_index': 6, 'per_family_instance_index': 4, 'run_name': 'TakeChunkedChunkedStringRandomIndicesNoNulls/524288/0', 'repetitions': 1, 'repetition_index': 0, 'threads': 1, 'iterations': 54, 'null_percent': 0.0}
   TakeChunkedChunkedStringRandomIndicesWithNulls/524288/1000  33.967M items/sec  34.330M items/sec     1.067  {'family_index': 7, 'per_family_instance_index': 0, 'run_name': 'TakeChunkedChunkedStringRandomIndicesWithNulls/524288/1000', 'repetitions': 1, 'repetition_index': 0, 'threads': 1, 'iterations': 45, 'null_percent': 0.1}
      TakeChunkedChunkedStringRandomIndicesWithNulls/524288/0  40.286M items/sec  39.971M items/sec    -0.782     {'family_index': 7, 'per_family_instance_index': 4, 'run_name': 'TakeChunkedChunkedStringRandomIndicesWithNulls/524288/0', 'repetitions': 1, 'repetition_index': 0, 'threads': 1, 'iterations': 53, 'null_percent': 0.0}
            TakeChunkedChunkedStringMonotonicIndices/524288/2  88.903M items/sec  87.193M items/sec    -1.924         {'family_index': 8, 'per_family_instance_index': 2, 'run_name': 'TakeChunkedChunkedStringMonotonicIndices/524288/2', 'repetitions': 1, 'repetition_index': 0, 'threads': 1, 'iterations': 117, 'null_percent': 50.0}
           TakeChunkedChunkedStringMonotonicIndices/524288/10  71.953M items/sec  70.246M items/sec    -2.372         {'family_index': 8, 'per_family_instance_index': 1, 'run_name': 'TakeChunkedChunkedStringMonotonicIndices/524288/10', 'repetitions': 1, 'repetition_index': 0, 'threads': 1, 'iterations': 96, 'null_percent': 10.0}
         TakeChunkedChunkedStringMonotonicIndices/524288/1000  70.934M items/sec  69.020M items/sec    -2.697        {'family_index': 8, 'per_family_instance_index': 0, 'run_name': 'TakeChunkedChunkedStringMonotonicIndices/524288/1000', 'repetitions': 1, 'repetition_index': 0, 'threads': 1, 'iterations': 94, 'null_percent': 0.1}
      TakeChunkedChunkedStringRandomIndicesWithNulls/524288/2  57.716M items/sec  55.633M items/sec    -3.608    {'family_index': 7, 'per_family_instance_index': 2, 'run_name': 'TakeChunkedChunkedStringRandomIndicesWithNulls/524288/2', 'repetitions': 1, 'repetition_index': 0, 'threads': 1, 'iterations': 70, 'null_percent': 50.0}
   
   --------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------
   Regressions: (61)
   --------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------
                                                   benchmark           baseline          contender  change %                                                                                                                                                                                                                                       counters
    TakeChunkedChunkedStringRandomIndicesWithNulls/524288/10  41.015M items/sec  37.718M items/sec    -8.039                     {'family_index': 7, 'per_family_instance_index': 1, 'run_name': 'TakeChunkedChunkedStringRandomIndicesWithNulls/524288/10', 'repetitions': 1, 'repetition_index': 0, 'threads': 1, 'iterations': 54, 'null_percent': 10.0}
            TakeChunkedChunkedFSBMonotonicIndices/524288/0/9 286.271M items/sec 221.528M items/sec   -22.616          {'family_index': 5, 'per_family_instance_index': 9, 'run_name': 'TakeChunkedChunkedFSBMonotonicIndices/524288/0/9', 'repetitions': 1, 'repetition_index': 0, 'threads': 1, 'iterations': 377, 'byte_width': 9.0, 'null_percent': 0.0}
            TakeChunkedChunkedFSBMonotonicIndices/524288/1/9 225.478M items/sec 169.862M items/sec   -24.666        {'family_index': 5, 'per_family_instance_index': 7, 'run_name': 'TakeChunkedChunkedFSBMonotonicIndices/524288/1/9', 'repetitions': 1, 'repetition_index': 0, 'threads': 1, 'iterations': 301, 'byte_width': 9.0, 'null_percent': 100.0}
            TakeChunkedChunkedFSBMonotonicIndices/524288/2/9 125.842M items/sec  92.300M items/sec   -26.654         {'family_index': 5, 'per_family_instance_index': 5, 'run_name': 'TakeChunkedChunkedFSBMonotonicIndices/524288/2/9', 'repetitions': 1, 'repetition_index': 0, 'threads': 1, 'iterations': 168, 'byte_width': 9.0, 'null_percent': 50.0}
         TakeChunkedChunkedFSBMonotonicIndices/524288/1000/9 188.734M items/sec 136.580M items/sec   -27.634       {'family_index': 5, 'per_family_instance_index': 1, 'run_name': 'TakeChunkedChunkedFSBMonotonicIndices/524288/1000/9', 'repetitions': 1, 'repetition_index': 0, 'threads': 1, 'iterations': 252, 'byte_width': 9.0, 'null_percent': 0.1}
           TakeChunkedChunkedFSBMonotonicIndices/524288/10/9 165.385M items/sec 119.599M items/sec   -27.685        {'family_index': 5, 'per_family_instance_index': 3, 'run_name': 'TakeChunkedChunkedFSBMonotonicIndices/524288/10/9', 'repetitions': 1, 'repetition_index': 0, 'threads': 1, 'iterations': 221, 'byte_width': 9.0, 'null_percent': 10.0}
            TakeChunkedChunkedInt64MonotonicIndices/524288/2 172.836M items/sec 107.515M items/sec   -37.794                            {'family_index': 2, 'per_family_instance_index': 2, 'run_name': 'TakeChunkedChunkedInt64MonotonicIndices/524288/2', 'repetitions': 1, 'repetition_index': 0, 'threads': 1, 'iterations': 232, 'null_percent': 50.0}
            TakeChunkedChunkedFSBMonotonicIndices/524288/2/8 173.764M items/sec 107.624M items/sec   -38.063         {'family_index': 5, 'per_family_instance_index': 4, 'run_name': 'TakeChunkedChunkedFSBMonotonicIndices/524288/2/8', 'repetitions': 1, 'repetition_index': 0, 'threads': 1, 'iterations': 231, 'byte_width': 8.0, 'null_percent': 50.0}
            TakeChunkedChunkedInt64MonotonicIndices/524288/1 348.952M items/sec 214.875M items/sec   -38.423                           {'family_index': 2, 'per_family_instance_index': 3, 'run_name': 'TakeChunkedChunkedInt64MonotonicIndices/524288/1', 'repetitions': 1, 'repetition_index': 0, 'threads': 1, 'iterations': 459, 'null_percent': 100.0}
            TakeChunkedChunkedFSBMonotonicIndices/524288/1/8 349.461M items/sec 214.302M items/sec   -38.676        {'family_index': 5, 'per_family_instance_index': 6, 'run_name': 'TakeChunkedChunkedFSBMonotonicIndices/524288/1/8', 'repetitions': 1, 'repetition_index': 0, 'threads': 1, 'iterations': 469, 'byte_width': 8.0, 'null_percent': 100.0}
               TakeChunkedFlatInt64MonotonicIndices/524288/2 186.121M items/sec 110.460M items/sec   -40.652                              {'family_index': 11, 'per_family_instance_index': 2, 'run_name': 'TakeChunkedFlatInt64MonotonicIndices/524288/2', 'repetitions': 1, 'repetition_index': 0, 'threads': 1, 'iterations': 249, 'null_percent': 50.0}
               TakeChunkedFlatInt64MonotonicIndices/524288/1 402.685M items/sec 237.605M items/sec   -40.995                             {'family_index': 11, 'per_family_instance_index': 3, 'run_name': 'TakeChunkedFlatInt64MonotonicIndices/524288/1', 'repetitions': 1, 'repetition_index': 0, 'threads': 1, 'iterations': 537, 'null_percent': 100.0}
           TakeChunkedChunkedInt64MonotonicIndices/524288/10 232.518M items/sec 134.620M items/sec   -42.103                           {'family_index': 2, 'per_family_instance_index': 1, 'run_name': 'TakeChunkedChunkedInt64MonotonicIndices/524288/10', 'repetitions': 1, 'repetition_index': 0, 'threads': 1, 'iterations': 312, 'null_percent': 10.0}
            TakeChunkedChunkedInt64MonotonicIndices/524288/0 550.430M items/sec 318.038M items/sec   -42.220                             {'family_index': 2, 'per_family_instance_index': 4, 'run_name': 'TakeChunkedChunkedInt64MonotonicIndices/524288/0', 'repetitions': 1, 'repetition_index': 0, 'threads': 1, 'iterations': 733, 'null_percent': 0.0}
           TakeChunkedChunkedFSBMonotonicIndices/524288/10/8 233.913M items/sec 134.929M items/sec   -42.316        {'family_index': 5, 'per_family_instance_index': 2, 'run_name': 'TakeChunkedChunkedFSBMonotonicIndices/524288/10/8', 'repetitions': 1, 'repetition_index': 0, 'threads': 1, 'iterations': 311, 'byte_width': 8.0, 'null_percent': 10.0}
            TakeChunkedChunkedFSBMonotonicIndices/524288/0/8 550.806M items/sec 315.331M items/sec   -42.751          {'family_index': 5, 'per_family_instance_index': 8, 'run_name': 'TakeChunkedChunkedFSBMonotonicIndices/524288/0/8', 'repetitions': 1, 'repetition_index': 0, 'threads': 1, 'iterations': 731, 'byte_width': 8.0, 'null_percent': 0.0}
         TakeChunkedChunkedInt64MonotonicIndices/524288/1000 276.014M items/sec 154.981M items/sec   -43.850                          {'family_index': 2, 'per_family_instance_index': 0, 'run_name': 'TakeChunkedChunkedInt64MonotonicIndices/524288/1000', 'repetitions': 1, 'repetition_index': 0, 'threads': 1, 'iterations': 366, 'null_percent': 0.1}
         TakeChunkedChunkedFSBMonotonicIndices/524288/1000/8 275.488M items/sec 154.412M items/sec   -43.950       {'family_index': 5, 'per_family_instance_index': 0, 'run_name': 'TakeChunkedChunkedFSBMonotonicIndices/524288/1000/8', 'repetitions': 1, 'repetition_index': 0, 'threads': 1, 'iterations': 373, 'byte_width': 8.0, 'null_percent': 0.1}
              TakeChunkedFlatInt64MonotonicIndices/524288/10 255.324M items/sec 136.158M items/sec   -46.672                             {'family_index': 11, 'per_family_instance_index': 1, 'run_name': 'TakeChunkedFlatInt64MonotonicIndices/524288/10', 'repetitions': 1, 'repetition_index': 0, 'threads': 1, 'iterations': 340, 'null_percent': 10.0}
            TakeChunkedFlatInt64MonotonicIndices/524288/1000 309.002M items/sec 163.782M items/sec   -46.996                            {'family_index': 11, 'per_family_instance_index': 0, 'run_name': 'TakeChunkedFlatInt64MonotonicIndices/524288/1000', 'repetitions': 1, 'repetition_index': 0, 'threads': 1, 'iterations': 412, 'null_percent': 0.1}
               TakeChunkedFlatInt64MonotonicIndices/524288/0 689.590M items/sec 358.889M items/sec   -47.956                               {'family_index': 11, 'per_family_instance_index': 4, 'run_name': 'TakeChunkedFlatInt64MonotonicIndices/524288/0', 'repetitions': 1, 'repetition_index': 0, 'threads': 1, 'iterations': 918, 'null_percent': 0.0}
      TakeChunkedChunkedFSBRandomIndicesWithNulls/524288/2/9  72.765M items/sec  25.177M items/sec   -65.400    {'family_index': 4, 'per_family_instance_index': 5, 'run_name': 'TakeChunkedChunkedFSBRandomIndicesWithNulls/524288/2/9', 'repetitions': 1, 'repetition_index': 0, 'threads': 1, 'iterations': 95, 'byte_width': 9.0, 'null_percent': 50.0}
      TakeChunkedChunkedFSBRandomIndicesWithNulls/524288/2/8  85.926M items/sec  26.774M items/sec   -68.841   {'family_index': 4, 'per_family_instance_index': 4, 'run_name': 'TakeChunkedChunkedFSBRandomIndicesWithNulls/524288/2/8', 'repetitions': 1, 'repetition_index': 0, 'threads': 1, 'iterations': 115, 'byte_width': 8.0, 'null_percent': 50.0}
      TakeChunkedChunkedInt64RandomIndicesWithNulls/524288/2  86.185M items/sec  26.795M items/sec   -68.910                      {'family_index': 1, 'per_family_instance_index': 2, 'run_name': 'TakeChunkedChunkedInt64RandomIndicesWithNulls/524288/2', 'repetitions': 1, 'repetition_index': 0, 'threads': 1, 'iterations': 114, 'null_percent': 50.0}
         TakeChunkedFlatInt64RandomIndicesWithNulls/524288/2  89.997M items/sec  26.168M items/sec   -70.923                        {'family_index': 10, 'per_family_instance_index': 2, 'run_name': 'TakeChunkedFlatInt64RandomIndicesWithNulls/524288/2', 'repetitions': 1, 'repetition_index': 0, 'threads': 1, 'iterations': 118, 'null_percent': 50.0}
     TakeChunkedChunkedFSBRandomIndicesWithNulls/524288/10/9  99.099M items/sec  27.917M items/sec   -71.829  {'family_index': 4, 'per_family_instance_index': 3, 'run_name': 'TakeChunkedChunkedFSBRandomIndicesWithNulls/524288/10/9', 'repetitions': 1, 'repetition_index': 0, 'threads': 1, 'iterations': 133, 'byte_width': 9.0, 'null_percent': 10.0}
        TakeChunkedChunkedFSBRandomIndicesNoNulls/524288/2/9 100.736M items/sec  26.627M items/sec   -73.568     {'family_index': 3, 'per_family_instance_index': 5, 'run_name': 'TakeChunkedChunkedFSBRandomIndicesNoNulls/524288/2/9', 'repetitions': 1, 'repetition_index': 0, 'threads': 1, 'iterations': 134, 'byte_width': 9.0, 'null_percent': 50.0}
     TakeChunkedChunkedInt64RandomIndicesWithNulls/524288/10 125.265M items/sec  29.373M items/sec   -76.551                     {'family_index': 1, 'per_family_instance_index': 1, 'run_name': 'TakeChunkedChunkedInt64RandomIndicesWithNulls/524288/10', 'repetitions': 1, 'repetition_index': 0, 'threads': 1, 'iterations': 167, 'null_percent': 10.0}
     TakeChunkedChunkedFSBRandomIndicesWithNulls/524288/10/8 125.343M items/sec  29.371M items/sec   -76.567  {'family_index': 4, 'per_family_instance_index': 2, 'run_name': 'TakeChunkedChunkedFSBRandomIndicesWithNulls/524288/10/8', 'repetitions': 1, 'repetition_index': 0, 'threads': 1, 'iterations': 167, 'byte_width': 8.0, 'null_percent': 10.0}
        TakeChunkedChunkedInt64RandomIndicesNoNulls/524288/2 130.626M items/sec  28.264M items/sec   -78.363                        {'family_index': 0, 'per_family_instance_index': 2, 'run_name': 'TakeChunkedChunkedInt64RandomIndicesNoNulls/524288/2', 'repetitions': 1, 'repetition_index': 0, 'threads': 1, 'iterations': 175, 'null_percent': 50.0}
       TakeChunkedChunkedFSBRandomIndicesNoNulls/524288/10/9 138.137M items/sec  29.807M items/sec   -78.422    {'family_index': 3, 'per_family_instance_index': 3, 'run_name': 'TakeChunkedChunkedFSBRandomIndicesNoNulls/524288/10/9', 'repetitions': 1, 'repetition_index': 0, 'threads': 1, 'iterations': 184, 'byte_width': 9.0, 'null_percent': 10.0}
        TakeChunkedFlatInt64RandomIndicesWithNulls/524288/10 133.355M items/sec  28.684M items/sec   -78.491                       {'family_index': 10, 'per_family_instance_index': 1, 'run_name': 'TakeChunkedFlatInt64RandomIndicesWithNulls/524288/10', 'repetitions': 1, 'repetition_index': 0, 'threads': 1, 'iterations': 178, 'null_percent': 10.0}
        TakeChunkedChunkedFSBRandomIndicesNoNulls/524288/2/8 130.778M items/sec  28.093M items/sec   -78.519     {'family_index': 3, 'per_family_instance_index': 4, 'run_name': 'TakeChunkedChunkedFSBRandomIndicesNoNulls/524288/2/8', 'repetitions': 1, 'repetition_index': 0, 'threads': 1, 'iterations': 174, 'byte_width': 8.0, 'null_percent': 50.0}
   TakeChunkedChunkedFSBRandomIndicesWithNulls/524288/1000/9 144.875M items/sec  30.345M items/sec   -79.054 {'family_index': 4, 'per_family_instance_index': 1, 'run_name': 'TakeChunkedChunkedFSBRandomIndicesWithNulls/524288/1000/9', 'repetitions': 1, 'repetition_index': 0, 'threads': 1, 'iterations': 194, 'byte_width': 9.0, 'null_percent': 0.1}
     TakeChunkedChunkedFSBRandomIndicesNoNulls/524288/1000/9 151.949M items/sec  30.617M items/sec   -79.851   {'family_index': 3, 'per_family_instance_index': 1, 'run_name': 'TakeChunkedChunkedFSBRandomIndicesNoNulls/524288/1000/9', 'repetitions': 1, 'repetition_index': 0, 'threads': 1, 'iterations': 203, 'byte_width': 9.0, 'null_percent': 0.1}
           TakeChunkedFlatInt64RandomIndicesNoNulls/524288/2 137.927M items/sec  27.554M items/sec   -80.023                           {'family_index': 9, 'per_family_instance_index': 2, 'run_name': 'TakeChunkedFlatInt64RandomIndicesNoNulls/524288/2', 'repetitions': 1, 'repetition_index': 0, 'threads': 1, 'iterations': 184, 'null_percent': 50.0}
   TakeChunkedChunkedFSBRandomIndicesWithNulls/524288/1000/8 174.761M items/sec  31.542M items/sec   -81.951 {'family_index': 4, 'per_family_instance_index': 0, 'run_name': 'TakeChunkedChunkedFSBRandomIndicesWithNulls/524288/1000/8', 'repetitions': 1, 'repetition_index': 0, 'threads': 1, 'iterations': 235, 'byte_width': 8.0, 'null_percent': 0.1}
   TakeChunkedChunkedInt64RandomIndicesWithNulls/524288/1000 175.242M items/sec  31.416M items/sec   -82.073                    {'family_index': 1, 'per_family_instance_index': 0, 'run_name': 'TakeChunkedChunkedInt64RandomIndicesWithNulls/524288/1000', 'repetitions': 1, 'repetition_index': 0, 'threads': 1, 'iterations': 234, 'null_percent': 0.1}
       TakeChunkedChunkedInt64RandomIndicesNoNulls/524288/10 177.783M items/sec  31.170M items/sec   -82.467                       {'family_index': 0, 'per_family_instance_index': 1, 'run_name': 'TakeChunkedChunkedInt64RandomIndicesNoNulls/524288/10', 'repetitions': 1, 'repetition_index': 0, 'threads': 1, 'iterations': 238, 'null_percent': 10.0}
       TakeChunkedChunkedFSBRandomIndicesNoNulls/524288/10/8 177.439M items/sec  30.984M items/sec   -82.538    {'family_index': 3, 'per_family_instance_index': 2, 'run_name': 'TakeChunkedChunkedFSBRandomIndicesNoNulls/524288/10/8', 'repetitions': 1, 'repetition_index': 0, 'threads': 1, 'iterations': 236, 'byte_width': 8.0, 'null_percent': 10.0}
     TakeChunkedChunkedFSBRandomIndicesNoNulls/524288/1000/8 191.503M items/sec  31.727M items/sec   -83.433   {'family_index': 3, 'per_family_instance_index': 0, 'run_name': 'TakeChunkedChunkedFSBRandomIndicesNoNulls/524288/1000/8', 'repetitions': 1, 'repetition_index': 0, 'threads': 1, 'iterations': 255, 'byte_width': 8.0, 'null_percent': 0.1}
     TakeChunkedChunkedInt64RandomIndicesNoNulls/524288/1000 193.078M items/sec  31.946M items/sec   -83.454                      {'family_index': 0, 'per_family_instance_index': 0, 'run_name': 'TakeChunkedChunkedInt64RandomIndicesNoNulls/524288/1000', 'repetitions': 1, 'repetition_index': 0, 'threads': 1, 'iterations': 256, 'null_percent': 0.1}
          TakeChunkedFlatInt64RandomIndicesNoNulls/524288/10 189.467M items/sec  30.142M items/sec   -84.091                          {'family_index': 9, 'per_family_instance_index': 1, 'run_name': 'TakeChunkedFlatInt64RandomIndicesNoNulls/524288/10', 'repetitions': 1, 'repetition_index': 0, 'threads': 1, 'iterations': 252, 'null_percent': 10.0}
      TakeChunkedFlatInt64RandomIndicesWithNulls/524288/1000 196.665M items/sec  30.772M items/sec   -84.353                      {'family_index': 10, 'per_family_instance_index': 0, 'run_name': 'TakeChunkedFlatInt64RandomIndicesWithNulls/524288/1000', 'repetitions': 1, 'repetition_index': 0, 'threads': 1, 'iterations': 263, 'null_percent': 0.1}
        TakeChunkedChunkedFSBRandomIndicesNoNulls/524288/1/9 222.674M items/sec  34.244M items/sec   -84.622    {'family_index': 3, 'per_family_instance_index': 7, 'run_name': 'TakeChunkedChunkedFSBRandomIndicesNoNulls/524288/1/9', 'repetitions': 1, 'repetition_index': 0, 'threads': 1, 'iterations': 298, 'byte_width': 9.0, 'null_percent': 100.0}
        TakeChunkedFlatInt64RandomIndicesNoNulls/524288/1000 206.747M items/sec  30.798M items/sec   -85.104                         {'family_index': 9, 'per_family_instance_index': 0, 'run_name': 'TakeChunkedFlatInt64RandomIndicesNoNulls/524288/1000', 'repetitions': 1, 'repetition_index': 0, 'threads': 1, 'iterations': 275, 'null_percent': 0.1}
      TakeChunkedChunkedFSBRandomIndicesWithNulls/524288/0/9 246.430M items/sec  35.724M items/sec   -85.504    {'family_index': 4, 'per_family_instance_index': 9, 'run_name': 'TakeChunkedChunkedFSBRandomIndicesWithNulls/524288/0/9', 'repetitions': 1, 'repetition_index': 0, 'threads': 1, 'iterations': 327, 'byte_width': 9.0, 'null_percent': 0.0}
        TakeChunkedChunkedFSBRandomIndicesNoNulls/524288/0/9 246.763M items/sec  35.540M items/sec   -85.598      {'family_index': 3, 'per_family_instance_index': 9, 'run_name': 'TakeChunkedChunkedFSBRandomIndicesNoNulls/524288/0/9', 'repetitions': 1, 'repetition_index': 0, 'threads': 1, 'iterations': 330, 'byte_width': 9.0, 'null_percent': 0.0}
        TakeChunkedChunkedInt64RandomIndicesNoNulls/524288/1 346.024M items/sec  35.537M items/sec   -89.730                       {'family_index': 0, 'per_family_instance_index': 3, 'run_name': 'TakeChunkedChunkedInt64RandomIndicesNoNulls/524288/1', 'repetitions': 1, 'repetition_index': 0, 'threads': 1, 'iterations': 460, 'null_percent': 100.0}
        TakeChunkedChunkedFSBRandomIndicesNoNulls/524288/1/8 346.674M items/sec  35.559M items/sec   -89.743    {'family_index': 3, 'per_family_instance_index': 6, 'run_name': 'TakeChunkedChunkedFSBRandomIndicesNoNulls/524288/1/8', 'repetitions': 1, 'repetition_index': 0, 'threads': 1, 'iterations': 459, 'byte_width': 8.0, 'null_percent': 100.0}
           TakeChunkedFlatInt64RandomIndicesNoNulls/524288/1 394.791M items/sec  34.899M items/sec   -91.160                          {'family_index': 9, 'per_family_instance_index': 3, 'run_name': 'TakeChunkedFlatInt64RandomIndicesNoNulls/524288/1', 'repetitions': 1, 'repetition_index': 0, 'threads': 1, 'iterations': 520, 'null_percent': 100.0}
      TakeChunkedChunkedInt64RandomIndicesWithNulls/524288/0 465.112M items/sec  38.014M items/sec   -91.827                       {'family_index': 1, 'per_family_instance_index': 4, 'run_name': 'TakeChunkedChunkedInt64RandomIndicesWithNulls/524288/0', 'repetitions': 1, 'repetition_index': 0, 'threads': 1, 'iterations': 624, 'null_percent': 0.0}
        TakeChunkedChunkedInt64RandomIndicesNoNulls/524288/0 468.038M items/sec  38.050M items/sec   -91.870                         {'family_index': 0, 'per_family_instance_index': 4, 'run_name': 'TakeChunkedChunkedInt64RandomIndicesNoNulls/524288/0', 'repetitions': 1, 'repetition_index': 0, 'threads': 1, 'iterations': 627, 'null_percent': 0.0}
      TakeChunkedChunkedFSBRandomIndicesWithNulls/524288/0/8 468.096M items/sec  38.036M items/sec   -91.874    {'family_index': 4, 'per_family_instance_index': 8, 'run_name': 'TakeChunkedChunkedFSBRandomIndicesWithNulls/524288/0/8', 'repetitions': 1, 'repetition_index': 0, 'threads': 1, 'iterations': 622, 'byte_width': 8.0, 'null_percent': 0.0}
        TakeChunkedChunkedFSBRandomIndicesNoNulls/524288/0/8 468.613M items/sec  37.968M items/sec   -91.898      {'family_index': 3, 'per_family_instance_index': 8, 'run_name': 'TakeChunkedChunkedFSBRandomIndicesNoNulls/524288/0/8', 'repetitions': 1, 'repetition_index': 0, 'threads': 1, 'iterations': 625, 'byte_width': 8.0, 'null_percent': 0.0}
         TakeChunkedFlatInt64RandomIndicesWithNulls/524288/0 537.788M items/sec  36.774M items/sec   -93.162                         {'family_index': 10, 'per_family_instance_index': 4, 'run_name': 'TakeChunkedFlatInt64RandomIndicesWithNulls/524288/0', 'repetitions': 1, 'repetition_index': 0, 'threads': 1, 'iterations': 717, 'null_percent': 0.0}
           TakeChunkedFlatInt64RandomIndicesNoNulls/524288/0 537.631M items/sec  36.663M items/sec   -93.181                            {'family_index': 9, 'per_family_instance_index': 4, 'run_name': 'TakeChunkedFlatInt64RandomIndicesNoNulls/524288/0', 'repetitions': 1, 'repetition_index': 0, 'threads': 1, 'iterations': 711, 'null_percent': 0.0}
      TakeChunkedChunkedFSBRandomIndicesWithNulls/524288/1/9 894.444M items/sec  40.420M items/sec   -95.481 {'family_index': 4, 'per_family_instance_index': 7, 'run_name': 'TakeChunkedChunkedFSBRandomIndicesWithNulls/524288/1/9', 'repetitions': 1, 'repetition_index': 0, 'threads': 1, 'iterations': 1165, 'byte_width': 9.0, 'null_percent': 100.0}
      TakeChunkedChunkedFSBRandomIndicesWithNulls/524288/1/8   1.087G items/sec  40.402M items/sec   -96.283 {'family_index': 4, 'per_family_instance_index': 6, 'run_name': 'TakeChunkedChunkedFSBRandomIndicesWithNulls/524288/1/8', 'repetitions': 1, 'repetition_index': 0, 'threads': 1, 'iterations': 1456, 'byte_width': 8.0, 'null_percent': 100.0}
      TakeChunkedChunkedInt64RandomIndicesWithNulls/524288/1   1.100G items/sec  40.322M items/sec   -96.333                    {'family_index': 1, 'per_family_instance_index': 3, 'run_name': 'TakeChunkedChunkedInt64RandomIndicesWithNulls/524288/1', 'repetitions': 1, 'repetition_index': 0, 'threads': 1, 'iterations': 1473, 'null_percent': 100.0}
         TakeChunkedFlatInt64RandomIndicesWithNulls/524288/1   1.840G items/sec  39.773M items/sec   -97.839                      {'family_index': 10, 'per_family_instance_index': 3, 'run_name': 'TakeChunkedFlatInt64RandomIndicesWithNulls/524288/1', 'repetitions': 1, 'repetition_index': 0, 'threads': 1, 'iterations': 2450, 'null_percent': 100.0}
   ```
   


-- 
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: github-unsubscribe@arrow.apache.org

For queries about this service, please contact Infrastructure at:
users@infra.apache.org


Re: [PR] GH-39565: [C++] Do not concatenate chunked values of fixed-width types to run "array_take" [arrow]

Posted by "pitrou (via GitHub)" <gi...@apache.org>.
pitrou commented on PR #41700:
URL: https://github.com/apache/arrow/pull/41700#issuecomment-2302064092

   I ran the new benchmarks (those with a small selection factor) and the results are more varied, see below:
   ```
   -----------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------
   Non-regressions: (13)
   -----------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------
                                                       benchmark           baseline          contender  change %                                                                                                                                                                                                                                                  counters
                TakeChunkedFlatInt64FewMonotonicIndices/524288/0   3.487G items/sec   6.131G items/sec    75.818             {'family_index': 5, 'per_family_instance_index': 4, 'run_name': 'TakeChunkedFlatInt64FewMonotonicIndices/524288/0', 'repetitions': 1, 'repetition_index': 0, 'threads': 1, 'iterations': 4676, 'null_percent': 0.0, 'selection_factor': 0.05}
             TakeChunkedChunkedInt64FewMonotonicIndices/524288/0   3.397G items/sec   5.278G items/sec    55.353          {'family_index': 1, 'per_family_instance_index': 4, 'run_name': 'TakeChunkedChunkedInt64FewMonotonicIndices/524288/0', 'repetitions': 1, 'repetition_index': 0, 'threads': 1, 'iterations': 4603, 'null_percent': 0.0, 'selection_factor': 0.05}
                TakeChunkedFlatInt64FewMonotonicIndices/524288/1   3.019G items/sec   4.508G items/sec    49.291           {'family_index': 5, 'per_family_instance_index': 3, 'run_name': 'TakeChunkedFlatInt64FewMonotonicIndices/524288/1', 'repetitions': 1, 'repetition_index': 0, 'threads': 1, 'iterations': 4000, 'null_percent': 100.0, 'selection_factor': 0.05}
             TakeChunkedChunkedInt64FewMonotonicIndices/524288/1   2.802G items/sec   4.135G items/sec    47.589        {'family_index': 1, 'per_family_instance_index': 3, 'run_name': 'TakeChunkedChunkedInt64FewMonotonicIndices/524288/1', 'repetitions': 1, 'repetition_index': 0, 'threads': 1, 'iterations': 3740, 'null_percent': 100.0, 'selection_factor': 0.05}
             TakeChunkedFlatInt64FewMonotonicIndices/524288/1000   2.316G items/sec   2.910G items/sec    25.628          {'family_index': 5, 'per_family_instance_index': 0, 'run_name': 'TakeChunkedFlatInt64FewMonotonicIndices/524288/1000', 'repetitions': 1, 'repetition_index': 0, 'threads': 1, 'iterations': 3104, 'null_percent': 0.1, 'selection_factor': 0.05}
          TakeChunkedChunkedInt64FewMonotonicIndices/524288/1000   2.254G items/sec   2.684G items/sec    19.075       {'family_index': 1, 'per_family_instance_index': 0, 'run_name': 'TakeChunkedChunkedInt64FewMonotonicIndices/524288/1000', 'repetitions': 1, 'repetition_index': 0, 'threads': 1, 'iterations': 3082, 'null_percent': 0.1, 'selection_factor': 0.05}
               TakeChunkedFlatInt64FewMonotonicIndices/524288/10   2.257G items/sec   2.635G items/sec    16.733           {'family_index': 5, 'per_family_instance_index': 1, 'run_name': 'TakeChunkedFlatInt64FewMonotonicIndices/524288/10', 'repetitions': 1, 'repetition_index': 0, 'threads': 1, 'iterations': 3052, 'null_percent': 10.0, 'selection_factor': 0.05}
            TakeChunkedChunkedInt64FewMonotonicIndices/524288/10   2.179G items/sec   2.466G items/sec    13.175        {'family_index': 1, 'per_family_instance_index': 1, 'run_name': 'TakeChunkedChunkedInt64FewMonotonicIndices/524288/10', 'repetitions': 1, 'repetition_index': 0, 'threads': 1, 'iterations': 2878, 'null_percent': 10.0, 'selection_factor': 0.05}
      TakeChunkedChunkedStringFewRandomIndicesWithNulls/524288/1   5.541G items/sec   5.568G items/sec     0.490 {'family_index': 2, 'per_family_instance_index': 3, 'run_name': 'TakeChunkedChunkedStringFewRandomIndicesWithNulls/524288/1', 'repetitions': 1, 'repetition_index': 0, 'threads': 1, 'iterations': 7344, 'null_percent': 100.0, 'selection_factor': 0.05}
            TakeChunkedChunkedStringFewMonotonicIndices/524288/1   2.753G items/sec   2.736G items/sec    -0.625       {'family_index': 3, 'per_family_instance_index': 3, 'run_name': 'TakeChunkedChunkedStringFewMonotonicIndices/524288/1', 'repetitions': 1, 'repetition_index': 0, 'threads': 1, 'iterations': 3674, 'null_percent': 100.0, 'selection_factor': 0.05}
                TakeChunkedFlatInt64FewMonotonicIndices/524288/2   1.880G items/sec   1.852G items/sec    -1.442            {'family_index': 5, 'per_family_instance_index': 2, 'run_name': 'TakeChunkedFlatInt64FewMonotonicIndices/524288/2', 'repetitions': 1, 'repetition_index': 0, 'threads': 1, 'iterations': 2520, 'null_percent': 50.0, 'selection_factor': 0.05}
             TakeChunkedChunkedInt64FewMonotonicIndices/524288/2   1.818G items/sec   1.766G items/sec    -2.872         {'family_index': 1, 'per_family_instance_index': 2, 'run_name': 'TakeChunkedChunkedInt64FewMonotonicIndices/524288/2', 'repetitions': 1, 'repetition_index': 0, 'threads': 1, 'iterations': 2403, 'null_percent': 50.0, 'selection_factor': 0.05}
   TakeChunkedChunkedStringFewRandomIndicesWithNulls/524288/1000 269.164M items/sec 256.848M items/sec    -4.576 {'family_index': 2, 'per_family_instance_index': 0, 'run_name': 'TakeChunkedChunkedStringFewRandomIndicesWithNulls/524288/1000', 'repetitions': 1, 'repetition_index': 0, 'threads': 1, 'iterations': 358, 'null_percent': 0.1, 'selection_factor': 0.05}
   
   ----------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------
   Regressions: (17)
   ----------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------
                                                      benchmark           baseline          contender  change %                                                                                                                                                                                                                                                  counters
           TakeChunkedChunkedStringFewMonotonicIndices/524288/2 854.187M items/sec 810.956M items/sec    -5.061        {'family_index': 3, 'per_family_instance_index': 2, 'run_name': 'TakeChunkedChunkedStringFewMonotonicIndices/524288/2', 'repetitions': 1, 'repetition_index': 0, 'threads': 1, 'iterations': 1124, 'null_percent': 50.0, 'selection_factor': 0.05}
           TakeChunkedChunkedStringFewMonotonicIndices/524288/0 420.243M items/sec 393.347M items/sec    -6.400          {'family_index': 3, 'per_family_instance_index': 4, 'run_name': 'TakeChunkedChunkedStringFewMonotonicIndices/524288/0', 'repetitions': 1, 'repetition_index': 0, 'threads': 1, 'iterations': 561, 'null_percent': 0.0, 'selection_factor': 0.05}
     TakeChunkedChunkedStringFewRandomIndicesWithNulls/524288/2 751.346M items/sec 700.885M items/sec    -6.716   {'family_index': 2, 'per_family_instance_index': 2, 'run_name': 'TakeChunkedChunkedStringFewRandomIndicesWithNulls/524288/2', 'repetitions': 1, 'repetition_index': 0, 'threads': 1, 'iterations': 982, 'null_percent': 50.0, 'selection_factor': 0.05}
        TakeChunkedChunkedStringFewMonotonicIndices/524288/1000 383.643M items/sec 353.206M items/sec    -7.934       {'family_index': 3, 'per_family_instance_index': 0, 'run_name': 'TakeChunkedChunkedStringFewMonotonicIndices/524288/1000', 'repetitions': 1, 'repetition_index': 0, 'threads': 1, 'iterations': 511, 'null_percent': 0.1, 'selection_factor': 0.05}
     TakeChunkedChunkedStringFewRandomIndicesWithNulls/524288/0 308.601M items/sec 283.361M items/sec    -8.179    {'family_index': 2, 'per_family_instance_index': 4, 'run_name': 'TakeChunkedChunkedStringFewRandomIndicesWithNulls/524288/0', 'repetitions': 1, 'repetition_index': 0, 'threads': 1, 'iterations': 411, 'null_percent': 0.0, 'selection_factor': 0.05}
    TakeChunkedChunkedStringFewRandomIndicesWithNulls/524288/10 327.708M items/sec 300.772M items/sec    -8.220  {'family_index': 2, 'per_family_instance_index': 1, 'run_name': 'TakeChunkedChunkedStringFewRandomIndicesWithNulls/524288/10', 'repetitions': 1, 'repetition_index': 0, 'threads': 1, 'iterations': 440, 'null_percent': 10.0, 'selection_factor': 0.05}
          TakeChunkedChunkedStringFewMonotonicIndices/524288/10 452.054M items/sec 393.971M items/sec   -12.849        {'family_index': 3, 'per_family_instance_index': 1, 'run_name': 'TakeChunkedChunkedStringFewMonotonicIndices/524288/10', 'repetitions': 1, 'repetition_index': 0, 'threads': 1, 'iterations': 602, 'null_percent': 10.0, 'selection_factor': 0.05}
      TakeChunkedChunkedInt64FewRandomIndicesWithNulls/524288/2   1.276G items/sec 509.634M items/sec   -60.060   {'family_index': 0, 'per_family_instance_index': 2, 'run_name': 'TakeChunkedChunkedInt64FewRandomIndicesWithNulls/524288/2', 'repetitions': 1, 'repetition_index': 0, 'threads': 1, 'iterations': 1691, 'null_percent': 50.0, 'selection_factor': 0.05}
         TakeChunkedFlatInt64FewRandomIndicesWithNulls/524288/2   1.323G items/sec 517.354M items/sec   -60.894      {'family_index': 4, 'per_family_instance_index': 2, 'run_name': 'TakeChunkedFlatInt64FewRandomIndicesWithNulls/524288/2', 'repetitions': 1, 'repetition_index': 0, 'threads': 1, 'iterations': 1750, 'null_percent': 50.0, 'selection_factor': 0.05}
     TakeChunkedChunkedInt64FewRandomIndicesWithNulls/524288/10   1.615G items/sec 549.705M items/sec   -65.960  {'family_index': 0, 'per_family_instance_index': 1, 'run_name': 'TakeChunkedChunkedInt64FewRandomIndicesWithNulls/524288/10', 'repetitions': 1, 'repetition_index': 0, 'threads': 1, 'iterations': 2171, 'null_percent': 10.0, 'selection_factor': 0.05}
        TakeChunkedFlatInt64FewRandomIndicesWithNulls/524288/10   1.709G items/sec 553.717M items/sec   -67.595     {'family_index': 4, 'per_family_instance_index': 1, 'run_name': 'TakeChunkedFlatInt64FewRandomIndicesWithNulls/524288/10', 'repetitions': 1, 'repetition_index': 0, 'threads': 1, 'iterations': 2274, 'null_percent': 10.0, 'selection_factor': 0.05}
   TakeChunkedChunkedInt64FewRandomIndicesWithNulls/524288/1000   2.026G items/sec 587.265M items/sec   -71.021 {'family_index': 0, 'per_family_instance_index': 0, 'run_name': 'TakeChunkedChunkedInt64FewRandomIndicesWithNulls/524288/1000', 'repetitions': 1, 'repetition_index': 0, 'threads': 1, 'iterations': 2670, 'null_percent': 0.1, 'selection_factor': 0.05}
      TakeChunkedFlatInt64FewRandomIndicesWithNulls/524288/1000   2.078G items/sec 588.468M items/sec   -71.680    {'family_index': 4, 'per_family_instance_index': 0, 'run_name': 'TakeChunkedFlatInt64FewRandomIndicesWithNulls/524288/1000', 'repetitions': 1, 'repetition_index': 0, 'threads': 1, 'iterations': 2771, 'null_percent': 0.1, 'selection_factor': 0.05}
      TakeChunkedChunkedInt64FewRandomIndicesWithNulls/524288/0   3.429G items/sec 717.438M items/sec   -79.076    {'family_index': 0, 'per_family_instance_index': 4, 'run_name': 'TakeChunkedChunkedInt64FewRandomIndicesWithNulls/524288/0', 'repetitions': 1, 'repetition_index': 0, 'threads': 1, 'iterations': 4639, 'null_percent': 0.0, 'selection_factor': 0.05}
         TakeChunkedFlatInt64FewRandomIndicesWithNulls/524288/0   3.582G items/sec 721.296M items/sec   -79.861       {'family_index': 4, 'per_family_instance_index': 4, 'run_name': 'TakeChunkedFlatInt64FewRandomIndicesWithNulls/524288/0', 'repetitions': 1, 'repetition_index': 0, 'threads': 1, 'iterations': 4799, 'null_percent': 0.0, 'selection_factor': 0.05}
      TakeChunkedChunkedInt64FewRandomIndicesWithNulls/524288/1   3.873G items/sec 759.915M items/sec   -80.381  {'family_index': 0, 'per_family_instance_index': 3, 'run_name': 'TakeChunkedChunkedInt64FewRandomIndicesWithNulls/524288/1', 'repetitions': 1, 'repetition_index': 0, 'threads': 1, 'iterations': 5316, 'null_percent': 100.0, 'selection_factor': 0.05}
         TakeChunkedFlatInt64FewRandomIndicesWithNulls/524288/1   4.173G items/sec 761.551M items/sec   -81.751     {'family_index': 4, 'per_family_instance_index': 3, 'run_name': 'TakeChunkedFlatInt64FewRandomIndicesWithNulls/524288/1', 'repetitions': 1, 'repetition_index': 0, 'threads': 1, 'iterations': 5385, 'null_percent': 100.0, 'selection_factor': 0.05}
   ```
   
   Putting aside the String perf changes which are minor and probably irrelevant, we can see that on monotonic indices, this PR actually increases performance, while still hurting it on random indices.
   


-- 
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: github-unsubscribe@arrow.apache.org

For queries about this service, please contact Infrastructure at:
users@infra.apache.org


Re: [PR] GH-39565: [C++] Do not concatenate chunked values of fixed-width types to run "array_take" [arrow]

Posted by "pitrou (via GitHub)" <gi...@apache.org>.
pitrou commented on PR #41700:
URL: https://github.com/apache/arrow/pull/41700#issuecomment-2230830712

   Another issue is this reproducer for the C/GLib failures:
   ```python
   >>> i1 = pa.array([1,0], pa.int16())
   >>> i2 = pa.array([2], pa.int16())
   >>> indices = pa.chunked_array([i1, i2])
   >>> pa.array([1,0,2], pa.int16()).take(indices)
   <pyarrow.lib.ChunkedArray object at 0x7fa24b1473d0>
   [
   <Invalid array: Missing values buffer in non-empty fixed-width array>,
   <Invalid array: Missing values buffer in non-empty fixed-width array>
   ]
   ```


-- 
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: github-unsubscribe@arrow.apache.org

For queries about this service, please contact Infrastructure at:
users@infra.apache.org


Re: [PR] GH-39565: [C++] Do not concatenate chunked values of fixed-width types to run "array_take" [arrow]

Posted by "mapleFU (via GitHub)" <gi...@apache.org>.
mapleFU commented on code in PR #41700:
URL: https://github.com/apache/arrow/pull/41700#discussion_r1682064444


##########
cpp/src/arrow/compute/kernels/vector_selection_take_internal.cc:
##########
@@ -715,12 +853,244 @@ class TakeMetaFunction : public MetaFunction {
     return Status::NotImplemented(
         "Unsupported types for take operation: "
         "values=",
-        args[0].ToString(), "indices=", args[1].ToString());
+        args[0].ToString(), ", indices=", args[1].ToString());
   }
 };
 
 // ----------------------------------------------------------------------
 
+/// \brief Prepare the output array like ExecuteArrayKernel::PrepareOutput()
+std::shared_ptr<ArrayData> PrepareOutput(const ExecBatch& batch, int64_t length) {
+  DCHECK_EQ(batch.length, length);
+  auto out = std::make_shared<ArrayData>(batch.values[0].type(), length);
+  out->buffers.resize(batch.values[0].type()->layout().buffers.size());
+  return out;
+}
+
+Result<std::shared_ptr<Array>> ChunkedArrayAsArray(
+    const std::shared_ptr<ChunkedArray>& values, MemoryPool* pool) {
+  switch (values->num_chunks()) {
+    case 0:
+      return MakeArrayOfNull(values->type(), /*length=*/0, pool);
+    case 1:
+      return values->chunk(0);
+    default:
+      return Concatenate(values->chunks(), pool);
+  }
+}
+
+Status CallAAAKernel(ArrayKernelExec take_aaa_exec, KernelContext* ctx,
+                     std::shared_ptr<ArrayData> values,
+                     std::shared_ptr<ArrayData> indices, Datum* out) {
+  int64_t batch_length = values->length;
+  std::vector<Datum> args = {std::move(values), std::move(indices)};
+  ExecBatch array_array_batch(std::move(args), batch_length);
+  DCHECK_EQ(out->kind(), Datum::ARRAY);
+  ExecSpan exec_span{array_array_batch};
+  ExecResult result;
+  result.value = out->array();
+  return take_aaa_exec(ctx, exec_span, &result);
+}
+
+Status CallCAAKernel(VectorKernel::ChunkedExec take_caa_exec, KernelContext* ctx,
+                     std::shared_ptr<ChunkedArray> values,
+                     std::shared_ptr<ArrayData> indices, Datum* out) {
+  int64_t batch_length = values->length();
+  std::vector<Datum> args = {std::move(values), std::move(indices)};
+  ExecBatch chunked_array_array_batch(std::move(args), batch_length);
+  DCHECK_EQ(out->kind(), Datum::ARRAY);
+  return take_caa_exec(ctx, chunked_array_array_batch, out);
+}
+
+Status TakeACCChunkedExec(ArrayKernelExec take_aaa_exec, KernelContext* ctx,
+                          const ExecBatch& batch, Datum* out) {
+  auto& values = batch.values[0].array();
+  auto& indices = batch.values[1].chunked_array();
+  auto num_chunks = indices->num_chunks();
+  std::vector<std::shared_ptr<Array>> new_chunks(num_chunks);
+  for (int i = 0; i < num_chunks; i++) {
+    // Take with that indices chunk
+    auto& indices_chunk = indices->chunk(i)->data();
+    Datum result = PrepareOutput(batch, values->length);
+    RETURN_NOT_OK(CallAAAKernel(take_aaa_exec, ctx, values, indices_chunk, &result));
+    new_chunks[i] = MakeArray(result.array());
+  }
+  out->value = std::make_shared<ChunkedArray>(std::move(new_chunks), values->type);
+  return Status::OK();
+}
+
+/// \brief Generic (slower) VectorKernel::exec_chunked (`CA->C`, `CC->C`, and `AC->C`).
+///
+/// This function concatenates the chunks of the values and then calls the `AA->A` take
+/// kernel to handle the `CA->C` cases. The ArrayData returned by the `AA->A` kernel is
+/// converted to a ChunkedArray with a single chunk to honor the `CA->C` contract.
+///
+/// For `CC->C` cases, it concatenates the chunks of the values and calls the `AA->A` take
+/// kernel for each chunk of the indices, producing a new chunked array with the same
+/// shape as the indices.
+///
+/// `AC->C` cases are trivially delegated to TakeACCChunkedExec without any concatenation.
+///
+/// \param take_aaa_exec The `AA->A` take kernel to use.
+Status GenericTakeChunkedExec(ArrayKernelExec take_aaa_exec, KernelContext* ctx,
+                              const ExecBatch& batch, Datum* out) {
+  const auto& args = batch.values;
+  if (args[0].kind() == Datum::CHUNKED_ARRAY) {
+    auto& values_chunked = args[0].chunked_array();
+    ARROW_ASSIGN_OR_RAISE(auto values_array,
+                          ChunkedArrayAsArray(values_chunked, ctx->memory_pool()));
+    if (args[1].kind() == Datum::ARRAY) {
+      // CA->C
+      auto& indices = args[1].array();
+      DCHECK_EQ(values_array->length(), batch.length);
+      {
+        // AA->A
+        RETURN_NOT_OK(
+            CallAAAKernel(take_aaa_exec, ctx, values_array->data(), indices, out));
+        out->value = std::make_shared<ChunkedArray>(MakeArray(out->array()));
+      }
+      return Status::OK();
+    } else if (args[1].kind() == Datum::CHUNKED_ARRAY) {
+      // CC->C
+      const auto& indices = args[1].chunked_array();
+      std::vector<std::shared_ptr<Array>> new_chunks;
+      for (int i = 0; i < indices->num_chunks(); i++) {
+        // AA->A
+        auto& indices_chunk = indices->chunk(i)->data();
+        Datum result = PrepareOutput(batch, values_array->length());
+        RETURN_NOT_OK(CallAAAKernel(take_aaa_exec, ctx, values_array->data(),
+                                    indices_chunk, &result));
+        new_chunks.push_back(MakeArray(result.array()));
+      }
+      DCHECK(out->is_array());
+      out->value =
+          std::make_shared<ChunkedArray>(std::move(new_chunks), values_chunked->type());
+      return Status::OK();
+    }
+  } else {
+    // VectorKernel::exec_chunked are only called when at least one of the inputs is
+    // chunked, so we should be able to assume that args[1] is a chunked array when
+    // everything is wired up correctly.
+    if (args[1].kind() == Datum::CHUNKED_ARRAY) {
+      // AC->C
+      return TakeACCChunkedExec(take_aaa_exec, ctx, batch, out);
+    } else {
+      DCHECK(false) << "Unexpected kind for array_take's exec_chunked kernel: values="
+                    << args[0].ToString() << ", indices=" << args[1].ToString();
+    }
+  }
+  return Status::NotImplemented(
+      "Unsupported kinds for 'array_take', try using 'take': "
+      "values=",
+      args[0].ToString(), ", indices=", args[1].ToString());
+}
+
+template <ArrayKernelExec kTakeAAAExec>
+struct GenericTakeChunkedExecFunctor {
+  static Status Exec(KernelContext* ctx, const ExecBatch& batch, Datum* out) {
+    return GenericTakeChunkedExec(kTakeAAAExec, ctx, batch, out);
+  }
+};
+
+/// \brief Specialized (faster) VectorKernel::exec_chunked (`CA->C`, `CC->C`, `AC->C`).
+///
+/// This function doesn't ever need to concatenate the chunks of the values, so it can be
+/// more efficient than GenericTakeChunkedExec that can only delegate to the `AA->A` take
+/// kernels.
+///
+/// For `CA->C` cases, it can call the `CA->A` take kernel directly [1] and trivially
+/// convert the result to a ChunkedArray of a single chunk to honor the `CA->C` contract.
+///
+/// For `CC->C` cases it can call the `CA->A` take kernel for each chunk of the indices to
+/// get each chunk that becomes the ChunkedArray output.
+///
+/// `AC->C` cases are trivially delegated to TakeACCChunkedExec.
+///
+/// \param take_aaa_exec The `AA->A` take kernel to use.
+Status SpecialTakeChunkedExec(const ArrayKernelExec take_aaa_exec,
+                              VectorKernel::ChunkedExec take_caa_exec, KernelContext* ctx,
+                              const ExecBatch& batch, Datum* out) {
+  Datum result = PrepareOutput(batch, batch.length);
+  auto* pool = ctx->memory_pool();
+  const auto& args = batch.values;
+  if (args[0].kind() == Datum::CHUNKED_ARRAY) {
+    auto& values_chunked = args[0].chunked_array();
+    std::shared_ptr<Array> single_chunk = nullptr;
+    if (values_chunked->num_chunks() == 0 || values_chunked->length() == 0) {
+      ARROW_ASSIGN_OR_RAISE(single_chunk,
+                            MakeArrayOfNull(values_chunked->type(), /*length=*/0, pool));
+    } else if (values_chunked->num_chunks() == 1) {
+      single_chunk = values_chunked->chunk(0);
+    }
+
+    if (args[1].kind() == Datum::ARRAY) {
+      // CA->C
+      auto& indices = args[1].array();
+      if (single_chunk) {
+        // AA->A
+        DCHECK_EQ(single_chunk->length(), batch.length);
+        // If the ChunkedArray was cheaply converted to a single chunk,
+        // we can use the AA->A take kernel directly.
+        RETURN_NOT_OK(
+            CallAAAKernel(take_aaa_exec, ctx, single_chunk->data(), indices, out));
+        out->value = std::make_shared<ChunkedArray>(MakeArray(out->array()));
+        return Status::OK();
+      }
+      // Instead of concatenating the chunks, we call the CA->A take kernel

Review Comment:
   (So this doesn't call `CallCAAKernel`?)



##########
cpp/src/arrow/compute/kernels/vector_selection_take_internal.cc:
##########
@@ -715,12 +853,244 @@ class TakeMetaFunction : public MetaFunction {
     return Status::NotImplemented(
         "Unsupported types for take operation: "
         "values=",
-        args[0].ToString(), "indices=", args[1].ToString());
+        args[0].ToString(), ", indices=", args[1].ToString());
   }
 };
 
 // ----------------------------------------------------------------------
 
+/// \brief Prepare the output array like ExecuteArrayKernel::PrepareOutput()
+std::shared_ptr<ArrayData> PrepareOutput(const ExecBatch& batch, int64_t length) {
+  DCHECK_EQ(batch.length, length);
+  auto out = std::make_shared<ArrayData>(batch.values[0].type(), length);
+  out->buffers.resize(batch.values[0].type()->layout().buffers.size());
+  return out;
+}
+
+Result<std::shared_ptr<Array>> ChunkedArrayAsArray(
+    const std::shared_ptr<ChunkedArray>& values, MemoryPool* pool) {
+  switch (values->num_chunks()) {
+    case 0:
+      return MakeArrayOfNull(values->type(), /*length=*/0, pool);
+    case 1:
+      return values->chunk(0);
+    default:
+      return Concatenate(values->chunks(), pool);
+  }
+}
+
+Status CallAAAKernel(ArrayKernelExec take_aaa_exec, KernelContext* ctx,
+                     std::shared_ptr<ArrayData> values,
+                     std::shared_ptr<ArrayData> indices, Datum* out) {
+  int64_t batch_length = values->length;
+  std::vector<Datum> args = {std::move(values), std::move(indices)};
+  ExecBatch array_array_batch(std::move(args), batch_length);
+  DCHECK_EQ(out->kind(), Datum::ARRAY);
+  ExecSpan exec_span{array_array_batch};
+  ExecResult result;
+  result.value = out->array();
+  return take_aaa_exec(ctx, exec_span, &result);
+}
+
+Status CallCAAKernel(VectorKernel::ChunkedExec take_caa_exec, KernelContext* ctx,
+                     std::shared_ptr<ChunkedArray> values,
+                     std::shared_ptr<ArrayData> indices, Datum* out) {
+  int64_t batch_length = values->length();
+  std::vector<Datum> args = {std::move(values), std::move(indices)};
+  ExecBatch chunked_array_array_batch(std::move(args), batch_length);
+  DCHECK_EQ(out->kind(), Datum::ARRAY);
+  return take_caa_exec(ctx, chunked_array_array_batch, out);
+}
+
+Status TakeACCChunkedExec(ArrayKernelExec take_aaa_exec, KernelContext* ctx,
+                          const ExecBatch& batch, Datum* out) {
+  auto& values = batch.values[0].array();
+  auto& indices = batch.values[1].chunked_array();
+  auto num_chunks = indices->num_chunks();
+  std::vector<std::shared_ptr<Array>> new_chunks(num_chunks);
+  for (int i = 0; i < num_chunks; i++) {
+    // Take with that indices chunk
+    auto& indices_chunk = indices->chunk(i)->data();
+    Datum result = PrepareOutput(batch, values->length);
+    RETURN_NOT_OK(CallAAAKernel(take_aaa_exec, ctx, values, indices_chunk, &result));
+    new_chunks[i] = MakeArray(result.array());
+  }
+  out->value = std::make_shared<ChunkedArray>(std::move(new_chunks), values->type);
+  return Status::OK();
+}
+
+/// \brief Generic (slower) VectorKernel::exec_chunked (`CA->C`, `CC->C`, and `AC->C`).
+///
+/// This function concatenates the chunks of the values and then calls the `AA->A` take
+/// kernel to handle the `CA->C` cases. The ArrayData returned by the `AA->A` kernel is
+/// converted to a ChunkedArray with a single chunk to honor the `CA->C` contract.
+///
+/// For `CC->C` cases, it concatenates the chunks of the values and calls the `AA->A` take
+/// kernel for each chunk of the indices, producing a new chunked array with the same
+/// shape as the indices.
+///
+/// `AC->C` cases are trivially delegated to TakeACCChunkedExec without any concatenation.
+///
+/// \param take_aaa_exec The `AA->A` take kernel to use.
+Status GenericTakeChunkedExec(ArrayKernelExec take_aaa_exec, KernelContext* ctx,
+                              const ExecBatch& batch, Datum* out) {
+  const auto& args = batch.values;
+  if (args[0].kind() == Datum::CHUNKED_ARRAY) {
+    auto& values_chunked = args[0].chunked_array();
+    ARROW_ASSIGN_OR_RAISE(auto values_array,
+                          ChunkedArrayAsArray(values_chunked, ctx->memory_pool()));
+    if (args[1].kind() == Datum::ARRAY) {
+      // CA->C
+      auto& indices = args[1].array();
+      DCHECK_EQ(values_array->length(), batch.length);
+      {
+        // AA->A
+        RETURN_NOT_OK(
+            CallAAAKernel(take_aaa_exec, ctx, values_array->data(), indices, out));
+        out->value = std::make_shared<ChunkedArray>(MakeArray(out->array()));
+      }
+      return Status::OK();
+    } else if (args[1].kind() == Datum::CHUNKED_ARRAY) {
+      // CC->C
+      const auto& indices = args[1].chunked_array();
+      std::vector<std::shared_ptr<Array>> new_chunks;
+      for (int i = 0; i < indices->num_chunks(); i++) {
+        // AA->A
+        auto& indices_chunk = indices->chunk(i)->data();
+        Datum result = PrepareOutput(batch, values_array->length());
+        RETURN_NOT_OK(CallAAAKernel(take_aaa_exec, ctx, values_array->data(),
+                                    indices_chunk, &result));
+        new_chunks.push_back(MakeArray(result.array()));
+      }
+      DCHECK(out->is_array());
+      out->value =
+          std::make_shared<ChunkedArray>(std::move(new_chunks), values_chunked->type());
+      return Status::OK();
+    }
+  } else {
+    // VectorKernel::exec_chunked are only called when at least one of the inputs is
+    // chunked, so we should be able to assume that args[1] is a chunked array when
+    // everything is wired up correctly.
+    if (args[1].kind() == Datum::CHUNKED_ARRAY) {
+      // AC->C
+      return TakeACCChunkedExec(take_aaa_exec, ctx, batch, out);
+    } else {
+      DCHECK(false) << "Unexpected kind for array_take's exec_chunked kernel: values="
+                    << args[0].ToString() << ", indices=" << args[1].ToString();
+    }
+  }
+  return Status::NotImplemented(
+      "Unsupported kinds for 'array_take', try using 'take': "
+      "values=",
+      args[0].ToString(), ", indices=", args[1].ToString());
+}
+
+template <ArrayKernelExec kTakeAAAExec>
+struct GenericTakeChunkedExecFunctor {
+  static Status Exec(KernelContext* ctx, const ExecBatch& batch, Datum* out) {
+    return GenericTakeChunkedExec(kTakeAAAExec, ctx, batch, out);
+  }
+};
+
+/// \brief Specialized (faster) VectorKernel::exec_chunked (`CA->C`, `CC->C`, `AC->C`).
+///
+/// This function doesn't ever need to concatenate the chunks of the values, so it can be
+/// more efficient than GenericTakeChunkedExec that can only delegate to the `AA->A` take
+/// kernels.
+///
+/// For `CA->C` cases, it can call the `CA->A` take kernel directly [1] and trivially
+/// convert the result to a ChunkedArray of a single chunk to honor the `CA->C` contract.
+///
+/// For `CC->C` cases it can call the `CA->A` take kernel for each chunk of the indices to
+/// get each chunk that becomes the ChunkedArray output.
+///
+/// `AC->C` cases are trivially delegated to TakeACCChunkedExec.
+///
+/// \param take_aaa_exec The `AA->A` take kernel to use.
+Status SpecialTakeChunkedExec(const ArrayKernelExec take_aaa_exec,
+                              VectorKernel::ChunkedExec take_caa_exec, KernelContext* ctx,
+                              const ExecBatch& batch, Datum* out) {
+  Datum result = PrepareOutput(batch, batch.length);
+  auto* pool = ctx->memory_pool();
+  const auto& args = batch.values;
+  if (args[0].kind() == Datum::CHUNKED_ARRAY) {
+    auto& values_chunked = args[0].chunked_array();
+    std::shared_ptr<Array> single_chunk = nullptr;
+    if (values_chunked->num_chunks() == 0 || values_chunked->length() == 0) {
+      ARROW_ASSIGN_OR_RAISE(single_chunk,
+                            MakeArrayOfNull(values_chunked->type(), /*length=*/0, pool));
+    } else if (values_chunked->num_chunks() == 1) {
+      single_chunk = values_chunked->chunk(0);
+    }
+
+    if (args[1].kind() == Datum::ARRAY) {
+      // CA->C
+      auto& indices = args[1].array();
+      if (single_chunk) {
+        // AA->A
+        DCHECK_EQ(single_chunk->length(), batch.length);
+        // If the ChunkedArray was cheaply converted to a single chunk,
+        // we can use the AA->A take kernel directly.
+        RETURN_NOT_OK(
+            CallAAAKernel(take_aaa_exec, ctx, single_chunk->data(), indices, out));
+        out->value = std::make_shared<ChunkedArray>(MakeArray(out->array()));
+        return Status::OK();
+      }
+      // Instead of concatenating the chunks, we call the CA->A take kernel
+      // which has a more efficient implementation for this case. At this point,
+      // that implementation doesn't have to care about empty or single-chunk
+      // ChunkedArrays.
+      RETURN_NOT_OK(take_caa_exec(ctx, batch, &result));
+      out->value = std::make_shared<ChunkedArray>(MakeArray(result.array()));
+      return Status::OK();
+    } else {
+      // CC->C
+      const auto& indices = args[1].chunked_array();
+      std::vector<std::shared_ptr<Array>> new_chunks;
+      for (int i = 0; i < indices->num_chunks(); i++) {
+        auto& indices_chunk = indices->chunk(i)->data();
+        result = PrepareOutput(batch, values_chunked->length());
+        if (single_chunk) {
+          // If the ChunkedArray was cheaply converted to a single chunk,
+          // we can use the AA->A take kernel directly.
+          RETURN_NOT_OK(CallAAAKernel(take_aaa_exec, ctx, single_chunk->data(),
+                                      indices_chunk, &result));
+        } else {
+          RETURN_NOT_OK(
+              CallCAAKernel(take_caa_exec, ctx, values_chunked, indices_chunk, &result));
+        }
+        new_chunks.push_back(MakeArray(result.array()));
+      }
+      DCHECK(out->is_array());
+      out->value =
+          std::make_shared<ChunkedArray>(std::move(new_chunks), values_chunked->type());
+      return Status::OK();
+    }
+  } else {
+    // VectorKernel::exec_chunked are only called when at least one of the inputs is
+    // chunked, so we should be able to assume that args[1] is a chunked array when
+    // everything is wired up correctly.
+    if (args[1].kind() == Datum::CHUNKED_ARRAY) {
+      // AC->C
+      return TakeACCChunkedExec(take_aaa_exec, ctx, batch, out);
+    } else {
+      DCHECK(false) << "Unexpected kind for array_take's exec_chunked kernel: values="
+                    << args[0].ToString() << ", indices=" << args[1].ToString();
+    }
+  }
+  return Status::NotImplemented(
+      "Unsupported kinds for 'array_take', try using 'take': "
+      "values=",
+      args[0].ToString(), ", indices=", args[1].ToString());
+}
+
+template <ArrayKernelExec kTakeAAAExec, VectorKernel::ChunkedExec kTakeCAAExec>

Review Comment:
   Why is template used here since it delegate implement to SpecialTakeChunkedExec directly?



##########
cpp/src/arrow/compute/kernels/vector_selection_take_internal.cc:
##########
@@ -715,12 +853,244 @@ class TakeMetaFunction : public MetaFunction {
     return Status::NotImplemented(
         "Unsupported types for take operation: "
         "values=",
-        args[0].ToString(), "indices=", args[1].ToString());
+        args[0].ToString(), ", indices=", args[1].ToString());
   }
 };
 
 // ----------------------------------------------------------------------
 
+/// \brief Prepare the output array like ExecuteArrayKernel::PrepareOutput()
+std::shared_ptr<ArrayData> PrepareOutput(const ExecBatch& batch, int64_t length) {
+  DCHECK_EQ(batch.length, length);
+  auto out = std::make_shared<ArrayData>(batch.values[0].type(), length);
+  out->buffers.resize(batch.values[0].type()->layout().buffers.size());
+  return out;
+}
+
+Result<std::shared_ptr<Array>> ChunkedArrayAsArray(
+    const std::shared_ptr<ChunkedArray>& values, MemoryPool* pool) {
+  switch (values->num_chunks()) {
+    case 0:
+      return MakeArrayOfNull(values->type(), /*length=*/0, pool);
+    case 1:
+      return values->chunk(0);
+    default:
+      return Concatenate(values->chunks(), pool);
+  }
+}
+
+Status CallAAAKernel(ArrayKernelExec take_aaa_exec, KernelContext* ctx,
+                     std::shared_ptr<ArrayData> values,
+                     std::shared_ptr<ArrayData> indices, Datum* out) {
+  int64_t batch_length = values->length;
+  std::vector<Datum> args = {std::move(values), std::move(indices)};
+  ExecBatch array_array_batch(std::move(args), batch_length);
+  DCHECK_EQ(out->kind(), Datum::ARRAY);
+  ExecSpan exec_span{array_array_batch};
+  ExecResult result;
+  result.value = out->array();
+  return take_aaa_exec(ctx, exec_span, &result);
+}
+
+Status CallCAAKernel(VectorKernel::ChunkedExec take_caa_exec, KernelContext* ctx,
+                     std::shared_ptr<ChunkedArray> values,
+                     std::shared_ptr<ArrayData> indices, Datum* out) {
+  int64_t batch_length = values->length();
+  std::vector<Datum> args = {std::move(values), std::move(indices)};
+  ExecBatch chunked_array_array_batch(std::move(args), batch_length);
+  DCHECK_EQ(out->kind(), Datum::ARRAY);
+  return take_caa_exec(ctx, chunked_array_array_batch, out);
+}
+
+Status TakeACCChunkedExec(ArrayKernelExec take_aaa_exec, KernelContext* ctx,
+                          const ExecBatch& batch, Datum* out) {
+  auto& values = batch.values[0].array();
+  auto& indices = batch.values[1].chunked_array();
+  auto num_chunks = indices->num_chunks();
+  std::vector<std::shared_ptr<Array>> new_chunks(num_chunks);
+  for (int i = 0; i < num_chunks; i++) {
+    // Take with that indices chunk
+    auto& indices_chunk = indices->chunk(i)->data();
+    Datum result = PrepareOutput(batch, values->length);
+    RETURN_NOT_OK(CallAAAKernel(take_aaa_exec, ctx, values, indices_chunk, &result));
+    new_chunks[i] = MakeArray(result.array());
+  }
+  out->value = std::make_shared<ChunkedArray>(std::move(new_chunks), values->type);
+  return Status::OK();
+}
+
+/// \brief Generic (slower) VectorKernel::exec_chunked (`CA->C`, `CC->C`, and `AC->C`).
+///
+/// This function concatenates the chunks of the values and then calls the `AA->A` take
+/// kernel to handle the `CA->C` cases. The ArrayData returned by the `AA->A` kernel is
+/// converted to a ChunkedArray with a single chunk to honor the `CA->C` contract.
+///
+/// For `CC->C` cases, it concatenates the chunks of the values and calls the `AA->A` take
+/// kernel for each chunk of the indices, producing a new chunked array with the same
+/// shape as the indices.
+///
+/// `AC->C` cases are trivially delegated to TakeACCChunkedExec without any concatenation.
+///
+/// \param take_aaa_exec The `AA->A` take kernel to use.
+Status GenericTakeChunkedExec(ArrayKernelExec take_aaa_exec, KernelContext* ctx,
+                              const ExecBatch& batch, Datum* out) {
+  const auto& args = batch.values;
+  if (args[0].kind() == Datum::CHUNKED_ARRAY) {
+    auto& values_chunked = args[0].chunked_array();
+    ARROW_ASSIGN_OR_RAISE(auto values_array,
+                          ChunkedArrayAsArray(values_chunked, ctx->memory_pool()));
+    if (args[1].kind() == Datum::ARRAY) {
+      // CA->C
+      auto& indices = args[1].array();
+      DCHECK_EQ(values_array->length(), batch.length);
+      {
+        // AA->A
+        RETURN_NOT_OK(
+            CallAAAKernel(take_aaa_exec, ctx, values_array->data(), indices, out));
+        out->value = std::make_shared<ChunkedArray>(MakeArray(out->array()));
+      }
+      return Status::OK();
+    } else if (args[1].kind() == Datum::CHUNKED_ARRAY) {
+      // CC->C
+      const auto& indices = args[1].chunked_array();
+      std::vector<std::shared_ptr<Array>> new_chunks;
+      for (int i = 0; i < indices->num_chunks(); i++) {
+        // AA->A
+        auto& indices_chunk = indices->chunk(i)->data();
+        Datum result = PrepareOutput(batch, values_array->length());
+        RETURN_NOT_OK(CallAAAKernel(take_aaa_exec, ctx, values_array->data(),
+                                    indices_chunk, &result));
+        new_chunks.push_back(MakeArray(result.array()));
+      }
+      DCHECK(out->is_array());
+      out->value =
+          std::make_shared<ChunkedArray>(std::move(new_chunks), values_chunked->type());
+      return Status::OK();
+    }
+  } else {
+    // VectorKernel::exec_chunked are only called when at least one of the inputs is
+    // chunked, so we should be able to assume that args[1] is a chunked array when
+    // everything is wired up correctly.
+    if (args[1].kind() == Datum::CHUNKED_ARRAY) {
+      // AC->C
+      return TakeACCChunkedExec(take_aaa_exec, ctx, batch, out);
+    } else {
+      DCHECK(false) << "Unexpected kind for array_take's exec_chunked kernel: values="
+                    << args[0].ToString() << ", indices=" << args[1].ToString();
+    }
+  }
+  return Status::NotImplemented(
+      "Unsupported kinds for 'array_take', try using 'take': "
+      "values=",
+      args[0].ToString(), ", indices=", args[1].ToString());
+}
+
+template <ArrayKernelExec kTakeAAAExec>
+struct GenericTakeChunkedExecFunctor {
+  static Status Exec(KernelContext* ctx, const ExecBatch& batch, Datum* out) {
+    return GenericTakeChunkedExec(kTakeAAAExec, ctx, batch, out);
+  }
+};
+
+/// \brief Specialized (faster) VectorKernel::exec_chunked (`CA->C`, `CC->C`, `AC->C`).
+///
+/// This function doesn't ever need to concatenate the chunks of the values, so it can be
+/// more efficient than GenericTakeChunkedExec that can only delegate to the `AA->A` take
+/// kernels.
+///
+/// For `CA->C` cases, it can call the `CA->A` take kernel directly [1] and trivially
+/// convert the result to a ChunkedArray of a single chunk to honor the `CA->C` contract.
+///
+/// For `CC->C` cases it can call the `CA->A` take kernel for each chunk of the indices to
+/// get each chunk that becomes the ChunkedArray output.
+///
+/// `AC->C` cases are trivially delegated to TakeACCChunkedExec.
+///
+/// \param take_aaa_exec The `AA->A` take kernel to use.
+Status SpecialTakeChunkedExec(const ArrayKernelExec take_aaa_exec,
+                              VectorKernel::ChunkedExec take_caa_exec, KernelContext* ctx,
+                              const ExecBatch& batch, Datum* out) {
+  Datum result = PrepareOutput(batch, batch.length);
+  auto* pool = ctx->memory_pool();
+  const auto& args = batch.values;
+  if (args[0].kind() == Datum::CHUNKED_ARRAY) {
+    auto& values_chunked = args[0].chunked_array();
+    std::shared_ptr<Array> single_chunk = nullptr;
+    if (values_chunked->num_chunks() == 0 || values_chunked->length() == 0) {
+      ARROW_ASSIGN_OR_RAISE(single_chunk,
+                            MakeArrayOfNull(values_chunked->type(), /*length=*/0, pool));
+    } else if (values_chunked->num_chunks() == 1) {
+      single_chunk = values_chunked->chunk(0);
+    }
+
+    if (args[1].kind() == Datum::ARRAY) {
+      // CA->C
+      auto& indices = args[1].array();
+      if (single_chunk) {
+        // AA->A
+        DCHECK_EQ(single_chunk->length(), batch.length);
+        // If the ChunkedArray was cheaply converted to a single chunk,
+        // we can use the AA->A take kernel directly.
+        RETURN_NOT_OK(
+            CallAAAKernel(take_aaa_exec, ctx, single_chunk->data(), indices, out));
+        out->value = std::make_shared<ChunkedArray>(MakeArray(out->array()));
+        return Status::OK();
+      }
+      // Instead of concatenating the chunks, we call the CA->A take kernel
+      // which has a more efficient implementation for this case. At this point,
+      // that implementation doesn't have to care about empty or single-chunk
+      // ChunkedArrays.
+      RETURN_NOT_OK(take_caa_exec(ctx, batch, &result));
+      out->value = std::make_shared<ChunkedArray>(MakeArray(result.array()));
+      return Status::OK();
+    } else {
+      // CC->C
+      const auto& indices = args[1].chunked_array();
+      std::vector<std::shared_ptr<Array>> new_chunks;
+      for (int i = 0; i < indices->num_chunks(); i++) {
+        auto& indices_chunk = indices->chunk(i)->data();
+        result = PrepareOutput(batch, values_chunked->length());
+        if (single_chunk) {
+          // If the ChunkedArray was cheaply converted to a single chunk,
+          // we can use the AA->A take kernel directly.
+          RETURN_NOT_OK(CallAAAKernel(take_aaa_exec, ctx, single_chunk->data(),
+                                      indices_chunk, &result));
+        } else {
+          RETURN_NOT_OK(
+              CallCAAKernel(take_caa_exec, ctx, values_chunked, indices_chunk, &result));
+        }
+        new_chunks.push_back(MakeArray(result.array()));
+      }
+      DCHECK(out->is_array());
+      out->value =
+          std::make_shared<ChunkedArray>(std::move(new_chunks), values_chunked->type());
+      return Status::OK();
+    }
+  } else {
+    // VectorKernel::exec_chunked are only called when at least one of the inputs is
+    // chunked, so we should be able to assume that args[1] is a chunked array when
+    // everything is wired up correctly.
+    if (args[1].kind() == Datum::CHUNKED_ARRAY) {
+      // AC->C
+      return TakeACCChunkedExec(take_aaa_exec, ctx, batch, out);
+    } else {
+      DCHECK(false) << "Unexpected kind for array_take's exec_chunked kernel: values="
+                    << args[0].ToString() << ", indices=" << args[1].ToString();
+    }
+  }
+  return Status::NotImplemented(
+      "Unsupported kinds for 'array_take', try using 'take': "
+      "values=",
+      args[0].ToString(), ", indices=", args[1].ToString());

Review Comment:
   Do we need just change the `Datum::Kind` to string rather than dump a huge object including it contents here?



-- 
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: github-unsubscribe@arrow.apache.org

For queries about this service, please contact Infrastructure at:
users@infra.apache.org


Re: [PR] GH-39565: [C++] Do not concatenate chunked values of fixed-width types to run "array_take" [arrow]

Posted by "mapleFU (via GitHub)" <gi...@apache.org>.
mapleFU commented on code in PR #41700:
URL: https://github.com/apache/arrow/pull/41700#discussion_r1682078031


##########
cpp/src/arrow/compute/kernels/vector_selection_take_internal.cc:
##########
@@ -715,12 +853,244 @@ class TakeMetaFunction : public MetaFunction {
     return Status::NotImplemented(
         "Unsupported types for take operation: "
         "values=",
-        args[0].ToString(), "indices=", args[1].ToString());
+        args[0].ToString(), ", indices=", args[1].ToString());
   }
 };
 
 // ----------------------------------------------------------------------
 
+/// \brief Prepare the output array like ExecuteArrayKernel::PrepareOutput()
+std::shared_ptr<ArrayData> PrepareOutput(const ExecBatch& batch, int64_t length) {
+  DCHECK_EQ(batch.length, length);
+  auto out = std::make_shared<ArrayData>(batch.values[0].type(), length);
+  out->buffers.resize(batch.values[0].type()->layout().buffers.size());
+  return out;
+}
+
+Result<std::shared_ptr<Array>> ChunkedArrayAsArray(
+    const std::shared_ptr<ChunkedArray>& values, MemoryPool* pool) {
+  switch (values->num_chunks()) {
+    case 0:
+      return MakeArrayOfNull(values->type(), /*length=*/0, pool);
+    case 1:
+      return values->chunk(0);
+    default:
+      return Concatenate(values->chunks(), pool);
+  }
+}
+
+Status CallAAAKernel(ArrayKernelExec take_aaa_exec, KernelContext* ctx,
+                     std::shared_ptr<ArrayData> values,
+                     std::shared_ptr<ArrayData> indices, Datum* out) {
+  int64_t batch_length = values->length;
+  std::vector<Datum> args = {std::move(values), std::move(indices)};
+  ExecBatch array_array_batch(std::move(args), batch_length);
+  DCHECK_EQ(out->kind(), Datum::ARRAY);
+  ExecSpan exec_span{array_array_batch};
+  ExecResult result;
+  result.value = out->array();
+  return take_aaa_exec(ctx, exec_span, &result);
+}
+
+Status CallCAAKernel(VectorKernel::ChunkedExec take_caa_exec, KernelContext* ctx,
+                     std::shared_ptr<ChunkedArray> values,
+                     std::shared_ptr<ArrayData> indices, Datum* out) {
+  int64_t batch_length = values->length();
+  std::vector<Datum> args = {std::move(values), std::move(indices)};
+  ExecBatch chunked_array_array_batch(std::move(args), batch_length);
+  DCHECK_EQ(out->kind(), Datum::ARRAY);
+  return take_caa_exec(ctx, chunked_array_array_batch, out);
+}
+
+Status TakeACCChunkedExec(ArrayKernelExec take_aaa_exec, KernelContext* ctx,
+                          const ExecBatch& batch, Datum* out) {
+  auto& values = batch.values[0].array();
+  auto& indices = batch.values[1].chunked_array();
+  auto num_chunks = indices->num_chunks();
+  std::vector<std::shared_ptr<Array>> new_chunks(num_chunks);
+  for (int i = 0; i < num_chunks; i++) {
+    // Take with that indices chunk
+    auto& indices_chunk = indices->chunk(i)->data();
+    Datum result = PrepareOutput(batch, values->length);
+    RETURN_NOT_OK(CallAAAKernel(take_aaa_exec, ctx, values, indices_chunk, &result));
+    new_chunks[i] = MakeArray(result.array());
+  }
+  out->value = std::make_shared<ChunkedArray>(std::move(new_chunks), values->type);
+  return Status::OK();
+}
+
+/// \brief Generic (slower) VectorKernel::exec_chunked (`CA->C`, `CC->C`, and `AC->C`).

Review Comment:
   So, the Generic (slower) one would also change the `args[0]` to array



-- 
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: github-unsubscribe@arrow.apache.org

For queries about this service, please contact Infrastructure at:
users@infra.apache.org


Re: [PR] GH-39565: [C++] Do not concatenate chunked values of fixed-width types to run "array_take" [arrow]

Posted by "felipecrv (via GitHub)" <gi...@apache.org>.
felipecrv commented on code in PR #41700:
URL: https://github.com/apache/arrow/pull/41700#discussion_r1723520874


##########
cpp/src/arrow/compute/kernels/vector_selection_take_internal.cc:
##########
@@ -395,10 +526,45 @@ struct FixedWidthTakeImpl {
     out_arr->null_count = out_arr->length - valid_count;
     return Status::OK();
   }
+
+  static Status ChunkedExec(KernelContext* ctx, const ChunkedArray& values,
+                            const ArraySpan& indices, ArrayData* out_arr,
+                            int64_t factor) {
+    const bool out_has_validity = values.null_count() > 0 || indices.MayHaveNulls();

Review Comment:
   `SpecialTakeChunkedExec` takes care of this. Look for the `single_chunk` variable. It will call `take_aaa_exec` instead of `take_caa_exec` and then produce a chunked array output with a single chunk.



-- 
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: github-unsubscribe@arrow.apache.org

For queries about this service, please contact Infrastructure at:
users@infra.apache.org


Re: [PR] GH-39565: [C++] Do not concatenate chunked values of fixed-width types to run "array_take" [arrow]

Posted by "felipecrv (via GitHub)" <gi...@apache.org>.
felipecrv commented on code in PR #41700:
URL: https://github.com/apache/arrow/pull/41700#discussion_r1723502720


##########
cpp/src/arrow/compute/kernels/vector_selection_take_internal.cc:
##########
@@ -736,22 +1109,40 @@ void PopulateTakeKernels(std::vector<SelectionKernelData>* out) {
   auto take_indices = match::Integer();
 
   *out = {
-      {InputType(match::Primitive()), take_indices, FixedWidthTakeExec},
-      {InputType(match::BinaryLike()), take_indices, VarBinaryTakeExec},
-      {InputType(match::LargeBinaryLike()), take_indices, LargeVarBinaryTakeExec},
-      {InputType(match::FixedSizeBinaryLike()), take_indices, FixedWidthTakeExec},
-      {InputType(null()), take_indices, NullTakeExec},
-      {InputType(Type::DICTIONARY), take_indices, DictionaryTake},
-      {InputType(Type::EXTENSION), take_indices, ExtensionTake},
-      {InputType(Type::LIST), take_indices, ListTakeExec},
-      {InputType(Type::LARGE_LIST), take_indices, LargeListTakeExec},
-      {InputType(Type::LIST_VIEW), take_indices, ListViewTakeExec},
-      {InputType(Type::LARGE_LIST_VIEW), take_indices, LargeListViewTakeExec},
-      {InputType(Type::FIXED_SIZE_LIST), take_indices, FSLTakeExec},
-      {InputType(Type::DENSE_UNION), take_indices, DenseUnionTakeExec},
-      {InputType(Type::SPARSE_UNION), take_indices, SparseUnionTakeExec},
-      {InputType(Type::STRUCT), take_indices, StructTakeExec},
-      {InputType(Type::MAP), take_indices, MapTakeExec},
+      {InputType(match::Primitive()), take_indices, FixedWidthTakeExec,
+       SpecialTakeChunkedExecFunctor<FixedWidthTakeExec,
+                                     FixedWidthTakeChunkedExec>::Exec},
+      {InputType(match::BinaryLike()), take_indices, VarBinaryTakeExec,
+       GenericTakeChunkedExecFunctor<VarBinaryTakeExec>::Exec},
+      {InputType(match::LargeBinaryLike()), take_indices, LargeVarBinaryTakeExec,
+       GenericTakeChunkedExecFunctor<LargeVarBinaryTakeExec>::Exec},
+      {InputType(match::FixedSizeBinaryLike()), take_indices, FixedWidthTakeExec,
+       SpecialTakeChunkedExecFunctor<FixedWidthTakeExec,
+                                     FixedWidthTakeChunkedExec>::Exec},
+      {InputType(null()), take_indices, NullTakeExec,
+       GenericTakeChunkedExecFunctor<NullTakeExec>::Exec},

Review Comment:
   https://github.com/apache/arrow/pull/41700#discussion_r1723501931



-- 
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: github-unsubscribe@arrow.apache.org

For queries about this service, please contact Infrastructure at:
users@infra.apache.org


Re: [PR] GH-39565: [C++] Do not concatenate chunked values of fixed-width types to run "array_take" [arrow]

Posted by "github-actions[bot] (via GitHub)" <gi...@apache.org>.
github-actions[bot] closed pull request #41700: GH-39565: [C++] Do not concatenate chunked values of fixed-width types to run "array_take"
URL: https://github.com/apache/arrow/pull/41700


-- 
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: github-unsubscribe@arrow.apache.org

For queries about this service, please contact Infrastructure at:
users@infra.apache.org


Re: [PR] GH-39565: [C++] Do not concatenate chunked values of fixed-width types to run "array_take" [arrow]

Posted by "felipecrv (via GitHub)" <gi...@apache.org>.
felipecrv commented on code in PR #41700:
URL: https://github.com/apache/arrow/pull/41700#discussion_r1685744803


##########
cpp/src/arrow/compute/kernels/vector_selection_take_internal.cc:
##########
@@ -715,12 +853,244 @@ class TakeMetaFunction : public MetaFunction {
     return Status::NotImplemented(
         "Unsupported types for take operation: "
         "values=",
-        args[0].ToString(), "indices=", args[1].ToString());
+        args[0].ToString(), ", indices=", args[1].ToString());
   }
 };
 
 // ----------------------------------------------------------------------
 
+/// \brief Prepare the output array like ExecuteArrayKernel::PrepareOutput()
+std::shared_ptr<ArrayData> PrepareOutput(const ExecBatch& batch, int64_t length) {
+  DCHECK_EQ(batch.length, length);
+  auto out = std::make_shared<ArrayData>(batch.values[0].type(), length);
+  out->buffers.resize(batch.values[0].type()->layout().buffers.size());
+  return out;
+}
+
+Result<std::shared_ptr<Array>> ChunkedArrayAsArray(
+    const std::shared_ptr<ChunkedArray>& values, MemoryPool* pool) {
+  switch (values->num_chunks()) {
+    case 0:
+      return MakeArrayOfNull(values->type(), /*length=*/0, pool);
+    case 1:
+      return values->chunk(0);
+    default:
+      return Concatenate(values->chunks(), pool);
+  }
+}
+
+Status CallAAAKernel(ArrayKernelExec take_aaa_exec, KernelContext* ctx,
+                     std::shared_ptr<ArrayData> values,
+                     std::shared_ptr<ArrayData> indices, Datum* out) {
+  int64_t batch_length = values->length;
+  std::vector<Datum> args = {std::move(values), std::move(indices)};
+  ExecBatch array_array_batch(std::move(args), batch_length);
+  DCHECK_EQ(out->kind(), Datum::ARRAY);
+  ExecSpan exec_span{array_array_batch};
+  ExecResult result;
+  result.value = out->array();
+  return take_aaa_exec(ctx, exec_span, &result);
+}
+
+Status CallCAAKernel(VectorKernel::ChunkedExec take_caa_exec, KernelContext* ctx,
+                     std::shared_ptr<ChunkedArray> values,
+                     std::shared_ptr<ArrayData> indices, Datum* out) {
+  int64_t batch_length = values->length();
+  std::vector<Datum> args = {std::move(values), std::move(indices)};
+  ExecBatch chunked_array_array_batch(std::move(args), batch_length);
+  DCHECK_EQ(out->kind(), Datum::ARRAY);
+  return take_caa_exec(ctx, chunked_array_array_batch, out);
+}
+
+Status TakeACCChunkedExec(ArrayKernelExec take_aaa_exec, KernelContext* ctx,
+                          const ExecBatch& batch, Datum* out) {
+  auto& values = batch.values[0].array();
+  auto& indices = batch.values[1].chunked_array();
+  auto num_chunks = indices->num_chunks();
+  std::vector<std::shared_ptr<Array>> new_chunks(num_chunks);
+  for (int i = 0; i < num_chunks; i++) {
+    // Take with that indices chunk
+    auto& indices_chunk = indices->chunk(i)->data();
+    Datum result = PrepareOutput(batch, values->length);
+    RETURN_NOT_OK(CallAAAKernel(take_aaa_exec, ctx, values, indices_chunk, &result));
+    new_chunks[i] = MakeArray(result.array());
+  }
+  out->value = std::make_shared<ChunkedArray>(std::move(new_chunks), values->type);
+  return Status::OK();
+}
+
+/// \brief Generic (slower) VectorKernel::exec_chunked (`CA->C`, `CC->C`, and `AC->C`).
+///
+/// This function concatenates the chunks of the values and then calls the `AA->A` take
+/// kernel to handle the `CA->C` cases. The ArrayData returned by the `AA->A` kernel is
+/// converted to a ChunkedArray with a single chunk to honor the `CA->C` contract.
+///
+/// For `CC->C` cases, it concatenates the chunks of the values and calls the `AA->A` take
+/// kernel for each chunk of the indices, producing a new chunked array with the same
+/// shape as the indices.
+///
+/// `AC->C` cases are trivially delegated to TakeACCChunkedExec without any concatenation.
+///
+/// \param take_aaa_exec The `AA->A` take kernel to use.
+Status GenericTakeChunkedExec(ArrayKernelExec take_aaa_exec, KernelContext* ctx,
+                              const ExecBatch& batch, Datum* out) {
+  const auto& args = batch.values;
+  if (args[0].kind() == Datum::CHUNKED_ARRAY) {
+    auto& values_chunked = args[0].chunked_array();
+    ARROW_ASSIGN_OR_RAISE(auto values_array,
+                          ChunkedArrayAsArray(values_chunked, ctx->memory_pool()));
+    if (args[1].kind() == Datum::ARRAY) {
+      // CA->C
+      auto& indices = args[1].array();
+      DCHECK_EQ(values_array->length(), batch.length);
+      {
+        // AA->A
+        RETURN_NOT_OK(
+            CallAAAKernel(take_aaa_exec, ctx, values_array->data(), indices, out));
+        out->value = std::make_shared<ChunkedArray>(MakeArray(out->array()));
+      }
+      return Status::OK();
+    } else if (args[1].kind() == Datum::CHUNKED_ARRAY) {
+      // CC->C
+      const auto& indices = args[1].chunked_array();
+      std::vector<std::shared_ptr<Array>> new_chunks;
+      for (int i = 0; i < indices->num_chunks(); i++) {
+        // AA->A
+        auto& indices_chunk = indices->chunk(i)->data();
+        Datum result = PrepareOutput(batch, values_array->length());
+        RETURN_NOT_OK(CallAAAKernel(take_aaa_exec, ctx, values_array->data(),
+                                    indices_chunk, &result));
+        new_chunks.push_back(MakeArray(result.array()));
+      }
+      DCHECK(out->is_array());
+      out->value =
+          std::make_shared<ChunkedArray>(std::move(new_chunks), values_chunked->type());
+      return Status::OK();
+    }
+  } else {
+    // VectorKernel::exec_chunked are only called when at least one of the inputs is
+    // chunked, so we should be able to assume that args[1] is a chunked array when
+    // everything is wired up correctly.
+    if (args[1].kind() == Datum::CHUNKED_ARRAY) {
+      // AC->C
+      return TakeACCChunkedExec(take_aaa_exec, ctx, batch, out);
+    } else {
+      DCHECK(false) << "Unexpected kind for array_take's exec_chunked kernel: values="
+                    << args[0].ToString() << ", indices=" << args[1].ToString();
+    }
+  }
+  return Status::NotImplemented(
+      "Unsupported kinds for 'array_take', try using 'take': "
+      "values=",
+      args[0].ToString(), ", indices=", args[1].ToString());
+}
+
+template <ArrayKernelExec kTakeAAAExec>
+struct GenericTakeChunkedExecFunctor {
+  static Status Exec(KernelContext* ctx, const ExecBatch& batch, Datum* out) {
+    return GenericTakeChunkedExec(kTakeAAAExec, ctx, batch, out);
+  }
+};
+
+/// \brief Specialized (faster) VectorKernel::exec_chunked (`CA->C`, `CC->C`, `AC->C`).
+///
+/// This function doesn't ever need to concatenate the chunks of the values, so it can be
+/// more efficient than GenericTakeChunkedExec that can only delegate to the `AA->A` take
+/// kernels.
+///
+/// For `CA->C` cases, it can call the `CA->A` take kernel directly [1] and trivially
+/// convert the result to a ChunkedArray of a single chunk to honor the `CA->C` contract.
+///
+/// For `CC->C` cases it can call the `CA->A` take kernel for each chunk of the indices to
+/// get each chunk that becomes the ChunkedArray output.
+///
+/// `AC->C` cases are trivially delegated to TakeACCChunkedExec.
+///
+/// \param take_aaa_exec The `AA->A` take kernel to use.
+Status SpecialTakeChunkedExec(const ArrayKernelExec take_aaa_exec,
+                              VectorKernel::ChunkedExec take_caa_exec, KernelContext* ctx,
+                              const ExecBatch& batch, Datum* out) {
+  Datum result = PrepareOutput(batch, batch.length);
+  auto* pool = ctx->memory_pool();
+  const auto& args = batch.values;
+  if (args[0].kind() == Datum::CHUNKED_ARRAY) {
+    auto& values_chunked = args[0].chunked_array();
+    std::shared_ptr<Array> single_chunk = nullptr;
+    if (values_chunked->num_chunks() == 0 || values_chunked->length() == 0) {
+      ARROW_ASSIGN_OR_RAISE(single_chunk,
+                            MakeArrayOfNull(values_chunked->type(), /*length=*/0, pool));
+    } else if (values_chunked->num_chunks() == 1) {
+      single_chunk = values_chunked->chunk(0);
+    }
+
+    if (args[1].kind() == Datum::ARRAY) {
+      // CA->C
+      auto& indices = args[1].array();
+      if (single_chunk) {
+        // AA->A
+        DCHECK_EQ(single_chunk->length(), batch.length);
+        // If the ChunkedArray was cheaply converted to a single chunk,
+        // we can use the AA->A take kernel directly.
+        RETURN_NOT_OK(
+            CallAAAKernel(take_aaa_exec, ctx, single_chunk->data(), indices, out));
+        out->value = std::make_shared<ChunkedArray>(MakeArray(out->array()));
+        return Status::OK();
+      }
+      // Instead of concatenating the chunks, we call the CA->A take kernel
+      // which has a more efficient implementation for this case. At this point,
+      // that implementation doesn't have to care about empty or single-chunk
+      // ChunkedArrays.
+      RETURN_NOT_OK(take_caa_exec(ctx, batch, &result));
+      out->value = std::make_shared<ChunkedArray>(MakeArray(result.array()));
+      return Status::OK();
+    } else {
+      // CC->C
+      const auto& indices = args[1].chunked_array();
+      std::vector<std::shared_ptr<Array>> new_chunks;
+      for (int i = 0; i < indices->num_chunks(); i++) {
+        auto& indices_chunk = indices->chunk(i)->data();
+        result = PrepareOutput(batch, values_chunked->length());
+        if (single_chunk) {
+          // If the ChunkedArray was cheaply converted to a single chunk,
+          // we can use the AA->A take kernel directly.
+          RETURN_NOT_OK(CallAAAKernel(take_aaa_exec, ctx, single_chunk->data(),
+                                      indices_chunk, &result));
+        } else {
+          RETURN_NOT_OK(
+              CallCAAKernel(take_caa_exec, ctx, values_chunked, indices_chunk, &result));
+        }
+        new_chunks.push_back(MakeArray(result.array()));
+      }
+      DCHECK(out->is_array());
+      out->value =
+          std::make_shared<ChunkedArray>(std::move(new_chunks), values_chunked->type());
+      return Status::OK();
+    }
+  } else {
+    // VectorKernel::exec_chunked are only called when at least one of the inputs is
+    // chunked, so we should be able to assume that args[1] is a chunked array when
+    // everything is wired up correctly.
+    if (args[1].kind() == Datum::CHUNKED_ARRAY) {
+      // AC->C
+      return TakeACCChunkedExec(take_aaa_exec, ctx, batch, out);
+    } else {
+      DCHECK(false) << "Unexpected kind for array_take's exec_chunked kernel: values="
+                    << args[0].ToString() << ", indices=" << args[1].ToString();
+    }
+  }
+  return Status::NotImplemented(
+      "Unsupported kinds for 'array_take', try using 'take': "
+      "values=",
+      args[0].ToString(), ", indices=", args[1].ToString());
+}
+
+template <ArrayKernelExec kTakeAAAExec, VectorKernel::ChunkedExec kTakeCAAExec>

Review Comment:
   For convenience of instantiation in `PopulateTakeKernels`.
   
   `SpecialTakeChunkedExecFunctor::Exec` gets inlined but `SpecialTakeChunkedExec` does not. We avoid binary bloat because I don't really want `SpecialTakeChunkedExec` to be specialized on every combination of `kTakeAAAExec` and `kTakeCAAExec` — I immediately force them into becoming function pointers that I dispatch to at runtime (from `SpecialTakeChunkedExec`) instead of having them inlined.



-- 
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: github-unsubscribe@arrow.apache.org

For queries about this service, please contact Infrastructure at:
users@infra.apache.org


Re: [PR] GH-39565: [C++] Do not concatenate chunked values of fixed-width types to run "array_take" [arrow]

Posted by "felipecrv (via GitHub)" <gi...@apache.org>.
felipecrv commented on code in PR #41700:
URL: https://github.com/apache/arrow/pull/41700#discussion_r1685743932


##########
cpp/src/arrow/compute/kernels/vector_selection_take_internal.cc:
##########
@@ -715,12 +853,244 @@ class TakeMetaFunction : public MetaFunction {
     return Status::NotImplemented(
         "Unsupported types for take operation: "
         "values=",
-        args[0].ToString(), "indices=", args[1].ToString());
+        args[0].ToString(), ", indices=", args[1].ToString());
   }
 };
 
 // ----------------------------------------------------------------------
 
+/// \brief Prepare the output array like ExecuteArrayKernel::PrepareOutput()
+std::shared_ptr<ArrayData> PrepareOutput(const ExecBatch& batch, int64_t length) {
+  DCHECK_EQ(batch.length, length);
+  auto out = std::make_shared<ArrayData>(batch.values[0].type(), length);
+  out->buffers.resize(batch.values[0].type()->layout().buffers.size());
+  return out;
+}
+
+Result<std::shared_ptr<Array>> ChunkedArrayAsArray(
+    const std::shared_ptr<ChunkedArray>& values, MemoryPool* pool) {
+  switch (values->num_chunks()) {
+    case 0:
+      return MakeArrayOfNull(values->type(), /*length=*/0, pool);
+    case 1:
+      return values->chunk(0);
+    default:
+      return Concatenate(values->chunks(), pool);
+  }
+}
+
+Status CallAAAKernel(ArrayKernelExec take_aaa_exec, KernelContext* ctx,
+                     std::shared_ptr<ArrayData> values,
+                     std::shared_ptr<ArrayData> indices, Datum* out) {
+  int64_t batch_length = values->length;
+  std::vector<Datum> args = {std::move(values), std::move(indices)};
+  ExecBatch array_array_batch(std::move(args), batch_length);
+  DCHECK_EQ(out->kind(), Datum::ARRAY);
+  ExecSpan exec_span{array_array_batch};
+  ExecResult result;
+  result.value = out->array();
+  return take_aaa_exec(ctx, exec_span, &result);
+}
+
+Status CallCAAKernel(VectorKernel::ChunkedExec take_caa_exec, KernelContext* ctx,
+                     std::shared_ptr<ChunkedArray> values,
+                     std::shared_ptr<ArrayData> indices, Datum* out) {
+  int64_t batch_length = values->length();
+  std::vector<Datum> args = {std::move(values), std::move(indices)};
+  ExecBatch chunked_array_array_batch(std::move(args), batch_length);
+  DCHECK_EQ(out->kind(), Datum::ARRAY);
+  return take_caa_exec(ctx, chunked_array_array_batch, out);
+}
+
+Status TakeACCChunkedExec(ArrayKernelExec take_aaa_exec, KernelContext* ctx,
+                          const ExecBatch& batch, Datum* out) {
+  auto& values = batch.values[0].array();
+  auto& indices = batch.values[1].chunked_array();
+  auto num_chunks = indices->num_chunks();
+  std::vector<std::shared_ptr<Array>> new_chunks(num_chunks);
+  for (int i = 0; i < num_chunks; i++) {
+    // Take with that indices chunk
+    auto& indices_chunk = indices->chunk(i)->data();
+    Datum result = PrepareOutput(batch, values->length);
+    RETURN_NOT_OK(CallAAAKernel(take_aaa_exec, ctx, values, indices_chunk, &result));
+    new_chunks[i] = MakeArray(result.array());
+  }
+  out->value = std::make_shared<ChunkedArray>(std::move(new_chunks), values->type);
+  return Status::OK();
+}
+
+/// \brief Generic (slower) VectorKernel::exec_chunked (`CA->C`, `CC->C`, and `AC->C`).
+///
+/// This function concatenates the chunks of the values and then calls the `AA->A` take
+/// kernel to handle the `CA->C` cases. The ArrayData returned by the `AA->A` kernel is
+/// converted to a ChunkedArray with a single chunk to honor the `CA->C` contract.
+///
+/// For `CC->C` cases, it concatenates the chunks of the values and calls the `AA->A` take
+/// kernel for each chunk of the indices, producing a new chunked array with the same
+/// shape as the indices.
+///
+/// `AC->C` cases are trivially delegated to TakeACCChunkedExec without any concatenation.
+///
+/// \param take_aaa_exec The `AA->A` take kernel to use.
+Status GenericTakeChunkedExec(ArrayKernelExec take_aaa_exec, KernelContext* ctx,
+                              const ExecBatch& batch, Datum* out) {
+  const auto& args = batch.values;
+  if (args[0].kind() == Datum::CHUNKED_ARRAY) {
+    auto& values_chunked = args[0].chunked_array();
+    ARROW_ASSIGN_OR_RAISE(auto values_array,
+                          ChunkedArrayAsArray(values_chunked, ctx->memory_pool()));
+    if (args[1].kind() == Datum::ARRAY) {
+      // CA->C
+      auto& indices = args[1].array();
+      DCHECK_EQ(values_array->length(), batch.length);
+      {
+        // AA->A
+        RETURN_NOT_OK(
+            CallAAAKernel(take_aaa_exec, ctx, values_array->data(), indices, out));
+        out->value = std::make_shared<ChunkedArray>(MakeArray(out->array()));
+      }
+      return Status::OK();
+    } else if (args[1].kind() == Datum::CHUNKED_ARRAY) {
+      // CC->C
+      const auto& indices = args[1].chunked_array();
+      std::vector<std::shared_ptr<Array>> new_chunks;
+      for (int i = 0; i < indices->num_chunks(); i++) {
+        // AA->A
+        auto& indices_chunk = indices->chunk(i)->data();
+        Datum result = PrepareOutput(batch, values_array->length());
+        RETURN_NOT_OK(CallAAAKernel(take_aaa_exec, ctx, values_array->data(),
+                                    indices_chunk, &result));
+        new_chunks.push_back(MakeArray(result.array()));
+      }
+      DCHECK(out->is_array());
+      out->value =
+          std::make_shared<ChunkedArray>(std::move(new_chunks), values_chunked->type());
+      return Status::OK();
+    }
+  } else {
+    // VectorKernel::exec_chunked are only called when at least one of the inputs is
+    // chunked, so we should be able to assume that args[1] is a chunked array when
+    // everything is wired up correctly.
+    if (args[1].kind() == Datum::CHUNKED_ARRAY) {
+      // AC->C
+      return TakeACCChunkedExec(take_aaa_exec, ctx, batch, out);
+    } else {
+      DCHECK(false) << "Unexpected kind for array_take's exec_chunked kernel: values="
+                    << args[0].ToString() << ", indices=" << args[1].ToString();
+    }
+  }
+  return Status::NotImplemented(
+      "Unsupported kinds for 'array_take', try using 'take': "
+      "values=",
+      args[0].ToString(), ", indices=", args[1].ToString());
+}
+
+template <ArrayKernelExec kTakeAAAExec>
+struct GenericTakeChunkedExecFunctor {
+  static Status Exec(KernelContext* ctx, const ExecBatch& batch, Datum* out) {
+    return GenericTakeChunkedExec(kTakeAAAExec, ctx, batch, out);
+  }
+};
+
+/// \brief Specialized (faster) VectorKernel::exec_chunked (`CA->C`, `CC->C`, `AC->C`).
+///
+/// This function doesn't ever need to concatenate the chunks of the values, so it can be
+/// more efficient than GenericTakeChunkedExec that can only delegate to the `AA->A` take
+/// kernels.
+///
+/// For `CA->C` cases, it can call the `CA->A` take kernel directly [1] and trivially
+/// convert the result to a ChunkedArray of a single chunk to honor the `CA->C` contract.
+///
+/// For `CC->C` cases it can call the `CA->A` take kernel for each chunk of the indices to
+/// get each chunk that becomes the ChunkedArray output.
+///
+/// `AC->C` cases are trivially delegated to TakeACCChunkedExec.
+///
+/// \param take_aaa_exec The `AA->A` take kernel to use.
+Status SpecialTakeChunkedExec(const ArrayKernelExec take_aaa_exec,
+                              VectorKernel::ChunkedExec take_caa_exec, KernelContext* ctx,
+                              const ExecBatch& batch, Datum* out) {
+  Datum result = PrepareOutput(batch, batch.length);
+  auto* pool = ctx->memory_pool();
+  const auto& args = batch.values;
+  if (args[0].kind() == Datum::CHUNKED_ARRAY) {
+    auto& values_chunked = args[0].chunked_array();
+    std::shared_ptr<Array> single_chunk = nullptr;
+    if (values_chunked->num_chunks() == 0 || values_chunked->length() == 0) {
+      ARROW_ASSIGN_OR_RAISE(single_chunk,
+                            MakeArrayOfNull(values_chunked->type(), /*length=*/0, pool));
+    } else if (values_chunked->num_chunks() == 1) {
+      single_chunk = values_chunked->chunk(0);
+    }
+
+    if (args[1].kind() == Datum::ARRAY) {
+      // CA->C
+      auto& indices = args[1].array();
+      if (single_chunk) {
+        // AA->A
+        DCHECK_EQ(single_chunk->length(), batch.length);
+        // If the ChunkedArray was cheaply converted to a single chunk,
+        // we can use the AA->A take kernel directly.
+        RETURN_NOT_OK(
+            CallAAAKernel(take_aaa_exec, ctx, single_chunk->data(), indices, out));
+        out->value = std::make_shared<ChunkedArray>(MakeArray(out->array()));
+        return Status::OK();
+      }
+      // Instead of concatenating the chunks, we call the CA->A take kernel
+      // which has a more efficient implementation for this case. At this point,
+      // that implementation doesn't have to care about empty or single-chunk
+      // ChunkedArrays.
+      RETURN_NOT_OK(take_caa_exec(ctx, batch, &result));
+      out->value = std::make_shared<ChunkedArray>(MakeArray(result.array()));
+      return Status::OK();
+    } else {
+      // CC->C
+      const auto& indices = args[1].chunked_array();
+      std::vector<std::shared_ptr<Array>> new_chunks;
+      for (int i = 0; i < indices->num_chunks(); i++) {
+        auto& indices_chunk = indices->chunk(i)->data();
+        result = PrepareOutput(batch, values_chunked->length());
+        if (single_chunk) {
+          // If the ChunkedArray was cheaply converted to a single chunk,
+          // we can use the AA->A take kernel directly.
+          RETURN_NOT_OK(CallAAAKernel(take_aaa_exec, ctx, single_chunk->data(),
+                                      indices_chunk, &result));
+        } else {
+          RETURN_NOT_OK(
+              CallCAAKernel(take_caa_exec, ctx, values_chunked, indices_chunk, &result));
+        }
+        new_chunks.push_back(MakeArray(result.array()));
+      }
+      DCHECK(out->is_array());
+      out->value =
+          std::make_shared<ChunkedArray>(std::move(new_chunks), values_chunked->type());
+      return Status::OK();
+    }
+  } else {
+    // VectorKernel::exec_chunked are only called when at least one of the inputs is
+    // chunked, so we should be able to assume that args[1] is a chunked array when
+    // everything is wired up correctly.
+    if (args[1].kind() == Datum::CHUNKED_ARRAY) {
+      // AC->C
+      return TakeACCChunkedExec(take_aaa_exec, ctx, batch, out);
+    } else {
+      DCHECK(false) << "Unexpected kind for array_take's exec_chunked kernel: values="
+                    << args[0].ToString() << ", indices=" << args[1].ToString();
+    }
+  }
+  return Status::NotImplemented(
+      "Unsupported kinds for 'array_take', try using 'take': "
+      "values=",
+      args[0].ToString(), ", indices=", args[1].ToString());

Review Comment:
   These `ToString()` converters are suitable for debugging. They don't print the entire array. To produce the entire array you would have to use `PrettyPrint` with the appropriate `PrettyPrintOptions`.



-- 
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: github-unsubscribe@arrow.apache.org

For queries about this service, please contact Infrastructure at:
users@infra.apache.org


Re: [PR] GH-39565: [C++] Do not concatenate chunked values of fixed-width types to run "array_take" [arrow]

Posted by "pitrou (via GitHub)" <gi...@apache.org>.
pitrou commented on PR #41700:
URL: https://github.com/apache/arrow/pull/41700#issuecomment-2299367878

   I submitted PR #43772 to add benchmarks with a smaller selection factor (the current take benchmarks would have a selection factor of 1.0). We could merge this PR before this one, to check what the slowdown is in that case too.


-- 
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: github-unsubscribe@arrow.apache.org

For queries about this service, please contact Infrastructure at:
users@infra.apache.org


Re: [PR] GH-39565: [C++] Do not concatenate chunked values of fixed-width types to run "array_take" [arrow]

Posted by "pitrou (via GitHub)" <gi...@apache.org>.
pitrou commented on code in PR #41700:
URL: https://github.com/apache/arrow/pull/41700#discussion_r1723426802


##########
cpp/src/arrow/compute/kernels/vector_selection_take_internal.cc:
##########
@@ -715,12 +853,247 @@ class TakeMetaFunction : public MetaFunction {
     return Status::NotImplemented(
         "Unsupported types for take operation: "
         "values=",
-        args[0].ToString(), "indices=", args[1].ToString());
+        args[0].ToString(), ", indices=", args[1].ToString());
   }
 };
 
 // ----------------------------------------------------------------------
 
+/// \brief Prepare the output array like ExecuteArrayKernel::PrepareOutput()
+std::shared_ptr<ArrayData> PrepareOutput(const ExecBatch& batch, int64_t length) {
+  DCHECK_EQ(batch.length, length);
+  auto out = std::make_shared<ArrayData>(batch.values[0].type(), length);
+  out->buffers.resize(batch.values[0].type()->layout().buffers.size());
+  return out;
+}
+
+Result<std::shared_ptr<Array>> ChunkedArrayAsArray(
+    const std::shared_ptr<ChunkedArray>& values, MemoryPool* pool) {
+  switch (values->num_chunks()) {
+    case 0:
+      return MakeArrayOfNull(values->type(), /*length=*/0, pool);
+    case 1:
+      return values->chunk(0);
+    default:
+      return Concatenate(values->chunks(), pool);
+  }
+}
+
+Status CallAAAKernel(ArrayKernelExec take_aaa_exec, KernelContext* ctx,
+                     std::shared_ptr<ArrayData> values,
+                     std::shared_ptr<ArrayData> indices, Datum* out) {
+  int64_t batch_length = values->length;
+  std::vector<Datum> args = {std::move(values), std::move(indices)};
+  ExecBatch array_array_batch(std::move(args), batch_length);
+  DCHECK_EQ(out->kind(), Datum::ARRAY);
+  ExecSpan exec_span{array_array_batch};
+  ExecResult result;
+  result.value = out->array();
+  RETURN_NOT_OK(take_aaa_exec(ctx, exec_span, &result));
+  DCHECK(result.is_array_data());
+  out->value = result.array_data();
+  return Status::OK();
+}
+
+Status CallCAAKernel(VectorKernel::ChunkedExec take_caa_exec, KernelContext* ctx,
+                     std::shared_ptr<ChunkedArray> values,
+                     std::shared_ptr<ArrayData> indices, Datum* out) {
+  int64_t batch_length = values->length();
+  std::vector<Datum> args = {std::move(values), std::move(indices)};
+  ExecBatch chunked_array_array_batch(std::move(args), batch_length);
+  DCHECK_EQ(out->kind(), Datum::ARRAY);
+  return take_caa_exec(ctx, chunked_array_array_batch, out);
+}
+
+Status TakeACCChunkedExec(ArrayKernelExec take_aaa_exec, KernelContext* ctx,
+                          const ExecBatch& batch, Datum* out) {
+  auto& values = batch.values[0].array();
+  auto& indices = batch.values[1].chunked_array();
+  auto num_chunks = indices->num_chunks();
+  std::vector<std::shared_ptr<Array>> new_chunks(num_chunks);
+  for (int i = 0; i < num_chunks; i++) {
+    // Take with that indices chunk
+    auto& indices_chunk = indices->chunk(i)->data();
+    Datum result = PrepareOutput(batch, values->length);
+    RETURN_NOT_OK(CallAAAKernel(take_aaa_exec, ctx, values, indices_chunk, &result));
+    new_chunks[i] = MakeArray(result.array());
+  }
+  out->value = std::make_shared<ChunkedArray>(std::move(new_chunks), values->type);
+  return Status::OK();
+}
+
+/// \brief Generic (slower) VectorKernel::exec_chunked (`CA->C`, `CC->C`, and `AC->C`).
+///
+/// This function concatenates the chunks of the values and then calls the `AA->A` take
+/// kernel to handle the `CA->C` cases. The ArrayData returned by the `AA->A` kernel is
+/// converted to a ChunkedArray with a single chunk to honor the `CA->C` contract.
+///
+/// For `CC->C` cases, it concatenates the chunks of the values and calls the `AA->A` take
+/// kernel for each chunk of the indices, producing a new chunked array with the same
+/// shape as the indices.
+///
+/// `AC->C` cases are trivially delegated to TakeACCChunkedExec without any concatenation.
+///
+/// \param take_aaa_exec The `AA->A` take kernel to use.
+Status GenericTakeChunkedExec(ArrayKernelExec take_aaa_exec, KernelContext* ctx,
+                              const ExecBatch& batch, Datum* out) {
+  const auto& args = batch.values;
+  if (args[0].kind() == Datum::CHUNKED_ARRAY) {
+    auto& values_chunked = args[0].chunked_array();

Review Comment:
   Can we settle on `const auto&` unless it's necessary to get a mutable ref?



##########
cpp/src/arrow/compute/kernels/vector_selection_take_internal.cc:
##########
@@ -395,10 +526,45 @@ struct FixedWidthTakeImpl {
     out_arr->null_count = out_arr->length - valid_count;
     return Status::OK();
   }
+
+  static Status ChunkedExec(KernelContext* ctx, const ChunkedArray& values,
+                            const ArraySpan& indices, ArrayData* out_arr,
+                            int64_t factor) {
+    const bool out_has_validity = values.null_count() > 0 || indices.MayHaveNulls();
+
+    ChunkedFixedWidthValuesSpan chunked_values{values};
+    ResolvedIndicesState resolved_idx;
+    RETURN_NOT_OK(resolved_idx.InitWithIndices<IndexCType>(
+        /*chunks=*/values.chunks(), /*idx_length=*/indices.length,
+        /*idx=*/indices.GetValues<IndexCType>(1), ctx->memory_pool()));
+
+    int64_t valid_count = 0;
+    arrow::internal::GatherFromChunks<kValueWidthInBits, IndexCType, WithFactor::value>

Review Comment:
   As a further optimization, perhaps we should test whether `chunk_index_vec` contains a single distinct chunk index, in which case we could similarly fallback on ArraySpan-take (I'm not sure how expensive the check would be, though).
   
   Probably for another PR/issue, if any.
   



##########
cpp/src/arrow/compute/kernels/vector_selection_take_internal.cc:
##########
@@ -395,10 +526,45 @@ struct FixedWidthTakeImpl {
     out_arr->null_count = out_arr->length - valid_count;
     return Status::OK();
   }
+
+  static Status ChunkedExec(KernelContext* ctx, const ChunkedArray& values,
+                            const ArraySpan& indices, ArrayData* out_arr,
+                            int64_t factor) {
+    const bool out_has_validity = values.null_count() > 0 || indices.MayHaveNulls();

Review Comment:
   Or it seems this is actually handled at a higher level, in the kernel exec scaffolding?



##########
cpp/src/arrow/compute/kernels/vector_selection_take_internal.cc:
##########
@@ -715,12 +853,247 @@ class TakeMetaFunction : public MetaFunction {
     return Status::NotImplemented(
         "Unsupported types for take operation: "
         "values=",
-        args[0].ToString(), "indices=", args[1].ToString());
+        args[0].ToString(), ", indices=", args[1].ToString());
   }
 };
 
 // ----------------------------------------------------------------------
 
+/// \brief Prepare the output array like ExecuteArrayKernel::PrepareOutput()
+std::shared_ptr<ArrayData> PrepareOutput(const ExecBatch& batch, int64_t length) {
+  DCHECK_EQ(batch.length, length);
+  auto out = std::make_shared<ArrayData>(batch.values[0].type(), length);
+  out->buffers.resize(batch.values[0].type()->layout().buffers.size());
+  return out;
+}
+
+Result<std::shared_ptr<Array>> ChunkedArrayAsArray(
+    const std::shared_ptr<ChunkedArray>& values, MemoryPool* pool) {
+  switch (values->num_chunks()) {
+    case 0:
+      return MakeArrayOfNull(values->type(), /*length=*/0, pool);
+    case 1:
+      return values->chunk(0);
+    default:
+      return Concatenate(values->chunks(), pool);
+  }
+}
+
+Status CallAAAKernel(ArrayKernelExec take_aaa_exec, KernelContext* ctx,
+                     std::shared_ptr<ArrayData> values,
+                     std::shared_ptr<ArrayData> indices, Datum* out) {
+  int64_t batch_length = values->length;
+  std::vector<Datum> args = {std::move(values), std::move(indices)};
+  ExecBatch array_array_batch(std::move(args), batch_length);
+  DCHECK_EQ(out->kind(), Datum::ARRAY);
+  ExecSpan exec_span{array_array_batch};
+  ExecResult result;
+  result.value = out->array();
+  RETURN_NOT_OK(take_aaa_exec(ctx, exec_span, &result));
+  DCHECK(result.is_array_data());
+  out->value = result.array_data();
+  return Status::OK();
+}
+
+Status CallCAAKernel(VectorKernel::ChunkedExec take_caa_exec, KernelContext* ctx,
+                     std::shared_ptr<ChunkedArray> values,
+                     std::shared_ptr<ArrayData> indices, Datum* out) {
+  int64_t batch_length = values->length();
+  std::vector<Datum> args = {std::move(values), std::move(indices)};
+  ExecBatch chunked_array_array_batch(std::move(args), batch_length);
+  DCHECK_EQ(out->kind(), Datum::ARRAY);
+  return take_caa_exec(ctx, chunked_array_array_batch, out);
+}
+
+Status TakeACCChunkedExec(ArrayKernelExec take_aaa_exec, KernelContext* ctx,
+                          const ExecBatch& batch, Datum* out) {
+  auto& values = batch.values[0].array();
+  auto& indices = batch.values[1].chunked_array();
+  auto num_chunks = indices->num_chunks();
+  std::vector<std::shared_ptr<Array>> new_chunks(num_chunks);
+  for (int i = 0; i < num_chunks; i++) {
+    // Take with that indices chunk
+    auto& indices_chunk = indices->chunk(i)->data();
+    Datum result = PrepareOutput(batch, values->length);
+    RETURN_NOT_OK(CallAAAKernel(take_aaa_exec, ctx, values, indices_chunk, &result));
+    new_chunks[i] = MakeArray(result.array());
+  }
+  out->value = std::make_shared<ChunkedArray>(std::move(new_chunks), values->type);
+  return Status::OK();
+}
+
+/// \brief Generic (slower) VectorKernel::exec_chunked (`CA->C`, `CC->C`, and `AC->C`).
+///
+/// This function concatenates the chunks of the values and then calls the `AA->A` take
+/// kernel to handle the `CA->C` cases. The ArrayData returned by the `AA->A` kernel is
+/// converted to a ChunkedArray with a single chunk to honor the `CA->C` contract.
+///
+/// For `CC->C` cases, it concatenates the chunks of the values and calls the `AA->A` take
+/// kernel for each chunk of the indices, producing a new chunked array with the same
+/// shape as the indices.
+///
+/// `AC->C` cases are trivially delegated to TakeACCChunkedExec without any concatenation.
+///
+/// \param take_aaa_exec The `AA->A` take kernel to use.
+Status GenericTakeChunkedExec(ArrayKernelExec take_aaa_exec, KernelContext* ctx,
+                              const ExecBatch& batch, Datum* out) {
+  const auto& args = batch.values;
+  if (args[0].kind() == Datum::CHUNKED_ARRAY) {
+    auto& values_chunked = args[0].chunked_array();
+    ARROW_ASSIGN_OR_RAISE(auto values_array,
+                          ChunkedArrayAsArray(values_chunked, ctx->memory_pool()));
+    if (args[1].kind() == Datum::ARRAY) {
+      // CA->C
+      auto& indices = args[1].array();
+      DCHECK_EQ(values_array->length(), batch.length);
+      {
+        // AA->A
+        RETURN_NOT_OK(
+            CallAAAKernel(take_aaa_exec, ctx, values_array->data(), indices, out));
+        out->value = std::make_shared<ChunkedArray>(MakeArray(out->array()));
+      }
+      return Status::OK();
+    } else if (args[1].kind() == Datum::CHUNKED_ARRAY) {
+      // CC->C
+      const auto& indices = args[1].chunked_array();
+      std::vector<std::shared_ptr<Array>> new_chunks;
+      for (int i = 0; i < indices->num_chunks(); i++) {
+        // AA->A
+        auto& indices_chunk = indices->chunk(i)->data();
+        Datum result = PrepareOutput(batch, values_array->length());
+        RETURN_NOT_OK(CallAAAKernel(take_aaa_exec, ctx, values_array->data(),
+                                    indices_chunk, &result));
+        new_chunks.push_back(MakeArray(result.array()));
+      }
+      DCHECK(out->is_array());
+      out->value =
+          std::make_shared<ChunkedArray>(std::move(new_chunks), values_chunked->type());
+      return Status::OK();
+    }
+  } else {
+    // VectorKernel::exec_chunked are only called when at least one of the inputs is
+    // chunked, so we should be able to assume that args[1] is a chunked array when
+    // everything is wired up correctly.
+    if (args[1].kind() == Datum::CHUNKED_ARRAY) {
+      // AC->C
+      return TakeACCChunkedExec(take_aaa_exec, ctx, batch, out);
+    } else {
+      DCHECK(false) << "Unexpected kind for array_take's exec_chunked kernel: values="
+                    << args[0].ToString() << ", indices=" << args[1].ToString();
+    }
+  }
+  return Status::NotImplemented(
+      "Unsupported kinds for 'array_take', try using 'take': "
+      "values=",
+      args[0].ToString(), ", indices=", args[1].ToString());
+}
+
+template <ArrayKernelExec kTakeAAAExec>
+struct GenericTakeChunkedExecFunctor {
+  static Status Exec(KernelContext* ctx, const ExecBatch& batch, Datum* out) {
+    return GenericTakeChunkedExec(kTakeAAAExec, ctx, batch, out);
+  }
+};
+
+/// \brief Specialized (faster) VectorKernel::exec_chunked (`CA->C`, `CC->C`, `AC->C`).
+///
+/// This function doesn't ever need to concatenate the chunks of the values, so it can be
+/// more efficient than GenericTakeChunkedExec that can only delegate to the `AA->A` take
+/// kernels.
+///
+/// For `CA->C` cases, it can call the `CA->A` take kernel directly [1] and trivially
+/// convert the result to a ChunkedArray of a single chunk to honor the `CA->C` contract.
+///
+/// For `CC->C` cases it can call the `CA->A` take kernel for each chunk of the indices to
+/// get each chunk that becomes the ChunkedArray output.
+///
+/// `AC->C` cases are trivially delegated to TakeACCChunkedExec.
+///
+/// \param take_aaa_exec The `AA->A` take kernel to use.
+Status SpecialTakeChunkedExec(const ArrayKernelExec take_aaa_exec,
+                              VectorKernel::ChunkedExec take_caa_exec, KernelContext* ctx,
+                              const ExecBatch& batch, Datum* out) {
+  Datum result = PrepareOutput(batch, batch.length);
+  auto* pool = ctx->memory_pool();
+  const auto& args = batch.values;
+  if (args[0].kind() == Datum::CHUNKED_ARRAY) {
+    auto& values_chunked = args[0].chunked_array();
+    std::shared_ptr<Array> single_chunk = nullptr;
+    if (values_chunked->num_chunks() == 0 || values_chunked->length() == 0) {

Review Comment:
   The disjonction is not necessary, is it? This can be reduced to
   ```suggestion
       if (values_chunked->length() == 0) {
   ```



##########
cpp/src/arrow/compute/kernels/vector_selection_take_internal.cc:
##########
@@ -736,22 +1109,40 @@ void PopulateTakeKernels(std::vector<SelectionKernelData>* out) {
   auto take_indices = match::Integer();
 
   *out = {
-      {InputType(match::Primitive()), take_indices, FixedWidthTakeExec},
-      {InputType(match::BinaryLike()), take_indices, VarBinaryTakeExec},
-      {InputType(match::LargeBinaryLike()), take_indices, LargeVarBinaryTakeExec},
-      {InputType(match::FixedSizeBinaryLike()), take_indices, FixedWidthTakeExec},
-      {InputType(null()), take_indices, NullTakeExec},
-      {InputType(Type::DICTIONARY), take_indices, DictionaryTake},
-      {InputType(Type::EXTENSION), take_indices, ExtensionTake},
-      {InputType(Type::LIST), take_indices, ListTakeExec},
-      {InputType(Type::LARGE_LIST), take_indices, LargeListTakeExec},
-      {InputType(Type::LIST_VIEW), take_indices, ListViewTakeExec},
-      {InputType(Type::LARGE_LIST_VIEW), take_indices, LargeListViewTakeExec},
-      {InputType(Type::FIXED_SIZE_LIST), take_indices, FSLTakeExec},
-      {InputType(Type::DENSE_UNION), take_indices, DenseUnionTakeExec},
-      {InputType(Type::SPARSE_UNION), take_indices, SparseUnionTakeExec},
-      {InputType(Type::STRUCT), take_indices, StructTakeExec},
-      {InputType(Type::MAP), take_indices, MapTakeExec},
+      {InputType(match::Primitive()), take_indices, FixedWidthTakeExec,
+       SpecialTakeChunkedExecFunctor<FixedWidthTakeExec,
+                                     FixedWidthTakeChunkedExec>::Exec},
+      {InputType(match::BinaryLike()), take_indices, VarBinaryTakeExec,
+       GenericTakeChunkedExecFunctor<VarBinaryTakeExec>::Exec},
+      {InputType(match::LargeBinaryLike()), take_indices, LargeVarBinaryTakeExec,
+       GenericTakeChunkedExecFunctor<LargeVarBinaryTakeExec>::Exec},
+      {InputType(match::FixedSizeBinaryLike()), take_indices, FixedWidthTakeExec,
+       SpecialTakeChunkedExecFunctor<FixedWidthTakeExec,
+                                     FixedWidthTakeChunkedExec>::Exec},
+      {InputType(null()), take_indices, NullTakeExec,
+       GenericTakeChunkedExecFunctor<NullTakeExec>::Exec},
+      {InputType(Type::DICTIONARY), take_indices, DictionaryTake,
+       GenericTakeChunkedExecFunctor<DictionaryTake>::Exec},
+      {InputType(Type::EXTENSION), take_indices, ExtensionTake,
+       GenericTakeChunkedExecFunctor<ExtensionTake>::Exec},
+      {InputType(Type::LIST), take_indices, ListTakeExec,
+       GenericTakeChunkedExecFunctor<ListTakeExec>::Exec},
+      {InputType(Type::LARGE_LIST), take_indices, LargeListTakeExec,
+       GenericTakeChunkedExecFunctor<LargeListTakeExec>::Exec},
+      {InputType(Type::LIST_VIEW), take_indices, ListViewTakeExec,
+       GenericTakeChunkedExecFunctor<ListViewTakeExec>::Exec},
+      {InputType(Type::LARGE_LIST_VIEW), take_indices, LargeListViewTakeExec,
+       GenericTakeChunkedExecFunctor<LargeListViewTakeExec>::Exec},
+      {InputType(Type::FIXED_SIZE_LIST), take_indices, FSLTakeExec,
+       GenericTakeChunkedExecFunctor<FSLTakeExec>::Exec},

Review Comment:
   We may need a more powerful type matcher, but ideally fixed size lists of fixed width types should go through the special chunked exec function?
   



##########
cpp/src/arrow/compute/kernels/vector_selection_take_internal.cc:
##########
@@ -736,22 +1109,40 @@ void PopulateTakeKernels(std::vector<SelectionKernelData>* out) {
   auto take_indices = match::Integer();
 
   *out = {
-      {InputType(match::Primitive()), take_indices, FixedWidthTakeExec},
-      {InputType(match::BinaryLike()), take_indices, VarBinaryTakeExec},
-      {InputType(match::LargeBinaryLike()), take_indices, LargeVarBinaryTakeExec},
-      {InputType(match::FixedSizeBinaryLike()), take_indices, FixedWidthTakeExec},
-      {InputType(null()), take_indices, NullTakeExec},
-      {InputType(Type::DICTIONARY), take_indices, DictionaryTake},
-      {InputType(Type::EXTENSION), take_indices, ExtensionTake},
-      {InputType(Type::LIST), take_indices, ListTakeExec},
-      {InputType(Type::LARGE_LIST), take_indices, LargeListTakeExec},
-      {InputType(Type::LIST_VIEW), take_indices, ListViewTakeExec},
-      {InputType(Type::LARGE_LIST_VIEW), take_indices, LargeListViewTakeExec},
-      {InputType(Type::FIXED_SIZE_LIST), take_indices, FSLTakeExec},
-      {InputType(Type::DENSE_UNION), take_indices, DenseUnionTakeExec},
-      {InputType(Type::SPARSE_UNION), take_indices, SparseUnionTakeExec},
-      {InputType(Type::STRUCT), take_indices, StructTakeExec},
-      {InputType(Type::MAP), take_indices, MapTakeExec},
+      {InputType(match::Primitive()), take_indices, FixedWidthTakeExec,
+       SpecialTakeChunkedExecFunctor<FixedWidthTakeExec,
+                                     FixedWidthTakeChunkedExec>::Exec},
+      {InputType(match::BinaryLike()), take_indices, VarBinaryTakeExec,
+       GenericTakeChunkedExecFunctor<VarBinaryTakeExec>::Exec},
+      {InputType(match::LargeBinaryLike()), take_indices, LargeVarBinaryTakeExec,
+       GenericTakeChunkedExecFunctor<LargeVarBinaryTakeExec>::Exec},
+      {InputType(match::FixedSizeBinaryLike()), take_indices, FixedWidthTakeExec,
+       SpecialTakeChunkedExecFunctor<FixedWidthTakeExec,
+                                     FixedWidthTakeChunkedExec>::Exec},
+      {InputType(null()), take_indices, NullTakeExec,
+       GenericTakeChunkedExecFunctor<NullTakeExec>::Exec},
+      {InputType(Type::DICTIONARY), take_indices, DictionaryTake,
+       GenericTakeChunkedExecFunctor<DictionaryTake>::Exec},
+      {InputType(Type::EXTENSION), take_indices, ExtensionTake,
+       GenericTakeChunkedExecFunctor<ExtensionTake>::Exec},
+      {InputType(Type::LIST), take_indices, ListTakeExec,
+       GenericTakeChunkedExecFunctor<ListTakeExec>::Exec},
+      {InputType(Type::LARGE_LIST), take_indices, LargeListTakeExec,
+       GenericTakeChunkedExecFunctor<LargeListTakeExec>::Exec},
+      {InputType(Type::LIST_VIEW), take_indices, ListViewTakeExec,
+       GenericTakeChunkedExecFunctor<ListViewTakeExec>::Exec},
+      {InputType(Type::LARGE_LIST_VIEW), take_indices, LargeListViewTakeExec,
+       GenericTakeChunkedExecFunctor<LargeListViewTakeExec>::Exec},
+      {InputType(Type::FIXED_SIZE_LIST), take_indices, FSLTakeExec,
+       GenericTakeChunkedExecFunctor<FSLTakeExec>::Exec},

Review Comment:
   Perhaps open a GH issue for this.



##########
cpp/src/arrow/compute/kernels/vector_selection_take_internal.cc:
##########
@@ -357,15 +481,22 @@ template <typename IndexCType, typename ValueBitWidthConstant,
 struct FixedWidthTakeImpl {
   static constexpr int kValueWidthInBits = ValueBitWidthConstant::value;
 
-  static Status Exec(KernelContext* ctx, const ArraySpan& values,
+  static Status Exec(KernelContext* ctx, const ValuesSpan& values,
                      const ArraySpan& indices, ArrayData* out_arr, int64_t factor) {
 #ifndef NDEBUG
-    int64_t bit_width = util::FixedWidthInBits(*values.type);
+    int64_t bit_width = util::FixedWidthInBits(*values.type());
     DCHECK(WithFactor::value || (kValueWidthInBits == bit_width && factor == 1));
     DCHECK(!WithFactor::value ||
            (factor > 0 && kValueWidthInBits == 8 &&  // factors are used with bytes
             static_cast<int64_t>(factor * kValueWidthInBits) == bit_width));
 #endif
+    return values.is_chunked()
+               ? ChunkedExec(ctx, values.chunked_array(), indices, out_arr, factor)
+               : Exec(ctx, values.array(), indices, out_arr, factor);
+  }
+
+  static Status Exec(KernelContext* ctx, const ArraySpan& values,

Review Comment:
   Perhaps call this `ContiguousExec` similar to `ChunkedExec` below?



##########
cpp/src/arrow/compute/kernels/vector_selection_take_internal.cc:
##########
@@ -736,22 +1109,40 @@ void PopulateTakeKernels(std::vector<SelectionKernelData>* out) {
   auto take_indices = match::Integer();
 
   *out = {
-      {InputType(match::Primitive()), take_indices, FixedWidthTakeExec},
-      {InputType(match::BinaryLike()), take_indices, VarBinaryTakeExec},
-      {InputType(match::LargeBinaryLike()), take_indices, LargeVarBinaryTakeExec},
-      {InputType(match::FixedSizeBinaryLike()), take_indices, FixedWidthTakeExec},
-      {InputType(null()), take_indices, NullTakeExec},
-      {InputType(Type::DICTIONARY), take_indices, DictionaryTake},
-      {InputType(Type::EXTENSION), take_indices, ExtensionTake},
-      {InputType(Type::LIST), take_indices, ListTakeExec},
-      {InputType(Type::LARGE_LIST), take_indices, LargeListTakeExec},
-      {InputType(Type::LIST_VIEW), take_indices, ListViewTakeExec},
-      {InputType(Type::LARGE_LIST_VIEW), take_indices, LargeListViewTakeExec},
-      {InputType(Type::FIXED_SIZE_LIST), take_indices, FSLTakeExec},
-      {InputType(Type::DENSE_UNION), take_indices, DenseUnionTakeExec},
-      {InputType(Type::SPARSE_UNION), take_indices, SparseUnionTakeExec},
-      {InputType(Type::STRUCT), take_indices, StructTakeExec},
-      {InputType(Type::MAP), take_indices, MapTakeExec},
+      {InputType(match::Primitive()), take_indices, FixedWidthTakeExec,
+       SpecialTakeChunkedExecFunctor<FixedWidthTakeExec,
+                                     FixedWidthTakeChunkedExec>::Exec},
+      {InputType(match::BinaryLike()), take_indices, VarBinaryTakeExec,
+       GenericTakeChunkedExecFunctor<VarBinaryTakeExec>::Exec},
+      {InputType(match::LargeBinaryLike()), take_indices, LargeVarBinaryTakeExec,
+       GenericTakeChunkedExecFunctor<LargeVarBinaryTakeExec>::Exec},
+      {InputType(match::FixedSizeBinaryLike()), take_indices, FixedWidthTakeExec,
+       SpecialTakeChunkedExecFunctor<FixedWidthTakeExec,
+                                     FixedWidthTakeChunkedExec>::Exec},
+      {InputType(null()), take_indices, NullTakeExec,
+       GenericTakeChunkedExecFunctor<NullTakeExec>::Exec},

Review Comment:
   This use case is probably not very important, but we should perhaps open a low-priority issue for optimizing the null-take kernel :-)



##########
cpp/src/arrow/compute/kernels/vector_selection_take_internal.cc:
##########
@@ -326,6 +327,129 @@ namespace {
 
 using TakeState = OptionsWrapper<TakeOptions>;
 
+class ValuesSpan {
+ private:
+  const std::shared_ptr<ChunkedArray> chunked_ = nullptr;
+  const ArraySpan chunk0_;  // first chunk or the whole array
+
+ public:
+  explicit ValuesSpan(const std::shared_ptr<ChunkedArray> values)
+      : chunked_(std::move(values)), chunk0_{*values->chunk(0)->data()} {
+    DCHECK(chunked_);
+    DCHECK_GT(chunked_->num_chunks(), 0);
+  }
+
+  explicit ValuesSpan(const ArraySpan& values) : chunk0_(values) {}
+
+  bool is_chunked() const { return chunked_ != nullptr; }
+
+  const ChunkedArray& chunked_array() const {
+    DCHECK(is_chunked());
+    return *chunked_;
+  }
+
+  const ArraySpan& chunk0() const { return chunk0_; }
+
+  const ArraySpan& array() const {
+    DCHECK(!is_chunked());
+    return chunk0_;
+  }
+
+  const DataType* type() const { return chunk0_.type; }
+
+  int64_t length() const { return is_chunked() ? chunked_->length() : array().length; }
+
+  bool MayHaveNulls() const {
+    return is_chunked() ? chunked_->null_count() != 0 : array().MayHaveNulls();
+  }
+};
+
+struct ChunkedFixedWidthValuesSpan {
+ private:
+  // src_residual_bit_offsets_[i] is used to store the bit offset of the first byte (0-7)
+  // in src_chunks_[i] iff kValueWidthInBits == 1.
+  std::vector<int> src_residual_bit_offsets;
+  // Pre-computed pointers to the start of the values in each chunk.
+  std::vector<const uint8_t*> src_chunks;
+
+ public:
+  explicit ChunkedFixedWidthValuesSpan(const ChunkedArray& values) {
+    const bool chunk_values_are_bit_sized = values.type()->id() == Type::BOOL;
+    DCHECK_EQ(chunk_values_are_bit_sized, util::FixedWidthInBytes(*values.type()) == -1);
+    if (chunk_values_are_bit_sized) {
+      src_residual_bit_offsets.resize(values.num_chunks());
+    }
+    src_chunks.resize(values.num_chunks());
+
+    for (int i = 0; i < values.num_chunks(); ++i) {
+      const ArraySpan chunk{*values.chunk(i)->data()};
+      DCHECK(util::IsFixedWidthLike(chunk));
+
+      auto offset_pointer = util::OffsetPointerOfFixedBitWidthValues(chunk);
+      if (chunk_values_are_bit_sized) {
+        src_residual_bit_offsets[i] = offset_pointer.first;
+      } else {
+        DCHECK_EQ(offset_pointer.first, 0);
+      }
+      src_chunks[i] = offset_pointer.second;
+    }
+  }
+
+  ~ChunkedFixedWidthValuesSpan() = default;

Review Comment:
   Is this actually necessary?



##########
cpp/src/arrow/compute/kernels/vector_selection_take_internal.cc:
##########
@@ -395,10 +526,45 @@ struct FixedWidthTakeImpl {
     out_arr->null_count = out_arr->length - valid_count;
     return Status::OK();
   }
+
+  static Status ChunkedExec(KernelContext* ctx, const ChunkedArray& values,
+                            const ArraySpan& indices, ArrayData* out_arr,
+                            int64_t factor) {
+    const bool out_has_validity = values.null_count() > 0 || indices.MayHaveNulls();

Review Comment:
   As an optimization, do we want to fallback on ArraySpan-take if `values.num_chunks() == 1`?



-- 
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: github-unsubscribe@arrow.apache.org

For queries about this service, please contact Infrastructure at:
users@infra.apache.org


Re: [PR] GH-39565: [C++] Do not concatenate chunked values of fixed-width types to run "array_take" [arrow]

Posted by "felipecrv (via GitHub)" <gi...@apache.org>.
felipecrv commented on code in PR #41700:
URL: https://github.com/apache/arrow/pull/41700#discussion_r1723505610


##########
cpp/src/arrow/compute/kernels/vector_selection_take_internal.cc:
##########
@@ -715,12 +853,247 @@ class TakeMetaFunction : public MetaFunction {
     return Status::NotImplemented(
         "Unsupported types for take operation: "
         "values=",
-        args[0].ToString(), "indices=", args[1].ToString());
+        args[0].ToString(), ", indices=", args[1].ToString());
   }
 };
 
 // ----------------------------------------------------------------------
 
+/// \brief Prepare the output array like ExecuteArrayKernel::PrepareOutput()
+std::shared_ptr<ArrayData> PrepareOutput(const ExecBatch& batch, int64_t length) {
+  DCHECK_EQ(batch.length, length);
+  auto out = std::make_shared<ArrayData>(batch.values[0].type(), length);
+  out->buffers.resize(batch.values[0].type()->layout().buffers.size());
+  return out;
+}
+
+Result<std::shared_ptr<Array>> ChunkedArrayAsArray(
+    const std::shared_ptr<ChunkedArray>& values, MemoryPool* pool) {
+  switch (values->num_chunks()) {
+    case 0:
+      return MakeArrayOfNull(values->type(), /*length=*/0, pool);
+    case 1:
+      return values->chunk(0);
+    default:
+      return Concatenate(values->chunks(), pool);
+  }
+}
+
+Status CallAAAKernel(ArrayKernelExec take_aaa_exec, KernelContext* ctx,
+                     std::shared_ptr<ArrayData> values,
+                     std::shared_ptr<ArrayData> indices, Datum* out) {
+  int64_t batch_length = values->length;
+  std::vector<Datum> args = {std::move(values), std::move(indices)};
+  ExecBatch array_array_batch(std::move(args), batch_length);
+  DCHECK_EQ(out->kind(), Datum::ARRAY);
+  ExecSpan exec_span{array_array_batch};
+  ExecResult result;
+  result.value = out->array();
+  RETURN_NOT_OK(take_aaa_exec(ctx, exec_span, &result));
+  DCHECK(result.is_array_data());
+  out->value = result.array_data();
+  return Status::OK();
+}
+
+Status CallCAAKernel(VectorKernel::ChunkedExec take_caa_exec, KernelContext* ctx,
+                     std::shared_ptr<ChunkedArray> values,
+                     std::shared_ptr<ArrayData> indices, Datum* out) {
+  int64_t batch_length = values->length();
+  std::vector<Datum> args = {std::move(values), std::move(indices)};
+  ExecBatch chunked_array_array_batch(std::move(args), batch_length);
+  DCHECK_EQ(out->kind(), Datum::ARRAY);
+  return take_caa_exec(ctx, chunked_array_array_batch, out);
+}
+
+Status TakeACCChunkedExec(ArrayKernelExec take_aaa_exec, KernelContext* ctx,
+                          const ExecBatch& batch, Datum* out) {
+  auto& values = batch.values[0].array();
+  auto& indices = batch.values[1].chunked_array();
+  auto num_chunks = indices->num_chunks();
+  std::vector<std::shared_ptr<Array>> new_chunks(num_chunks);
+  for (int i = 0; i < num_chunks; i++) {
+    // Take with that indices chunk
+    auto& indices_chunk = indices->chunk(i)->data();
+    Datum result = PrepareOutput(batch, values->length);
+    RETURN_NOT_OK(CallAAAKernel(take_aaa_exec, ctx, values, indices_chunk, &result));
+    new_chunks[i] = MakeArray(result.array());
+  }
+  out->value = std::make_shared<ChunkedArray>(std::move(new_chunks), values->type);
+  return Status::OK();
+}
+
+/// \brief Generic (slower) VectorKernel::exec_chunked (`CA->C`, `CC->C`, and `AC->C`).
+///
+/// This function concatenates the chunks of the values and then calls the `AA->A` take
+/// kernel to handle the `CA->C` cases. The ArrayData returned by the `AA->A` kernel is
+/// converted to a ChunkedArray with a single chunk to honor the `CA->C` contract.
+///
+/// For `CC->C` cases, it concatenates the chunks of the values and calls the `AA->A` take
+/// kernel for each chunk of the indices, producing a new chunked array with the same
+/// shape as the indices.
+///
+/// `AC->C` cases are trivially delegated to TakeACCChunkedExec without any concatenation.
+///
+/// \param take_aaa_exec The `AA->A` take kernel to use.
+Status GenericTakeChunkedExec(ArrayKernelExec take_aaa_exec, KernelContext* ctx,
+                              const ExecBatch& batch, Datum* out) {
+  const auto& args = batch.values;
+  if (args[0].kind() == Datum::CHUNKED_ARRAY) {
+    auto& values_chunked = args[0].chunked_array();

Review Comment:
   No problem. Even though `const` is inferred here and wouldn't be on line 940.



-- 
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: github-unsubscribe@arrow.apache.org

For queries about this service, please contact Infrastructure at:
users@infra.apache.org


Re: [PR] GH-39565: [C++] Do not concatenate chunked values of fixed-width types to run "array_take" [arrow]

Posted by "felipecrv (via GitHub)" <gi...@apache.org>.
felipecrv commented on code in PR #41700:
URL: https://github.com/apache/arrow/pull/41700#discussion_r1604325538


##########
cpp/src/arrow/compute/kernels/vector_selection_take_internal.cc:
##########
@@ -823,6 +732,129 @@ class TakeMetaFunction : public MetaFunction {
   TakeMetaFunction()
       : MetaFunction("take", Arity::Binary(), take_doc, GetDefaultTakeOptions()) {}
 
+  static Result<Datum> CallArrayTake(const std::vector<Datum>& args,
+                                     const TakeOptions& options, ExecContext* ctx) {
+    ARROW_ASSIGN_OR_RAISE(auto array_take_func,
+                          ctx->func_registry()->GetFunction("array_take"));
+    return array_take_func->Execute(args, &options, ctx);
+  }
+
+  static Result<std::shared_ptr<ArrayData>> TakeAAA(const std::vector<Datum>& args,
+                                                    const TakeOptions& options,
+                                                    ExecContext* ctx) {
+    DCHECK_EQ(args[0].kind(), Datum::ARRAY);
+    DCHECK_EQ(args[1].kind(), Datum::ARRAY);
+    ARROW_ASSIGN_OR_RAISE(Datum result, CallArrayTake(args, options, ctx));
+    return result.array();
+  }
+
+  static Result<std::shared_ptr<Array>> ChunkedArrayAsArray(
+      const std::shared_ptr<ChunkedArray>& values, MemoryPool* pool) {
+    switch (values->num_chunks()) {
+      case 0:
+        return MakeArrayOfNull(values->type(), /*length=*/0, pool);
+      case 1:
+        return values->chunk(0);
+      default:
+        return Concatenate(values->chunks(), pool);
+    }
+  }
+
+  static Result<std::shared_ptr<ArrayData>> TakeCAA(
+      const std::shared_ptr<ChunkedArray>& values, const Array& indices,
+      const TakeOptions& options, ExecContext* ctx) {
+    // "array_take" can handle CA->A cases directly
+    // (via their VectorKernel::chunked_exec)
+    ARROW_ASSIGN_OR_RAISE(auto result, CallArrayTake({values, indices}, options, ctx));
+    return result.array();
+  }
+
+  static Result<std::shared_ptr<ChunkedArray>> TakeCAC(
+      const std::shared_ptr<ChunkedArray>& values, const Array& indices,
+      const TakeOptions& options, ExecContext* ctx) {
+    ARROW_ASSIGN_OR_RAISE(auto new_chunk, TakeCAA(values, indices, options, ctx));
+    return std::make_shared<ChunkedArray>(MakeArray(std::move(new_chunk)));
+  }
+
+  static Result<std::shared_ptr<ChunkedArray>> TakeCCC(
+      const std::shared_ptr<ChunkedArray>& values,
+      const std::shared_ptr<ChunkedArray>& indices, const TakeOptions& options,
+      ExecContext* ctx) {
+    // XXX: for every chunk in indices, values are gathered from all chunks in values to
+    // form a new chunk in the result. Performing this concatenation is not ideal, but
+    // greatly simplifies the implementation before something more efficient is
+    // implemented.
+    ARROW_ASSIGN_OR_RAISE(auto values_array,
+                          ChunkedArrayAsArray(values, ctx->memory_pool()));
+    std::vector<Datum> args = {std::move(values_array), {}};
+    std::vector<std::shared_ptr<Array>> new_chunks;
+    new_chunks.resize(indices->num_chunks());
+    for (int i = 0; i < indices->num_chunks(); i++) {
+      args[1] = indices->chunk(i);
+      // XXX: this loop can use TakeCAA once it can handle ChunkedArray
+      // without concatenating first

Review Comment:
    I'm working on this one.



-- 
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: github-unsubscribe@arrow.apache.org

For queries about this service, please contact Infrastructure at:
users@infra.apache.org


Re: [PR] GH-39565: [C++] Do not concatenate chunked values of fixed-width types to run "array_take" [arrow]

Posted by "mapleFU (via GitHub)" <gi...@apache.org>.
mapleFU commented on PR #41700:
URL: https://github.com/apache/arrow/pull/41700#issuecomment-2117785204

   May I ask a unrelated question, when would we call assert and when call DCHECK, since I think they would likely to be same?


-- 
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: github-unsubscribe@arrow.apache.org

For queries about this service, please contact Infrastructure at:
users@infra.apache.org


Re: [PR] GH-39565: [C++] Do not concatenate chunked values of fixed-width types to run "array_take" [arrow]

Posted by "pitrou (via GitHub)" <gi...@apache.org>.
pitrou commented on PR #41700:
URL: https://github.com/apache/arrow/pull/41700#issuecomment-2298968603

   @github-actions crossbow submit -g cpp


-- 
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: github-unsubscribe@arrow.apache.org

For queries about this service, please contact Infrastructure at:
users@infra.apache.org


Re: [PR] GH-39565: [C++] Do not concatenate chunked values of fixed-width types to run "array_take" [arrow]

Posted by "pitrou (via GitHub)" <gi...@apache.org>.
pitrou commented on PR #41700:
URL: https://github.com/apache/arrow/pull/41700#issuecomment-2299076111

   Note that there's something inherently suboptimal in this PR: we're trading the concatenation of the chunked values (essentially allocating a new values array) against the resolution of many chunked indices (essentially allocating _two_ new indices arrays). This is only beneficial if the value width is quite large (say a 256-byte FSB) _or_ the number of indices is much smaller than the number of values.
   
   In the end, perhaps we want to guard this with a heuristic based on total byte size of values and length of indices.


-- 
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: github-unsubscribe@arrow.apache.org

For queries about this service, please contact Infrastructure at:
users@infra.apache.org


Re: [PR] GH-39565: [C++] Do not concatenate chunked values of fixed-width types to run "array_take" [arrow]

Posted by "felipecrv (via GitHub)" <gi...@apache.org>.
felipecrv commented on PR #41700:
URL: https://github.com/apache/arrow/pull/41700#issuecomment-2299183276

   > Note that there's something inherently suboptimal in this PR: we're trading the concatenation of the chunked values (essentially allocating a new values array) against the resolution of many chunked indices (essentially allocating _two_ new indices arrays). This is only beneficial if the value width is quite large (say a 256-byte FSB) _or_ the number of indices is much smaller than the number of values.
   
   I don't remember getting bad results like this on an ARM Macbook. I will try benchmarking on x86 as well.
   
   > _(the fact that our take benchmarks currently use the same number of indices as values doesn't help :-))_
   
   Indeed. My assumption when going for the allocation of indices was that indices are cheaper to allocate than the concatenation of values.
    
   > In the end, perhaps we want to guard this with a heuristic based on total byte size of values and length of indices.
   
   Yeah, but this kind of branching is really bad for the confidence in unit tests. I will see what can be done.


-- 
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: github-unsubscribe@arrow.apache.org

For queries about this service, please contact Infrastructure at:
users@infra.apache.org


Re: [PR] GH-39565: [C++] Do not concatenate chunked values of fixed-width types to run "array_take" [arrow]

Posted by "pitrou (via GitHub)" <gi...@apache.org>.
pitrou commented on PR #41700:
URL: https://github.com/apache/arrow/pull/41700#issuecomment-2299272905

   Something you could do in this PR, though, is to resolve the indices in chunks of say 1024. This would at least ease the allocation cost and memory pressure.
   
   


-- 
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: github-unsubscribe@arrow.apache.org

For queries about this service, please contact Infrastructure at:
users@infra.apache.org


Re: [PR] GH-39565: [C++] Do not concatenate chunked values of fixed-width types to run "array_take" [arrow]

Posted by "felipecrv (via GitHub)" <gi...@apache.org>.
felipecrv commented on code in PR #41700:
URL: https://github.com/apache/arrow/pull/41700#discussion_r1641239721


##########
cpp/src/arrow/compute/kernels/vector_selection_internal.cc:
##########
@@ -60,6 +60,7 @@ void RegisterSelectionFunction(const std::string& name, FunctionDoc doc,
         {std::move(kernel_data.value_type), std::move(kernel_data.selection_type)},
         OutputType(FirstType));
     base_kernel.exec = kernel_data.exec;
+    base_kernel.exec_chunked = kernel_data.chunked_exec;

Review Comment:
   The member variable is called `exec_chunked` but the type is called `ChunkedExec` (so confusing). In this PR I ended up sticking to `chunked_exec`. Once everything is reviewed and merged I could try to unify things to the direction people prefer.



-- 
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: github-unsubscribe@arrow.apache.org

For queries about this service, please contact Infrastructure at:
users@infra.apache.org


Re: [PR] GH-39565: [C++] Do not concatenate chunked values of fixed-width types to run "array_take" [arrow]

Posted by "felipecrv (via GitHub)" <gi...@apache.org>.
felipecrv commented on PR #41700:
URL: https://github.com/apache/arrow/pull/41700#issuecomment-2232107261

   @pitrou I improved the tests (#43291) and fixed one of the issues you reproduced. Tomorrow I will fix the one related to dictionary arrays (which the modified tests successfully reproduce).
   
   The tests start failing after the `Take: Make "array_take" handle CA->C cases by populating VectorKernel::exec_chunked` commit.
   
   (I pushed the tests changes here as well, so this PR is expected to fail before I fix the DICTIONARY array issue)


-- 
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: github-unsubscribe@arrow.apache.org

For queries about this service, please contact Infrastructure at:
users@infra.apache.org


Re: [PR] GH-39565: [C++] Do not concatenate chunked values of fixed-width types to run "array_take" [arrow]

Posted by "felipecrv (via GitHub)" <gi...@apache.org>.
felipecrv commented on PR #41700:
URL: https://github.com/apache/arrow/pull/41700#issuecomment-2117838394

   > May I ask a unrelated question, when would we call assert and when call DCHECK, since I think they would likely to be same?
   
   We call assert in headers because we don't want to pay the cost of including `logging.h` everywhere. Think of `assert` as lighter-weight debug checks. But if you see an assert in a `.cc` file tell me to change it to `DCHECK*`.


-- 
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: github-unsubscribe@arrow.apache.org

For queries about this service, please contact Infrastructure at:
users@infra.apache.org


Re: [PR] GH-39565: [C++] Do not concatenate chunked values of fixed-width types to run "array_take" [arrow]

Posted by "github-actions[bot] (via GitHub)" <gi...@apache.org>.
github-actions[bot] commented on PR #41700:
URL: https://github.com/apache/arrow/pull/41700#issuecomment-4680547585

   Thank you for your contribution. Unfortunately, this pull request 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 PR will be closed in 14 days.  Feel free to re-open this if it has been closed in error. If you do not have repository permissions to reopen the PR, please tag a maintainer.


-- 
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: github-unsubscribe@arrow.apache.org

For queries about this service, please contact Infrastructure at:
users@infra.apache.org


Re: [PR] GH-39565: [C++] Do not concatenate chunked values of fixed-width types to run "array_take" [arrow]

Posted by "felipecrv (via GitHub)" <gi...@apache.org>.
felipecrv commented on code in PR #41700:
URL: https://github.com/apache/arrow/pull/41700#discussion_r1685743464


##########
cpp/src/arrow/compute/kernels/vector_selection_take_internal.cc:
##########
@@ -715,12 +853,244 @@ class TakeMetaFunction : public MetaFunction {
     return Status::NotImplemented(
         "Unsupported types for take operation: "
         "values=",
-        args[0].ToString(), "indices=", args[1].ToString());
+        args[0].ToString(), ", indices=", args[1].ToString());
   }
 };
 
 // ----------------------------------------------------------------------
 
+/// \brief Prepare the output array like ExecuteArrayKernel::PrepareOutput()
+std::shared_ptr<ArrayData> PrepareOutput(const ExecBatch& batch, int64_t length) {
+  DCHECK_EQ(batch.length, length);
+  auto out = std::make_shared<ArrayData>(batch.values[0].type(), length);
+  out->buffers.resize(batch.values[0].type()->layout().buffers.size());
+  return out;
+}
+
+Result<std::shared_ptr<Array>> ChunkedArrayAsArray(
+    const std::shared_ptr<ChunkedArray>& values, MemoryPool* pool) {
+  switch (values->num_chunks()) {
+    case 0:
+      return MakeArrayOfNull(values->type(), /*length=*/0, pool);
+    case 1:
+      return values->chunk(0);
+    default:
+      return Concatenate(values->chunks(), pool);
+  }
+}
+
+Status CallAAAKernel(ArrayKernelExec take_aaa_exec, KernelContext* ctx,
+                     std::shared_ptr<ArrayData> values,
+                     std::shared_ptr<ArrayData> indices, Datum* out) {
+  int64_t batch_length = values->length;
+  std::vector<Datum> args = {std::move(values), std::move(indices)};
+  ExecBatch array_array_batch(std::move(args), batch_length);
+  DCHECK_EQ(out->kind(), Datum::ARRAY);
+  ExecSpan exec_span{array_array_batch};
+  ExecResult result;
+  result.value = out->array();
+  return take_aaa_exec(ctx, exec_span, &result);
+}
+
+Status CallCAAKernel(VectorKernel::ChunkedExec take_caa_exec, KernelContext* ctx,
+                     std::shared_ptr<ChunkedArray> values,
+                     std::shared_ptr<ArrayData> indices, Datum* out) {
+  int64_t batch_length = values->length();
+  std::vector<Datum> args = {std::move(values), std::move(indices)};
+  ExecBatch chunked_array_array_batch(std::move(args), batch_length);
+  DCHECK_EQ(out->kind(), Datum::ARRAY);
+  return take_caa_exec(ctx, chunked_array_array_batch, out);
+}
+
+Status TakeACCChunkedExec(ArrayKernelExec take_aaa_exec, KernelContext* ctx,
+                          const ExecBatch& batch, Datum* out) {
+  auto& values = batch.values[0].array();
+  auto& indices = batch.values[1].chunked_array();
+  auto num_chunks = indices->num_chunks();
+  std::vector<std::shared_ptr<Array>> new_chunks(num_chunks);
+  for (int i = 0; i < num_chunks; i++) {
+    // Take with that indices chunk
+    auto& indices_chunk = indices->chunk(i)->data();
+    Datum result = PrepareOutput(batch, values->length);
+    RETURN_NOT_OK(CallAAAKernel(take_aaa_exec, ctx, values, indices_chunk, &result));
+    new_chunks[i] = MakeArray(result.array());
+  }
+  out->value = std::make_shared<ChunkedArray>(std::move(new_chunks), values->type);
+  return Status::OK();
+}
+
+/// \brief Generic (slower) VectorKernel::exec_chunked (`CA->C`, `CC->C`, and `AC->C`).
+///
+/// This function concatenates the chunks of the values and then calls the `AA->A` take
+/// kernel to handle the `CA->C` cases. The ArrayData returned by the `AA->A` kernel is
+/// converted to a ChunkedArray with a single chunk to honor the `CA->C` contract.
+///
+/// For `CC->C` cases, it concatenates the chunks of the values and calls the `AA->A` take
+/// kernel for each chunk of the indices, producing a new chunked array with the same
+/// shape as the indices.
+///
+/// `AC->C` cases are trivially delegated to TakeACCChunkedExec without any concatenation.
+///
+/// \param take_aaa_exec The `AA->A` take kernel to use.
+Status GenericTakeChunkedExec(ArrayKernelExec take_aaa_exec, KernelContext* ctx,
+                              const ExecBatch& batch, Datum* out) {
+  const auto& args = batch.values;
+  if (args[0].kind() == Datum::CHUNKED_ARRAY) {
+    auto& values_chunked = args[0].chunked_array();
+    ARROW_ASSIGN_OR_RAISE(auto values_array,
+                          ChunkedArrayAsArray(values_chunked, ctx->memory_pool()));
+    if (args[1].kind() == Datum::ARRAY) {
+      // CA->C
+      auto& indices = args[1].array();
+      DCHECK_EQ(values_array->length(), batch.length);
+      {
+        // AA->A
+        RETURN_NOT_OK(
+            CallAAAKernel(take_aaa_exec, ctx, values_array->data(), indices, out));
+        out->value = std::make_shared<ChunkedArray>(MakeArray(out->array()));
+      }
+      return Status::OK();
+    } else if (args[1].kind() == Datum::CHUNKED_ARRAY) {
+      // CC->C
+      const auto& indices = args[1].chunked_array();
+      std::vector<std::shared_ptr<Array>> new_chunks;
+      for (int i = 0; i < indices->num_chunks(); i++) {
+        // AA->A
+        auto& indices_chunk = indices->chunk(i)->data();
+        Datum result = PrepareOutput(batch, values_array->length());
+        RETURN_NOT_OK(CallAAAKernel(take_aaa_exec, ctx, values_array->data(),
+                                    indices_chunk, &result));
+        new_chunks.push_back(MakeArray(result.array()));
+      }
+      DCHECK(out->is_array());
+      out->value =
+          std::make_shared<ChunkedArray>(std::move(new_chunks), values_chunked->type());
+      return Status::OK();
+    }
+  } else {
+    // VectorKernel::exec_chunked are only called when at least one of the inputs is
+    // chunked, so we should be able to assume that args[1] is a chunked array when
+    // everything is wired up correctly.
+    if (args[1].kind() == Datum::CHUNKED_ARRAY) {
+      // AC->C
+      return TakeACCChunkedExec(take_aaa_exec, ctx, batch, out);
+    } else {
+      DCHECK(false) << "Unexpected kind for array_take's exec_chunked kernel: values="
+                    << args[0].ToString() << ", indices=" << args[1].ToString();
+    }
+  }
+  return Status::NotImplemented(
+      "Unsupported kinds for 'array_take', try using 'take': "
+      "values=",
+      args[0].ToString(), ", indices=", args[1].ToString());
+}
+
+template <ArrayKernelExec kTakeAAAExec>
+struct GenericTakeChunkedExecFunctor {
+  static Status Exec(KernelContext* ctx, const ExecBatch& batch, Datum* out) {
+    return GenericTakeChunkedExec(kTakeAAAExec, ctx, batch, out);
+  }
+};
+
+/// \brief Specialized (faster) VectorKernel::exec_chunked (`CA->C`, `CC->C`, `AC->C`).
+///
+/// This function doesn't ever need to concatenate the chunks of the values, so it can be
+/// more efficient than GenericTakeChunkedExec that can only delegate to the `AA->A` take
+/// kernels.
+///
+/// For `CA->C` cases, it can call the `CA->A` take kernel directly [1] and trivially
+/// convert the result to a ChunkedArray of a single chunk to honor the `CA->C` contract.
+///
+/// For `CC->C` cases it can call the `CA->A` take kernel for each chunk of the indices to
+/// get each chunk that becomes the ChunkedArray output.
+///
+/// `AC->C` cases are trivially delegated to TakeACCChunkedExec.
+///
+/// \param take_aaa_exec The `AA->A` take kernel to use.
+Status SpecialTakeChunkedExec(const ArrayKernelExec take_aaa_exec,
+                              VectorKernel::ChunkedExec take_caa_exec, KernelContext* ctx,
+                              const ExecBatch& batch, Datum* out) {
+  Datum result = PrepareOutput(batch, batch.length);
+  auto* pool = ctx->memory_pool();
+  const auto& args = batch.values;
+  if (args[0].kind() == Datum::CHUNKED_ARRAY) {
+    auto& values_chunked = args[0].chunked_array();
+    std::shared_ptr<Array> single_chunk = nullptr;
+    if (values_chunked->num_chunks() == 0 || values_chunked->length() == 0) {
+      ARROW_ASSIGN_OR_RAISE(single_chunk,
+                            MakeArrayOfNull(values_chunked->type(), /*length=*/0, pool));
+    } else if (values_chunked->num_chunks() == 1) {
+      single_chunk = values_chunked->chunk(0);
+    }
+
+    if (args[1].kind() == Datum::ARRAY) {
+      // CA->C
+      auto& indices = args[1].array();
+      if (single_chunk) {
+        // AA->A
+        DCHECK_EQ(single_chunk->length(), batch.length);
+        // If the ChunkedArray was cheaply converted to a single chunk,
+        // we can use the AA->A take kernel directly.
+        RETURN_NOT_OK(
+            CallAAAKernel(take_aaa_exec, ctx, single_chunk->data(), indices, out));
+        out->value = std::make_shared<ChunkedArray>(MakeArray(out->array()));
+        return Status::OK();
+      }
+      // Instead of concatenating the chunks, we call the CA->A take kernel

Review Comment:
   It dispatches to the kernel directly (via a C function pointer call) without going through dispatching logic again.



-- 
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: github-unsubscribe@arrow.apache.org

For queries about this service, please contact Infrastructure at:
users@infra.apache.org


Re: [PR] GH-39565: [C++] Do not concatenate chunked values of fixed-width types to run "array_take" [arrow]

Posted by "pitrou (via GitHub)" <gi...@apache.org>.
pitrou commented on PR #41700:
URL: https://github.com/apache/arrow/pull/41700#issuecomment-2299054390

   @archery please benchmark lang=c++


-- 
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: github-unsubscribe@arrow.apache.org

For queries about this service, please contact Infrastructure at:
users@infra.apache.org


Re: [PR] GH-39565: [C++] Do not concatenate chunked values of fixed-width types to run "array_take" [arrow]

Posted by "felipecrv (via GitHub)" <gi...@apache.org>.
felipecrv commented on code in PR #41700:
URL: https://github.com/apache/arrow/pull/41700#discussion_r1723514025


##########
cpp/src/arrow/compute/kernels/vector_selection_take_internal.cc:
##########
@@ -357,15 +481,22 @@ template <typename IndexCType, typename ValueBitWidthConstant,
 struct FixedWidthTakeImpl {
   static constexpr int kValueWidthInBits = ValueBitWidthConstant::value;
 
-  static Status Exec(KernelContext* ctx, const ArraySpan& values,
+  static Status Exec(KernelContext* ctx, const ValuesSpan& values,
                      const ArraySpan& indices, ArrayData* out_arr, int64_t factor) {
 #ifndef NDEBUG
-    int64_t bit_width = util::FixedWidthInBits(*values.type);
+    int64_t bit_width = util::FixedWidthInBits(*values.type());
     DCHECK(WithFactor::value || (kValueWidthInBits == bit_width && factor == 1));
     DCHECK(!WithFactor::value ||
            (factor > 0 && kValueWidthInBits == 8 &&  // factors are used with bytes
             static_cast<int64_t>(factor * kValueWidthInBits) == bit_width));
 #endif
+    return values.is_chunked()
+               ? ChunkedExec(ctx, values.chunked_array(), indices, out_arr, factor)
+               : Exec(ctx, values.array(), indices, out_arr, factor);
+  }
+
+  static Status Exec(KernelContext* ctx, const ArraySpan& values,

Review Comment:
   Related: https://github.com/apache/arrow/pull/41700#discussion_r1641239721



-- 
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: github-unsubscribe@arrow.apache.org

For queries about this service, please contact Infrastructure at:
users@infra.apache.org


Re: [PR] GH-39565: [C++] Do not concatenate chunked values of fixed-width types to run "array_take" [arrow]

Posted by "felipecrv (via GitHub)" <gi...@apache.org>.
felipecrv commented on code in PR #41700:
URL: https://github.com/apache/arrow/pull/41700#discussion_r1723511661


##########
cpp/src/arrow/compute/kernels/vector_selection_take_internal.cc:
##########
@@ -326,6 +327,129 @@ namespace {
 
 using TakeState = OptionsWrapper<TakeOptions>;
 
+class ValuesSpan {
+ private:
+  const std::shared_ptr<ChunkedArray> chunked_ = nullptr;
+  const ArraySpan chunk0_;  // first chunk or the whole array
+
+ public:
+  explicit ValuesSpan(const std::shared_ptr<ChunkedArray> values)
+      : chunked_(std::move(values)), chunk0_{*values->chunk(0)->data()} {
+    DCHECK(chunked_);
+    DCHECK_GT(chunked_->num_chunks(), 0);
+  }
+
+  explicit ValuesSpan(const ArraySpan& values) : chunk0_(values) {}
+
+  bool is_chunked() const { return chunked_ != nullptr; }
+
+  const ChunkedArray& chunked_array() const {
+    DCHECK(is_chunked());
+    return *chunked_;
+  }
+
+  const ArraySpan& chunk0() const { return chunk0_; }
+
+  const ArraySpan& array() const {
+    DCHECK(!is_chunked());
+    return chunk0_;
+  }
+
+  const DataType* type() const { return chunk0_.type; }
+
+  int64_t length() const { return is_chunked() ? chunked_->length() : array().length; }
+
+  bool MayHaveNulls() const {
+    return is_chunked() ? chunked_->null_count() != 0 : array().MayHaveNulls();
+  }
+};
+
+struct ChunkedFixedWidthValuesSpan {
+ private:
+  // src_residual_bit_offsets_[i] is used to store the bit offset of the first byte (0-7)
+  // in src_chunks_[i] iff kValueWidthInBits == 1.
+  std::vector<int> src_residual_bit_offsets;
+  // Pre-computed pointers to the start of the values in each chunk.
+  std::vector<const uint8_t*> src_chunks;
+
+ public:
+  explicit ChunkedFixedWidthValuesSpan(const ChunkedArray& values) {
+    const bool chunk_values_are_bit_sized = values.type()->id() == Type::BOOL;
+    DCHECK_EQ(chunk_values_are_bit_sized, util::FixedWidthInBytes(*values.type()) == -1);
+    if (chunk_values_are_bit_sized) {
+      src_residual_bit_offsets.resize(values.num_chunks());
+    }
+    src_chunks.resize(values.num_chunks());
+
+    for (int i = 0; i < values.num_chunks(); ++i) {
+      const ArraySpan chunk{*values.chunk(i)->data()};
+      DCHECK(util::IsFixedWidthLike(chunk));
+
+      auto offset_pointer = util::OffsetPointerOfFixedBitWidthValues(chunk);
+      if (chunk_values_are_bit_sized) {
+        src_residual_bit_offsets[i] = offset_pointer.first;
+      } else {
+        DCHECK_EQ(offset_pointer.first, 0);
+      }
+      src_chunks[i] = offset_pointer.second;
+    }
+  }
+
+  ~ChunkedFixedWidthValuesSpan() = default;

Review Comment:
   I will remove.



-- 
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: github-unsubscribe@arrow.apache.org

For queries about this service, please contact Infrastructure at:
users@infra.apache.org


Re: [PR] GH-39565: [C++] Do not concatenate chunked values of fixed-width types to run "array_take" [arrow]

Posted by "felipecrv (via GitHub)" <gi...@apache.org>.
felipecrv commented on code in PR #41700:
URL: https://github.com/apache/arrow/pull/41700#discussion_r1723512057


##########
cpp/src/arrow/compute/kernels/vector_selection_take_internal.cc:
##########
@@ -357,15 +481,22 @@ template <typename IndexCType, typename ValueBitWidthConstant,
 struct FixedWidthTakeImpl {
   static constexpr int kValueWidthInBits = ValueBitWidthConstant::value;
 
-  static Status Exec(KernelContext* ctx, const ArraySpan& values,
+  static Status Exec(KernelContext* ctx, const ValuesSpan& values,
                      const ArraySpan& indices, ArrayData* out_arr, int64_t factor) {
 #ifndef NDEBUG
-    int64_t bit_width = util::FixedWidthInBits(*values.type);
+    int64_t bit_width = util::FixedWidthInBits(*values.type());
     DCHECK(WithFactor::value || (kValueWidthInBits == bit_width && factor == 1));
     DCHECK(!WithFactor::value ||
            (factor > 0 && kValueWidthInBits == 8 &&  // factors are used with bytes
             static_cast<int64_t>(factor * kValueWidthInBits) == bit_width));
 #endif
+    return values.is_chunked()
+               ? ChunkedExec(ctx, values.chunked_array(), indices, out_arr, factor)
+               : Exec(ctx, values.array(), indices, out_arr, factor);
+  }
+
+  static Status Exec(KernelContext* ctx, const ArraySpan& values,

Review Comment:
   The "exec" and "chunked exec" dual seems to be all over the place. Adding `Contiguous` here would introduce new terminology.
   https://github.com/apache/arrow/blob/cc3c868aea7317a58447658f1c165ad352cd4865/cpp/src/arrow/compute/kernel.h#L600-L605



-- 
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: github-unsubscribe@arrow.apache.org

For queries about this service, please contact Infrastructure at:
users@infra.apache.org


Re: [PR] GH-39565: [C++] Do not concatenate chunked values of fixed-width types to run "array_take" [arrow]

Posted by "github-actions[bot] (via GitHub)" <gi...@apache.org>.
github-actions[bot] commented on PR #41700:
URL: https://github.com/apache/arrow/pull/41700#issuecomment-2299254025

   Revision: c0de2252c2ec3bd208e50bc88393dfb8163d8c5b
   
   Submitted crossbow builds: [ursacomputing/crossbow @ actions-ea181364bd](https://github.com/ursacomputing/crossbow/branches/all?query=actions-ea181364bd)
   
   |Task|Status|
   |----|------|
   |test-alpine-linux-cpp|[![GitHub Actions](https://github.com/ursacomputing/crossbow/actions/workflows/crossbow.yml/badge.svg?branch=actions-ea181364bd-github-test-alpine-linux-cpp)](https://github.com/ursacomputing/crossbow/actions/runs/10475352031/job/29011801655)|
   |test-build-cpp-fuzz|[![GitHub Actions](https://github.com/ursacomputing/crossbow/actions/workflows/crossbow.yml/badge.svg?branch=actions-ea181364bd-github-test-build-cpp-fuzz)](https://github.com/ursacomputing/crossbow/actions/runs/10475352394/job/29011803417)|
   |test-conda-cpp|[![GitHub Actions](https://github.com/ursacomputing/crossbow/actions/workflows/crossbow.yml/badge.svg?branch=actions-ea181364bd-github-test-conda-cpp)](https://github.com/ursacomputing/crossbow/actions/runs/10475352242/job/29011802884)|
   |test-conda-cpp-valgrind|[![GitHub Actions](https://github.com/ursacomputing/crossbow/actions/workflows/crossbow.yml/badge.svg?branch=actions-ea181364bd-github-test-conda-cpp-valgrind)](https://github.com/ursacomputing/crossbow/actions/runs/10475352159/job/29011802608)|
   |test-cuda-cpp|[![GitHub Actions](https://github.com/ursacomputing/crossbow/actions/workflows/crossbow.yml/badge.svg?branch=actions-ea181364bd-github-test-cuda-cpp)](https://github.com/ursacomputing/crossbow/actions/runs/10475352612/job/29011804243)|
   |test-debian-12-cpp-amd64|[![GitHub Actions](https://github.com/ursacomputing/crossbow/actions/workflows/crossbow.yml/badge.svg?branch=actions-ea181364bd-github-test-debian-12-cpp-amd64)](https://github.com/ursacomputing/crossbow/actions/runs/10475352592/job/29011804068)|
   |test-debian-12-cpp-i386|[![GitHub Actions](https://github.com/ursacomputing/crossbow/actions/workflows/crossbow.yml/badge.svg?branch=actions-ea181364bd-github-test-debian-12-cpp-i386)](https://github.com/ursacomputing/crossbow/actions/runs/10475352444/job/29011803449)|
   |test-fedora-39-cpp|[![GitHub Actions](https://github.com/ursacomputing/crossbow/actions/workflows/crossbow.yml/badge.svg?branch=actions-ea181364bd-github-test-fedora-39-cpp)](https://github.com/ursacomputing/crossbow/actions/runs/10475352029/job/29011802010)|
   |test-ubuntu-20.04-cpp|[![GitHub Actions](https://github.com/ursacomputing/crossbow/actions/workflows/crossbow.yml/badge.svg?branch=actions-ea181364bd-github-test-ubuntu-20.04-cpp)](https://github.com/ursacomputing/crossbow/actions/runs/10475352042/job/29011801526)|
   |test-ubuntu-20.04-cpp-bundled|[![GitHub Actions](https://github.com/ursacomputing/crossbow/actions/workflows/crossbow.yml/badge.svg?branch=actions-ea181364bd-github-test-ubuntu-20.04-cpp-bundled)](https://github.com/ursacomputing/crossbow/actions/runs/10475352259/job/29011803198)|
   |test-ubuntu-20.04-cpp-minimal-with-formats|[![GitHub Actions](https://github.com/ursacomputing/crossbow/actions/workflows/crossbow.yml/badge.svg?branch=actions-ea181364bd-github-test-ubuntu-20.04-cpp-minimal-with-formats)](https://github.com/ursacomputing/crossbow/actions/runs/10475352026/job/29011801507)|
   |test-ubuntu-20.04-cpp-thread-sanitizer|[![GitHub Actions](https://github.com/ursacomputing/crossbow/actions/workflows/crossbow.yml/badge.svg?branch=actions-ea181364bd-github-test-ubuntu-20.04-cpp-thread-sanitizer)](https://github.com/ursacomputing/crossbow/actions/runs/10475352353/job/29011803186)|
   |test-ubuntu-22.04-cpp|[![GitHub Actions](https://github.com/ursacomputing/crossbow/actions/workflows/crossbow.yml/badge.svg?branch=actions-ea181364bd-github-test-ubuntu-22.04-cpp)](https://github.com/ursacomputing/crossbow/actions/runs/10475352185/job/29011802616)|
   |test-ubuntu-22.04-cpp-20|[![GitHub Actions](https://github.com/ursacomputing/crossbow/actions/workflows/crossbow.yml/badge.svg?branch=actions-ea181364bd-github-test-ubuntu-22.04-cpp-20)](https://github.com/ursacomputing/crossbow/actions/runs/10475352406/job/29011803431)|
   |test-ubuntu-22.04-cpp-emscripten|[![GitHub Actions](https://github.com/ursacomputing/crossbow/actions/workflows/crossbow.yml/badge.svg?branch=actions-ea181364bd-github-test-ubuntu-22.04-cpp-emscripten)](https://github.com/ursacomputing/crossbow/actions/runs/10475352016/job/29011801931)|
   |test-ubuntu-22.04-cpp-no-threading|[![GitHub Actions](https://github.com/ursacomputing/crossbow/actions/workflows/crossbow.yml/badge.svg?branch=actions-ea181364bd-github-test-ubuntu-22.04-cpp-no-threading)](https://github.com/ursacomputing/crossbow/actions/runs/10475352108/job/29011802394)|
   |test-ubuntu-24.04-cpp|[![GitHub Actions](https://github.com/ursacomputing/crossbow/actions/workflows/crossbow.yml/badge.svg?branch=actions-ea181364bd-github-test-ubuntu-24.04-cpp)](https://github.com/ursacomputing/crossbow/actions/runs/10475352037/job/29011801584)|
   |test-ubuntu-24.04-cpp-gcc-13-bundled|[![GitHub Actions](https://github.com/ursacomputing/crossbow/actions/workflows/crossbow.yml/badge.svg?branch=actions-ea181364bd-github-test-ubuntu-24.04-cpp-gcc-13-bundled)](https://github.com/ursacomputing/crossbow/actions/runs/10475352371/job/29011803185)|
   |test-ubuntu-24.04-cpp-gcc-14|[![GitHub Actions](https://github.com/ursacomputing/crossbow/actions/workflows/crossbow.yml/badge.svg?branch=actions-ea181364bd-github-test-ubuntu-24.04-cpp-gcc-14)](https://github.com/ursacomputing/crossbow/actions/runs/10475352187/job/29011803184)|


-- 
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: github-unsubscribe@arrow.apache.org

For queries about this service, please contact Infrastructure at:
users@infra.apache.org


Re: [PR] GH-39565: [C++] Do not concatenate chunked values of fixed-width types to run "array_take" [arrow]

Posted by "felipecrv (via GitHub)" <gi...@apache.org>.
felipecrv commented on PR #41700:
URL: https://github.com/apache/arrow/pull/41700#issuecomment-2531607070

   @pitrou what conditional checks should I add here to avoid regressions? I'm giving up on making the non-concatenation versions work well for integer arrays and want to merge this PR sooner rather than later and then start working on the string array implementation which is what will unlock most user value in the first place.


-- 
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: github-unsubscribe@arrow.apache.org

For queries about this service, please contact Infrastructure at:
users@infra.apache.org


Re: [PR] GH-39565: [C++] Do not concatenate chunked values of fixed-width types to run "array_take" [arrow]

Posted by "felipecrv (via GitHub)" <gi...@apache.org>.
felipecrv commented on code in PR #41700:
URL: https://github.com/apache/arrow/pull/41700#discussion_r1685742964


##########
cpp/src/arrow/compute/kernels/vector_selection_take_internal.cc:
##########
@@ -715,12 +853,244 @@ class TakeMetaFunction : public MetaFunction {
     return Status::NotImplemented(
         "Unsupported types for take operation: "
         "values=",
-        args[0].ToString(), "indices=", args[1].ToString());
+        args[0].ToString(), ", indices=", args[1].ToString());
   }
 };
 
 // ----------------------------------------------------------------------
 
+/// \brief Prepare the output array like ExecuteArrayKernel::PrepareOutput()
+std::shared_ptr<ArrayData> PrepareOutput(const ExecBatch& batch, int64_t length) {
+  DCHECK_EQ(batch.length, length);
+  auto out = std::make_shared<ArrayData>(batch.values[0].type(), length);
+  out->buffers.resize(batch.values[0].type()->layout().buffers.size());
+  return out;
+}
+
+Result<std::shared_ptr<Array>> ChunkedArrayAsArray(
+    const std::shared_ptr<ChunkedArray>& values, MemoryPool* pool) {
+  switch (values->num_chunks()) {
+    case 0:
+      return MakeArrayOfNull(values->type(), /*length=*/0, pool);
+    case 1:
+      return values->chunk(0);
+    default:
+      return Concatenate(values->chunks(), pool);
+  }
+}
+
+Status CallAAAKernel(ArrayKernelExec take_aaa_exec, KernelContext* ctx,
+                     std::shared_ptr<ArrayData> values,
+                     std::shared_ptr<ArrayData> indices, Datum* out) {
+  int64_t batch_length = values->length;
+  std::vector<Datum> args = {std::move(values), std::move(indices)};
+  ExecBatch array_array_batch(std::move(args), batch_length);
+  DCHECK_EQ(out->kind(), Datum::ARRAY);
+  ExecSpan exec_span{array_array_batch};
+  ExecResult result;
+  result.value = out->array();
+  return take_aaa_exec(ctx, exec_span, &result);
+}
+
+Status CallCAAKernel(VectorKernel::ChunkedExec take_caa_exec, KernelContext* ctx,
+                     std::shared_ptr<ChunkedArray> values,
+                     std::shared_ptr<ArrayData> indices, Datum* out) {
+  int64_t batch_length = values->length();
+  std::vector<Datum> args = {std::move(values), std::move(indices)};
+  ExecBatch chunked_array_array_batch(std::move(args), batch_length);
+  DCHECK_EQ(out->kind(), Datum::ARRAY);
+  return take_caa_exec(ctx, chunked_array_array_batch, out);
+}
+
+Status TakeACCChunkedExec(ArrayKernelExec take_aaa_exec, KernelContext* ctx,
+                          const ExecBatch& batch, Datum* out) {
+  auto& values = batch.values[0].array();
+  auto& indices = batch.values[1].chunked_array();
+  auto num_chunks = indices->num_chunks();
+  std::vector<std::shared_ptr<Array>> new_chunks(num_chunks);
+  for (int i = 0; i < num_chunks; i++) {
+    // Take with that indices chunk
+    auto& indices_chunk = indices->chunk(i)->data();
+    Datum result = PrepareOutput(batch, values->length);
+    RETURN_NOT_OK(CallAAAKernel(take_aaa_exec, ctx, values, indices_chunk, &result));
+    new_chunks[i] = MakeArray(result.array());
+  }
+  out->value = std::make_shared<ChunkedArray>(std::move(new_chunks), values->type);
+  return Status::OK();
+}
+
+/// \brief Generic (slower) VectorKernel::exec_chunked (`CA->C`, `CC->C`, and `AC->C`).

Review Comment:
   Yes, when you have only a hand-written AAA kernel, it uses `Concatenate` to make the other ones.



-- 
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: github-unsubscribe@arrow.apache.org

For queries about this service, please contact Infrastructure at:
users@infra.apache.org


Re: [PR] GH-39565: [C++] Do not concatenate chunked values of fixed-width types to run "array_take" [arrow]

Posted by "pitrou (via GitHub)" <gi...@apache.org>.
pitrou commented on PR #41700:
URL: https://github.com/apache/arrow/pull/41700#issuecomment-2299186553

   > Yeah, but this kind of branching is really bad for the confidence in unit tests. I will see what can be done.
   
   We can do that in a later PR and issue as well.


-- 
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: github-unsubscribe@arrow.apache.org

For queries about this service, please contact Infrastructure at:
users@infra.apache.org


Re: [PR] GH-39565: [C++] Do not concatenate chunked values of fixed-width types to run "array_take" [arrow]

Posted by "felipecrv (via GitHub)" <gi...@apache.org>.
felipecrv commented on PR #41700:
URL: https://github.com/apache/arrow/pull/41700#issuecomment-2298960209

   @pitrou this is ready for review again. Passing all tests (which were extended in a previous PR to more carefully test the implementation).


-- 
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: github-unsubscribe@arrow.apache.org

For queries about this service, please contact Infrastructure at:
users@infra.apache.org


Re: [PR] GH-39565: [C++] Do not concatenate chunked values of fixed-width types to run "array_take" [arrow]

Posted by "felipecrv (via GitHub)" <gi...@apache.org>.
felipecrv commented on code in PR #41700:
URL: https://github.com/apache/arrow/pull/41700#discussion_r1723501931


##########
cpp/src/arrow/compute/kernels/vector_selection_take_internal.cc:
##########
@@ -736,22 +1109,40 @@ void PopulateTakeKernels(std::vector<SelectionKernelData>* out) {
   auto take_indices = match::Integer();
 
   *out = {
-      {InputType(match::Primitive()), take_indices, FixedWidthTakeExec},
-      {InputType(match::BinaryLike()), take_indices, VarBinaryTakeExec},
-      {InputType(match::LargeBinaryLike()), take_indices, LargeVarBinaryTakeExec},
-      {InputType(match::FixedSizeBinaryLike()), take_indices, FixedWidthTakeExec},
-      {InputType(null()), take_indices, NullTakeExec},
-      {InputType(Type::DICTIONARY), take_indices, DictionaryTake},
-      {InputType(Type::EXTENSION), take_indices, ExtensionTake},
-      {InputType(Type::LIST), take_indices, ListTakeExec},
-      {InputType(Type::LARGE_LIST), take_indices, LargeListTakeExec},
-      {InputType(Type::LIST_VIEW), take_indices, ListViewTakeExec},
-      {InputType(Type::LARGE_LIST_VIEW), take_indices, LargeListViewTakeExec},
-      {InputType(Type::FIXED_SIZE_LIST), take_indices, FSLTakeExec},
-      {InputType(Type::DENSE_UNION), take_indices, DenseUnionTakeExec},
-      {InputType(Type::SPARSE_UNION), take_indices, SparseUnionTakeExec},
-      {InputType(Type::STRUCT), take_indices, StructTakeExec},
-      {InputType(Type::MAP), take_indices, MapTakeExec},
+      {InputType(match::Primitive()), take_indices, FixedWidthTakeExec,
+       SpecialTakeChunkedExecFunctor<FixedWidthTakeExec,
+                                     FixedWidthTakeChunkedExec>::Exec},
+      {InputType(match::BinaryLike()), take_indices, VarBinaryTakeExec,
+       GenericTakeChunkedExecFunctor<VarBinaryTakeExec>::Exec},
+      {InputType(match::LargeBinaryLike()), take_indices, LargeVarBinaryTakeExec,
+       GenericTakeChunkedExecFunctor<LargeVarBinaryTakeExec>::Exec},
+      {InputType(match::FixedSizeBinaryLike()), take_indices, FixedWidthTakeExec,
+       SpecialTakeChunkedExecFunctor<FixedWidthTakeExec,
+                                     FixedWidthTakeChunkedExec>::Exec},
+      {InputType(null()), take_indices, NullTakeExec,
+       GenericTakeChunkedExecFunctor<NullTakeExec>::Exec},
+      {InputType(Type::DICTIONARY), take_indices, DictionaryTake,
+       GenericTakeChunkedExecFunctor<DictionaryTake>::Exec},
+      {InputType(Type::EXTENSION), take_indices, ExtensionTake,
+       GenericTakeChunkedExecFunctor<ExtensionTake>::Exec},
+      {InputType(Type::LIST), take_indices, ListTakeExec,
+       GenericTakeChunkedExecFunctor<ListTakeExec>::Exec},
+      {InputType(Type::LARGE_LIST), take_indices, LargeListTakeExec,
+       GenericTakeChunkedExecFunctor<LargeListTakeExec>::Exec},
+      {InputType(Type::LIST_VIEW), take_indices, ListViewTakeExec,
+       GenericTakeChunkedExecFunctor<ListViewTakeExec>::Exec},
+      {InputType(Type::LARGE_LIST_VIEW), take_indices, LargeListViewTakeExec,
+       GenericTakeChunkedExecFunctor<LargeListViewTakeExec>::Exec},
+      {InputType(Type::FIXED_SIZE_LIST), take_indices, FSLTakeExec,
+       GenericTakeChunkedExecFunctor<FSLTakeExec>::Exec},

Review Comment:
   Yes. All the types using the generic functor will have a separate issue so I can make struct and table filtering avoid concatenation.



-- 
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: github-unsubscribe@arrow.apache.org

For queries about this service, please contact Infrastructure at:
users@infra.apache.org


Re: [PR] GH-39565: [C++] Do not concatenate chunked values of fixed-width types to run "array_take" [arrow]

Posted by "felipecrv (via GitHub)" <gi...@apache.org>.
felipecrv commented on code in PR #41700:
URL: https://github.com/apache/arrow/pull/41700#discussion_r1723503934


##########
cpp/src/arrow/compute/kernels/vector_selection_take_internal.cc:
##########
@@ -715,12 +853,247 @@ class TakeMetaFunction : public MetaFunction {
     return Status::NotImplemented(
         "Unsupported types for take operation: "
         "values=",
-        args[0].ToString(), "indices=", args[1].ToString());
+        args[0].ToString(), ", indices=", args[1].ToString());
   }
 };
 
 // ----------------------------------------------------------------------
 
+/// \brief Prepare the output array like ExecuteArrayKernel::PrepareOutput()
+std::shared_ptr<ArrayData> PrepareOutput(const ExecBatch& batch, int64_t length) {
+  DCHECK_EQ(batch.length, length);
+  auto out = std::make_shared<ArrayData>(batch.values[0].type(), length);
+  out->buffers.resize(batch.values[0].type()->layout().buffers.size());
+  return out;
+}
+
+Result<std::shared_ptr<Array>> ChunkedArrayAsArray(
+    const std::shared_ptr<ChunkedArray>& values, MemoryPool* pool) {
+  switch (values->num_chunks()) {
+    case 0:
+      return MakeArrayOfNull(values->type(), /*length=*/0, pool);
+    case 1:
+      return values->chunk(0);
+    default:
+      return Concatenate(values->chunks(), pool);
+  }
+}
+
+Status CallAAAKernel(ArrayKernelExec take_aaa_exec, KernelContext* ctx,
+                     std::shared_ptr<ArrayData> values,
+                     std::shared_ptr<ArrayData> indices, Datum* out) {
+  int64_t batch_length = values->length;
+  std::vector<Datum> args = {std::move(values), std::move(indices)};
+  ExecBatch array_array_batch(std::move(args), batch_length);
+  DCHECK_EQ(out->kind(), Datum::ARRAY);
+  ExecSpan exec_span{array_array_batch};
+  ExecResult result;
+  result.value = out->array();
+  RETURN_NOT_OK(take_aaa_exec(ctx, exec_span, &result));
+  DCHECK(result.is_array_data());
+  out->value = result.array_data();
+  return Status::OK();
+}
+
+Status CallCAAKernel(VectorKernel::ChunkedExec take_caa_exec, KernelContext* ctx,
+                     std::shared_ptr<ChunkedArray> values,
+                     std::shared_ptr<ArrayData> indices, Datum* out) {
+  int64_t batch_length = values->length();
+  std::vector<Datum> args = {std::move(values), std::move(indices)};
+  ExecBatch chunked_array_array_batch(std::move(args), batch_length);
+  DCHECK_EQ(out->kind(), Datum::ARRAY);
+  return take_caa_exec(ctx, chunked_array_array_batch, out);
+}
+
+Status TakeACCChunkedExec(ArrayKernelExec take_aaa_exec, KernelContext* ctx,
+                          const ExecBatch& batch, Datum* out) {
+  auto& values = batch.values[0].array();
+  auto& indices = batch.values[1].chunked_array();
+  auto num_chunks = indices->num_chunks();
+  std::vector<std::shared_ptr<Array>> new_chunks(num_chunks);
+  for (int i = 0; i < num_chunks; i++) {
+    // Take with that indices chunk
+    auto& indices_chunk = indices->chunk(i)->data();
+    Datum result = PrepareOutput(batch, values->length);
+    RETURN_NOT_OK(CallAAAKernel(take_aaa_exec, ctx, values, indices_chunk, &result));
+    new_chunks[i] = MakeArray(result.array());
+  }
+  out->value = std::make_shared<ChunkedArray>(std::move(new_chunks), values->type);
+  return Status::OK();
+}
+
+/// \brief Generic (slower) VectorKernel::exec_chunked (`CA->C`, `CC->C`, and `AC->C`).
+///
+/// This function concatenates the chunks of the values and then calls the `AA->A` take
+/// kernel to handle the `CA->C` cases. The ArrayData returned by the `AA->A` kernel is
+/// converted to a ChunkedArray with a single chunk to honor the `CA->C` contract.
+///
+/// For `CC->C` cases, it concatenates the chunks of the values and calls the `AA->A` take
+/// kernel for each chunk of the indices, producing a new chunked array with the same
+/// shape as the indices.
+///
+/// `AC->C` cases are trivially delegated to TakeACCChunkedExec without any concatenation.
+///
+/// \param take_aaa_exec The `AA->A` take kernel to use.
+Status GenericTakeChunkedExec(ArrayKernelExec take_aaa_exec, KernelContext* ctx,
+                              const ExecBatch& batch, Datum* out) {
+  const auto& args = batch.values;
+  if (args[0].kind() == Datum::CHUNKED_ARRAY) {
+    auto& values_chunked = args[0].chunked_array();
+    ARROW_ASSIGN_OR_RAISE(auto values_array,
+                          ChunkedArrayAsArray(values_chunked, ctx->memory_pool()));
+    if (args[1].kind() == Datum::ARRAY) {
+      // CA->C
+      auto& indices = args[1].array();
+      DCHECK_EQ(values_array->length(), batch.length);
+      {
+        // AA->A
+        RETURN_NOT_OK(
+            CallAAAKernel(take_aaa_exec, ctx, values_array->data(), indices, out));
+        out->value = std::make_shared<ChunkedArray>(MakeArray(out->array()));
+      }
+      return Status::OK();
+    } else if (args[1].kind() == Datum::CHUNKED_ARRAY) {
+      // CC->C
+      const auto& indices = args[1].chunked_array();
+      std::vector<std::shared_ptr<Array>> new_chunks;
+      for (int i = 0; i < indices->num_chunks(); i++) {
+        // AA->A
+        auto& indices_chunk = indices->chunk(i)->data();
+        Datum result = PrepareOutput(batch, values_array->length());
+        RETURN_NOT_OK(CallAAAKernel(take_aaa_exec, ctx, values_array->data(),
+                                    indices_chunk, &result));
+        new_chunks.push_back(MakeArray(result.array()));
+      }
+      DCHECK(out->is_array());
+      out->value =
+          std::make_shared<ChunkedArray>(std::move(new_chunks), values_chunked->type());
+      return Status::OK();
+    }
+  } else {
+    // VectorKernel::exec_chunked are only called when at least one of the inputs is
+    // chunked, so we should be able to assume that args[1] is a chunked array when
+    // everything is wired up correctly.
+    if (args[1].kind() == Datum::CHUNKED_ARRAY) {
+      // AC->C
+      return TakeACCChunkedExec(take_aaa_exec, ctx, batch, out);
+    } else {
+      DCHECK(false) << "Unexpected kind for array_take's exec_chunked kernel: values="
+                    << args[0].ToString() << ", indices=" << args[1].ToString();
+    }
+  }
+  return Status::NotImplemented(
+      "Unsupported kinds for 'array_take', try using 'take': "
+      "values=",
+      args[0].ToString(), ", indices=", args[1].ToString());
+}
+
+template <ArrayKernelExec kTakeAAAExec>
+struct GenericTakeChunkedExecFunctor {
+  static Status Exec(KernelContext* ctx, const ExecBatch& batch, Datum* out) {
+    return GenericTakeChunkedExec(kTakeAAAExec, ctx, batch, out);
+  }
+};
+
+/// \brief Specialized (faster) VectorKernel::exec_chunked (`CA->C`, `CC->C`, `AC->C`).
+///
+/// This function doesn't ever need to concatenate the chunks of the values, so it can be
+/// more efficient than GenericTakeChunkedExec that can only delegate to the `AA->A` take
+/// kernels.
+///
+/// For `CA->C` cases, it can call the `CA->A` take kernel directly [1] and trivially
+/// convert the result to a ChunkedArray of a single chunk to honor the `CA->C` contract.
+///
+/// For `CC->C` cases it can call the `CA->A` take kernel for each chunk of the indices to
+/// get each chunk that becomes the ChunkedArray output.
+///
+/// `AC->C` cases are trivially delegated to TakeACCChunkedExec.
+///
+/// \param take_aaa_exec The `AA->A` take kernel to use.
+Status SpecialTakeChunkedExec(const ArrayKernelExec take_aaa_exec,
+                              VectorKernel::ChunkedExec take_caa_exec, KernelContext* ctx,
+                              const ExecBatch& batch, Datum* out) {
+  Datum result = PrepareOutput(batch, batch.length);
+  auto* pool = ctx->memory_pool();
+  const auto& args = batch.values;
+  if (args[0].kind() == Datum::CHUNKED_ARRAY) {
+    auto& values_chunked = args[0].chunked_array();
+    std::shared_ptr<Array> single_chunk = nullptr;
+    if (values_chunked->num_chunks() == 0 || values_chunked->length() == 0) {

Review Comment:
   Nothing necessarily prevents chunked arrays of many empty chunks, does it?



-- 
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: github-unsubscribe@arrow.apache.org

For queries about this service, please contact Infrastructure at:
users@infra.apache.org