[C++] compute: Why AddMinMaxAvx512AggKernels add AVX2 in some cases

[mapleFU]

Describe the enhancement requested

void AddMinMaxAvx512AggKernels(ScalarAggregateFunction* func) {
  // Enable 32/64 int types for avx512 variants, no advantage on 8/16 int.
  AddMinMaxKernels(MinMaxInitAvx512, {int32(), uint32(), int64(), uint64()}, func,
                   SimdLevel::AVX512);
  AddMinMaxKernels(MinMaxInitAvx512, TemporalTypes(), func, SimdLevel::AVX512);
  AddMinMaxKernels(MinMaxInitAvx512, BaseBinaryTypes(), func, SimdLevel::AVX2);
  AddMinMaxKernel(MinMaxInitAvx512, Type::FIXED_SIZE_BINARY, func, SimdLevel::AVX2);
  AddMinMaxKernel(MinMaxInitAvx512, Type::INTERVAL_MONTHS, func, SimdLevel::AVX512);
}

Here TemporalTypes() and BaseBinaryTypes() just add SimdLevel::AVX2. Would this intented or just a mistake?

Component(s)

C++

[mapleFU]

@zanmato1984 @felipecrv Would you mind take a look? If it's an error I can just edit this :-)

[felipecrv]

Technically the SIMD levels are inclusive of all previous SIMD levels. If a kernel is dispatched with an Avx512 SIMD level, an Avx2 kernel can be used.

That said, naming functions Add-<single SIMD level>-AggKernels should be avoided because it's unlikely that we have all the implementations for each SIMD level. I would be in favor of inlining these with the normal AddMinMaxAggKernels or naming it with just Avx to mean that it includes Avx (of any version) kernels.

[mapleFU]

Technically the SIMD levels are inclusive of all previous SIMD levels. If a kernel is dispatched with an Avx512 SIMD level, an Avx2 kernel can be used.

This make sense to me. My concern is should we change like

