You are viewing a plain text version of this content. The canonical link for it is here.
Posted to commits@impala.apache.org by ta...@apache.org on 2016/10/25 20:16:12 UTC
[25/33] incubator-impala git commit: Remove unused Bitmap code.
Remove unused Bitmap code.
These methods and code paths have been made obsolete by the switch to
Bloom filters.
Change-Id: I95fcaaa40243999800c2ec2ead5b3479d66a63e7
Reviewed-on: http://gerrit.cloudera.org:8080/4801
Reviewed-by: Henry Robinson <he...@cloudera.com>
Tested-by: Internal Jenkins
Project: http://git-wip-us.apache.org/repos/asf/incubator-impala/repo
Commit: http://git-wip-us.apache.org/repos/asf/incubator-impala/commit/0fbb5b7e
Tree: http://git-wip-us.apache.org/repos/asf/incubator-impala/tree/0fbb5b7e
Diff: http://git-wip-us.apache.org/repos/asf/incubator-impala/diff/0fbb5b7e
Branch: refs/heads/hadoop-next
Commit: 0fbb5b7e71e55346c8b97ec143854dba0088f124
Parents: ff6b450
Author: Jim Apple <jb...@cloudera.com>
Authored: Sat Oct 22 10:42:51 2016 -0700
Committer: Internal Jenkins <cl...@gerrit.cloudera.org>
Committed: Mon Oct 24 17:53:33 2016 +0000
----------------------------------------------------------------------
be/src/benchmarks/bitmap-benchmark.cc | 6 +--
be/src/exec/hash-table.h | 4 +-
be/src/exec/nested-loop-join-node.cc | 12 ++---
be/src/util/bitmap-test.cc | 82 +++++-------------------------
be/src/util/bitmap.cc | 8 +--
be/src/util/bitmap.h | 42 ++-------------
6 files changed, 32 insertions(+), 122 deletions(-)
----------------------------------------------------------------------
http://git-wip-us.apache.org/repos/asf/incubator-impala/blob/0fbb5b7e/be/src/benchmarks/bitmap-benchmark.cc
----------------------------------------------------------------------
diff --git a/be/src/benchmarks/bitmap-benchmark.cc b/be/src/benchmarks/bitmap-benchmark.cc
index 26c51d8..5c1c9e6 100644
--- a/be/src/benchmarks/bitmap-benchmark.cc
+++ b/be/src/benchmarks/bitmap-benchmark.cc
@@ -110,7 +110,7 @@ struct TestData {
void Benchmark(int batch_size, void* data) {
TestData* d = reinterpret_cast<TestData*>(data);
for (int i = 0; i < batch_size; ++i) {
- d->bm.Set<true>(d->data[i & (d->data.size() - 1)], true);
+ d->bm.Set(d->data[i & (d->data.size() - 1)] % d->bm.num_bits(), true);
}
}
@@ -122,7 +122,7 @@ struct TestData {
TestData(int64_t size)
: bm(size), data (1ull << 20) {
for (size_t i = 0; i < size/2; ++i) {
- bm.Set<true>(MakeNonNegativeRand(), true);
+ bm.Set(MakeNonNegativeRand() % size, true);
}
for (size_t i = 0; i < data.size(); ++i) {
data[i] = MakeNonNegativeRand();
@@ -138,7 +138,7 @@ struct TestData {
void Benchmark(int batch_size, void* data) {
TestData* d = reinterpret_cast<TestData*>(data);
for (int i = 0; i < batch_size; ++i) {
- d->result += d->bm.Get<true>(d->data[i & (d->data.size() - 1)]);
+ d->result += d->bm.Get(d->data[i & (d->data.size() - 1)] % d->bm.num_bits());
}
}
http://git-wip-us.apache.org/repos/asf/incubator-impala/blob/0fbb5b7e/be/src/exec/hash-table.h
----------------------------------------------------------------------
diff --git a/be/src/exec/hash-table.h b/be/src/exec/hash-table.h
index 404b294..2ebc22f 100644
--- a/be/src/exec/hash-table.h
+++ b/be/src/exec/hash-table.h
@@ -290,11 +290,11 @@ class HashTableCtx {
/// Returns true if the current row is null but nulls are not considered in the current
/// phase (build or probe).
- bool ALWAYS_INLINE IsRowNull() const { return null_bitmap_.Get<false>(CurIdx()); }
+ bool ALWAYS_INLINE IsRowNull() const { return null_bitmap_.Get(CurIdx()); }
/// Record in a bitmap that the current row is null but nulls are not considered in
/// the current phase (build or probe).
- void ALWAYS_INLINE SetRowNull() { null_bitmap_.Set<false>(CurIdx(), true); }
+ void ALWAYS_INLINE SetRowNull() { null_bitmap_.Set(CurIdx(), true); }
/// Returns the hash values of the current row.
uint32_t ALWAYS_INLINE CurExprValuesHash() const { return *cur_expr_values_hash_; }
http://git-wip-us.apache.org/repos/asf/incubator-impala/blob/0fbb5b7e/be/src/exec/nested-loop-join-node.cc
----------------------------------------------------------------------
diff --git a/be/src/exec/nested-loop-join-node.cc b/be/src/exec/nested-loop-join-node.cc
index 0a115c6..6c75797 100644
--- a/be/src/exec/nested-loop-join-node.cc
+++ b/be/src/exec/nested-loop-join-node.cc
@@ -410,7 +410,7 @@ Status NestedLoopJoinNode::GetNextRightSemiJoin(RuntimeState* state,
}
// Check if we already have a match for the build row.
- if (matching_build_rows_->Get<false>(current_build_row_idx_)) {
+ if (matching_build_rows_->Get(current_build_row_idx_)) {
build_row_iterator_.Next();
++current_build_row_idx_;
continue;
@@ -424,7 +424,7 @@ Status NestedLoopJoinNode::GetNextRightSemiJoin(RuntimeState* state,
continue;
}
TupleRow* output_row = output_batch->GetRow(output_batch->AddRow());
- matching_build_rows_->Set<false>(current_build_row_idx_, true);
+ matching_build_rows_->Set(current_build_row_idx_, true);
output_batch->CopyRow(build_row_iterator_.GetRow(), output_row);
build_row_iterator_.Next();
++current_build_row_idx_;
@@ -461,7 +461,7 @@ Status NestedLoopJoinNode::GetNextRightAntiJoin(RuntimeState* state,
RETURN_IF_ERROR(QueryMaintenance(state));
}
- if (matching_build_rows_->Get<false>(current_build_row_idx_)) {
+ if (matching_build_rows_->Get(current_build_row_idx_)) {
build_row_iterator_.Next();
++current_build_row_idx_;
continue;
@@ -469,7 +469,7 @@ Status NestedLoopJoinNode::GetNextRightAntiJoin(RuntimeState* state,
CreateOutputRow(semi_join_staging_row_, current_probe_row_,
build_row_iterator_.GetRow());
if (EvalConjuncts(join_conjunct_ctxs, num_join_ctxs, semi_join_staging_row_)) {
- matching_build_rows_->Set<false>(current_build_row_idx_, true);
+ matching_build_rows_->Set(current_build_row_idx_, true);
}
build_row_iterator_.Next();
++current_build_row_idx_;
@@ -548,7 +548,7 @@ Status NestedLoopJoinNode::ProcessUnmatchedBuildRows(
RETURN_IF_ERROR(QueryMaintenance(state));
}
- if (matching_build_rows_->Get<false>(current_build_row_idx_)) {
+ if (matching_build_rows_->Get(current_build_row_idx_)) {
build_row_iterator_.Next();
++current_build_row_idx_;
continue;
@@ -612,7 +612,7 @@ Status NestedLoopJoinNode::FindBuildMatches(
if (!EvalConjuncts(join_conjunct_ctxs, num_join_ctxs, output_row)) continue;
matched_probe_ = true;
if (matching_build_rows_ != NULL) {
- matching_build_rows_->Set<false>(current_build_row_idx_ - 1, true);
+ matching_build_rows_->Set(current_build_row_idx_ - 1, true);
}
if (!EvalConjuncts(conjunct_ctxs, num_ctxs, output_row)) continue;
VLOG_ROW << "match row: " << PrintRow(output_row, row_desc());
http://git-wip-us.apache.org/repos/asf/incubator-impala/blob/0fbb5b7e/be/src/util/bitmap-test.cc
----------------------------------------------------------------------
diff --git a/be/src/util/bitmap-test.cc b/be/src/util/bitmap-test.cc
index 238b5fc..c0a3899 100644
--- a/be/src/util/bitmap-test.cc
+++ b/be/src/util/bitmap-test.cc
@@ -30,14 +30,14 @@ namespace impala {
void CreateRandomBitmap(Bitmap* bitmap) {
for (int64_t i = 0; i < bitmap->num_bits(); ++i) {
- bitmap->Set<false>(i, rand() % 2 == 0);
+ bitmap->Set(i, rand() % 2 == 0);
}
}
// Returns true if all the bits in the bitmap are equal to 'value'.
bool CheckAll(const Bitmap& bitmap, const bool value) {
for (int64_t i = 0; i < bitmap.num_bits(); ++i) {
- if (bitmap.Get<false>(i) != value) return false;
+ if (bitmap.Get(i) != value) return false;
}
return true;
}
@@ -70,24 +70,6 @@ TEST(Bitmap, SetAllTest) {
EXPECT_TRUE(CheckAll(bm, false));
}
-TEST(Bitmap, AndTest) {
- Bitmap bm(1024);
- CreateRandomBitmap(&bm);
- Bitmap bm_zeros(1024);
- bm_zeros.SetAllBits(false);
- bm.And(&bm_zeros);
- EXPECT_TRUE(CheckAll(bm, false));
-}
-
-TEST(Bitmap, OrTest) {
- Bitmap bm(1024);
- CreateRandomBitmap(&bm);
- Bitmap bm_ones(1024);
- bm_ones.SetAllBits(true);
- bm.Or(&bm_ones);
- EXPECT_TRUE(CheckAll(bm, true));
-}
-
// Regression test for IMPALA-2155.
TEST(Bitmap, SetGetTest) {
Bitmap bm(1024);
@@ -96,36 +78,16 @@ TEST(Bitmap, SetGetTest) {
// to 0 and 1.
for (int64_t bit_idx = 0; bit_idx < 63; ++bit_idx) {
for (int64_t i = 0; i < 4; ++i) {
- bm.Set<false>((1 << (6 + i)) + bit_idx, (i + bit_idx) % 2 == 0);
+ bm.Set((1 << (6 + i)) + bit_idx, (i + bit_idx) % 2 == 0);
}
}
for (int64_t bit_idx = 0; bit_idx < 63; ++bit_idx) {
for (int64_t i = 0; i < 4; ++i) {
- EXPECT_EQ(bm.Get<false>((1 << (6 + i)) + bit_idx), (i + bit_idx) % 2 == 0);
+ EXPECT_EQ(bm.Get((1 << (6 + i)) + bit_idx), (i + bit_idx) % 2 == 0);
}
}
}
-TEST(Bitmap, SetGetModTest) {
- Bitmap bm(256);
- bm.SetAllBits(false);
- for (int64_t bit_idx = 0; bit_idx < 1024; ++bit_idx) {
- bm.Set<true>(bit_idx, true);
- EXPECT_TRUE(bm.Get<true>(bit_idx));
- bm.Set<true>(bit_idx, false);
- EXPECT_FALSE(bm.Get<true>(bit_idx));
- }
-
- bm.SetAllBits(false);
- EXPECT_TRUE(CheckAll(bm, false));
- for (int64_t bit_idx = 0; bit_idx < 1024; ++bit_idx) {
- bm.Set<true>(bit_idx, bit_idx % 2 == 0);
- }
- for (int64_t bit_idx = 0; bit_idx < 1024; ++bit_idx) {
- EXPECT_EQ(bm.Get<true>(bit_idx), bit_idx % 2 == 0);
- }
-}
-
/// Regression test for IMPALA-2307.
TEST(Bitmap, OverflowTest) {
Bitmap bm(64);
@@ -133,36 +95,20 @@ TEST(Bitmap, OverflowTest) {
int64_t bit_idx = 45;
int64_t ovr_idx = 13;
- bm.Set<false>(bit_idx, true);
- EXPECT_FALSE(bm.Get<false>(ovr_idx));
- EXPECT_TRUE(bm.Get<false>(bit_idx));
-
- bm.SetAllBits(false);
- bm.Set<false>(ovr_idx, true);
- EXPECT_FALSE(bm.Get<false>(bit_idx));
- EXPECT_TRUE(bm.Get<false>(ovr_idx));
-
- bm.SetAllBits(false);
- bm.Set<false>(ovr_idx, true);
- bm.Set<false>(bit_idx, false);
- EXPECT_TRUE(bm.Get<false>(ovr_idx));
- EXPECT_FALSE(bm.Get<false>(bit_idx));
-
- bm.SetAllBits(false);
- bm.Set<true>(bit_idx, true);
- EXPECT_FALSE(bm.Get<true>(ovr_idx));
- EXPECT_TRUE(bm.Get<true>(bit_idx));
+ bm.Set(bit_idx, true);
+ EXPECT_FALSE(bm.Get(ovr_idx));
+ EXPECT_TRUE(bm.Get(bit_idx));
bm.SetAllBits(false);
- bm.Set<true>(ovr_idx, true);
- EXPECT_FALSE(bm.Get<true>(bit_idx));
- EXPECT_TRUE(bm.Get<true>(ovr_idx));
+ bm.Set(ovr_idx, true);
+ EXPECT_FALSE(bm.Get(bit_idx));
+ EXPECT_TRUE(bm.Get(ovr_idx));
bm.SetAllBits(false);
- bm.Set<true>(ovr_idx, true);
- bm.Set<true>(bit_idx, false);
- EXPECT_TRUE(bm.Get<true>(ovr_idx));
- EXPECT_FALSE(bm.Get<true>(bit_idx));
+ bm.Set(ovr_idx, true);
+ bm.Set(bit_idx, false);
+ EXPECT_TRUE(bm.Get(ovr_idx));
+ EXPECT_FALSE(bm.Get(bit_idx));
}
/// Test that bitmap memory usage calculation is correct.
http://git-wip-us.apache.org/repos/asf/incubator-impala/blob/0fbb5b7e/be/src/util/bitmap.cc
----------------------------------------------------------------------
diff --git a/be/src/util/bitmap.cc b/be/src/util/bitmap.cc
index b1f54bc..504c919 100644
--- a/be/src/util/bitmap.cc
+++ b/be/src/util/bitmap.cc
@@ -23,21 +23,21 @@
using namespace impala;
-string Bitmap::DebugString(bool print_bits) {
+string Bitmap::DebugString(bool print_bits) const {
int64_t words = BitUtil::RoundUp(num_bits_, 64) / 64;
stringstream ss;
ss << "Size (" << num_bits_ << ") words (" << words << ") ";
if (print_bits) {
for (int i = 0; i < num_bits(); ++i) {
- if (Get<false>(i)) {
+ if (Get(i)) {
ss << "1";
} else {
ss << "0";
}
}
} else {
- for (vector<uint64_t>::iterator it = buffer_.begin(); it != buffer_.end(); ++it) {
- ss << *it << ".";
+ for (auto v : buffer_) {
+ ss << v << ".";
}
}
ss << endl;
http://git-wip-us.apache.org/repos/asf/incubator-impala/blob/0fbb5b7e/be/src/util/bitmap.h
----------------------------------------------------------------------
diff --git a/be/src/util/bitmap.h b/be/src/util/bitmap.h
index 1ff8050..5f02f60 100644
--- a/be/src/util/bitmap.h
+++ b/be/src/util/bitmap.h
@@ -37,10 +37,6 @@ class Bitmap {
num_bits_ = num_bits;
}
- Bitmap(const uint64_t* from_buf, int64_t num_bits) {
- SetFromBuffer(from_buf, num_bits);
- }
-
/// Resize bitmap and set all bits to zero.
void Reset(int64_t num_bits) {
DCHECK_GE(num_bits, 0);
@@ -49,30 +45,17 @@ class Bitmap {
SetAllBits(false);
}
- void SetFromBuffer(const uint64_t* from_buf, int64_t num_bits) {
- buffer_.resize(BitUtil::RoundUpNumi64(num_bits));
- for (int i = 0; i < buffer_.size(); ++i) {
- buffer_[i] = from_buf[i];
- }
- num_bits_ = num_bits;
- }
-
/// Compute memory usage of a bitmap, not including the Bitmap object itself.
static int64_t MemUsage(int64_t num_bits) {
DCHECK_GE(num_bits, 0);
return BitUtil::RoundUpNumi64(num_bits) * sizeof(int64_t);
}
- static int64_t DefaultHashSeed() { return 1234; }
-
/// Compute memory usage of this bitmap, not including the Bitmap object itself.
int64_t MemUsage() const { return MemUsage(num_bits_); }
- /// Sets the bit at 'bit_index' to v. If mod is true, this
- /// function will first mod the bit_index by the bitmap size.
- template<bool mod>
+ /// Sets the bit at 'bit_index' to v.
void Set(int64_t bit_index, bool v) {
- if (mod) bit_index &= (num_bits() - 1);
int64_t word_index = bit_index >> NUM_OFFSET_BITS;
bit_index &= BIT_INDEX_MASK;
DCHECK_LT(word_index, buffer_.size());
@@ -83,33 +66,14 @@ class Bitmap {
}
}
- /// Returns true if the bit at 'bit_index' is set. If mod is true, this
- /// function will first mod the bit_index by the bitmap size.
- template<bool mod>
+ /// Returns true if the bit at 'bit_index' is set.
bool Get(int64_t bit_index) const {
- if (mod) bit_index &= (num_bits() - 1);
int64_t word_index = bit_index >> NUM_OFFSET_BITS;
bit_index &= BIT_INDEX_MASK;
DCHECK_LT(word_index, buffer_.size());
return (buffer_[word_index] & (1LL << bit_index)) != 0;
}
- /// Bitwise ANDs the src bitmap into this one.
- void And(const Bitmap* src) {
- DCHECK_EQ(num_bits(), src->num_bits());
- for (int i = 0; i < buffer_.size(); ++i) {
- buffer_[i] &= src->buffer_[i];
- }
- }
-
- /// Bitwise ORs the src bitmap into this one.
- void Or(const Bitmap* src) {
- DCHECK_EQ(num_bits(), src->num_bits());
- for (int i = 0; i < buffer_.size(); ++i) {
- buffer_[i] |= src->buffer_[i];
- }
- }
-
void SetAllBits(bool b) {
memset(&buffer_[0], 255 * b, buffer_.size() * sizeof(uint64_t));
}
@@ -117,7 +81,7 @@ class Bitmap {
int64_t num_bits() const { return num_bits_; }
/// If 'print_bits' prints 0/1 per bit, otherwise it prints the int64_t value.
- std::string DebugString(bool print_bits);
+ std::string DebugString(bool print_bits) const;
private:
std::vector<uint64_t> buffer_;