diff options
author | Sage Weil <sage@inktank.com> | 2013-10-06 10:18:30 -0700 |
---|---|---|
committer | Sage Weil <sage@inktank.com> | 2013-10-06 10:18:30 -0700 |
commit | 055dc4c1f22bf7751059d589c33ba5c32b009184 (patch) | |
tree | 61d5f1985f123bb5632f7fc31a21f1a5d1e7f68f | |
parent | aaabc657396255101cb3311fb80f84e26fab3705 (diff) | |
download | ceph-055dc4c1f22bf7751059d589c33ba5c32b009184.tar.gz |
common/bloom_filter: fix estimated element count for compressed filters
We need to compensate for the fact that there are fewer bits than there
used to be.
This is a crappy adjustment; it is non-linear. It's clone enough for now,
though.
Signed-off-by: Sage Weil <sage@inktank.com>
-rw-r--r-- | src/common/bloom_filter.hpp | 10 |
1 files changed, 9 insertions, 1 deletions
diff --git a/src/common/bloom_filter.hpp b/src/common/bloom_filter.hpp index 4b711526676..8587caa2d8d 100644 --- a/src/common/bloom_filter.hpp +++ b/src/common/bloom_filter.hpp @@ -317,7 +317,7 @@ public: return (double)set / (double)(table_size_ << 3); } - inline double approx_unique_element_count() const { + virtual inline double approx_unique_element_count() const { // this is not a very good estimate; a better solution should have // some asymptotic behavior as density() approaches 1.0. return (double)target_element_count_ * 2.0 * density(); @@ -637,6 +637,14 @@ public: return true; } + virtual inline double approx_unique_element_count() const { + // this is not a very good estimate; a better solution should have + // some asymptotic behavior as density() approaches 1.0. + // + // the compress() correction is also bad; it tends to under-estimate. + return (double)target_element_count_ * 2.0 * density() * (double)size_list.back() / (double)size_list.front(); + } + private: inline virtual void compute_indices(const bloom_type& hash, std::size_t& bit_index, std::size_t& bit) const |