You are viewing a plain text version of this content. The canonical link for it is here.
Posted to commits@doris.apache.org by zc...@apache.org on 2025/10/23 07:20:40 UTC
(doris) branch master updated: [opt](arm) Improve BlockBloomFilter performance with NEON intrinsics (#57183)
This is an automated email from the ASF dual-hosted git repository.
zclll 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 08a5143b8c1 [opt](arm) Improve BlockBloomFilter performance with NEON intrinsics (#57183)
08a5143b8c1 is described below
commit 08a5143b8c1c61f586d6fa030b68598f5b194551
Author: Zhiguo Wu <zh...@linaro.org>
AuthorDate: Thu Oct 23 15:20:33 2025 +0800
[opt](arm) Improve BlockBloomFilter performance with NEON intrinsics (#57183)
Summary: NEON optimization shows significant improvements in BucketInsert operations (11.5-15.0%) and consistent gains in BucketFind operations (2.5-4.2%).
---
be/benchmark/benchmark_bit_pack.hpp | 8 +-
be/benchmark/benchmark_block_bloom_filter.hpp | 97 +++++++++++++++++++++++
be/benchmark/benchmark_main.cpp | 1 +
be/src/exprs/block_bloom_filter.hpp | 109 +++++++++++++-------------
be/src/exprs/block_bloom_filter_avx_impl.cc | 8 +-
be/src/exprs/block_bloom_filter_impl.cc | 58 ++++++--------
6 files changed, 182 insertions(+), 99 deletions(-)
diff --git a/be/benchmark/benchmark_bit_pack.hpp b/be/benchmark/benchmark_bit_pack.hpp
index a4f269dd471..c0e383c6b1c 100644
--- a/be/benchmark/benchmark_bit_pack.hpp
+++ b/be/benchmark/benchmark_bit_pack.hpp
@@ -50,7 +50,7 @@ void bit_pack(const T* input, uint8_t in_num, int bit_width, uint8_t* output) {
}
static void BM_BitPack(benchmark::State& state) {
- int w = state.range(0);
+ int w = (int)state.range(0);
int n = 255;
std::default_random_engine e;
@@ -67,7 +67,7 @@ static void BM_BitPack(benchmark::State& state) {
for (auto _ : state) {
benchmark::DoNotOptimize(test_data.data());
benchmark::DoNotOptimize(output.data());
- bit_pack(test_data.data(), n, w, output.data());
+ bit_pack(test_data.data(), (uint8_t)n, w, output.data());
benchmark::ClobberMemory();
}
@@ -75,7 +75,7 @@ static void BM_BitPack(benchmark::State& state) {
}
static void BM_BitPackOptimized(benchmark::State& state) {
- int w = state.range(0);
+ int w = (int)state.range(0);
int n = 255;
std::default_random_engine e;
@@ -94,7 +94,7 @@ static void BM_BitPackOptimized(benchmark::State& state) {
for (auto _ : state) {
benchmark::DoNotOptimize(test_data.data());
benchmark::DoNotOptimize(output.data());
- forEncoder.bit_pack(test_data.data(), n, w, output.data());
+ forEncoder.bit_pack(test_data.data(), (uint8_t)n, w, output.data());
benchmark::ClobberMemory();
}
diff --git a/be/benchmark/benchmark_block_bloom_filter.hpp b/be/benchmark/benchmark_block_bloom_filter.hpp
new file mode 100644
index 00000000000..cc75ed3b44d
--- /dev/null
+++ b/be/benchmark/benchmark_block_bloom_filter.hpp
@@ -0,0 +1,97 @@
+// 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 <benchmark/benchmark.h>
+
+#include "common/status.h"
+#include "exprs/block_bloom_filter.hpp"
+
+namespace doris {
+ static std::unique_ptr<BlockBloomFilter> create_bloom_filter(int batch, int log_space_bytes = 20) {
+ auto bloom_filter = std::make_unique<BlockBloomFilter>();
+ [[maybe_unused]] Status status = bloom_filter->init(log_space_bytes, 0);
+
+ for (int i = 0; i < batch; i++) {
+ bloom_filter->insert(i);
+ }
+
+ return bloom_filter;
+ }
+} // namespace doris
+
+static void BM_BBF_BucketInsert(benchmark::State& state) {
+ const int batch = static_cast<int>(state.range(0));
+ auto bf = doris::create_bloom_filter(batch);
+
+ for (auto _ : state) {
+ for (int i = 0; i < batch; i++) {
+ bf->insert(i);
+ }
+ }
+
+ state.SetItemsProcessed(state.iterations() * static_cast<int64_t>(batch));
+}
+
+static void BM_BBF_BucketFind_Hit(benchmark::State& state) {
+ const int batch = static_cast<int>(state.range(0));
+ auto bf = doris::create_bloom_filter(batch);
+
+ for (auto _ : state) {
+ bool acc = false;
+ for (int i = 0; i < batch; i++) {
+ acc ^= bf->find(i);
+ }
+ benchmark::DoNotOptimize(acc);
+ }
+ state.SetItemsProcessed(state.iterations() * static_cast<int64_t>(batch));
+}
+
+static void BM_BBF_BucketFind_Miss(benchmark::State& state) {
+ const int batch = static_cast<int>(state.range(0));
+ auto bf = doris::create_bloom_filter(batch);
+
+ for (auto _ : state) {
+ bool acc = false;
+ for (int i = 0; i < batch; i++) {
+ acc ^= bf->find(i + batch);
+ }
+ benchmark::DoNotOptimize(acc);
+ }
+ state.SetItemsProcessed(state.iterations() * static_cast<int64_t>(batch));
+}
+
+BENCHMARK(BM_BBF_BucketInsert)
+ ->Unit(benchmark::kNanosecond)
+ ->Arg(1 << 12)
+ ->Arg(1 << 15)
+ ->Arg(1 << 18)
+ ->Repetitions(5)
+ ->DisplayAggregatesOnly();
+BENCHMARK(BM_BBF_BucketFind_Hit)
+ ->Unit(benchmark::kNanosecond)
+ ->Arg(1 << 12)
+ ->Arg(1 << 15)
+ ->Arg(1 << 18)
+ ->Repetitions(5)
+ ->DisplayAggregatesOnly();
+BENCHMARK(BM_BBF_BucketFind_Miss)
+ ->Unit(benchmark::kNanosecond)
+ ->Arg(1 << 12)
+ ->Arg(1 << 15)
+ ->Arg(1 << 18)
+ ->Repetitions(5)
+ ->DisplayAggregatesOnly();
diff --git a/be/benchmark/benchmark_main.cpp b/be/benchmark/benchmark_main.cpp
index 6e7213a89ec..b124222ba62 100644
--- a/be/benchmark/benchmark_main.cpp
+++ b/be/benchmark/benchmark_main.cpp
@@ -18,6 +18,7 @@
#include <benchmark/benchmark.h>
#include "benchmark_bit_pack.hpp"
+#include "benchmark_block_bloom_filter.hpp"
#include "benchmark_fastunion.hpp"
#include "benchmark_hll_merge.hpp"
#include "benchmark_string.hpp"
diff --git a/be/src/exprs/block_bloom_filter.hpp b/be/src/exprs/block_bloom_filter.hpp
index 8c7e6a2d8c2..1d00da3b648 100644
--- a/be/src/exprs/block_bloom_filter.hpp
+++ b/be/src/exprs/block_bloom_filter.hpp
@@ -23,6 +23,8 @@
#include "vec/common/string_ref.h"
#ifdef __AVX2__
#include <immintrin.h>
+#elif defined(__ARM_NEON)
+#include <arm_neon.h>
#endif
#include "common/status.h"
@@ -78,22 +80,6 @@ public:
}
}
-#ifdef __AVX2__
-
- static __attribute__((always_inline, __target__("avx2"))) __m256i make_mark(
- const uint32_t hash) {
- const __m256i ones = _mm256_set1_epi32(1);
- const __m256i rehash = _mm256_setr_epi32(BLOOM_HASH_CONSTANTS);
- // Load hash into a YMM register, repeated eight times
- __m256i hash_data = _mm256_set1_epi32(hash);
- // Multiply-shift hashing ala Dietzfelbinger et al.: multiply 'hash' by eight different
- // odd constants, then keep the 5 most significant bits from each product.
- hash_data = _mm256_mullo_epi32(rehash, hash_data);
- hash_data = _mm256_srli_epi32(hash_data, 27);
- // Use these 5 bits to shift a single bit to a location in each 32-bit lane
- return _mm256_sllv_epi32(ones, hash_data);
- }
-#endif
// Finds an element in the BloomFilter, returning true if it is found and false (with
// high probability) if it is not.
ALWAYS_INLINE bool find(uint32_t hash) const noexcept {
@@ -102,7 +88,7 @@ public:
}
const uint32_t bucket_idx = rehash32to32(hash) & _directory_mask;
#ifdef __AVX2__
- const __m256i mask = make_mark(hash);
+ const __m256i mask = make_mask(hash);
const __m256i bucket = reinterpret_cast<__m256i*>(_directory)[bucket_idx];
// We should return true if 'bucket' has a one wherever 'mask' does. _mm256_testc_si256
// takes the negation of its first argument and ands that with its second argument. In
@@ -115,6 +101,7 @@ public:
return bucket_find(bucket_idx, hash);
#endif
}
+
// Same as above with convenience of hashing the key.
bool find(const StringRef& key) const noexcept {
if (key.data) {
@@ -123,39 +110,6 @@ public:
return false;
}
-#ifdef __ARM_NEON
- void make_find_mask(uint32_t key, uint32x4_t* masks) const noexcept {
- uint32x4_t hash_data_1 = vdupq_n_u32(key);
- uint32x4_t hash_data_2 = vdupq_n_u32(key);
-
- uint32x4_t rehash_1 = vld1q_u32(&kRehash[0]);
- uint32x4_t rehash_2 = vld1q_u32(&kRehash[4]);
-
- // masks[i] = key * kRehash[i];
- hash_data_1 = vmulq_u32(rehash_1, hash_data_1);
- hash_data_2 = vmulq_u32(rehash_2, hash_data_2);
- // masks[i] = masks[i] >> shift_num;
- hash_data_1 = vshrq_n_u32(hash_data_1, shift_num);
- hash_data_2 = vshrq_n_u32(hash_data_2, shift_num);
-
- const uint32x4_t ones = vdupq_n_u32(1);
-
- // masks[i] = 0x1 << masks[i];
- masks[0] = vshlq_u32(ones, reinterpret_cast<int32x4_t>(hash_data_1));
- masks[1] = vshlq_u32(ones, reinterpret_cast<int32x4_t>(hash_data_2));
- }
-#else
- void make_find_mask(uint32_t key, uint32_t* masks) const noexcept {
- for (int i = 0; i < kBucketWords; ++i) {
- masks[i] = key * kRehash[i];
-
- masks[i] = masks[i] >> shift_num;
-
- masks[i] = 0x1 << masks[i];
- }
- }
-#endif
-
// Computes the logical OR of this filter with 'other' and stores the result in this
// filter.
// Notes:
@@ -195,6 +149,7 @@ private:
// log2(number of bits in a BucketWord)
static constexpr int kLogBucketWordBits = 5;
static constexpr BucketWord kBucketWordMask = (1 << kLogBucketWordBits) - 1;
+
// (>> 27) is equivalent to (mod 32)
static constexpr auto shift_num = ((1 << kLogBucketWordBits) - kLogBucketWordBits);
// log2(number of bytes in a bucket)
@@ -223,9 +178,6 @@ private:
// Helper function for public Init() variants.
Status init_internal(int log_space_bytes, uint32_t hash_seed);
- // Same as Insert(), but skips the CPU check and assumes that AVX2 is not available.
- void insert_no_avx2(uint32_t hash) noexcept;
-
// Does the actual work of Insert(). bucket_idx is the index of the bucket to insert
// into and 'hash' is the value passed to Insert().
void bucket_insert(uint32_t bucket_idx, uint32_t hash) noexcept;
@@ -242,9 +194,6 @@ private:
uint8_t* __restrict__ out);
#ifdef __AVX2__
- // Same as Insert(), but skips the CPU check and assumes that AVX2 is available.
- void insert_avx2(uint32_t hash) noexcept __attribute__((__target__("avx2")));
-
// A faster SIMD version of BucketInsert().
void bucket_insert_avx2(uint32_t bucket_idx, uint32_t hash) noexcept
__attribute__((__target__("avx2")));
@@ -275,6 +224,54 @@ private:
// Rehash32to32(hash2) is minimal.
return (static_cast<uint64_t>(hash) * m + a) >> 32U;
}
+
+#ifdef __AVX2__
+ static inline ALWAYS_INLINE __m256i make_mask(const uint32_t hash) noexcept {
+ const __m256i ones = _mm256_set1_epi32(1);
+ const __m256i rehash = _mm256_setr_epi32(BLOOM_HASH_CONSTANTS);
+ // Load hash into a YMM register, repeated eight times
+ __m256i hash_data = _mm256_set1_epi32(hash);
+ // Multiply-shift hashing ala Dietzfelbinger et al.: multiply 'hash' by eight different
+ // odd constants, then keep the 5 most significant bits from each product.
+ hash_data = _mm256_mullo_epi32(rehash, hash_data);
+ hash_data = _mm256_srli_epi32(hash_data, shift_num);
+ // Use these 5 bits to shift a single bit to a location in each 32-bit lane
+ return _mm256_sllv_epi32(ones, hash_data);
+ }
+#endif
+
+#ifdef __ARM_NEON
+ static inline ALWAYS_INLINE uint32x4x2_t make_mask(const uint32_t hash) noexcept {
+ const uint32x4_t ones = vdupq_n_u32(1);
+ const uint32x4x2_t rehash = vld1q_u32_x2(&kRehash[0]);
+ // Load hash, repeated 4 times.
+ uint32x4_t hash_data = vdupq_n_u32(hash);
+
+ // Multiply-shift hashing ala Dietzfelbinger et al.: multiply 'hash' by eight different
+ // odd constants, then keep the 5 most significant bits from each product.
+ int32x4x2_t t;
+ t.val[0] =
+ vreinterpretq_s32_u32(vshrq_n_u32(vmulq_u32(rehash.val[0], hash_data), shift_num));
+ t.val[1] =
+ vreinterpretq_s32_u32(vshrq_n_u32(vmulq_u32(rehash.val[1], hash_data), shift_num));
+
+ // Use these 5 bits to shift a single bit to a location in each 32-bit lane
+ uint32x4x2_t res;
+ res.val[0] = vshlq_u32(ones, t.val[0]);
+ res.val[1] = vshlq_u32(ones, t.val[1]);
+ return res;
+ }
+#else
+ static inline ALWAYS_INLINE void make_mask(uint32_t hash, uint32_t* masks) noexcept {
+ for (int i = 0; i < kBucketWords; ++i) {
+ masks[i] = hash * kRehash[i];
+
+ masks[i] = masks[i] >> shift_num;
+
+ masks[i] = 0x1 << masks[i];
+ }
+ }
+#endif
};
} // namespace doris
diff --git a/be/src/exprs/block_bloom_filter_avx_impl.cc b/be/src/exprs/block_bloom_filter_avx_impl.cc
index 6781a233323..fe2a347ef99 100644
--- a/be/src/exprs/block_bloom_filter_avx_impl.cc
+++ b/be/src/exprs/block_bloom_filter_avx_impl.cc
@@ -32,7 +32,7 @@
namespace doris {
void BlockBloomFilter::bucket_insert_avx2(const uint32_t bucket_idx, const uint32_t hash) noexcept {
- const __m256i mask = make_mark(hash);
+ const __m256i mask = make_mask(hash);
__m256i* const bucket = &(reinterpret_cast<__m256i*>(_directory)[bucket_idx]);
_mm256_store_si256(bucket, _mm256_or_si256(*bucket, mask));
// For SSE compatibility, unset the high bits of each YMM register so SSE instructions
@@ -40,12 +40,6 @@ void BlockBloomFilter::bucket_insert_avx2(const uint32_t bucket_idx, const uint3
_mm256_zeroupper();
}
-void BlockBloomFilter::insert_avx2(const uint32_t hash) noexcept {
- _always_false = false;
- const uint32_t bucket_idx = rehash32to32(hash) & _directory_mask;
- bucket_insert_avx2(bucket_idx, hash);
-}
-
void BlockBloomFilter::or_equal_array_avx2(size_t n, const uint8_t* __restrict__ in,
uint8_t* __restrict__ out) {
static constexpr size_t kAVXRegisterBytes = sizeof(__m256d);
diff --git a/be/src/exprs/block_bloom_filter_impl.cc b/be/src/exprs/block_bloom_filter_impl.cc
index c3dcd166099..c9dd1918a08 100644
--- a/be/src/exprs/block_bloom_filter_impl.cc
+++ b/be/src/exprs/block_bloom_filter_impl.cc
@@ -21,14 +21,14 @@
#include <butil/iobuf.h>
#include <fmt/format.h>
#include <glog/logging.h>
-#include <stdint.h>
#include <algorithm>
#include <climits> // IWYU pragma: keep
#include <cmath> // IWYU pragma: keep
+#include <cstddef>
+#include <cstdint>
#include <cstdlib>
#include <cstring>
-#include <string>
#include "common/status.h"
#include "exprs/block_bloom_filter.hpp"
@@ -119,6 +119,28 @@ void BlockBloomFilter::close() {
}
}
+#ifdef __ARM_NEON
+void BlockBloomFilter::bucket_insert(const uint32_t bucket_idx, const uint32_t hash) noexcept {
+ const uint32x4x2_t mask = make_mask(hash);
+ uint32x4x2_t data = vld1q_u32_x2(&_directory[bucket_idx][0]);
+ data.val[0] = vorrq_u32(data.val[0], mask.val[0]);
+ data.val[1] = vorrq_u32(data.val[1], mask.val[1]);
+ vst1q_u32_x2(&_directory[bucket_idx][0], data);
+}
+
+bool BlockBloomFilter::bucket_find(const uint32_t bucket_idx, const uint32_t hash) const noexcept {
+ const uint32x4x2_t mask = make_mask(hash);
+ uint32x4x2_t data = vld1q_u32_x2(&_directory[bucket_idx][0]);
+ // The condition for returning true is that all the bits in _directory[bucket_idx][i] specified by masks[i] are 1.
+ // This can be equivalently expressed as all the bits in not( _directory[bucket_idx][i]) specified by masks[i] are 0.
+ // vbicq_u32(vec1, vec2) : Result of (vec1 AND NOT vec2)
+ // If true is returned, out_1 and out_2 should be all zeros.
+ uint32x4_t miss0 = vbicq_u32(mask.val[0], data.val[0]);
+ uint32x4_t miss1 = vbicq_u32(mask.val[1], data.val[1]);
+ uint32x4_t miss = vorrq_u32(miss0, miss1);
+ return vmaxvq_u32(miss) == 0U;
+}
+#else
void BlockBloomFilter::bucket_insert(const uint32_t bucket_idx, const uint32_t hash) noexcept {
// new_bucket will be all zeros except for eight 1-bits, one in each 32-bit word. It is
// 16-byte aligned so it can be read as a __m128i using aligned SIMD loads in the second
@@ -138,44 +160,16 @@ void BlockBloomFilter::bucket_insert(const uint32_t bucket_idx, const uint32_t h
}
bool BlockBloomFilter::bucket_find(const uint32_t bucket_idx, const uint32_t hash) const noexcept {
-#if defined(__ARM_NEON)
- uint32x4_t masks[2];
-
- uint32x4_t directory_1 = vld1q_u32(&_directory[bucket_idx][0]);
- uint32x4_t directory_2 = vld1q_u32(&_directory[bucket_idx][4]);
-
- make_find_mask(hash, masks);
- // The condition for returning true is that all the bits in _directory[bucket_idx][i] specified by masks[i] are 1.
- // This can be equivalently expressed as all the bits in not( _directory[bucket_idx][i]) specified by masks[i] are 0.
- // vbicq_u32(vec1, vec2) : Result of (vec1 AND NOT vec2)
- // If true is returned, out_1 and out_2 should be all zeros.
- uint32x4_t out_1 = vbicq_u32(masks[0], directory_1);
- uint32x4_t out_2 = vbicq_u32(masks[1], directory_2);
-
- out_1 = vorrq_u32(out_1, out_2);
-
- uint32x2_t low = vget_low_u32(out_1);
- uint32x2_t high = vget_high_u32(out_1);
- low = vorr_u32(low, high);
- uint32_t res = vget_lane_u32(low, 0) | vget_lane_u32(low, 1);
- return !(res);
-#else
uint32_t masks[kBucketWords];
- make_find_mask(hash, masks);
+ make_mask(hash, masks);
for (int i = 0; i < kBucketWords; ++i) {
if ((DCHECK_NOTNULL(_directory)[bucket_idx][i] & masks[i]) == 0) {
return false;
}
}
return true;
-#endif
-}
-
-void BlockBloomFilter::insert_no_avx2(const uint32_t hash) noexcept {
- _always_false = false;
- const uint32_t bucket_idx = rehash32to32(hash) & _directory_mask;
- bucket_insert(bucket_idx, hash);
}
+#endif
// To set 8 bits in an 32-byte Bloom filter, we set one bit in each 32-bit uint32_t. This
// is a "split Bloom filter", and it has approximately the same false positive probability
---------------------------------------------------------------------
To unsubscribe, e-mail: commits-unsubscribe@doris.apache.org
For additional commands, e-mail: commits-help@doris.apache.org