You are viewing a plain text version of this content. The canonical link for it is here.
Posted to commits@quickstep.apache.org by na...@apache.org on 2016/07/14 14:17:45 UTC
incubator-quickstep git commit: Improve rounding of bloom filter size
Repository: incubator-quickstep
Updated Branches:
refs/heads/expt_bloom_filter_hash_fn 3c841706b -> 6369ee91c
Improve rounding of bloom filter size
Project: http://git-wip-us.apache.org/repos/asf/incubator-quickstep/repo
Commit: http://git-wip-us.apache.org/repos/asf/incubator-quickstep/commit/6369ee91
Tree: http://git-wip-us.apache.org/repos/asf/incubator-quickstep/tree/6369ee91
Diff: http://git-wip-us.apache.org/repos/asf/incubator-quickstep/diff/6369ee91
Branch: refs/heads/expt_bloom_filter_hash_fn
Commit: 6369ee91cc383c9e5f409958a45e3ba95f9c0352
Parents: 3c84170
Author: Navneet Potti <na...@gmail.com>
Authored: Thu Jul 14 08:58:14 2016 -0500
Committer: Navneet Potti <na...@gmail.com>
Committed: Thu Jul 14 08:58:14 2016 -0500
----------------------------------------------------------------------
utility/BloomFilter.hpp | 20 ++++++++++++++------
1 file changed, 14 insertions(+), 6 deletions(-)
----------------------------------------------------------------------
http://git-wip-us.apache.org/repos/asf/incubator-quickstep/blob/6369ee91/utility/BloomFilter.hpp
----------------------------------------------------------------------
diff --git a/utility/BloomFilter.hpp b/utility/BloomFilter.hpp
index 49d00e7..17a6da8 100644
--- a/utility/BloomFilter.hpp
+++ b/utility/BloomFilter.hpp
@@ -49,8 +49,6 @@ class BloomFilterOriginal;
class BloomFilterBlocked;
typedef BloomFilterBlocked BloomFilter;
-#define PREV_CACHE_LINE_SIZE_MULTIPLE(n) ((n)/kCacheLineBytes) * kCacheLineBytes
-
/**
* @brief A "blocked" version of Bloom Filter based on this paper:
* Putze, Felix, Peter Sanders, and Johannes Singler.
@@ -81,8 +79,18 @@ class BloomFilterBlocked {
} byte_pos;
};
- static std::uint64_t getNearestAllowedSize(const std::uint64_t approx_size) {
- return (approx_size / kCacheLineBytes) * kCacheLineBytes;
+ // This Bloom filter implementation requires the bit array to be a
+ // multiple of the cache-line size. So we either have to round up to a
+ // multiple (default behavior) or round down to a multiple.
+ // Rounding up is usually preferable but rounding down is necessary when
+ // we are given a bit array that we don't control the size of, in the
+ // constructor.
+ static std::uint64_t getNearestAllowedSize(
+ const std::uint64_t approx_size,
+ bool round_down = false) {
+ if (round_down)
+ return (approx_size / kCacheLineBytes) * kCacheLineBytes;
+ return ((approx_size + kCacheLineBytes - 1)/ kCacheLineBytes) * kCacheLineBytes;
}
@@ -97,7 +105,7 @@ class BloomFilterBlocked {
BloomFilterBlocked(const std::uint8_t hash_fn_count,
const std::uint64_t bit_array_size_in_bytes)
: hash_fn_count_(hash_fn_count),
- array_size_in_bytes_(PREV_CACHE_LINE_SIZE_MULTIPLE(bit_array_size_in_bytes)),
+ array_size_in_bytes_(getNearestAllowedSize(bit_array_size_in_bytes)),
is_bit_array_owner_(true),
bit_array_(new std::uint8_t[array_size_in_bytes_]) {
reset();
@@ -119,7 +127,7 @@ class BloomFilterBlocked {
std::uint8_t *bit_array,
const bool is_initialized)
: hash_fn_count_(hash_fn_count),
- array_size_in_bytes_(PREV_CACHE_LINE_SIZE_MULTIPLE(bit_array_size_in_bytes)),
+ array_size_in_bytes_(getNearestAllowedSize(bit_array_size_in_bytes, true)),
is_bit_array_owner_(false),
bit_array_(bit_array) { // Owned by the calling method.
if (!is_initialized) {