This is an automated email from the ASF dual-hosted git repository.
HappenLee pushed a commit to branch master
in repository https://gitbox.apache.org/repos/asf/doris.git
The following commit(s) were added to refs/heads/master by this push:
new 9245684556b [improvement](be) Accelerate fixed-size CRC32 hashing on
ARM64 (#70513)
9245684556b is described below
commit 9245684556b735408e6f991f8e1522970fe3380c
Author: HappenLee <[email protected]>
AuthorDate: Sat Nov 14 17:07:11 2026 +0800
[improvement](be) Accelerate fixed-size CRC32 hashing on ARM64 (#70513)
### What problem does this PR solve?
Issue Number: None
Problem Summary:
Fixed-size numeric bucket hashing uses software lookup tables on ARM64
even when the build enables the CRC extension. Use IEEE CRC32 intrinsics
for 1-, 2-, 4- and 8-byte values in `HashUtil::zlib_crc32_fixed`.
Preserve zlib-compatible seed handling, byte order and incremental hash
results through the existing alignment-safe little-endian loads. Keep
the table implementation for targets without the ARM64 CRC extension and
the zlib fallback for other input sizes. Add byte-pattern and
mixed-width chaining tests against zlib.
### Release note
None
### Check List (For Author)
- Test
- [ ] Regression test
- [x] Unit Test
- All 14 `ZlibCRC32Fixed` tests passed in a separately linked x86_64
ASAN binary compiled from the current test translation unit.
- [x] Manual test (add detailed scripts or steps below)
- Cross-compiled an extracted-template harness for ARM64 with and
without `+crc`; verified `crc32b`, `crc32h`, `crc32w`, `crc32x` and the
software fallback.
- clang-format 16, build hygiene, diff checks and clang-tidy on modified
lines passed.
- The standard `./run-be-ut.sh -j 48 --run --filter='ZlibCRC32Fixed.*'`
build was blocked by existing `ColumnVector`/`PODArray` constructor
compilation errors in the local workspace.
- Native ARM64 correctness and performance testing remain pending. No
measured speedup is claimed.
- Behavior changed:
- [x] No.
- [ ] Yes.
- Does this need documentation?
- [x] No.
- [ ] Yes.
### Check List (For Reviewer who merge this PR)
- [ ] Confirm the release note
- [ ] Confirm test cases
- [ ] Confirm document
- [ ] Add branch pick label
---
be/src/util/hash_util.hpp | 82 ++++++++++++++++++++++++++------------------
be/test/util/crc32c_test.cpp | 48 ++++++++++++++++++++++++++
2 files changed, 97 insertions(+), 33 deletions(-)
diff --git a/be/src/util/hash_util.hpp b/be/src/util/hash_util.hpp
index ab5b72bffda..970fdbe227c 100644
--- a/be/src/util/hash_util.hpp
+++ b/be/src/util/hash_util.hpp
@@ -28,6 +28,10 @@
#include <bit>
#include <functional>
+#if defined(__aarch64__) && defined(__ARM_FEATURE_CRC32)
+#include <arm_acle.h>
+#endif
+
#include "common/compiler_util.h" // IWYU pragma: keep
#include "exec/common/endian.h"
#include "util/cpu_info.h"
@@ -73,46 +77,58 @@ public:
}
// Inline CRC32 (zlib-compatible, standard CRC32 polynomial) for
fixed-size types.
- // Uses Slicing-by-4 technique for 4/8-byte types: processes 4 bytes at a
time using
- // 4 precomputed lookup tables, reducing serial table lookups from 4 to 1
per 4-byte chunk.
+ // Uses ARM64 CRC instructions when available, otherwise table lookups with
+ // Slicing-by-4 for 4/8-byte types.
// Polynomial: 0xEDB88320 (reflected form of 0x04C11DB7).
// Endian note: CRC32 reflected algorithm processes bytes in address order
(byte[0] first).
- // Slicing-by-4 requires byte[0] at LSB of the loaded uint32_t, which is
little-endian layout.
- // LittleEndian::Load32 provides this on ALL platforms: noop on LE, bswap
on BE.
+ // Both paths require byte[0] at the LSB of loaded integers.
+ // LittleEndian loads preserve this order and allow unaligned input.
template <typename T>
static uint32_t zlib_crc32_fixed(const T& value, uint32_t hash) {
- const auto* p = reinterpret_cast<const uint8_t*>(&value);
- // zlib convention: pre/post XOR with 0xFFFFFFFF
- uint32_t crc = hash ^ 0xFFFFFFFFU;
-
- if constexpr (sizeof(T) == 1) {
- // 1 byte: single table lookup
- crc = CRC32_TABLE.t[0][(crc ^ p[0]) & 0xFF] ^ (crc >> 8);
- } else if constexpr (sizeof(T) == 2) {
- // 2 bytes: two sequential table lookups (slicing doesn't help
below 4 bytes)
- crc = CRC32_TABLE.t[0][(crc ^ p[0]) & 0xFF] ^ (crc >> 8);
- crc = CRC32_TABLE.t[0][(crc ^ p[1]) & 0xFF] ^ (crc >> 8);
- } else if constexpr (sizeof(T) == 4) {
- // 4 bytes: one Slicing-by-4 step — 4 independent lookups in
parallel
- // LittleEndian::Load32 handles unaligned load + byte-swap on
big-endian,
- // ensuring byte[0] is always at LSB for correct CRC byte
processing order.
- uint32_t word = LittleEndian::Load32(p) ^ crc;
- crc = CRC32_TABLE.t[3][(word)&0xFF] ^ CRC32_TABLE.t[2][(word >> 8)
& 0xFF] ^
- CRC32_TABLE.t[1][(word >> 16) & 0xFF] ^
CRC32_TABLE.t[0][(word >> 24) & 0xFF];
- } else if constexpr (sizeof(T) == 8) {
- // 8 bytes: two Slicing-by-4 steps
- uint32_t word = LittleEndian::Load32(p) ^ crc;
- crc = CRC32_TABLE.t[3][(word)&0xFF] ^ CRC32_TABLE.t[2][(word >> 8)
& 0xFF] ^
- CRC32_TABLE.t[1][(word >> 16) & 0xFF] ^
CRC32_TABLE.t[0][(word >> 24) & 0xFF];
-
- word = LittleEndian::Load32(p + 4) ^ crc;
- crc = CRC32_TABLE.t[3][(word)&0xFF] ^ CRC32_TABLE.t[2][(word >> 8)
& 0xFF] ^
- CRC32_TABLE.t[1][(word >> 16) & 0xFF] ^
CRC32_TABLE.t[0][(word >> 24) & 0xFF];
+ if constexpr (sizeof(T) == 1 || sizeof(T) == 2 || sizeof(T) == 4 ||
sizeof(T) == 8) {
+ const auto* p = reinterpret_cast<const uint8_t*>(&value);
+ // zlib convention: pre/post XOR with 0xFFFFFFFF
+ uint32_t crc = hash ^ 0xFFFFFFFFU;
+#if defined(__aarch64__) && defined(__ARM_FEATURE_CRC32)
+ // Use IEEE CRC32 instructions; CRC32C would change existing
bucket hashes.
+ if constexpr (sizeof(T) == 1) {
+ crc = __crc32b(crc, p[0]);
+ } else if constexpr (sizeof(T) == 2) {
+ crc = __crc32h(crc, LittleEndian::Load16(p));
+ } else if constexpr (sizeof(T) == 4) {
+ crc = __crc32w(crc, LittleEndian::Load32(p));
+ } else {
+ crc = __crc32d(crc, LittleEndian::Load64(p));
+ }
+#else
+ if constexpr (sizeof(T) == 1) {
+ // 1 byte: single table lookup
+ crc = CRC32_TABLE.t[0][(crc ^ p[0]) & 0xFF] ^ (crc >> 8);
+ } else if constexpr (sizeof(T) == 2) {
+ // 2 bytes: two sequential table lookups
+ crc = CRC32_TABLE.t[0][(crc ^ p[0]) & 0xFF] ^ (crc >> 8);
+ crc = CRC32_TABLE.t[0][(crc ^ p[1]) & 0xFF] ^ (crc >> 8);
+ } else if constexpr (sizeof(T) == 4) {
+ // LittleEndian::Load32 preserves byte order on every platform.
+ uint32_t word = LittleEndian::Load32(p) ^ crc;
+ crc = CRC32_TABLE.t[3][word & 0xFF] ^ CRC32_TABLE.t[2][(word
>> 8) & 0xFF] ^
+ CRC32_TABLE.t[1][(word >> 16) & 0xFF] ^
CRC32_TABLE.t[0][(word >> 24) & 0xFF];
+ } else {
+ // 8 bytes: two Slicing-by-4 steps
+ uint32_t word = LittleEndian::Load32(p) ^ crc;
+ crc = CRC32_TABLE.t[3][word & 0xFF] ^ CRC32_TABLE.t[2][(word
>> 8) & 0xFF] ^
+ CRC32_TABLE.t[1][(word >> 16) & 0xFF] ^
CRC32_TABLE.t[0][(word >> 24) & 0xFF];
+
+ word = LittleEndian::Load32(p + 4) ^ crc;
+ crc = CRC32_TABLE.t[3][word & 0xFF] ^ CRC32_TABLE.t[2][(word
>> 8) & 0xFF] ^
+ CRC32_TABLE.t[1][(word >> 16) & 0xFF] ^
CRC32_TABLE.t[0][(word >> 24) & 0xFF];
+ }
+#endif
+ return crc ^ 0xFFFFFFFFU;
} else {
// Fallback to zlib for larger/unusual types
- return (uint32_t)crc32(hash, (const unsigned char*)&value,
sizeof(T));
+ return zlib_crc_hash(&value, sizeof(T), hash);
}
- return crc ^ 0xFFFFFFFFU;
}
static uint32_t zlib_crc_hash_null(uint32_t hash) {
diff --git a/be/test/util/crc32c_test.cpp b/be/test/util/crc32c_test.cpp
index e9795882b36..48aeb203aaa 100644
--- a/be/test/util/crc32c_test.cpp
+++ b/be/test/util/crc32c_test.cpp
@@ -24,6 +24,7 @@
#include <string.h>
#include <zlib.h>
+#include <array>
#include <cstdint>
#include <limits>
#include <vector>
@@ -464,6 +465,53 @@ TEST(ZlibCRC32Fixed, SequentialInt32) {
}
}
*/
+template <size_t Size>
+void check_zlib_crc32_byte_patterns() {
+ std::array<uint8_t, Size> value {};
+ for (uint32_t seed : {0U, 1U, 0xFFFFFFFFU, 0xDEADBEEFU}) {
+ for (int pattern = 0; pattern < 256; ++pattern) {
+ for (size_t i = 0; i < Size; ++i) {
+ value[i] = static_cast<uint8_t>(pattern + i * 37);
+ }
+ EXPECT_EQ(HashUtil::zlib_crc32_fixed(value, seed),
zlib_crc32_reference(value, seed))
+ << "size=" << Size << " seed=" << seed << " pattern=" <<
pattern;
+ }
+ for (size_t bit = 0; bit < Size * 8; ++bit) {
+ value.fill(0);
+ value[bit / 8] = static_cast<uint8_t>(1U << (bit % 8));
+ EXPECT_EQ(HashUtil::zlib_crc32_fixed(value, seed),
zlib_crc32_reference(value, seed))
+ << "size=" << Size << " seed=" << seed << " bit=" << bit;
+ }
+ }
+}
+
+TEST(ZlibCRC32Fixed, FixedSizeBytePatterns) {
+ check_zlib_crc32_byte_patterns<1>();
+ check_zlib_crc32_byte_patterns<2>();
+ check_zlib_crc32_byte_patterns<4>();
+ check_zlib_crc32_byte_patterns<8>();
+}
+
+TEST(ZlibCRC32Fixed, MixedWidthChain) {
+ const uint8_t a = 0x81;
+ const uint16_t b = 0x1234;
+ const uint32_t c = 0x89ABCDEF;
+ const uint64_t d = 0x0123456789ABCDEFULL;
+ std::array<uint8_t, sizeof(a) + sizeof(b) + sizeof(c) + sizeof(d)> bytes
{};
+ memcpy(bytes.data(), &a, sizeof(a));
+ memcpy(bytes.data() + sizeof(a), &b, sizeof(b));
+ memcpy(bytes.data() + sizeof(a) + sizeof(b), &c, sizeof(c));
+ memcpy(bytes.data() + sizeof(a) + sizeof(b) + sizeof(c), &d, sizeof(d));
+ for (uint32_t seed : {0U, 1U, 0xFFFFFFFFU, 0xDEADBEEFU}) {
+ uint32_t hash = HashUtil::zlib_crc32_fixed(a, seed);
+ hash = HashUtil::zlib_crc32_fixed(b, hash);
+ hash = HashUtil::zlib_crc32_fixed(c, hash);
+ hash = HashUtil::zlib_crc32_fixed(d, hash);
+ EXPECT_EQ(hash, HashUtil::zlib_crc_hash(bytes.data(), bytes.size(),
seed))
+ << "seed=" << seed;
+ }
+}
+
// ==================== Large 16-byte type fallback test ====================
TEST(ZlibCRC32Fixed, LargeTypeFallback) {
---------------------------------------------------------------------
To unsubscribe, e-mail: [email protected]
For additional commands, e-mail: [email protected]