This is an automated email from the ASF dual-hosted git repository.
yiguolei 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 a01d824256 [Improvement](bloom filter) inline function call (#18396)
a01d824256 is described below
commit a01d824256bd078bb9dbede022d0884f7d884a99
Author: Gabriel <gabrielleeb...@gmail.com>
AuthorDate: Thu Apr 6 10:21:48 2023 +0800
[Improvement](bloom filter) inline function call (#18396)
---
be/src/exprs/block_bloom_filter.hpp | 55 +++++++++++++++++++++++------
be/src/exprs/block_bloom_filter_avx_impl.cc | 26 --------------
be/src/exprs/block_bloom_filter_impl.cc | 12 -------
3 files changed, 45 insertions(+), 48 deletions(-)
diff --git a/be/src/exprs/block_bloom_filter.hpp
b/be/src/exprs/block_bloom_filter.hpp
index 2a9be09981..0d196cbbe7 100644
--- a/be/src/exprs/block_bloom_filter.hpp
+++ b/be/src/exprs/block_bloom_filter.hpp
@@ -20,6 +20,11 @@
#pragma once
+#ifdef __AVX2__
+#include <immintrin.h>
+
+#include "gutil/macros.h"
+#endif
#include "common/status.h"
#include "fmt/format.h"
#include "util/hash_util.hpp"
@@ -39,6 +44,11 @@ namespace doris {
// BlockBloomFilter will not store null values, and will always return a false
if the input is null.
+// Some constants used in hashing. #defined for efficiency reasons.
+#define BLOOM_HASH_CONSTANTS
\
+ 0x47b6137bU, 0x44974d91U, 0x8824ad5bU, 0xa2b7289dU, 0x705495c7U,
0x2df1424bU, 0x9efc4947U, \
+ 0x5c6bfb31U
+
class BlockBloomFilter {
public:
explicit BlockBloomFilter();
@@ -68,9 +78,43 @@ public:
}
}
+#ifdef __AVX2__
+
+ static inline ATTRIBUTE_ALWAYS_INLINE __attribute__((__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.
- bool find(uint32_t hash) const noexcept;
+ ALWAYS_INLINE bool find(uint32_t hash) const noexcept {
+ if (_always_false) {
+ return false;
+ }
+ const uint32_t bucket_idx = rehash32to32(hash) & _directory_mask;
+#ifdef __AVX2__
+ const __m256i mask = make_mark(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
+ // our case, the result is zero everywhere iff there is a one in
'bucket' wherever
+ // 'mask' is one. testc returns 1 if the result is 0 everywhere and
returns 0 otherwise.
+ const bool result = _mm256_testc_si256(bucket, mask);
+ _mm256_zeroupper();
+ return result;
+#else
+ return bucket_find(bucket_idx, hash);
+#endif
+ }
// Same as above with convenience of hashing the key.
bool find(const Slice& key) const noexcept {
if (key.data) {
@@ -172,10 +216,6 @@ private:
void bucket_insert_avx2(uint32_t bucket_idx, uint32_t hash) noexcept
__attribute__((__target__("avx2")));
- // A faster SIMD version of BucketFind().
- bool bucket_find_avx2(uint32_t bucket_idx, uint32_t hash) const noexcept
- __attribute__((__target__("avx2")));
-
// Computes out[i] |= in[i] for the arrays 'in' and 'out' of length 'n'
using AVX2
// instructions. 'n' must be a multiple of 32.
static void or_equal_array_avx2(size_t n, const uint8_t* __restrict__ in,
@@ -185,11 +225,6 @@ private:
// Size of the internal directory structure in bytes.
size_t directory_size() const { return 1ULL << log_space_bytes(); }
- // Some constants used in hashing. #defined for efficiency reasons.
-#define BLOOM_HASH_CONSTANTS
\
- 0x47b6137bU, 0x44974d91U, 0x8824ad5bU, 0xa2b7289dU, 0x705495c7U,
0x2df1424bU, 0x9efc4947U, \
- 0x5c6bfb31U
-
// kRehash is used as 8 odd 32-bit unsigned ints. See Dietzfelbinger et
al.'s "A
// reliable randomized algorithm for the closest-pair problem".
static constexpr uint32_t kRehash[8] __attribute__((aligned(32))) =
{BLOOM_HASH_CONSTANTS};
diff --git a/be/src/exprs/block_bloom_filter_avx_impl.cc
b/be/src/exprs/block_bloom_filter_avx_impl.cc
index b6512f9848..db8b9156f0 100644
--- a/be/src/exprs/block_bloom_filter_avx_impl.cc
+++ b/be/src/exprs/block_bloom_filter_avx_impl.cc
@@ -26,19 +26,6 @@
#include "gutil/macros.h"
namespace doris {
-static inline ATTRIBUTE_ALWAYS_INLINE __attribute__((__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);
-}
void BlockBloomFilter::bucket_insert_avx2(const uint32_t bucket_idx, const
uint32_t hash) noexcept {
const __m256i mask = make_mark(hash);
@@ -49,19 +36,6 @@ void BlockBloomFilter::bucket_insert_avx2(const uint32_t
bucket_idx, const uint3
_mm256_zeroupper();
}
-bool BlockBloomFilter::bucket_find_avx2(const uint32_t bucket_idx,
- const uint32_t hash) const noexcept {
- const __m256i mask = make_mark(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
- // our case, the result is zero everywhere iff there is a one in 'bucket'
wherever
- // 'mask' is one. testc returns 1 if the result is 0 everywhere and
returns 0 otherwise.
- const bool result = _mm256_testc_si256(bucket, mask);
- _mm256_zeroupper();
- return result;
-}
-
void BlockBloomFilter::insert_avx2(const uint32_t hash) noexcept {
_always_false = false;
const uint32_t bucket_idx = rehash32to32(hash) & _directory_mask;
diff --git a/be/src/exprs/block_bloom_filter_impl.cc
b/be/src/exprs/block_bloom_filter_impl.cc
index b619b239a4..9a9faf3ebf 100644
--- a/be/src/exprs/block_bloom_filter_impl.cc
+++ b/be/src/exprs/block_bloom_filter_impl.cc
@@ -170,18 +170,6 @@ void BlockBloomFilter::insert(const uint32_t hash)
noexcept {
#endif
}
-bool BlockBloomFilter::find(const uint32_t hash) const noexcept {
- if (_always_false) {
- return false;
- }
- const uint32_t bucket_idx = rehash32to32(hash) & _directory_mask;
-#ifdef __AVX2__
- return bucket_find_avx2(bucket_idx, hash);
-#else
- return bucket_find(bucket_idx, hash);
-#endif
-}
-
void BlockBloomFilter::or_equal_array_internal(size_t n, const uint8_t*
__restrict__ in,
uint8_t* __restrict__ out) {
#ifdef __AVX2__
---------------------------------------------------------------------
To unsubscribe, e-mail: commits-unsubscr...@doris.apache.org
For additional commands, e-mail: commits-h...@doris.apache.org