void AddMinMaxAvx512AggKernels(ScalarAggregateFunction* func) {
-  AddMinMaxKernels(MinMaxInitAvx512, BaseBinaryTypes(), func, SimdLevel::AVX2);
+  AddMinMaxKernels(MinMaxInitAvx512, BaseBinaryTypes(), func, SimdLevel::AVX512);

Or this is just intended?

AFAIK, if AVX512 has enabled, the same kernel with AVX2 or lower would be registered? So it's a bit weird to me

@felipecrv

[felipecrv]

This make sense to me. My concern is should we change like

void AddMinMaxAvx512AggKernels(ScalarAggregateFunction* func) {
-  AddMinMaxKernels(MinMaxInitAvx512, BaseBinaryTypes(), func, SimdLevel::AVX2);
+  AddMinMaxKernels(MinMaxInitAvx512, BaseBinaryTypes(), func, SimdLevel::AVX512);

Or this is just intended?

No. Some places in the codebase do this, but it's a mistake: it only generates unnecessary template instances. The SIMD level parameter should be the smallest level that the kernel requires.

[mapleFU]

void AddAggKernel(std::shared_ptr<KernelSignature> sig, KernelInit init,
                  ScalarAggregateFunction* func, SimdLevel::type simd_level,
                  const bool ordered) {
  ScalarAggregateKernel kernel(std::move(sig), std::move(init), AggregateConsume,
                               AggregateMerge, AggregateFinalize, ordered);
  // Set the simd level
  kernel.simd_level = simd_level;
  DCHECK_OK(func->AddKernel(std::move(kernel)));
}

Seems this would not generate one?

  append_runtime_avx2_src(ARROW_COMPUTE_SRCS compute/kernels/aggregate_basic_avx2.cc)
  append_runtime_avx512_src(ARROW_COMPUTE_SRCS compute/kernels/aggregate_basic_avx512.cc)

I think they've been compile with different argument in aggregate_basic_avx512.cc, so I think the SIMD level should be avx512 here?

[mapleFU]

The SIMD level parameter should be the smallest level that the kernel requires.

This remind me of this. So generally, SIMD-level is just the "smallest level", not the "exact level"? And compiler can generate SIMD code if user decide to compile with SIMD flag themselves? I'm a bit confusing on this

[felipecrv]

Seems this would not generate one?

Sorry, the unnecessary template expansions only exist when you pass high SIMD levels as template parameters on template functions that don't really use instructions from those SIMD levels.

SumArray is an example of this problem:
https://github.com/apache/arrow/blob/main/cpp/src/arrow/compute/kernels/aggregate_internal.h#L148

Functions like MeanImpl shouldn't pass AVX512 SIMD level to SumArray<> when the SumArray implementation never uses these SIMD instructions. We are generating the same code for functions with different mangled names.

The SIMD level parameter should be the smallest level that the kernel requires.

This remind me of this. So generally, SIMD-level is just the "smallest level", not the "exact level"? And compiler can generate SIMD code if user decide to compile with SIMD flag themselves? I'm a bit confusing on this

It can't be the "exact level" because you could have a kernel that uses AVX512 for a step while also using AVX2 (or no SIMD at all) for other phases.

In other words: a SIMD level Y kernel can call any SIMD level X kernel iff X <= Y.

[zanmato1984]

This make sense to me. My concern is should we change like

void AddMinMaxAvx512AggKernels(ScalarAggregateFunction* func) {
-  AddMinMaxKernels(MinMaxInitAvx512, BaseBinaryTypes(), func, SimdLevel::AVX2);
+  AddMinMaxKernels(MinMaxInitAvx512, BaseBinaryTypes(), func, SimdLevel::AVX512);

Or this is just intended?

No. Some places in the codebase do this, but it's a mistake: it only generates unnecessary template instances. The SIMD level parameter should be the smallest level that the kernel requires.

I'm a little confused about the code too: why specifying AVX2 for string-like and fixed-size-binary types, as opposed to specifying AVX512 like for other types.

However I would try to answer myself: for other types, the compiler generates different SIMD code for AVX512 than for AVX2. So for these kernels, we have to mark them AVX512-only because an AVX2-only architecture wouldn't know them. For string-like and fixed-size-binary types, on the other hand, we are sure that the SIMD code generated by the compiler for both AVX512 and AVX2 are the same (all AVX2-capable?)? So these kernels are actually AVX2-capable, hence we specify a more relaxing SIMD level (AVX2) for them?

@felipecrv Could you help to confirm if I'm getting this right? Thanks.

[mapleFU]

  /// \brief Indicates the level of SIMD instruction support in the host CPU is
  /// required to use the function. The intention is for functions to be able to
  /// contain multiple kernels with the same signature but different levels of SIMD,
  /// so that the most optimized kernel supported on a host's processor can be chosen.
  SimdLevel::type simd_level = SimdLevel::NONE;

I think this is the "exact" simd-level it's using. Since a AVX2 machine execute a code with higher level is not wise

besides, from DispatchExactImpl, this would cause override of avx2 in the kernel_matches. I don't think this is expected?

template <typename KernelType>
const KernelType* DispatchExactImpl(const std::vector<KernelType*>& kernels,
                                    const std::vector<TypeHolder>& values) {
  const KernelType* kernel_matches[SimdLevel::MAX] = {nullptr};

  // Validate arity
  for (const auto& kernel : kernels) {
    if (kernel->signature->MatchesInputs(values)) {
      kernel_matches[kernel->simd_level] = kernel;
    }
  }

#if defined(ARROW_HAVE_RUNTIME_AVX512) || defined(ARROW_HAVE_RUNTIME_AVX2)
  auto cpu_info = arrow::internal::CpuInfo::GetInstance();
#endif
#if defined(ARROW_HAVE_RUNTIME_AVX512)
  if (cpu_info->IsSupported(arrow::internal::CpuInfo::AVX512)) {
    if (kernel_matches[SimdLevel::AVX512]) {
      return kernel_matches[SimdLevel::AVX512];
    }
  }
#endif

From the code above, if a machine supports avx512, and it just use avx2. The avx512 kernel would be executed. I think this is not expected?

Since this kernel is set as a tag, and would affect dispatching, I think we should do some change like:

diff --git a/cpp/src/arrow/compute/kernels/aggregate_basic_avx512.cc b/cpp/src/arrow/compute/kernels/aggregate_basic_avx512.cc
index 0d66ed2ec..05356e0aa 100644
--- a/cpp/src/arrow/compute/kernels/aggregate_basic_avx512.cc
+++ b/cpp/src/arrow/compute/kernels/aggregate_basic_avx512.cc
@@ -80,8 +80,8 @@ void AddMinMaxAvx512AggKernels(ScalarAggregateFunction* func) {
   AddMinMaxKernels(MinMaxInitAvx512, {int32(), uint32(), int64(), uint64()}, func,
                    SimdLevel::AVX512);
   AddMinMaxKernels(MinMaxInitAvx512, TemporalTypes(), func, SimdLevel::AVX512);
-  AddMinMaxKernels(MinMaxInitAvx512, BaseBinaryTypes(), func, SimdLevel::AVX2);
-  AddMinMaxKernel(MinMaxInitAvx512, Type::FIXED_SIZE_BINARY, func, SimdLevel::AVX2);
+  AddMinMaxKernels(MinMaxInitAvx512, BaseBinaryTypes(), func, SimdLevel::AVX512);
+  AddMinMaxKernel(MinMaxInitAvx512, Type::FIXED_SIZE_BINARY, func, SimdLevel::AVX512);
   AddMinMaxKernel(MinMaxInitAvx512, Type::INTERVAL_MONTHS, func, SimdLevel::AVX512);
 }

[felipecrv]

I think this is the "exact" simd-level it's using. Since a AVX2 machine execute a code with higher level is not wise

No, the comment says "the required level" :D Are there CPUs that support AVX512 and don't support AVX2?

The code checks for CPU support for AVX512 instructions. Then it checks if a kernel exists. If an AVX512 kernel doesn't exist... no problem, it will look for the AVX2 kernel.

#if defined(ARROW_HAVE_RUNTIME_AVX512)
  if (cpu_info->IsSupported(arrow::internal::CpuInfo::AVX512)) {
    if (kernel_matches[SimdLevel::AVX512]) {
      return kernel_matches[SimdLevel::AVX512];
    }
  }
#endif
#if defined(ARROW_HAVE_RUNTIME_AVX2)
  if (cpu_info->IsSupported(arrow::internal::CpuInfo::AVX2)) {
    if (kernel_matches[SimdLevel::AVX2]) {
      return kernel_matches[SimdLevel::AVX2];
    }
  }
#endif

We should never allow a compilation config that has ARROW_HAVE_RUNTIME_AVX512 enabled and ARROW_HAVE_RUNTIME_AVX2 disabled though.

UPDATE: if you check the CMake files you will already see that AVX2 is enabled if AVX512 is requested.

[mapleFU]

The code checks for CPU support for AVX512 instructions. Then it checks if a kernel exists. If an AVX512 kernel doesn't exist... no problem, it will look for the AVX2 kernel.

I mean when a avx512 machine and avx2 CpuInfo enabled:

(1) Both are registered

void AddMinMaxAvx512AggKernels(ScalarAggregateFunction* func) {
  // Enable 32/64 int types for avx512 variants, no advantage on 8/16 int.
  AddMinMaxKernels(MinMaxInitAvx512, {int32(), uint32(), int64(), uint64()}, func,
                   SimdLevel::AVX512);
  AddMinMaxKernels(MinMaxInitAvx512, TemporalTypes(), func, SimdLevel::AVX512);
  AddMinMaxKernels(MinMaxInitAvx512, BaseBinaryTypes(), func, SimdLevel::AVX2);
  AddMinMaxKernel(MinMaxInitAvx512, Type::FIXED_SIZE_BINARY, func, SimdLevel::AVX2);
  AddMinMaxKernel(MinMaxInitAvx512, Type::INTERVAL_MONTHS, func, SimdLevel::AVX512);
}

void AddMinMaxAvx2AggKernels(ScalarAggregateFunction* func) {
  // Enable int types for AVX2 variants.
  // No auto vectorize for float/double as it use fmin/fmax which has NaN handling.
  AddMinMaxKernels(MinMaxInitAvx2, IntTypes(), func, SimdLevel::AVX2);
  AddMinMaxKernels(MinMaxInitAvx2, TemporalTypes(), func, SimdLevel::AVX2);
  AddMinMaxKernels(MinMaxInitAvx2, BaseBinaryTypes(), func, SimdLevel::AVX2);
  AddMinMaxKernel(MinMaxInitAvx2, Type::FIXED_SIZE_BINARY, func, SimdLevel::AVX2);
  AddMinMaxKernel(MinMaxInitAvx2, Type::INTERVAL_MONTHS, func, SimdLevel::AVX2);
}

(2) When dispatch, firstly, avx2 is set to kernel_matches[SimdLevel::AVX2], and then, avx512 version is set to kernel_matches[SimdLevel::AVX2], which overrides the avx2 code

(3.1) When user with avx512 want to select avx512, the code works well, it check avx512, and doesn't find any thing. then it fallback to avx2

(3.2) When user with avx512 want to select avx2, the code doesn't works well, it check avx2, and get the kernel compiled with avx512.

(3.2) is the problem I mentioned here

[felipecrv]

However I would try to answer myself: for other types, the compiler generates different SIMD code for AVX512 than for AVX2. So for these kernels, we have to mark them AVX512-only because an AVX2-only architecture wouldn't know them. For string-like and fixed-size-binary types, on the other hand, we are sure that the SIMD code generated by the compiler for both AVX512 and AVX2 are the same (all AVX2-capable?)? So these kernels are actually AVX2-capable, hence we specify a more relaxing SIMD level (AVX2) for them?

@zanmato1984 yes. I mean, you have to check the code carefully, but that is the intention: don't instantiate the AVX512 template if the template never needs AVX512 instructions and AVX2 is enough.

SumArray is instantiated with AVX512 unnecessarily because the implementation of SumArray for most types doesn't, in fact, use AVX512 instructions. It's very hard to structure this code correctly. I have never written SIMD kernels in Arrow. All I learned was from trying to answer support questions like the ones you're asking now.

[mapleFU]

However I would try to answer myself: for other types, the compiler generates different SIMD code for AVX512 than for AVX2. So for these kernels, we have to mark them AVX512-only because an AVX2-only architecture wouldn't know them. For string-like and fixed-size-binary types, on the other hand, we are sure that the SIMD code generated by the compiler for both AVX512 and AVX2 are the same (all AVX2-capable?)? So these kernels are actually AVX2-capable, hence we specify a more relaxing SIMD level (AVX2) for them?

This make sense to me. Seems if we have hand written avx2/avx512 kernel, and we know currently they'd work better than compiler generated, we'd like to marking them as SimdLevel::xxx code

I don't know the idea why generate with different SimdLevel, a "None" with user-compiled code seems suitable for the case when user'd like to compile it themselve with auto-vectorization and flag like -march=native. I'm also curious why handle the SIMD code like current implementation.

@pitrou would you mind take a look? I'm a bit confusion on extract different simd level here