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]

Reply via email to