This is an automated email from the ASF dual-hosted git repository.
zhouyuan pushed a commit to branch main
in repository https://gitbox.apache.org/repos/asf/gluten.git
The following commit(s) were added to refs/heads/main by this push:
new 832d62df05 [CORE] Optimize FFOR min/max scan with AVX-512 runtime
dispatch (#13363)
832d62df05 is described below
commit 832d62df050f7f6c907160a2f02fb8ed1c29d044
Author: hu hengrui <[email protected]>
AuthorDate: Thu Nov 5 20:04:24 2026 +0800
[CORE] Optimize FFOR min/max scan with AVX-512 runtime dispatch (#13363)
Optimize the FFOR min/max scan using GCC target_clones, which generates a
baseline (AVX2) and an AVX-512 (x86-64-v4) version from a single scalar
function.
Signed-off-by: huhengrui <[email protected]>
Co-authored-by: Zhu Lipeng <[email protected]>
Co-authored-by: Guo Wangyang <[email protected]>
---
cpp/core/tests/FForCodecTest.cc | 114 ++++++++++++++++++++++++++++++++++++++++
cpp/core/utils/tac/FForCodec.cc | 33 ++++++++++++
cpp/core/utils/tac/ffor.hpp | 24 +++++----
3 files changed, 161 insertions(+), 10 deletions(-)
diff --git a/cpp/core/tests/FForCodecTest.cc b/cpp/core/tests/FForCodecTest.cc
index d4ef8aa4b9..3d9a2132ce 100644
--- a/cpp/core/tests/FForCodecTest.cc
+++ b/cpp/core/tests/FForCodecTest.cc
@@ -20,6 +20,7 @@
#include "utils/tac/ffor.hpp"
#include <gtest/gtest.h>
+#include <algorithm>
#include <cstring>
#include <random>
#include <vector>
@@ -201,6 +202,119 @@ TEST(FForTest, AnalyzeCorrectness) {
ASSERT_EQ(w, 8u);
}
+// The cases above all have a zero high half, so none of them covers a block
whose values sit on both
+// sides of a 2^32 boundary. These verify exact min/max there, plus the
property the encoding
+// actually relies on: base <= v for all v, and v - base < 2^bw.
+TEST(FForTest, AnalyzeStraddlesTwoPow32) {
+ constexpr uint64_t kBoundary = uint64_t(1) << 32;
+ std::vector<std::vector<uint64_t>> shapes = {
+ // A narrow range centred on the boundary.
+ {kBoundary - 2, kBoundary - 1, kBoundary, kBoundary + 1},
+ // One outlier a whole boundary above an otherwise narrow block.
+ {1000, 1001, 1002, kBoundary + 1003},
+ // Boundary pairs, in both orders.
+ {kBoundary, kBoundary - 1},
+ {kBoundary - 1, kBoundary},
+ // Mixed-sign BIGINT: -1 and 1 as unsigned are the two ends of the
domain.
+ {~uint64_t(0), 1, 0, 7},
+ // The sign-extended high half of a small negative 128-bit value next to
a small positive one.
+ {~uint64_t(0), ~uint64_t(0) - 5, 0, 3},
+ // Both extremes a full window apart, with the smallest value carrying
the largest low half.
+ {kBoundary | 0xFFFFFFFF, 3 * kBoundary, 2 * kBoundary + 50, 2 *
kBoundary + 60},
+ };
+
+ // Block-scale shapes so the vectorised body runs as well as its scalar
tail: 256 values is a full
+ // block, 259 leaves a 3-value tail.
+ std::mt19937_64 rng(999);
+ for (size_t n : {size_t(256), size_t(259)}) {
+ std::vector<uint64_t> data(n);
+ for (size_t i = 0; i < n; ++i) {
+ data[i] = kBoundary - 8 + (rng() & 0xF);
+ }
+ shapes.push_back(std::move(data));
+ }
+
+ for (const auto& data : shapes) {
+ uint64_t trueMin = data[0];
+ uint64_t trueMax = data[0];
+ for (uint64_t v : data) {
+ trueMin = std::min(trueMin, v);
+ trueMax = std::max(trueMax, v);
+ }
+ unsigned exactBw = 0;
+ for (uint64_t range = trueMax - trueMin; range > 0; range >>= 1) {
+ ++exactBw;
+ }
+ uint64_t base = 0;
+ unsigned bw = 0;
+ analyze(data.data(), data.size(), base, bw);
+
+ // Exact extremes across the boundary, not just the fit property.
+ ASSERT_EQ(base, trueMin);
+ ASSERT_EQ(bw, exactBw);
+ ASSERT_LE(bw, 64u);
+ if (bw < 64) {
+ ASSERT_LT(trueMax - base, uint64_t(1) << bw);
+ }
+
+ // The fit property above is what makes the encoding lossless, so check
that too.
+ compressRoundtrip(data.data(), data.size());
+ }
+}
+
+// Where AVX2 has no unsigned 64-bit min/max, a baseline build compares with
the sign bit flipped, so the
+// values that matter are the ones either side of 2^63 and the extremes 0 and
2^64 - 1. Each shape is
+// checked as a 4-value block and inside a 256-value block, so the vectorised
body runs and not only its
+// scalar tail; the extremes are placed away from the ends.
+TEST(FForTest, AnalyzeAroundTwoPow63) {
+ constexpr uint64_t kSign = uint64_t(1) << 63;
+ struct Shape {
+ std::vector<uint64_t> values;
+ uint64_t base;
+ unsigned bw;
+ };
+ const std::vector<Shape> shapes = {
+ {{kSign - 2, kSign - 1, kSign, kSign + 1}, kSign - 2, 2},
+ {{kSign - 1, kSign}, kSign - 1, 1},
+ {{0, kSign - 1, kSign, ~uint64_t(0)}, 0, 64},
+ {{kSign, ~uint64_t(0)}, kSign, 63},
+ };
+
+ for (const auto& shape : shapes) {
+ for (size_t n : {size_t(shape.values.size()), size_t(256)}) {
+ std::vector<uint64_t> data(n, shape.values[0]);
+ for (size_t i = 0; i < shape.values.size(); ++i) {
+ data[n == shape.values.size() ? i : 5 + 61 * i] = shape.values[i];
+ }
+ uint64_t base = 0;
+ unsigned bw = 0;
+ analyze(data.data(), data.size(), base, bw);
+ ASSERT_EQ(base, shape.base) << "n=" << n;
+ ASSERT_EQ(bw, shape.bw) << "n=" << n;
+ compressRoundtrip(data.data(), data.size());
+ }
+ }
+}
+
+// Exercise full blocks and short trailing values across the boundary through
the public compression
+// entry point.
+TEST(FForTest, Compress64StraddlesTwoPow32) {
+ constexpr uint64_t kBoundary = uint64_t(1) << 32;
+ std::mt19937_64 rng(12345);
+ for (size_t n : {size_t(3), size_t(17), size_t(256), size_t(259),
size_t(1000)}) {
+ std::vector<uint64_t> data(n);
+ for (size_t i = 0; i < n; ++i) {
+ data[i] = kBoundary - 4 + (rng() & 0x7);
+ }
+ compressRoundtrip(data.data(), n);
+
+ for (size_t i = 0; i < n; ++i) {
+ data[i] = (i % 3 == 0) ? ~uint64_t(0) - (rng() & 0xFFFF) : (rng() &
0xFFFF);
+ }
+ compressRoundtrip(data.data(), n);
+ }
+}
+
TEST(FForTest, CompressedSize) {
ASSERT_EQ(compressedWords(256, 6), size_t(24));
ASSERT_EQ(compressedWords(256, 1), size_t(4));
diff --git a/cpp/core/utils/tac/FForCodec.cc b/cpp/core/utils/tac/FForCodec.cc
index f31eb1a36c..746ce96b5a 100644
--- a/cpp/core/utils/tac/FForCodec.cc
+++ b/cpp/core/utils/tac/FForCodec.cc
@@ -16,9 +16,42 @@
*/
#include "utils/tac/FForCodec.h"
+#include "utils/Exception.h"
#include "utils/tac/ffor.hpp"
namespace gluten {
+namespace ffor {
+namespace detail {
+
+// AVX2 has no unsigned 64-bit min/max (vpminuq/vpmaxuq need AVX-512), so
GCC's AVX2 vectorization of
+// this loop emulates them with a bias, a signed compare and a blend on the
loop-carried chain. The
+// source is a plain scalar loop; target_clones adds an x86-64-v4 version and
an ifunc that picks
+// one at load time, and the result is identical.
+// Defined here so the clones and the resolver are emitted once, not once per
including TU.
+// GCC 11 rejects the attribute (no runtime x86-64-v4 level check) and clang's
support is untested,
+// so those builds, non-ELF/non-x86-64 targets and
GLUTEN_ENABLE_MULTITARGET_CODE=0 get a plain function.
+#if defined(__GNUC__) && !defined(__clang__) && __GNUC__ >= 12 &&
defined(__x86_64__) && defined(__ELF__) && \
+ (!defined(GLUTEN_ENABLE_MULTITARGET_CODE) ||
GLUTEN_ENABLE_MULTITARGET_CODE)
+__attribute__((target_clones("arch=x86-64-v4", "default")))
+#endif
+void minMaxScan(const uint64_t* data, size_t n, uint64_t& mn, uint64_t& mx) {
+ GLUTEN_DCHECK(n > 0, "minMaxScan requires at least one value");
+ uint64_t low = data[0];
+ uint64_t high = data[0];
+ for (size_t i = 1; i < n; ++i) {
+ if (data[i] < low) {
+ low = data[i];
+ }
+ if (data[i] > high) {
+ high = data[i];
+ }
+ }
+ mn = low;
+ mx = high;
+}
+
+} // namespace detail
+} // namespace ffor
int64_t FForCodec::maxCompressedLength(int64_t inputSize) {
size_t numValues = inputSize / sizeof(uint64_t);
diff --git a/cpp/core/utils/tac/ffor.hpp b/cpp/core/utils/tac/ffor.hpp
index d659d3bb35..0f2d3d3be5 100644
--- a/cpp/core/utils/tac/ffor.hpp
+++ b/cpp/core/utils/tac/ffor.hpp
@@ -280,6 +280,17 @@ inline void decodeRt(const uint64_t* in, uint64_t* out,
uint64_t base, size_t n,
detail::kDecodeTable[bw](in, out, base, n);
}
+namespace detail {
+// Minimum and maximum of data[0, n); requires n > 0. Defined in
FForCodec.cc, where it is
+// multiversioned for x86-64-v4 (AVX2 has no unsigned 64-bit min/max).
Callers of analyze() must
+// therefore link FForCodec.cc (part of libgluten). Default visibility keeps
the symbol exported
+// from libgluten under -fvisibility=hidden when target_clones is compiled out
(plain function).
+#if defined(__GNUC__) || defined(__clang__)
+__attribute__((visibility("default")))
+#endif
+void minMaxScan(const uint64_t* data, size_t n, uint64_t& mn, uint64_t& mx);
+} // namespace detail
+
// Compute base (min) and bitwidth for a vector of values.
inline void analyze(const uint64_t* data, size_t n, uint64_t& base, unsigned&
bw) {
if (n == 0) {
@@ -287,16 +298,9 @@ inline void analyze(const uint64_t* data, size_t n,
uint64_t& base, unsigned& bw
bw = 0;
return;
}
- uint64_t mn = data[0];
- uint64_t mx = data[0];
- for (size_t i = 1; i < n; ++i) {
- if (data[i] < mn) {
- mn = data[i];
- }
- if (data[i] > mx) {
- mx = data[i];
- }
- }
+ uint64_t mn = 0;
+ uint64_t mx = 0;
+ detail::minMaxScan(data, n, mn, mx);
base = mn;
uint64_t range = mx - mn;
bw = 0;
---------------------------------------------------------------------
To unsubscribe, e-mail: [email protected]
For additional commands, e-mail: [email protected]