Repository: incubator-impala Updated Branches: refs/heads/master ff6b450ad -> 61fcb4897
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 <[email protected]> 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/master Commit: 0fbb5b7e71e55346c8b97ec143854dba0088f124 Parents: ff6b450 Author: Jim Apple <[email protected]> Authored: Sat Oct 22 10:42:51 2016 -0700 Committer: Internal Jenkins <[email protected]> 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_;
