From 26e703475231b27f3b9a1f4b644e371406621715 Mon Sep 17 00:00:00 2001 From: Kefu Chai Date: Tue, 27 Jul 2021 14:58:01 +0800 Subject: [PATCH] common/bloom_filter: use popcount() to implement density() instead of counting the bits using a loop, it'd be more efficient to do this using the SIMD instruction. Signed-off-by: Kefu Chai --- src/common/bloom_filter.hpp | 20 +++++++++----------- 1 file changed, 9 insertions(+), 11 deletions(-) diff --git a/src/common/bloom_filter.hpp b/src/common/bloom_filter.hpp index ff6f707566f92..3e75e4e60a7ba 100644 --- a/src/common/bloom_filter.hpp +++ b/src/common/bloom_filter.hpp @@ -23,9 +23,11 @@ #define COMMON_BLOOM_FILTER_HPP #include +#include -#include "include/mempool.h" #include "include/encoding.h" +#include "include/intarith.h" +#include "include/mempool.h" static const unsigned char bit_mask[CHAR_BIT] = { 0x01, //00000001 @@ -277,16 +279,12 @@ public: */ inline double density() const { - size_t set = 0; - auto p = bit_table_.begin(); - size_t left = table_size_; - while (left-- > 0) { - uint8_t c = *p; - for (; c; ++set) - c &= c - 1; - ++p; - } - return (double)set / (double)(table_size_ << 3); + unsigned set = std::transform_reduce( + bit_table_.begin(), + bit_table_.begin() + table_size_, + 0, std::plus<>(), + popcount); + return (double)set / (table_size_ * sizeof(cell_type) * CHAR_BIT); } virtual inline double approx_unique_element_count() const { -- 2.39.5