You are viewing a plain text version of this content. The canonical link for it is here.
Posted to commits@arrow.apache.org by ap...@apache.org on 2025/07/08 11:19:05 UTC
(arrow) branch main updated: GH-46962: [C++][Parquet] Generic xsimd function and dynamic dispatch for Byte Stream Split (#46963)
This is an automated email from the ASF dual-hosted git repository.
apitrou 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 11c97b8799 GH-46962: [C++][Parquet] Generic xsimd function and dynamic dispatch for Byte Stream Split (#46963)
11c97b8799 is described below
commit 11c97b879920fcdabc3b0a8baf04955454003ed3
Author: Antoine Prouvost <An...@users.noreply.github.com>
AuthorDate: Tue Jul 8 13:18:59 2025 +0200
GH-46962: [C++][Parquet] Generic xsimd function and dynamic dispatch for Byte Stream Split (#46963)
Thanks for opening a pull request!
### Rationale for this change
Lot of linux systems ship arrow with SSE4.2, but the AVX2 instructions are quite available.
For byte stream split, they are faster than SSE4.2.
### What changes are included in this PR?
- Make the xsimd functions refactored in #46789 to make them arch independent.
- Use dynamic dispatch to AVX2 at runtime if available (it was considered that builds without SSE4.2 or Neon at compile time were not so popular to add them to the dynamic dispatch).
### Are these changes tested?
Yes, the exisiting tests already cover the code.
### Are there any user-facing changes?
No
* GitHub Issue: #46962
Lead-authored-by: AntoinePrv <An...@users.noreply.github.com>
Co-authored-by: Antoine Pitrou <an...@python.org>
Signed-off-by: Antoine Pitrou <an...@python.org>
---
ci/scripts/python_wheel_macos_build.sh | 1 +
ci/scripts/python_wheel_windows_build.bat | 1 +
ci/scripts/python_wheel_xlinux_build.sh | 1 +
ci/vcpkg/vcpkg.json | 1 -
cpp/cmake_modules/SetupCxxFlags.cmake | 6 +-
cpp/src/arrow/CMakeLists.txt | 3 +
cpp/src/arrow/util/byte_stream_split_internal.cc | 122 ++++++
cpp/src/arrow/util/byte_stream_split_internal.h | 416 ++++++++-------------
.../arrow/util/byte_stream_split_internal_avx2.cc | 137 +++++++
cpp/src/arrow/util/byte_stream_split_test.cc | 31 +-
cpp/src/arrow/util/dispatch_internal.h | 3 +-
cpp/src/arrow/util/math_internal.h | 16 +
cpp/src/arrow/util/small_vector.h | 1 +
cpp/src/parquet/encoding_benchmark.cc | 94 ++++-
dev/tasks/vcpkg-tests/cpp-build-vcpkg.bat | 3 +
15 files changed, 533 insertions(+), 303 deletions(-)
diff --git a/ci/scripts/python_wheel_macos_build.sh b/ci/scripts/python_wheel_macos_build.sh
index 1eaecd6bea..5ddf186646 100755
--- a/ci/scripts/python_wheel_macos_build.sh
+++ b/ci/scripts/python_wheel_macos_build.sh
@@ -147,6 +147,7 @@ cmake \
-DPARQUET_REQUIRE_ENCRYPTION=${PARQUET_REQUIRE_ENCRYPTION} \
-DVCPKG_MANIFEST_MODE=OFF \
-DVCPKG_TARGET_TRIPLET=${VCPKG_TARGET_TRIPLET} \
+ -Dxsimd_SOURCE=BUNDLED \
-G ${CMAKE_GENERATOR} \
${source_dir}/cpp
cmake --build . --target install
diff --git a/ci/scripts/python_wheel_windows_build.bat b/ci/scripts/python_wheel_windows_build.bat
index fd6d059166..00b0071641 100644
--- a/ci/scripts/python_wheel_windows_build.bat
+++ b/ci/scripts/python_wheel_windows_build.bat
@@ -101,6 +101,7 @@ cmake ^
-DPARQUET_REQUIRE_ENCRYPTION=%PARQUET_REQUIRE_ENCRYPTION% ^
-DVCPKG_MANIFEST_MODE=OFF ^
-DVCPKG_TARGET_TRIPLET=%VCGPK_TARGET_TRIPLET% ^
+ -Dxsimd_SOURCE=BUNDLED ^
-G "%CMAKE_GENERATOR%" ^
-A "%CMAKE_PLATFORM%" ^
C:\arrow\cpp || exit /B 1
diff --git a/ci/scripts/python_wheel_xlinux_build.sh b/ci/scripts/python_wheel_xlinux_build.sh
index 9cebf1ac6b..44a1bb919f 100755
--- a/ci/scripts/python_wheel_xlinux_build.sh
+++ b/ci/scripts/python_wheel_xlinux_build.sh
@@ -128,6 +128,7 @@ cmake \
-DPARQUET_REQUIRE_ENCRYPTION=${PARQUET_REQUIRE_ENCRYPTION} \
-DVCPKG_MANIFEST_MODE=OFF \
-DVCPKG_TARGET_TRIPLET=${VCPKG_TARGET_TRIPLET} \
+ -Dxsimd_SOURCE=BUNDLED \
${ARROW_EXTRA_CMAKE_FLAGS} \
-G ${CMAKE_GENERATOR} \
/arrow/cpp
diff --git a/ci/vcpkg/vcpkg.json b/ci/vcpkg/vcpkg.json
index 5dfe61a0c6..0107153f01 100644
--- a/ci/vcpkg/vcpkg.json
+++ b/ci/vcpkg/vcpkg.json
@@ -19,7 +19,6 @@
"re2",
"snappy",
"utf8proc",
- "xsimd",
"zlib",
"zstd",
{
diff --git a/cpp/cmake_modules/SetupCxxFlags.cmake b/cpp/cmake_modules/SetupCxxFlags.cmake
index 2211308de8..15ebfef55d 100644
--- a/cpp/cmake_modules/SetupCxxFlags.cmake
+++ b/cpp/cmake_modules/SetupCxxFlags.cmake
@@ -49,7 +49,11 @@ endif()
if(ARROW_CPU_FLAG STREQUAL "x86")
# x86/amd64 compiler flags, msvc/gcc/clang
if(MSVC)
- set(ARROW_SSE4_2_FLAG "")
+ set(ARROW_SSE4_2_FLAG "/arch:SSE4.2")
+ # These definitions are needed for xsimd to consider the corresponding instruction
+ # sets available, but they are not set by MSVC (unlike other compilers).
+ # See https://github.com/AcademySoftwareFoundation/OpenImageIO/issues/4265
+ add_definitions(-D__SSE2__ -D__SSE4_1__ -D__SSE4_2__)
set(ARROW_AVX2_FLAG "/arch:AVX2")
# MSVC has no specific flag for BMI2, it seems to be enabled with AVX2
set(ARROW_BMI2_FLAG "/arch:AVX2")
diff --git a/cpp/src/arrow/CMakeLists.txt b/cpp/src/arrow/CMakeLists.txt
index b33acae5b9..42b0bcc151 100644
--- a/cpp/src/arrow/CMakeLists.txt
+++ b/cpp/src/arrow/CMakeLists.txt
@@ -491,6 +491,7 @@ set(ARROW_UTIL_SRCS
util/bitmap_ops.cc
util/bpacking.cc
util/byte_size.cc
+ util/byte_stream_split_internal.cc
util/cancel.cc
util/compression.cc
util/counting_semaphore.cc
@@ -530,6 +531,8 @@ set(ARROW_UTIL_SRCS
util/utf8.cc
util/value_parsing.cc)
+append_runtime_avx2_src(ARROW_UTIL_SRCS util/byte_stream_split_internal_avx2.cc)
+
append_runtime_avx2_src(ARROW_UTIL_SRCS util/bpacking_avx2.cc)
append_runtime_avx512_src(ARROW_UTIL_SRCS util/bpacking_avx512.cc)
if(ARROW_HAVE_NEON)
diff --git a/cpp/src/arrow/util/byte_stream_split_internal.cc b/cpp/src/arrow/util/byte_stream_split_internal.cc
new file mode 100644
index 0000000000..7e9e339cff
--- /dev/null
+++ b/cpp/src/arrow/util/byte_stream_split_internal.cc
@@ -0,0 +1,122 @@
+// Licensed to the Apache Software Foundation (ASF) under one
+// or more contributor license agreements. See the NOTICE file
+// distributed with this work for additional information
+// regarding copyright ownership. The ASF licenses this file
+// to you under the Apache License, Version 2.0 (the
+// "License"); you may not use this file except in compliance
+// with the License. You may obtain a copy of the License at
+//
+// http://www.apache.org/licenses/LICENSE-2.0
+//
+// Unless required by applicable law or agreed to in writing,
+// software distributed under the License is distributed on an
+// "AS IS" BASIS, WITHOUT WARRANTIES OR CONDITIONS OF ANY
+// KIND, either express or implied. See the License for the
+// specific language governing permissions and limitations
+// under the License.
+
+#include "arrow/util/byte_stream_split_internal.h"
+#include "arrow/util/dispatch_internal.h"
+
+#include <array>
+
+namespace arrow::util::internal {
+
+using ::arrow::internal::DispatchLevel;
+using ::arrow::internal::DynamicDispatch;
+
+/************************
+ * Decode dispatching *
+ ************************/
+
+template <int kNumStreams>
+struct ByteStreamSplitDecodeDynamic {
+ using FunctionType = decltype(&ByteStreamSplitDecodeScalar<kNumStreams>);
+ using Implementation = std::pair<DispatchLevel, FunctionType>;
+
+ constexpr static auto implementations() {
+ return std::array {
+ Implementation {
+ DispatchLevel::NONE,
+#if defined(ARROW_HAVE_NEON)
+ // We always expect Neon to be available on Arm64
+ &ByteStreamSplitDecodeSimd<xsimd::neon64, kNumStreams>,
+#elif defined(ARROW_HAVE_SSE4_2)
+ // We always expect SSE4.2 to be available on x86_64
+ &ByteStreamSplitDecodeSimd<xsimd::sse4_2, kNumStreams>,
+#else
+ &ByteStreamSplitDecodeScalar<kNumStreams>,
+#endif
+ }
+ ,
+#if defined(ARROW_HAVE_RUNTIME_AVX2)
+ Implementation{
+ DispatchLevel::AVX2,
+ &ByteStreamSplitDecodeSimd<xsimd::avx2, kNumStreams>,
+ },
+#endif
+ };
+ }
+};
+
+template <int kNumStreams>
+void ByteStreamSplitDecodeSimdDispatch(const uint8_t* data, int width, int64_t num_values,
+ int64_t stride, uint8_t* out) {
+ static const DynamicDispatch<ByteStreamSplitDecodeDynamic<kNumStreams>> dispatch;
+ return dispatch.func(data, width, num_values, stride, out);
+}
+
+template void ByteStreamSplitDecodeSimdDispatch<2>(const uint8_t*, int, int64_t, int64_t,
+ uint8_t*);
+template void ByteStreamSplitDecodeSimdDispatch<4>(const uint8_t*, int, int64_t, int64_t,
+ uint8_t*);
+template void ByteStreamSplitDecodeSimdDispatch<8>(const uint8_t*, int, int64_t, int64_t,
+ uint8_t*);
+
+/************************
+ * Encode dispatching *
+ ************************/
+
+template <int kNumStreams>
+struct ByteStreamSplitEncodeDynamic {
+ using FunctionType = decltype(&ByteStreamSplitEncodeScalar<kNumStreams>);
+ using Implementation = std::pair<DispatchLevel, FunctionType>;
+
+ constexpr static auto implementations() {
+ return std::array {
+ Implementation {
+ DispatchLevel::NONE,
+#if defined(ARROW_HAVE_NEON)
+ // We always expect Neon to be available on Arm64
+ &ByteStreamSplitEncodeSimd<xsimd::neon64, kNumStreams>,
+#elif defined(ARROW_HAVE_SSE4_2)
+ // We always expect SSE4.2 to be available on x86_64
+ &ByteStreamSplitEncodeSimd<xsimd::sse4_2, kNumStreams>,
+#else
+ &ByteStreamSplitEncodeScalar<kNumStreams>,
+#endif
+ }
+ ,
+#if defined(ARROW_HAVE_RUNTIME_AVX2)
+ Implementation{DispatchLevel::AVX2, &ByteStreamSplitEncodeAvx2<kNumStreams>},
+#endif
+ };
+ }
+};
+
+template <int kNumStreams>
+void ByteStreamSplitEncodeSimdDispatch(const uint8_t* raw_values, int width,
+ const int64_t num_values,
+ uint8_t* output_buffer_raw) {
+ static const DynamicDispatch<ByteStreamSplitEncodeDynamic<kNumStreams>> dispatch;
+ return dispatch.func(raw_values, width, num_values, output_buffer_raw);
+}
+
+template void ByteStreamSplitEncodeSimdDispatch<2>(const uint8_t*, int, const int64_t,
+ uint8_t*);
+template void ByteStreamSplitEncodeSimdDispatch<4>(const uint8_t*, int, const int64_t,
+ uint8_t*);
+template void ByteStreamSplitEncodeSimdDispatch<8>(const uint8_t*, int, const int64_t,
+ uint8_t*);
+
+} // namespace arrow::util::internal
diff --git a/cpp/src/arrow/util/byte_stream_split_internal.h b/cpp/src/arrow/util/byte_stream_split_internal.h
index 2eb678cbfb..3125857f69 100644
--- a/cpp/src/arrow/util/byte_stream_split_internal.h
+++ b/cpp/src/arrow/util/byte_stream_split_internal.h
@@ -18,12 +18,12 @@
#pragma once
#include "arrow/util/endian.h"
-#include "arrow/util/simd.h"
+#include "arrow/util/math_internal.h"
#include "arrow/util/small_vector.h"
#include "arrow/util/type_traits.h"
#include "arrow/util/ubsan.h"
+#include "arrow/util/visibility.h"
-#include <algorithm>
#include <array>
#include <cassert>
#include <cstdint>
@@ -36,38 +36,39 @@
namespace arrow::util::internal {
-//
-// SIMD implementations
-//
+#if defined(ARROW_HAVE_SIMD_SPLIT)
-template <typename T>
-constexpr T ReversePow2(T x) {
- for (T n = 0, y = 1; n <= (8 * static_cast<T>(sizeof(T))); ++n, y = y * 2) {
- if (y == x) {
- return n;
- }
- }
- return 0;
-}
+/***************************
+ * xsimd implementations *
+ ***************************/
-static_assert(ReversePow2(8) == 3);
-static_assert(ReversePow2(4) == 2);
-static_assert(ReversePow2(2) == 1);
+using ::arrow::internal::ReversePow2;
-#if defined(ARROW_HAVE_NEON) || defined(ARROW_HAVE_SSE4_2)
-template <int kNumStreams>
-void ByteStreamSplitDecodeSimd128(const uint8_t* data, int width, int64_t num_values,
- int64_t stride, uint8_t* out) {
- using simd_batch = xsimd::make_sized_batch_t<int8_t, 16>;
+template <typename Arch, int kNumStreams>
+void ByteStreamSplitDecodeSimd(const uint8_t* data, int width, int64_t num_values,
+ int64_t stride, uint8_t* out) {
+ using simd_batch = xsimd::batch<int8_t, Arch>;
+ // For signed arithmetic
+ constexpr int kBatchSize = static_cast<int>(simd_batch::size);
- static_assert(kNumStreams <= simd_batch::size,
+ static_assert(kBatchSize >= 16, "The smallest SIMD size is 128 bits");
+
+ if constexpr (kBatchSize > 16) {
+ if (num_values < kBatchSize) {
+ using Arch128 = xsimd::make_sized_batch_t<int8_t, 16>::arch_type;
+ return ByteStreamSplitDecodeSimd<Arch128, kNumStreams>(data, width, num_values,
+ stride, out);
+ }
+ }
+
+ static_assert(kNumStreams <= kBatchSize,
"The algorithm works when the number of streams is smaller than the SIMD "
"batch size.");
assert(width == kNumStreams);
constexpr int kNumStreamsLog2 = ReversePow2(kNumStreams);
static_assert(kNumStreamsLog2 != 0,
"The algorithm works for a number of streams being a power of two.");
- constexpr int64_t kBlockSize = simd_batch::size * kNumStreams;
+ constexpr int64_t kBlockSize = kBatchSize * kNumStreams;
const int64_t size = num_values * kNumStreams;
const int64_t num_blocks = size / kBlockSize;
@@ -82,7 +83,7 @@ void ByteStreamSplitDecodeSimd128(const uint8_t* data, int width, int64_t num_va
const int64_t byte_index = b * stride + i;
gathered_byte_data[b] = data[byte_index];
}
- memcpy(out + i * kNumStreams, gathered_byte_data, kNumStreams);
+ std::memcpy(out + i * kNumStreams, gathered_byte_data, kNumStreams);
}
// The blocks get processed hierarchically using the unpack intrinsics.
@@ -92,67 +93,101 @@ void ByteStreamSplitDecodeSimd128(const uint8_t* data, int width, int64_t num_va
// Stage 3: ABCD ABCD ABCD ABCD
constexpr int kNumStreamsHalf = kNumStreams / 2U;
- for (int64_t i = 0; i < num_blocks; ++i) {
+ for (int64_t block_index = 0; block_index < num_blocks; ++block_index) {
simd_batch stage[kNumStreamsLog2 + 1][kNumStreams];
- for (int j = 0; j < kNumStreams; ++j) {
- stage[0][j] = simd_batch::load_unaligned(&data[i * simd_batch::size + j * stride]);
+
+ for (int i = 0; i < kNumStreams; ++i) {
+ stage[0][i] =
+ simd_batch::load_unaligned(&data[block_index * kBatchSize + i * stride]);
}
+
for (int step = 0; step < kNumStreamsLog2; ++step) {
- for (int j = 0; j < kNumStreamsHalf; ++j) {
- stage[step + 1U][j * 2] =
- xsimd::zip_lo(stage[step][j], stage[step][kNumStreamsHalf + j]);
- stage[step + 1U][j * 2 + 1U] =
- xsimd::zip_hi(stage[step][j], stage[step][kNumStreamsHalf + j]);
+ for (int i = 0; i < kNumStreamsHalf; ++i) {
+ stage[step + 1U][i * 2] =
+ xsimd::zip_lo(stage[step][i], stage[step][kNumStreamsHalf + i]);
+ stage[step + 1U][i * 2 + 1U] =
+ xsimd::zip_hi(stage[step][i], stage[step][kNumStreamsHalf + i]);
}
}
- for (int j = 0; j < kNumStreams; ++j) {
+
+ for (int i = 0; i < kNumStreams; ++i) {
xsimd::store_unaligned(
- reinterpret_cast<int8_t*>(out + (i * kNumStreams + j) * simd_batch::size),
- stage[kNumStreamsLog2][j]);
+ reinterpret_cast<int8_t*>(out + (block_index * kNumStreams + i) * kBatchSize),
+ stage[kNumStreamsLog2][i]);
}
}
}
// Like xsimd::zip_lo, but zip groups of kNumBytes at once.
-template <int kNumBytes, int kBatchSize = 16,
- typename Batch = xsimd::make_sized_batch_t<int8_t, kBatchSize>>
-auto zip_lo_n(Batch const& a, Batch const& b) -> Batch {
+template <typename Arch, int kNumBytes>
+auto zip_lo_n(xsimd::batch<int8_t, Arch> const& a, xsimd::batch<int8_t, Arch> const& b)
+ -> xsimd::batch<int8_t, Arch> {
using arrow::internal::SizedInt;
+ using simd_batch = xsimd::batch<int8_t, Arch>;
+ // For signed arithmetic
+ constexpr int kBatchSize = static_cast<int>(simd_batch::size);
if constexpr (kNumBytes == kBatchSize) {
return a;
- } else {
+ } else if constexpr (kNumBytes <= 8) {
return xsimd::bitwise_cast<int8_t>(
xsimd::zip_lo(xsimd::bitwise_cast<SizedInt<kNumBytes>>(a),
xsimd::bitwise_cast<SizedInt<kNumBytes>>(b)));
+ } else if constexpr (kNumBytes == 16 && kBatchSize == 32) {
+ // No data type for 128 bits.
+ // This could be made generic by simply computing the shuffle permute constant
+ return xsimd::bitwise_cast<int8_t>(
+ xsimd::shuffle(xsimd::bitwise_cast<int64_t>(a), xsimd::bitwise_cast<int64_t>(b),
+ xsimd::batch_constant<uint64_t, Arch, 0, 1, 4, 5>{}));
}
}
// Like xsimd::zip_hi, but zip groups of kNumBytes at once.
-template <int kNumBytes, int kBatchSize = 16,
- typename Batch = xsimd::make_sized_batch_t<int8_t, kBatchSize>>
-auto zip_hi_n(Batch const& a, Batch const& b) -> Batch {
+template <typename Arch, int kNumBytes>
+auto zip_hi_n(xsimd::batch<int8_t, Arch> const& a, xsimd::batch<int8_t, Arch> const& b)
+ -> xsimd::batch<int8_t, Arch> {
+ using simd_batch = xsimd::batch<int8_t, Arch>;
using arrow::internal::SizedInt;
+ // For signed arithmetic
+ constexpr int kBatchSize = static_cast<int>(simd_batch::size);
if constexpr (kNumBytes == kBatchSize) {
return b;
- } else {
+ } else if constexpr (kNumBytes <= 8) {
return xsimd::bitwise_cast<int8_t>(
xsimd::zip_hi(xsimd::bitwise_cast<SizedInt<kNumBytes>>(a),
xsimd::bitwise_cast<SizedInt<kNumBytes>>(b)));
+ } else if constexpr (kNumBytes == 16 && kBatchSize == 32) {
+ // No data type for 128 bits
+ // This could be made generic by simply computing the shuffle permute constant
+ return xsimd::bitwise_cast<int8_t>(
+ xsimd::shuffle(xsimd::bitwise_cast<int64_t>(a), xsimd::bitwise_cast<int64_t>(b),
+ xsimd::batch_constant<uint64_t, Arch, 2, 3, 6, 7>{}));
}
}
-template <int kNumStreams>
-void ByteStreamSplitEncodeSimd128(const uint8_t* raw_values, int width,
- const int64_t num_values, uint8_t* output_buffer_raw) {
- using simd_batch = xsimd::make_sized_batch_t<int8_t, 16>;
+template <typename Arch, int kNumStreams>
+void ByteStreamSplitEncodeSimd(const uint8_t* raw_values, int width,
+ const int64_t num_values, uint8_t* output_buffer_raw) {
+ using simd_batch = xsimd::batch<int8_t, Arch>;
+ // For signed arithmetic
+ constexpr int kBatchSize = static_cast<int>(simd_batch::size);
+
+ static_assert(kBatchSize >= 16, "The smallest SIMD size is 128 bits");
+
+ if constexpr (kBatchSize > 16) {
+ if (num_values < kBatchSize) {
+ using Arch128 = xsimd::make_sized_batch_t<int8_t, 16>::arch_type;
+ return ByteStreamSplitEncodeSimd<Arch128, kNumStreams>(
+ raw_values, width, num_values, output_buffer_raw);
+ }
+ }
assert(width == kNumStreams);
- static_assert(kNumStreams <= simd_batch::size,
+ static_assert(kNumStreams <= kBatchSize,
"The algorithm works when the number of streams is smaller than the SIMD "
"batch size.");
- constexpr int kBlockSize = simd_batch::size * kNumStreams;
+ constexpr int kBlockSize = kBatchSize * kNumStreams;
static_assert(ReversePow2(kNumStreams) != 0,
"The algorithm works for a number of streams being a power of two.");
@@ -174,7 +209,7 @@ void ByteStreamSplitEncodeSimd128(const uint8_t* raw_values, int width,
}
// Number of input values we can fit in a simd register
- constexpr int kNumValuesInBatch = simd_batch::size / kNumStreams;
+ constexpr int kNumValuesInBatch = kBatchSize / kNumStreams;
static_assert(kNumValuesInBatch > 0);
// Number of bytes we'll bring together in the first byte-level part of the algorithm.
// Since we zip with the next batch, the number of values in a batch determines how many
@@ -183,14 +218,13 @@ void ByteStreamSplitEncodeSimd128(const uint8_t* raw_values, int width,
// Number of steps in the first part of the algorithm with byte-level zipping
constexpr int kNumStepsByte = ReversePow2(kNumValuesInBatch) + 1;
// Number of steps in the first part of the algorithm with large data type zipping
- constexpr int kNumStepsLarge =
- ReversePow2(static_cast<int>(simd_batch::size) / kNumBytes);
+ constexpr int kNumStepsLarge = ReversePow2(static_cast<int>(kBatchSize) / kNumBytes);
// Total number of steps
constexpr int kNumSteps = kNumStepsByte + kNumStepsLarge;
- static_assert(kNumSteps == ReversePow2(simd_batch::size));
+ static_assert(kNumSteps == ReversePow2(kBatchSize));
// Two step shuffling algorithm that starts with bytes and ends with a larger data type.
- // An algorithm similar to the decoding one with log2(simd_batch::size) + 1 stages is
+ // An algorithm similar to the decoding one with log2(kBatchSize) + 1 stages is
// also valid but not as performant.
for (int64_t block_index = 0; block_index < num_blocks; ++block_index) {
simd_batch stage[kNumSteps + 1][kNumStreams];
@@ -198,7 +232,7 @@ void ByteStreamSplitEncodeSimd128(const uint8_t* raw_values, int width,
// First copy the data to stage 0.
for (int i = 0; i < kNumStreams; ++i) {
stage[0][i] = simd_batch::load_unaligned(
- &raw_values[(block_index * kNumStreams + i) * simd_batch::size]);
+ &raw_values[(block_index * kNumStreams + i) * kBatchSize]);
}
// We first make byte-level shuffling, until we have gather enough bytes together
@@ -236,217 +270,50 @@ void ByteStreamSplitEncodeSimd128(const uint8_t* raw_values, int width,
for (int step = kNumStepsByte; step < kNumSteps; ++step) {
for (int i = 0; i < kNumStreamsHalf; ++i) {
stage[step + 1][i * 2] =
- zip_lo_n<kNumBytes>(stage[step][i], stage[step][i + kNumStreamsHalf]);
+ zip_lo_n<Arch, kNumBytes>(stage[step][i], stage[step][i + kNumStreamsHalf]);
stage[step + 1][i * 2 + 1] =
- zip_hi_n<kNumBytes>(stage[step][i], stage[step][i + kNumStreamsHalf]);
+ zip_hi_n<Arch, kNumBytes>(stage[step][i], stage[step][i + kNumStreamsHalf]);
}
}
// Save the encoded data to the output buffer
for (int i = 0; i < kNumStreams; ++i) {
- xsimd::store_unaligned(&output_buffer_streams[i][block_index * simd_batch::size],
+ xsimd::store_unaligned(&output_buffer_streams[i][block_index * kBatchSize],
stage[kNumSteps][i]);
}
}
}
-#endif
+# if defined(ARROW_HAVE_RUNTIME_AVX2)
-#if defined(ARROW_HAVE_AVX2)
-template <int kNumStreams>
-void ByteStreamSplitDecodeAvx2(const uint8_t* data, int width, int64_t num_values,
- int64_t stride, uint8_t* out) {
- assert(width == kNumStreams);
- static_assert(kNumStreams == 4 || kNumStreams == 8, "Invalid number of streams.");
- constexpr int kNumStreamsLog2 = (kNumStreams == 8 ? 3 : 2);
- constexpr int64_t kBlockSize = sizeof(__m256i) * kNumStreams;
+// The extern template declaration are used internally and need export
+// to be used in tests and benchmarks.
- const int64_t size = num_values * kNumStreams;
- if (size < kBlockSize) // Back to SSE for small size
- return ByteStreamSplitDecodeSimd128<kNumStreams>(data, width, num_values, stride,
- out);
- const int64_t num_blocks = size / kBlockSize;
-
- // First handle suffix.
- const int64_t num_processed_elements = (num_blocks * kBlockSize) / kNumStreams;
- for (int64_t i = num_processed_elements; i < num_values; ++i) {
- uint8_t gathered_byte_data[kNumStreams];
- for (int b = 0; b < kNumStreams; ++b) {
- const int64_t byte_index = b * stride + i;
- gathered_byte_data[b] = data[byte_index];
- }
- memcpy(out + i * kNumStreams, gathered_byte_data, kNumStreams);
- }
-
- // Processed hierarchically using unpack intrinsics, then permute intrinsics.
- __m256i stage[kNumStreamsLog2 + 1][kNumStreams];
- __m256i final_result[kNumStreams];
- constexpr int kNumStreamsHalf = kNumStreams / 2;
-
- for (int64_t i = 0; i < num_blocks; ++i) {
- for (int j = 0; j < kNumStreams; ++j) {
- stage[0][j] = _mm256_loadu_si256(
- reinterpret_cast<const __m256i*>(&data[i * sizeof(__m256i) + j * stride]));
- }
-
- for (int step = 0; step < kNumStreamsLog2; ++step) {
- for (int j = 0; j < kNumStreamsHalf; ++j) {
- stage[step + 1][j * 2] =
- _mm256_unpacklo_epi8(stage[step][j], stage[step][kNumStreamsHalf + j]);
- stage[step + 1][j * 2 + 1] =
- _mm256_unpackhi_epi8(stage[step][j], stage[step][kNumStreamsHalf + j]);
- }
- }
-
- if constexpr (kNumStreams == 8) {
- // path for double, 128i index:
- // {0x00, 0x08}, {0x01, 0x09}, {0x02, 0x0A}, {0x03, 0x0B},
- // {0x04, 0x0C}, {0x05, 0x0D}, {0x06, 0x0E}, {0x07, 0x0F},
- final_result[0] = _mm256_permute2x128_si256(stage[kNumStreamsLog2][0],
- stage[kNumStreamsLog2][1], 0b00100000);
- final_result[1] = _mm256_permute2x128_si256(stage[kNumStreamsLog2][2],
- stage[kNumStreamsLog2][3], 0b00100000);
- final_result[2] = _mm256_permute2x128_si256(stage[kNumStreamsLog2][4],
- stage[kNumStreamsLog2][5], 0b00100000);
- final_result[3] = _mm256_permute2x128_si256(stage[kNumStreamsLog2][6],
- stage[kNumStreamsLog2][7], 0b00100000);
- final_result[4] = _mm256_permute2x128_si256(stage[kNumStreamsLog2][0],
- stage[kNumStreamsLog2][1], 0b00110001);
- final_result[5] = _mm256_permute2x128_si256(stage[kNumStreamsLog2][2],
- stage[kNumStreamsLog2][3], 0b00110001);
- final_result[6] = _mm256_permute2x128_si256(stage[kNumStreamsLog2][4],
- stage[kNumStreamsLog2][5], 0b00110001);
- final_result[7] = _mm256_permute2x128_si256(stage[kNumStreamsLog2][6],
- stage[kNumStreamsLog2][7], 0b00110001);
- } else {
- // path for float, 128i index:
- // {0x00, 0x04}, {0x01, 0x05}, {0x02, 0x06}, {0x03, 0x07}
- final_result[0] = _mm256_permute2x128_si256(stage[kNumStreamsLog2][0],
- stage[kNumStreamsLog2][1], 0b00100000);
- final_result[1] = _mm256_permute2x128_si256(stage[kNumStreamsLog2][2],
- stage[kNumStreamsLog2][3], 0b00100000);
- final_result[2] = _mm256_permute2x128_si256(stage[kNumStreamsLog2][0],
- stage[kNumStreamsLog2][1], 0b00110001);
- final_result[3] = _mm256_permute2x128_si256(stage[kNumStreamsLog2][2],
- stage[kNumStreamsLog2][3], 0b00110001);
- }
-
- for (int j = 0; j < kNumStreams; ++j) {
- _mm256_storeu_si256(
- reinterpret_cast<__m256i*>(out + (i * kNumStreams + j) * sizeof(__m256i)),
- final_result[j]);
- }
- }
-}
+extern template ARROW_TEMPLATE_EXPORT void ByteStreamSplitDecodeSimd<xsimd::avx2, 2>(
+ const uint8_t*, int, int64_t, int64_t, uint8_t*);
+extern template ARROW_TEMPLATE_EXPORT void ByteStreamSplitDecodeSimd<xsimd::avx2, 4>(
+ const uint8_t*, int, int64_t, int64_t, uint8_t*);
+extern template ARROW_TEMPLATE_EXPORT void ByteStreamSplitDecodeSimd<xsimd::avx2, 8>(
+ const uint8_t*, int, int64_t, int64_t, uint8_t*);
template <int kNumStreams>
-void ByteStreamSplitEncodeAvx2(const uint8_t* raw_values, int width,
- const int64_t num_values, uint8_t* output_buffer_raw) {
- assert(width == kNumStreams);
- static_assert(kNumStreams == 4, "Invalid number of streams.");
- constexpr int kBlockSize = sizeof(__m256i) * kNumStreams;
-
- const int64_t size = num_values * kNumStreams;
- if (size < kBlockSize) // Back to SSE for small size
- return ByteStreamSplitEncodeSimd128<kNumStreams>(raw_values, width, num_values,
- output_buffer_raw);
- const int64_t num_blocks = size / kBlockSize;
- const __m256i* raw_values_simd = reinterpret_cast<const __m256i*>(raw_values);
- __m256i* output_buffer_streams[kNumStreams];
-
- for (int i = 0; i < kNumStreams; ++i) {
- output_buffer_streams[i] =
- reinterpret_cast<__m256i*>(&output_buffer_raw[num_values * i]);
- }
-
- // First handle suffix.
- const int64_t num_processed_elements = (num_blocks * kBlockSize) / kNumStreams;
- for (int64_t i = num_processed_elements; i < num_values; ++i) {
- for (int j = 0; j < kNumStreams; ++j) {
- const uint8_t byte_in_value = raw_values[i * kNumStreams + j];
- output_buffer_raw[j * num_values + i] = byte_in_value;
- }
- }
-
- // Path for float.
- // 1. Processed hierarchically to 32i block using the unpack intrinsics.
- // 2. Pack 128i block using _mm256_permutevar8x32_epi32.
- // 3. Pack final 256i block with _mm256_permute2x128_si256.
- constexpr int kNumUnpack = 3;
- __m256i stage[kNumUnpack + 1][kNumStreams];
- static const __m256i kPermuteMask =
- _mm256_set_epi32(0x07, 0x03, 0x06, 0x02, 0x05, 0x01, 0x04, 0x00);
- __m256i permute[kNumStreams];
- __m256i final_result[kNumStreams];
-
- for (int64_t block_index = 0; block_index < num_blocks; ++block_index) {
- for (int i = 0; i < kNumStreams; ++i) {
- stage[0][i] = _mm256_loadu_si256(&raw_values_simd[block_index * kNumStreams + i]);
- }
-
- for (int stage_lvl = 0; stage_lvl < kNumUnpack; ++stage_lvl) {
- for (int i = 0; i < kNumStreams / 2; ++i) {
- stage[stage_lvl + 1][i * 2] =
- _mm256_unpacklo_epi8(stage[stage_lvl][i * 2], stage[stage_lvl][i * 2 + 1]);
- stage[stage_lvl + 1][i * 2 + 1] =
- _mm256_unpackhi_epi8(stage[stage_lvl][i * 2], stage[stage_lvl][i * 2 + 1]);
- }
- }
+void ByteStreamSplitEncodeAvx2(const uint8_t*, int, const int64_t, uint8_t*);
+
+extern template ARROW_TEMPLATE_EXPORT void ByteStreamSplitEncodeAvx2<2>(const uint8_t*,
+ int,
+ const int64_t,
+ uint8_t*);
+extern template ARROW_TEMPLATE_EXPORT void ByteStreamSplitEncodeAvx2<4>(const uint8_t*,
+ int,
+ const int64_t,
+ uint8_t*);
+extern template ARROW_TEMPLATE_EXPORT void ByteStreamSplitEncodeAvx2<8>(const uint8_t*,
+ int,
+ const int64_t,
+ uint8_t*);
- for (int i = 0; i < kNumStreams; ++i) {
- permute[i] = _mm256_permutevar8x32_epi32(stage[kNumUnpack][i], kPermuteMask);
- }
-
- final_result[0] = _mm256_permute2x128_si256(permute[0], permute[2], 0b00100000);
- final_result[1] = _mm256_permute2x128_si256(permute[0], permute[2], 0b00110001);
- final_result[2] = _mm256_permute2x128_si256(permute[1], permute[3], 0b00100000);
- final_result[3] = _mm256_permute2x128_si256(permute[1], permute[3], 0b00110001);
-
- for (int i = 0; i < kNumStreams; ++i) {
- _mm256_storeu_si256(&output_buffer_streams[i][block_index], final_result[i]);
- }
- }
-}
-#endif // ARROW_HAVE_AVX2
-
-#if defined(ARROW_HAVE_SIMD_SPLIT)
-template <int kNumStreams>
-void inline ByteStreamSplitDecodeSimd(const uint8_t* data, int width, int64_t num_values,
- int64_t stride, uint8_t* out) {
-# if defined(ARROW_HAVE_AVX2)
- // Not implemented
- if constexpr (kNumStreams == 2) {
- return ByteStreamSplitDecodeSimd128<2>(data, width, num_values, stride, out);
- } else {
- return ByteStreamSplitDecodeAvx2<kNumStreams>(data, width, num_values, stride, out);
- }
-# elif defined(ARROW_HAVE_SSE4_2) || defined(ARROW_HAVE_NEON)
- return ByteStreamSplitDecodeSimd128<kNumStreams>(data, width, num_values, stride, out);
-# else
-# error "ByteStreamSplitDecodeSimd not implemented"
# endif
-}
-template <int kNumStreams>
-void inline ByteStreamSplitEncodeSimd(const uint8_t* raw_values, int width,
- const int64_t num_values,
- uint8_t* output_buffer_raw) {
-# if defined(ARROW_HAVE_AVX2)
- // Not implemented
- if constexpr (kNumStreams == 2 || kNumStreams == 8) {
- return ByteStreamSplitEncodeSimd128<kNumStreams>(raw_values, width, num_values,
- output_buffer_raw);
- } else {
- return ByteStreamSplitEncodeAvx2<kNumStreams>(raw_values, width, num_values,
- output_buffer_raw);
- }
-# elif defined(ARROW_HAVE_SSE4_2) || defined(ARROW_HAVE_NEON)
- return ByteStreamSplitEncodeSimd128<kNumStreams>(raw_values, width, num_values,
- output_buffer_raw);
-# else
-# error "ByteStreamSplitEncodeSimd not implemented"
-# endif
-}
#endif
//
@@ -584,52 +451,63 @@ inline void ByteStreamSplitDecodeScalarDynamic(const uint8_t* data, int width,
DoMergeStreams(src_streams.data(), width, num_values, out);
}
+template <int kNumStreams>
+void ByteStreamSplitDecodeSimdDispatch(const uint8_t* data, int width, int64_t num_values,
+ int64_t stride, uint8_t* out);
+
+extern template ARROW_TEMPLATE_EXPORT void ByteStreamSplitDecodeSimdDispatch<2>(
+ const uint8_t*, int, int64_t, int64_t, uint8_t*);
+extern template ARROW_TEMPLATE_EXPORT void ByteStreamSplitDecodeSimdDispatch<4>(
+ const uint8_t*, int, int64_t, int64_t, uint8_t*);
+extern template ARROW_TEMPLATE_EXPORT void ByteStreamSplitDecodeSimdDispatch<8>(
+ const uint8_t*, int, int64_t, int64_t, uint8_t*);
+
+template <int kNumStreams>
+void ByteStreamSplitEncodeSimdDispatch(const uint8_t* raw_values, int width,
+ const int64_t num_values,
+ uint8_t* output_buffer_raw);
+
+extern template ARROW_TEMPLATE_EXPORT void ByteStreamSplitEncodeSimdDispatch<2>(
+ const uint8_t*, int, const int64_t, uint8_t*);
+extern template ARROW_TEMPLATE_EXPORT void ByteStreamSplitEncodeSimdDispatch<4>(
+ const uint8_t*, int, const int64_t, uint8_t*);
+extern template ARROW_TEMPLATE_EXPORT void ByteStreamSplitEncodeSimdDispatch<8>(
+ const uint8_t*, int, const int64_t, uint8_t*);
+
inline void ByteStreamSplitEncode(const uint8_t* raw_values, int width,
const int64_t num_values, uint8_t* out) {
-#if defined(ARROW_HAVE_SIMD_SPLIT)
-# define ByteStreamSplitEncodePerhapsSimd ByteStreamSplitEncodeSimd
-#else
-# define ByteStreamSplitEncodePerhapsSimd ByteStreamSplitEncodeScalar
-#endif
switch (width) {
case 1:
- memcpy(out, raw_values, num_values);
+ std::memcpy(out, raw_values, num_values);
return;
case 2:
- return ByteStreamSplitEncodePerhapsSimd<2>(raw_values, width, num_values, out);
+ return ByteStreamSplitEncodeSimdDispatch<2>(raw_values, width, num_values, out);
case 4:
- return ByteStreamSplitEncodePerhapsSimd<4>(raw_values, width, num_values, out);
+ return ByteStreamSplitEncodeSimdDispatch<4>(raw_values, width, num_values, out);
case 8:
- return ByteStreamSplitEncodePerhapsSimd<8>(raw_values, width, num_values, out);
+ return ByteStreamSplitEncodeSimdDispatch<8>(raw_values, width, num_values, out);
case 16:
return ByteStreamSplitEncodeScalar<16>(raw_values, width, num_values, out);
}
return ByteStreamSplitEncodeScalarDynamic(raw_values, width, num_values, out);
-#undef ByteStreamSplitEncodePerhapsSimd
}
inline void ByteStreamSplitDecode(const uint8_t* data, int width, int64_t num_values,
int64_t stride, uint8_t* out) {
-#if defined(ARROW_HAVE_SIMD_SPLIT)
-# define ByteStreamSplitDecodePerhapsSimd ByteStreamSplitDecodeSimd
-#else
-# define ByteStreamSplitDecodePerhapsSimd ByteStreamSplitDecodeScalar
-#endif
switch (width) {
case 1:
- memcpy(out, data, num_values);
+ std::memcpy(out, data, num_values);
return;
case 2:
- return ByteStreamSplitDecodePerhapsSimd<2>(data, width, num_values, stride, out);
+ return ByteStreamSplitDecodeSimdDispatch<2>(data, width, num_values, stride, out);
case 4:
- return ByteStreamSplitDecodePerhapsSimd<4>(data, width, num_values, stride, out);
+ return ByteStreamSplitDecodeSimdDispatch<4>(data, width, num_values, stride, out);
case 8:
- return ByteStreamSplitDecodePerhapsSimd<8>(data, width, num_values, stride, out);
+ return ByteStreamSplitDecodeSimdDispatch<8>(data, width, num_values, stride, out);
case 16:
return ByteStreamSplitDecodeScalar<16>(data, width, num_values, stride, out);
}
return ByteStreamSplitDecodeScalarDynamic(data, width, num_values, stride, out);
-#undef ByteStreamSplitDecodePerhapsSimd
}
} // namespace arrow::util::internal
diff --git a/cpp/src/arrow/util/byte_stream_split_internal_avx2.cc b/cpp/src/arrow/util/byte_stream_split_internal_avx2.cc
new file mode 100644
index 0000000000..d94932e88c
--- /dev/null
+++ b/cpp/src/arrow/util/byte_stream_split_internal_avx2.cc
@@ -0,0 +1,137 @@
+// Licensed to the Apache Software Foundation (ASF) under one
+// or more contributor license agreements. See the NOTICE file
+// distributed with this work for additional information
+// regarding copyright ownership. The ASF licenses this file
+// to you under the Apache License, Version 2.0 (the
+// "License"); you may not use this file except in compliance
+// with the License. You may obtain a copy of the License at
+//
+// http://www.apache.org/licenses/LICENSE-2.0
+//
+// Unless required by applicable law or agreed to in writing,
+// software distributed under the License is distributed on an
+// "AS IS" BASIS, WITHOUT WARRANTIES OR CONDITIONS OF ANY
+// KIND, either express or implied. See the License for the
+// specific language governing permissions and limitations
+// under the License.
+
+#include "arrow/util/byte_stream_split_internal.h"
+#include "arrow/util/math_internal.h"
+#include "arrow/util/simd.h"
+
+#include <xsimd/types/xsimd_avx2_register.hpp>
+#include <xsimd/xsimd.hpp>
+
+#include <cassert>
+#include <cstdint>
+#include <cstring>
+
+namespace arrow::util::internal {
+
+using ::arrow::internal::ReversePow2;
+
+template void ByteStreamSplitDecodeSimd<xsimd::avx2, 2>(const uint8_t*, int, int64_t,
+ int64_t, uint8_t*);
+template void ByteStreamSplitDecodeSimd<xsimd::avx2, 4>(const uint8_t*, int, int64_t,
+ int64_t, uint8_t*);
+template void ByteStreamSplitDecodeSimd<xsimd::avx2, 8>(const uint8_t*, int, int64_t,
+ int64_t, uint8_t*);
+
+// Faster implementation in AVX2 using native intrinsics.
+// Probably because the zip/unpack on AVX2 really work on two bits lanes,
+// which is not general enough for xsimd to abstract.
+inline void ByteStreamSplitEncodeAvx2Impl4(const uint8_t* raw_values, int width,
+ const int64_t num_values,
+ uint8_t* output_buffer_raw) {
+ constexpr int kNumStreams = 4;
+ assert(width == kNumStreams);
+ constexpr int kBlockSize = sizeof(__m256i) * kNumStreams;
+
+ const int64_t size = num_values * kNumStreams;
+ if (size < kBlockSize) // Back to SSE for small size
+ return ByteStreamSplitEncodeSimd<xsimd::sse4_2, kNumStreams>(
+ raw_values, width, num_values, output_buffer_raw);
+ const int64_t num_blocks = size / kBlockSize;
+ const __m256i* raw_values_simd = reinterpret_cast<const __m256i*>(raw_values);
+ __m256i* output_buffer_streams[kNumStreams];
+
+ for (int i = 0; i < kNumStreams; ++i) {
+ output_buffer_streams[i] =
+ reinterpret_cast<__m256i*>(&output_buffer_raw[num_values * i]);
+ }
+
+ // First handle suffix.
+ const int64_t num_processed_elements = (num_blocks * kBlockSize) / kNumStreams;
+ for (int64_t i = num_processed_elements; i < num_values; ++i) {
+ for (int j = 0; j < kNumStreams; ++j) {
+ const uint8_t byte_in_value = raw_values[i * kNumStreams + j];
+ output_buffer_raw[j * num_values + i] = byte_in_value;
+ }
+ }
+
+ // Path for float.
+ // 1. Processed hierarchically to 32i block using the unpack intrinsics.
+ // 2. Pack 128i block using _mm256_permutevar8x32_epi32.
+ // 3. Pack final 256i block with _mm256_permute2x128_si256.
+ constexpr int kNumUnpack = 3;
+ __m256i stage[kNumUnpack + 1][kNumStreams];
+ __m256i permute[kNumStreams];
+ __m256i final_result[kNumStreams];
+
+ for (int64_t block_index = 0; block_index < num_blocks; ++block_index) {
+ for (int i = 0; i < kNumStreams; ++i) {
+ stage[0][i] = _mm256_loadu_si256(&raw_values_simd[block_index * kNumStreams + i]);
+ }
+
+ // We first make byte-level shuffling, until we have gather enough bytes together
+ // and in the correct order to use a bigger data type.
+ //
+ // Loop order does not matter so we prefer higher locality
+ constexpr int kNumStreamsHalf = kNumStreams / 2;
+ for (int i = 0; i < kNumStreamsHalf; ++i) {
+ for (int stage_lvl = 0; stage_lvl < kNumUnpack; ++stage_lvl) {
+ stage[stage_lvl + 1][i * 2] =
+ _mm256_unpacklo_epi8(stage[stage_lvl][i * 2], stage[stage_lvl][i * 2 + 1]);
+ stage[stage_lvl + 1][i * 2 + 1] =
+ _mm256_unpackhi_epi8(stage[stage_lvl][i * 2], stage[stage_lvl][i * 2 + 1]);
+ }
+ }
+
+ for (int i = 0; i < kNumStreamsHalf; ++i) {
+ permute[i] = _mm256_permute2x128_si256(
+ stage[kNumUnpack][i], stage[kNumUnpack][i + kNumStreamsHalf], 0b00100000);
+ permute[i + kNumStreamsHalf] = _mm256_permute2x128_si256(
+ stage[kNumUnpack][i], stage[kNumUnpack][i + kNumStreamsHalf], 0b00110001);
+ }
+
+ for (int i = 0; i < kNumStreams / 2; ++i) {
+ final_result[i * 2] =
+ _mm256_unpacklo_epi32(permute[i], permute[i + kNumStreamsHalf]);
+ final_result[i * 2 + 1] =
+ _mm256_unpackhi_epi32(permute[i], permute[i + kNumStreamsHalf]);
+ }
+
+ for (int i = 0; i < kNumStreams; ++i) {
+ _mm256_storeu_si256(&output_buffer_streams[i][block_index], final_result[i]);
+ }
+ }
+}
+
+template <int kNumStreams>
+void ByteStreamSplitEncodeAvx2(const uint8_t* raw_values, int width,
+ const int64_t num_values, uint8_t* output_buffer_raw) {
+ // Only size with a different implementation
+ if constexpr (kNumStreams == 4) {
+ return ByteStreamSplitEncodeAvx2Impl4(raw_values, width, num_values,
+ output_buffer_raw);
+ } else {
+ return ByteStreamSplitEncodeSimd<xsimd::avx2, kNumStreams>(
+ raw_values, width, num_values, output_buffer_raw);
+ }
+}
+
+template void ByteStreamSplitEncodeAvx2<2>(const uint8_t*, int, const int64_t, uint8_t*);
+template void ByteStreamSplitEncodeAvx2<4>(const uint8_t*, int, const int64_t, uint8_t*);
+template void ByteStreamSplitEncodeAvx2<8>(const uint8_t*, int, const int64_t, uint8_t*);
+
+} // namespace arrow::util::internal
diff --git a/cpp/src/arrow/util/byte_stream_split_test.cc b/cpp/src/arrow/util/byte_stream_split_test.cc
index ec995a0a9a..13a99d937c 100644
--- a/cpp/src/arrow/util/byte_stream_split_test.cc
+++ b/cpp/src/arrow/util/byte_stream_split_test.cc
@@ -143,20 +143,23 @@ class TestByteStreamSplitSpecialized : public ::testing::Test {
funcs.push_back({"scalar", &ByteStreamSplitDecodeScalar<kWidth>});
#if defined(ARROW_HAVE_SIMD_SPLIT)
if constexpr (kSimdImplemented) {
- funcs.push_back({"simd", &ByteStreamSplitDecodeSimd<kWidth>});
- funcs.push_back({"simd128", &ByteStreamSplitDecodeSimd128<kWidth>});
+ funcs.push_back({"simd_dispatch", &ByteStreamSplitDecodeSimdDispatch<kWidth>});
+# if defined(ARROW_HAVE_NEON)
+ funcs.push_back({"xsimd_neon", &ByteStreamSplitDecodeSimd<xsimd::neon64, kWidth>});
+# endif
+# if defined(ARROW_HAVE_SSE4_2)
+ funcs.push_back(
+ {"xsimd_sse4_2", &ByteStreamSplitDecodeSimd<xsimd::sse4_2, kWidth>});
+# endif
# if defined(ARROW_HAVE_AVX2)
- // The only available implementations
- if constexpr (kWidth == 4 || kWidth == 8) {
- funcs.push_back({"avx2", &ByteStreamSplitDecodeAvx2<kWidth>});
- }
+ funcs.push_back({"xsimd_avx2", &ByteStreamSplitDecodeSimd<xsimd::avx2, kWidth>});
# endif
}
#endif // defined(ARROW_HAVE_SIMD_SPLIT)
return funcs;
}
- template <bool kSimdImplemented = (kWidth == 4 || kWidth == 8)>
+ template <bool kSimdImplemented = (kWidth == 2 || kWidth == 4 || kWidth == 8)>
static std::vector<EncodeFunc> MakeEncodeFuncs() {
std::vector<EncodeFunc> funcs;
funcs.push_back({"reference", &ReferenceByteStreamSplitEncode});
@@ -164,12 +167,18 @@ class TestByteStreamSplitSpecialized : public ::testing::Test {
funcs.push_back({"scalar", &ByteStreamSplitEncodeScalar<kWidth>});
#if defined(ARROW_HAVE_SIMD_SPLIT)
if constexpr (kSimdImplemented) {
- funcs.push_back({"simd", &ByteStreamSplitEncodeSimd<kWidth>});
- funcs.push_back({"simd128", &ByteStreamSplitEncodeSimd128<kWidth>});
+ funcs.push_back({"simd_dispatch", &ByteStreamSplitEncodeSimdDispatch<kWidth>});
+# if defined(ARROW_HAVE_NEON)
+ funcs.push_back({"xsimd_neon", &ByteStreamSplitEncodeSimd<xsimd::neon64, kWidth>});
+# endif
+# if defined(ARROW_HAVE_SSE4_2)
+ funcs.push_back(
+ {"xsimd_sse4_2", &ByteStreamSplitEncodeSimd<xsimd::sse4_2, kWidth>});
+# endif
# if defined(ARROW_HAVE_AVX2)
- // The only available implementation
+ funcs.push_back({"xsimd_avx2", &ByteStreamSplitEncodeSimd<xsimd::avx2, kWidth>});
if constexpr (kWidth == 4) {
- funcs.push_back({"avx2", &ByteStreamSplitEncodeAvx2<kWidth>});
+ funcs.push_back({"intrinsics_avx2", &ByteStreamSplitEncodeAvx2<kWidth>});
}
# endif
}
diff --git a/cpp/src/arrow/util/dispatch_internal.h b/cpp/src/arrow/util/dispatch_internal.h
index fae9293f9e..7ac19b0b24 100644
--- a/cpp/src/arrow/util/dispatch_internal.h
+++ b/cpp/src/arrow/util/dispatch_internal.h
@@ -76,7 +76,8 @@ class DynamicDispatch {
protected:
// Use the Implementation with the highest DispatchLevel
- void Resolve(const std::vector<Implementation>& implementations) {
+ template <typename Range>
+ void Resolve(const Range& implementations) {
Implementation cur{DispatchLevel::NONE, {}};
for (const auto& impl : implementations) {
diff --git a/cpp/src/arrow/util/math_internal.h b/cpp/src/arrow/util/math_internal.h
index 3ff30cabf2..a57083ce7f 100644
--- a/cpp/src/arrow/util/math_internal.h
+++ b/cpp/src/arrow/util/math_internal.h
@@ -59,4 +59,20 @@ double NeumaierSum(Range&& inputs) {
return sum + c;
}
+/// Based-2 logarithm that works only on powers of two.
+template <typename T>
+constexpr T ReversePow2(T x) {
+ constexpr T kByteLen = 8;
+ for (T n = 0, y = 1; n <= (kByteLen * static_cast<T>(sizeof(T))); ++n, y = y * 2) {
+ if (y == x) {
+ return n;
+ }
+ }
+ return 0;
+}
+
+static_assert(ReversePow2(8) == 3);
+static_assert(ReversePow2(4) == 2);
+static_assert(ReversePow2(2) == 1);
+
} // namespace arrow::internal
diff --git a/cpp/src/arrow/util/small_vector.h b/cpp/src/arrow/util/small_vector.h
index 52e191c4c0..f371e64715 100644
--- a/cpp/src/arrow/util/small_vector.h
+++ b/cpp/src/arrow/util/small_vector.h
@@ -26,6 +26,7 @@
#include <new>
#include <type_traits>
#include <utility>
+#include <vector>
#include "arrow/util/aligned_storage.h"
#include "arrow/util/macros.h"
diff --git a/cpp/src/parquet/encoding_benchmark.cc b/cpp/src/parquet/encoding_benchmark.cc
index aee30bf762..bea1a5807a 100644
--- a/cpp/src/parquet/encoding_benchmark.cc
+++ b/cpp/src/parquet/encoding_benchmark.cc
@@ -464,6 +464,11 @@ static void BM_ByteStreamSplitEncode_FLBA_Generic(benchmark::State& state) {
state, ::arrow::util::internal::ByteStreamSplitEncode);
}
+static void BM_ByteStreamSplitDecode_Int16_Scalar(benchmark::State& state) {
+ BM_ByteStreamSplitDecode<int16_t>(
+ state, ::arrow::util::internal::ByteStreamSplitDecodeScalar<sizeof(int16_t)>);
+}
+
static void BM_ByteStreamSplitDecode_Float_Scalar(benchmark::State& state) {
BM_ByteStreamSplitDecode<float>(
state, ::arrow::util::internal::ByteStreamSplitDecodeScalar<sizeof(float)>);
@@ -474,6 +479,11 @@ static void BM_ByteStreamSplitDecode_Double_Scalar(benchmark::State& state) {
state, ::arrow::util::internal::ByteStreamSplitDecodeScalar<sizeof(double)>);
}
+static void BM_ByteStreamSplitEncode_Int16_Scalar(benchmark::State& state) {
+ BM_ByteStreamSplitEncode<int16_t>(
+ state, ::arrow::util::internal::ByteStreamSplitEncodeScalar<sizeof(int16_t)>);
+}
+
static void BM_ByteStreamSplitEncode_Float_Scalar(benchmark::State& state) {
BM_ByteStreamSplitEncode<float>(
state, ::arrow::util::internal::ByteStreamSplitEncodeScalar<sizeof(float)>);
@@ -503,40 +513,48 @@ BENCHMARK_TEMPLATE(BM_ByteStreamSplitEncode_FLBA_Generic, 7)->Apply(ByteStreamSp
BENCHMARK_TEMPLATE(BM_ByteStreamSplitEncode_FLBA_Generic, 16)
->Apply(ByteStreamSplitApply);
+BENCHMARK(BM_ByteStreamSplitDecode_Int16_Scalar)->Apply(ByteStreamSplitApply);
BENCHMARK(BM_ByteStreamSplitDecode_Float_Scalar)->Apply(ByteStreamSplitApply);
BENCHMARK(BM_ByteStreamSplitDecode_Double_Scalar)->Apply(ByteStreamSplitApply);
+BENCHMARK(BM_ByteStreamSplitEncode_Int16_Scalar)->Apply(ByteStreamSplitApply);
BENCHMARK(BM_ByteStreamSplitEncode_Float_Scalar)->Apply(ByteStreamSplitApply);
BENCHMARK(BM_ByteStreamSplitEncode_Double_Scalar)->Apply(ByteStreamSplitApply);
#if defined(ARROW_HAVE_SSE4_2)
static void BM_ByteStreamSplitDecode_Int16_Sse2(benchmark::State& state) {
BM_ByteStreamSplitDecode<int16_t>(
- state, ::arrow::util::internal::ByteStreamSplitDecodeSimd128<sizeof(int16_t)>);
+ state,
+ ::arrow::util::internal::ByteStreamSplitDecodeSimd<xsimd::sse4_2, sizeof(int16_t)>);
}
static void BM_ByteStreamSplitDecode_Float_Sse2(benchmark::State& state) {
BM_ByteStreamSplitDecode<float>(
- state, ::arrow::util::internal::ByteStreamSplitDecodeSimd128<sizeof(float)>);
+ state,
+ ::arrow::util::internal::ByteStreamSplitDecodeSimd<xsimd::sse4_2, sizeof(float)>);
}
static void BM_ByteStreamSplitDecode_Double_Sse2(benchmark::State& state) {
BM_ByteStreamSplitDecode<double>(
- state, ::arrow::util::internal::ByteStreamSplitDecodeSimd128<sizeof(double)>);
+ state,
+ ::arrow::util::internal::ByteStreamSplitDecodeSimd<xsimd::sse4_2, sizeof(double)>);
}
static void BM_ByteStreamSplitEncode_Int16_Sse2(benchmark::State& state) {
BM_ByteStreamSplitEncode<int16_t>(
- state, ::arrow::util::internal::ByteStreamSplitEncodeSimd128<sizeof(int16_t)>);
+ state,
+ ::arrow::util::internal::ByteStreamSplitEncodeSimd<xsimd::sse4_2, sizeof(int16_t)>);
}
static void BM_ByteStreamSplitEncode_Float_Sse2(benchmark::State& state) {
BM_ByteStreamSplitEncode<float>(
- state, ::arrow::util::internal::ByteStreamSplitEncodeSimd128<sizeof(float)>);
+ state,
+ ::arrow::util::internal::ByteStreamSplitEncodeSimd<xsimd::sse4_2, sizeof(float)>);
}
static void BM_ByteStreamSplitEncode_Double_Sse2(benchmark::State& state) {
BM_ByteStreamSplitEncode<double>(
- state, ::arrow::util::internal::ByteStreamSplitEncodeSimd128<sizeof(double)>);
+ state,
+ ::arrow::util::internal::ByteStreamSplitEncodeSimd<xsimd::sse4_2, sizeof(double)>);
}
BENCHMARK(BM_ByteStreamSplitDecode_Int16_Sse2)->Apply(ByteStreamSplitApply);
@@ -548,14 +566,27 @@ BENCHMARK(BM_ByteStreamSplitEncode_Double_Sse2)->Apply(ByteStreamSplitApply);
#endif
#if defined(ARROW_HAVE_AVX2)
+static void BM_ByteStreamSplitDecode_Int16_Avx2(benchmark::State& state) {
+ BM_ByteStreamSplitDecode<int16_t>(
+ state,
+ ::arrow::util::internal::ByteStreamSplitDecodeSimd<xsimd::avx2, sizeof(int16_t)>);
+}
+
static void BM_ByteStreamSplitDecode_Float_Avx2(benchmark::State& state) {
BM_ByteStreamSplitDecode<float>(
- state, ::arrow::util::internal::ByteStreamSplitDecodeAvx2<sizeof(float)>);
+ state,
+ ::arrow::util::internal::ByteStreamSplitDecodeSimd<xsimd::avx2, sizeof(float)>);
}
static void BM_ByteStreamSplitDecode_Double_Avx2(benchmark::State& state) {
BM_ByteStreamSplitDecode<double>(
- state, ::arrow::util::internal::ByteStreamSplitDecodeAvx2<sizeof(double)>);
+ state,
+ ::arrow::util::internal::ByteStreamSplitDecodeSimd<xsimd::avx2, sizeof(double)>);
+}
+
+static void BM_ByteStreamSplitEncode_Int16_Avx2(benchmark::State& state) {
+ BM_ByteStreamSplitEncode<int16_t>(
+ state, ::arrow::util::internal::ByteStreamSplitEncodeAvx2<sizeof(int16_t)>);
}
static void BM_ByteStreamSplitEncode_Float_Avx2(benchmark::State& state) {
@@ -563,48 +594,71 @@ static void BM_ByteStreamSplitEncode_Float_Avx2(benchmark::State& state) {
state, ::arrow::util::internal::ByteStreamSplitEncodeAvx2<sizeof(float)>);
}
+static void BM_ByteStreamSplitEncode_Double_Avx2(benchmark::State& state) {
+ BM_ByteStreamSplitEncode<double>(
+ state, ::arrow::util::internal::ByteStreamSplitEncodeAvx2<sizeof(double)>);
+}
+
+BENCHMARK(BM_ByteStreamSplitDecode_Int16_Avx2)->Apply(ByteStreamSplitApply);
BENCHMARK(BM_ByteStreamSplitDecode_Float_Avx2)->Apply(ByteStreamSplitApply);
BENCHMARK(BM_ByteStreamSplitDecode_Double_Avx2)->Apply(ByteStreamSplitApply);
+BENCHMARK(BM_ByteStreamSplitEncode_Int16_Avx2)->Apply(ByteStreamSplitApply);
BENCHMARK(BM_ByteStreamSplitEncode_Float_Avx2)->Apply(ByteStreamSplitApply);
+BENCHMARK(BM_ByteStreamSplitEncode_Double_Avx2)->Apply(ByteStreamSplitApply);
+
+// This instantiation is not used but we show it in benchmark for comparison
+static void BM_ByteStreamSplitEncode_Float_Avx2_xsimd(benchmark::State& state) {
+ BM_ByteStreamSplitEncode<float>(
+ state,
+ ::arrow::util::internal::ByteStreamSplitEncodeSimd<xsimd::avx2, sizeof(float)>);
+}
+
+BENCHMARK(BM_ByteStreamSplitEncode_Float_Avx2_xsimd)->Apply(ByteStreamSplitApply);
#endif
#if defined(ARROW_HAVE_NEON)
static void BM_ByteStreamSplitDecode_Int16_Neon(benchmark::State& state) {
BM_ByteStreamSplitDecode<int16_t>(
- state, ::arrow::util::internal::ByteStreamSplitDecodeSimd128<sizeof(int16_t)>);
+ state,
+ ::arrow::util::internal::ByteStreamSplitDecodeSimd<xsimd::neon64, sizeof(int16_t)>);
}
static void BM_ByteStreamSplitDecode_Float_Neon(benchmark::State& state) {
BM_ByteStreamSplitDecode<float>(
- state, ::arrow::util::internal::ByteStreamSplitDecodeSimd128<sizeof(float)>);
+ state,
+ ::arrow::util::internal::ByteStreamSplitDecodeSimd<xsimd::neon64, sizeof(float)>);
}
static void BM_ByteStreamSplitDecode_Double_Neon(benchmark::State& state) {
BM_ByteStreamSplitDecode<double>(
- state, ::arrow::util::internal::ByteStreamSplitDecodeSimd128<sizeof(double)>);
+ state,
+ ::arrow::util::internal::ByteStreamSplitDecodeSimd<xsimd::neon64, sizeof(double)>);
}
static void BM_ByteStreamSplitEncode_Int16_Neon(benchmark::State& state) {
BM_ByteStreamSplitEncode<int16_t>(
- state, ::arrow::util::internal::ByteStreamSplitEncodeSimd128<sizeof(int16_t)>);
+ state,
+ ::arrow::util::internal::ByteStreamSplitEncodeSimd<xsimd::neon64, sizeof(int16_t)>);
}
static void BM_ByteStreamSplitEncode_Float_Neon(benchmark::State& state) {
BM_ByteStreamSplitEncode<float>(
- state, ::arrow::util::internal::ByteStreamSplitEncodeSimd128<sizeof(float)>);
+ state,
+ ::arrow::util::internal::ByteStreamSplitEncodeSimd<xsimd::neon64, sizeof(float)>);
}
static void BM_ByteStreamSplitEncode_Double_Neon(benchmark::State& state) {
BM_ByteStreamSplitEncode<double>(
- state, ::arrow::util::internal::ByteStreamSplitEncodeSimd128<sizeof(double)>);
+ state,
+ ::arrow::util::internal::ByteStreamSplitEncodeSimd<xsimd::neon64, sizeof(double)>);
}
-BENCHMARK(BM_ByteStreamSplitDecode_Int16_Neon)->Range(MIN_RANGE, MAX_RANGE);
-BENCHMARK(BM_ByteStreamSplitDecode_Float_Neon)->Range(MIN_RANGE, MAX_RANGE);
-BENCHMARK(BM_ByteStreamSplitDecode_Double_Neon)->Range(MIN_RANGE, MAX_RANGE);
-BENCHMARK(BM_ByteStreamSplitEncode_Int16_Neon)->Range(MIN_RANGE, MAX_RANGE);
-BENCHMARK(BM_ByteStreamSplitEncode_Float_Neon)->Range(MIN_RANGE, MAX_RANGE);
-BENCHMARK(BM_ByteStreamSplitEncode_Double_Neon)->Range(MIN_RANGE, MAX_RANGE);
+BENCHMARK(BM_ByteStreamSplitDecode_Int16_Neon)->Apply(ByteStreamSplitApply);
+BENCHMARK(BM_ByteStreamSplitDecode_Float_Neon)->Apply(ByteStreamSplitApply);
+BENCHMARK(BM_ByteStreamSplitDecode_Double_Neon)->Apply(ByteStreamSplitApply);
+BENCHMARK(BM_ByteStreamSplitEncode_Int16_Neon)->Apply(ByteStreamSplitApply);
+BENCHMARK(BM_ByteStreamSplitEncode_Float_Neon)->Apply(ByteStreamSplitApply);
+BENCHMARK(BM_ByteStreamSplitEncode_Double_Neon)->Apply(ByteStreamSplitApply);
#endif
template <typename DType>
diff --git a/dev/tasks/vcpkg-tests/cpp-build-vcpkg.bat b/dev/tasks/vcpkg-tests/cpp-build-vcpkg.bat
index 44124d6c32..8ca2e815c5 100644
--- a/dev/tasks/vcpkg-tests/cpp-build-vcpkg.bat
+++ b/dev/tasks/vcpkg-tests/cpp-build-vcpkg.bat
@@ -51,6 +51,8 @@ pushd cpp\build
@rem TODO(ianmcook): Add -DARROW_BUILD_BENCHMARKS=ON after the issue described
@rem at https://github.com/google/benchmark/issues/1046 is resolved
+@rem xsimd is bundled to get a more recent version.
+
cmake -G "Visual Studio 17 2022" -A x64 ^
-DARROW_BOOST_USE_SHARED=ON ^
-DARROW_BUILD_SHARED=ON ^
@@ -70,6 +72,7 @@ cmake -G "Visual Studio 17 2022" -A x64 ^
-DARROW_WITH_ZSTD=ON ^
-DCMAKE_BUILD_TYPE=release ^
-DCMAKE_UNITY_BUILD=ON ^
+ -Dxsimd_SOURCE=BUNDLED ^
.. || exit /B 1
cmake --build . --target INSTALL --config Release || exit /B 1