bloom_test.cc raw

   1  // Copyright (c) 2012 The LevelDB Authors. All rights reserved.
   2  // Use of this source code is governed by a BSD-style license that can be
   3  // found in the LICENSE file. See the AUTHORS file for names of contributors.
   4  
   5  #include "leveldb/filter_policy.h"
   6  
   7  #include "util/coding.h"
   8  #include "util/logging.h"
   9  #include "util/testharness.h"
  10  #include "util/testutil.h"
  11  
  12  namespace leveldb {
  13  
  14  static const int kVerbose = 1;
  15  
  16  static Slice Key(int i, char* buffer) {
  17    EncodeFixed32(buffer, i);
  18    return Slice(buffer, sizeof(uint32_t));
  19  }
  20  
  21  class BloomTest {
  22   public:
  23    BloomTest() : policy_(NewBloomFilterPolicy(10)) {}
  24  
  25    ~BloomTest() { delete policy_; }
  26  
  27    void Reset() {
  28      keys_.clear();
  29      filter_.clear();
  30    }
  31  
  32    void Add(const Slice& s) { keys_.push_back(s.ToString()); }
  33  
  34    void Build() {
  35      std::vector<Slice> key_slices;
  36      for (size_t i = 0; i < keys_.size(); i++) {
  37        key_slices.push_back(Slice(keys_[i]));
  38      }
  39      filter_.clear();
  40      policy_->CreateFilter(&key_slices[0], static_cast<int>(key_slices.size()),
  41                            &filter_);
  42      keys_.clear();
  43      if (kVerbose >= 2) DumpFilter();
  44    }
  45  
  46    size_t FilterSize() const { return filter_.size(); }
  47  
  48    void DumpFilter() {
  49      fprintf(stderr, "F(");
  50      for (size_t i = 0; i + 1 < filter_.size(); i++) {
  51        const unsigned int c = static_cast<unsigned int>(filter_[i]);
  52        for (int j = 0; j < 8; j++) {
  53          fprintf(stderr, "%c", (c & (1 << j)) ? '1' : '.');
  54        }
  55      }
  56      fprintf(stderr, ")\n");
  57    }
  58  
  59    bool Matches(const Slice& s) {
  60      if (!keys_.empty()) {
  61        Build();
  62      }
  63      return policy_->KeyMayMatch(s, filter_);
  64    }
  65  
  66    double FalsePositiveRate() {
  67      char buffer[sizeof(int)];
  68      int result = 0;
  69      for (int i = 0; i < 10000; i++) {
  70        if (Matches(Key(i + 1000000000, buffer))) {
  71          result++;
  72        }
  73      }
  74      return result / 10000.0;
  75    }
  76  
  77   private:
  78    const FilterPolicy* policy_;
  79    std::string filter_;
  80    std::vector<std::string> keys_;
  81  };
  82  
  83  TEST(BloomTest, EmptyFilter) {
  84    ASSERT_TRUE(!Matches("hello"));
  85    ASSERT_TRUE(!Matches("world"));
  86  }
  87  
  88  TEST(BloomTest, Small) {
  89    Add("hello");
  90    Add("world");
  91    ASSERT_TRUE(Matches("hello"));
  92    ASSERT_TRUE(Matches("world"));
  93    ASSERT_TRUE(!Matches("x"));
  94    ASSERT_TRUE(!Matches("foo"));
  95  }
  96  
  97  static int NextLength(int length) {
  98    if (length < 10) {
  99      length += 1;
 100    } else if (length < 100) {
 101      length += 10;
 102    } else if (length < 1000) {
 103      length += 100;
 104    } else {
 105      length += 1000;
 106    }
 107    return length;
 108  }
 109  
 110  TEST(BloomTest, VaryingLengths) {
 111    char buffer[sizeof(int)];
 112  
 113    // Count number of filters that significantly exceed the false positive rate
 114    int mediocre_filters = 0;
 115    int good_filters = 0;
 116  
 117    for (int length = 1; length <= 10000; length = NextLength(length)) {
 118      Reset();
 119      for (int i = 0; i < length; i++) {
 120        Add(Key(i, buffer));
 121      }
 122      Build();
 123  
 124      ASSERT_LE(FilterSize(), static_cast<size_t>((length * 10 / 8) + 40))
 125          << length;
 126  
 127      // All added keys must match
 128      for (int i = 0; i < length; i++) {
 129        ASSERT_TRUE(Matches(Key(i, buffer)))
 130            << "Length " << length << "; key " << i;
 131      }
 132  
 133      // Check false positive rate
 134      double rate = FalsePositiveRate();
 135      if (kVerbose >= 1) {
 136        fprintf(stderr, "False positives: %5.2f%% @ length = %6d ; bytes = %6d\n",
 137                rate * 100.0, length, static_cast<int>(FilterSize()));
 138      }
 139      ASSERT_LE(rate, 0.02);  // Must not be over 2%
 140      if (rate > 0.0125)
 141        mediocre_filters++;  // Allowed, but not too often
 142      else
 143        good_filters++;
 144    }
 145    if (kVerbose >= 1) {
 146      fprintf(stderr, "Filters: %d good, %d mediocre\n", good_filters,
 147              mediocre_filters);
 148    }
 149    ASSERT_LE(mediocre_filters, good_filters / 5);
 150  }
 151  
 152  // Different bits-per-byte
 153  
 154  }  // namespace leveldb
 155  
 156  int main(int argc, char** argv) { return leveldb::test::RunAllTests(); }
 157