This is an automated email from the ASF dual-hosted git repository.
pitrou pushed a commit to branch main
in repository https://gitbox.apache.org/repos/asf/arrow.git
The following commit(s) were added to refs/heads/main by this push:
new 36f655f44cc GH-51476: [C++][Parquet] Vectorise FindMinMax explicitly
(#51478)
36f655f44cc is described below
commit 36f655f44cc4fa63c389a35b0bcfbe6723c0f87d
Author: Dominique Belhachemi <[email protected]>
AuthorDate: Tue Oct 6 04:56:00 2026 -0400
GH-51476: [C++][Parquet] Vectorise FindMinMax explicitly (#51478)
### Rationale for this change
FindMinMaxAvx2 in parquet/level_comparison_avx2.cc was not vectorised.
### What changes are included in this PR?
A single xsimd kernel `FindMinMaxSimd<Arch>` in
`level_comparison_simd_kernel_internal.h`,
plus support for multiple architectures.
### Are these changes tested?
Yes, with a nice speedup.
| dispatch level | time |
|---|---|
| NONE | 513 ns |
| SSE4_2 | 54.9 ns (9.3x) |
| AVX2 | 28.7 ns (17.9x) |
### Are there any user-facing changes?
No
### Was AI used for this PR?
**PR code and description written by:**
- [x] Human
- [x] AI
**Reviewed before submission by:**
- [x] Human
- [x] AI
- [ ] Not reviewed
* GitHub Issue: #51476
Authored-by: Dominique Belhachemi <[email protected]>
Signed-off-by: Antoine Pitrou <[email protected]>
---
cpp/src/parquet/CMakeLists.txt | 9 ++++++
cpp/src/parquet/level_comparison.cc | 6 ++--
cpp/src/parquet/level_comparison.h | 2 +-
cpp/src/parquet/level_comparison_avx2.cc | 4 ---
cpp/src/parquet/level_comparison_avx2_internal.h | 1 -
...l_comparison.h => level_comparison_simd_128.cc} | 33 ++++++++++++----------
...l_comparison.h => level_comparison_simd_256.cc} | 31 ++++++++++----------
...internal.h => level_comparison_simd_internal.h} | 11 +++++++-
...l.h => level_comparison_simd_kernel_internal.h} | 31 ++++++++++++++++++--
cpp/src/parquet/level_conversion_benchmark.cc | 20 +++++++++++++
10 files changed, 107 insertions(+), 41 deletions(-)
diff --git a/cpp/src/parquet/CMakeLists.txt b/cpp/src/parquet/CMakeLists.txt
index 5810317a959..a4091a80d3b 100644
--- a/cpp/src/parquet/CMakeLists.txt
+++ b/cpp/src/parquet/CMakeLists.txt
@@ -193,6 +193,15 @@ set(PARQUET_SRCS
stream_writer.cc
types.cc)
+# guards itself: Neon on aarch64, SSE4.2 on x86, empty elsewhere
+list(APPEND PARQUET_SRCS level_comparison_simd_128.cc)
+if(ARROW_CPU_FLAG STREQUAL "x86" AND ARROW_HAVE_RUNTIME_SSE4_2)
+ set_source_files_properties(level_comparison_simd_128.cc
+ PROPERTIES COMPILE_OPTIONS
"${ARROW_SSE4_2_FLAG}")
+endif()
+
+append_runtime_avx2_src(PARQUET_SRCS level_comparison_simd_256.cc)
+
if(ARROW_HAVE_RUNTIME_AVX2)
# AVX2 is used as a proxy for BMI2.
list(APPEND
diff --git a/cpp/src/parquet/level_comparison.cc
b/cpp/src/parquet/level_comparison.cc
index 81e42445853..beb9c66c5f9 100644
--- a/cpp/src/parquet/level_comparison.cc
+++ b/cpp/src/parquet/level_comparison.cc
@@ -23,6 +23,8 @@
# include "parquet/level_comparison_avx2_internal.h"
#endif
+#include "parquet/level_comparison_simd_internal.h"
+
#define PARQUET_IMPL_NAMESPACE standard
#include "parquet/level_comparison_inc.h"
#undef PARQUET_IMPL_NAMESPACE
@@ -37,8 +39,6 @@ using ::arrow::internal::DispatchLevel;
using ::arrow::internal::DynamicDispatch;
using ::arrow::internal::DynamicDispatchTarget;
-// defined in level_comparison_avx2.cc
-
struct GreaterThanDynamicFunction {
using FunctionType = decltype(&GreaterThanBitmap);
@@ -56,6 +56,8 @@ struct MinMaxDynamicFunction {
static constexpr auto targets() {
return std::array{
ARROW_DISPATCH_TARGET_NONE(&standard::FindMinMaxImpl) //
+ ARROW_DISPATCH_TARGET_NEON(&FindMinMaxNeon) //
+ ARROW_DISPATCH_TARGET_SSE4_2(&FindMinMaxSse42) //
ARROW_DISPATCH_TARGET_AVX2(&FindMinMaxAvx2) //
};
}
diff --git a/cpp/src/parquet/level_comparison.h
b/cpp/src/parquet/level_comparison.h
index 3ae442dd46e..966b21fad37 100644
--- a/cpp/src/parquet/level_comparison.h
+++ b/cpp/src/parquet/level_comparison.h
@@ -33,6 +33,6 @@ struct MinMax {
int16_t max;
};
-MinMax FindMinMax(const int16_t* levels, int64_t num_levels);
+MinMax PARQUET_EXPORT FindMinMax(const int16_t* levels, int64_t num_levels);
} // namespace parquet::internal
diff --git a/cpp/src/parquet/level_comparison_avx2.cc
b/cpp/src/parquet/level_comparison_avx2.cc
index db8935d4037..12cb122a942 100644
--- a/cpp/src/parquet/level_comparison_avx2.cc
+++ b/cpp/src/parquet/level_comparison_avx2.cc
@@ -28,9 +28,5 @@ uint64_t GreaterThanBitmapAvx2(const int16_t* levels, int64_t
num_levels, int16_
return avx2::GreaterThanBitmapImpl(levels, num_levels, rhs);
}
-MinMax FindMinMaxAvx2(const int16_t* levels, int64_t num_levels) {
- return avx2::FindMinMaxImpl(levels, num_levels);
-}
-
} // namespace internal
} // namespace parquet
diff --git a/cpp/src/parquet/level_comparison_avx2_internal.h
b/cpp/src/parquet/level_comparison_avx2_internal.h
index 3f68a6ff05d..d95fb856419 100644
--- a/cpp/src/parquet/level_comparison_avx2_internal.h
+++ b/cpp/src/parquet/level_comparison_avx2_internal.h
@@ -23,7 +23,6 @@
namespace parquet::internal {
-MinMax FindMinMaxAvx2(const int16_t* levels, int64_t num_levels);
uint64_t GreaterThanBitmapAvx2(const int16_t* levels, int64_t num_levels,
int16_t rhs);
} // namespace parquet::internal
diff --git a/cpp/src/parquet/level_comparison.h
b/cpp/src/parquet/level_comparison_simd_128.cc
similarity index 57%
copy from cpp/src/parquet/level_comparison.h
copy to cpp/src/parquet/level_comparison_simd_128.cc
index 3ae442dd46e..af5f5f882ad 100644
--- a/cpp/src/parquet/level_comparison.h
+++ b/cpp/src/parquet/level_comparison_simd_128.cc
@@ -14,25 +14,28 @@
// KIND, either express or implied. See the License for the
// specific language governing permissions and limitations
// under the License.
-#pragma once
-#include <algorithm>
-#include <cstdint>
+#if defined(ARROW_HAVE_NEON)
+# define FIND_MIN_MAX_PLATFORM FindMinMaxNeon
+# define ARCH_PLATFORM xsimd::neon64
+#elif defined(ARROW_HAVE_SSE4_2) || defined(ARROW_HAVE_RUNTIME_SSE4_2)
+# define FIND_MIN_MAX_PLATFORM FindMinMaxSse42
+# define ARCH_PLATFORM xsimd::sse4_2
+#endif
-#include "parquet/platform.h"
+#if defined(FIND_MIN_MAX_PLATFORM)
-namespace parquet::internal {
-
-/// Builds a bitmap where each set bit indicates the corresponding level is
greater
-/// than rhs.
-uint64_t PARQUET_EXPORT GreaterThanBitmap(const int16_t* levels, int64_t
num_levels,
- int16_t rhs);
+# include "parquet/level_comparison_simd_internal.h"
+# include "parquet/level_comparison_simd_kernel_internal.h"
-struct MinMax {
- int16_t min;
- int16_t max;
-};
+namespace parquet::internal {
-MinMax FindMinMax(const int16_t* levels, int64_t num_levels);
+MinMax FIND_MIN_MAX_PLATFORM(const int16_t* levels, int64_t num_levels) {
+ return FindMinMaxSimd<ARCH_PLATFORM>(levels, num_levels);
+}
} // namespace parquet::internal
+
+# undef ARCH_PLATFORM
+# undef FIND_MIN_MAX_PLATFORM
+#endif // FIND_MIN_MAX_PLATFORM
diff --git a/cpp/src/parquet/level_comparison.h
b/cpp/src/parquet/level_comparison_simd_256.cc
similarity index 61%
copy from cpp/src/parquet/level_comparison.h
copy to cpp/src/parquet/level_comparison_simd_256.cc
index 3ae442dd46e..024353dbc85 100644
--- a/cpp/src/parquet/level_comparison.h
+++ b/cpp/src/parquet/level_comparison_simd_256.cc
@@ -14,25 +14,26 @@
// KIND, either express or implied. See the License for the
// specific language governing permissions and limitations
// under the License.
-#pragma once
-#include <algorithm>
-#include <cstdint>
+#if defined(ARROW_HAVE_RUNTIME_AVX2)
+# define FIND_MIN_MAX_PLATFORM FindMinMaxAvx2
+# define ARCH_PLATFORM xsimd::avx2
+#endif
-#include "parquet/platform.h"
+#if !defined(FIND_MIN_MAX_PLATFORM)
+# error "This file must be compiled with a known SIMD micro architecture"
+#endif
-namespace parquet::internal {
-
-/// Builds a bitmap where each set bit indicates the corresponding level is
greater
-/// than rhs.
-uint64_t PARQUET_EXPORT GreaterThanBitmap(const int16_t* levels, int64_t
num_levels,
- int16_t rhs);
+#include "parquet/level_comparison_simd_internal.h"
+#include "parquet/level_comparison_simd_kernel_internal.h"
-struct MinMax {
- int16_t min;
- int16_t max;
-};
+namespace parquet::internal {
-MinMax FindMinMax(const int16_t* levels, int64_t num_levels);
+MinMax FIND_MIN_MAX_PLATFORM(const int16_t* levels, int64_t num_levels) {
+ return FindMinMaxSimd<ARCH_PLATFORM>(levels, num_levels);
+}
} // namespace parquet::internal
+
+#undef ARCH_PLATFORM
+#undef FIND_MIN_MAX_PLATFORM
diff --git a/cpp/src/parquet/level_comparison_avx2_internal.h
b/cpp/src/parquet/level_comparison_simd_internal.h
similarity index 77%
copy from cpp/src/parquet/level_comparison_avx2_internal.h
copy to cpp/src/parquet/level_comparison_simd_internal.h
index 3f68a6ff05d..518ce16f39e 100644
--- a/cpp/src/parquet/level_comparison_avx2_internal.h
+++ b/cpp/src/parquet/level_comparison_simd_internal.h
@@ -23,7 +23,16 @@
namespace parquet::internal {
+#if defined(ARROW_HAVE_NEON)
+MinMax FindMinMaxNeon(const int16_t* levels, int64_t num_levels);
+#endif
+
+#if defined(ARROW_HAVE_SSE4_2) || defined(ARROW_HAVE_RUNTIME_SSE4_2)
+MinMax FindMinMaxSse42(const int16_t* levels, int64_t num_levels);
+#endif
+
+#if defined(ARROW_HAVE_RUNTIME_AVX2)
MinMax FindMinMaxAvx2(const int16_t* levels, int64_t num_levels);
-uint64_t GreaterThanBitmapAvx2(const int16_t* levels, int64_t num_levels,
int16_t rhs);
+#endif
} // namespace parquet::internal
diff --git a/cpp/src/parquet/level_comparison_avx2_internal.h
b/cpp/src/parquet/level_comparison_simd_kernel_internal.h
similarity index 52%
copy from cpp/src/parquet/level_comparison_avx2_internal.h
copy to cpp/src/parquet/level_comparison_simd_kernel_internal.h
index 3f68a6ff05d..5b15a8f77b0 100644
--- a/cpp/src/parquet/level_comparison_avx2_internal.h
+++ b/cpp/src/parquet/level_comparison_simd_kernel_internal.h
@@ -17,13 +17,40 @@
#pragma once
+#include <xsimd/xsimd.hpp>
+
+#include <algorithm>
#include <cstdint>
+#include <limits>
#include "parquet/level_comparison.h"
namespace parquet::internal {
-MinMax FindMinMaxAvx2(const int16_t* levels, int64_t num_levels);
-uint64_t GreaterThanBitmapAvx2(const int16_t* levels, int64_t num_levels,
int16_t rhs);
+template <typename Arch>
+MinMax FindMinMaxSimd(const int16_t* levels, int64_t num_levels) {
+ using batch = xsimd::batch<int16_t, Arch>;
+ constexpr int64_t kLanes = static_cast<int64_t>(batch::size);
+
+ MinMax out{std::numeric_limits<int16_t>::max(),
std::numeric_limits<int16_t>::min()};
+
+ int64_t i = 0;
+ if (num_levels >= kLanes) {
+ batch vmin(out.min);
+ batch vmax(out.max);
+ for (; i + kLanes <= num_levels; i += kLanes) {
+ const auto v = batch::load_unaligned(levels + i);
+ vmin = xsimd::min(vmin, v);
+ vmax = xsimd::max(vmax, v);
+ }
+ out.min = xsimd::reduce_min(vmin);
+ out.max = xsimd::reduce_max(vmax);
+ }
+ for (; i < num_levels; ++i) {
+ out.min = std::min(levels[i], out.min);
+ out.max = std::max(levels[i], out.max);
+ }
+ return out;
+}
} // namespace parquet::internal
diff --git a/cpp/src/parquet/level_conversion_benchmark.cc
b/cpp/src/parquet/level_conversion_benchmark.cc
index f3a4f8095e3..0702b39ec20 100644
--- a/cpp/src/parquet/level_conversion_benchmark.cc
+++ b/cpp/src/parquet/level_conversion_benchmark.cc
@@ -19,6 +19,7 @@
#include <vector>
#include "benchmark/benchmark.h"
+#include "parquet/level_comparison.h"
#include "parquet/level_conversion.h"
constexpr int64_t kLevelCount = 2048;
@@ -78,3 +79,22 @@ void
BM_DefinitionLevelsToBitmapRepeatedMostPresent(::benchmark::State& state) {
}
BENCHMARK(BM_DefinitionLevelsToBitmapRepeatedMostPresent);
+
+void BM_FindMinMax(::benchmark::State& state) {
+ const int64_t num_levels = state.range(0);
+ std::vector<int16_t> levels(/*count=*/static_cast<size_t>(num_levels),
+ kPresentDefLevel);
+ for (size_t x = 0; x < levels.size(); x++) {
+ if (x % 10 == 0) {
+ levels[x] = kMissingDefLevel;
+ }
+ }
+ for (auto _ : state) {
+ auto min_max = parquet::internal::FindMinMax(levels.data(), num_levels);
+ ::benchmark::DoNotOptimize(min_max);
+ }
+ state.SetItemsProcessed(int64_t(state.iterations()) * num_levels);
+ state.SetBytesProcessed(int64_t(state.iterations()) * num_levels *
sizeof(int16_t));
+}
+
+BENCHMARK(BM_FindMinMax)->Arg(7)->Arg(1024)->Arg(2047)->Arg(kLevelCount);
