folly/test/SparseByteSetBench.cpp

   1 /*
   2  * Copyright 2016 Facebook, Inc.
   3  *
   4  * Licensed under the Apache License, Version 2.0 (the "License");
   5  * you may not use this file except in compliance with the License.
   6  * You may obtain a copy of the License at
   7  *
   8  *   http://www.apache.org/licenses/LICENSE-2.0
   9  *
  10  * Unless required by applicable law or agreed to in writing, software
  11  * distributed under the License is distributed on an "AS IS" BASIS,
  12  * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
  13  * See the License for the specific language governing permissions and
  14  * limitations under the License.
  15  */
  16
  17 /***
  18  *  A benchmark comparing SparseByteSet to bitset<256> and bool[256].
  19  */
  20
  21 #include <folly/Benchmark.h>
  22 #include <folly/Format.h>
  23 #include <folly/SparseByteSet.h>
  24 #include <folly/portability/GFlags.h>
  25 #include <bitset>
  26 #include <random>
  27 #include <vector>
  28
  29 using namespace std;
  30 using namespace folly;
  31
  32 namespace {
  33
  34 //  Interface-identical to SparseByteSet. So that we can do compile-time
  35 //  polymorphism.
  36 class BitSetWrapper {
  37  public:
  38   inline bool add(uint8_t i) {
  39     auto r = !contains(i);
  40     if (r) {
  41       rep_[i] = true;
  42     }
  43     return r;
  44   }
  45   inline bool contains(uint8_t i) {
  46     return rep_[i];
  47   }
  48  private:
  49   bitset<256> rep_;
  50 };
  51 class BoolArraySet {
  52  public:
  53   BoolArraySet() {
  54     memset(rep_, 0, sizeof(rep_));
  55   }
  56   inline bool add(uint8_t i) {
  57     auto r = !contains(i);
  58     if (r) {
  59       rep_[i] = true;
  60     }
  61     return r;
  62   }
  63   inline bool contains(uint8_t i) {
  64     return rep_[i];
  65   }
  66  private:
  67   bool rep_[256];
  68 };
  69
  70 template <typename Coll>
  71 void rand_bench(int iters, size_t size_add, size_t size_contains) {
  72   BenchmarkSuspender braces;
  73   vector<uint8_t> seq_add;
  74   vector<uint8_t> seq_contains;
  75   mt19937 rng;
  76   uniform_int_distribution<uint8_t> dist;
  77   for (size_t i = 0; i < size_add; ++i) {
  78     seq_add.push_back(dist(rng));
  79   }
  80   for (size_t i = 0; i < size_contains; ++i) {
  81     seq_contains.push_back(dist(rng));
  82   }
  83   braces.dismissing([&] {
  84       while (iters--) {
  85         Coll coll;
  86         for (auto b : seq_add) {
  87           coll.add(b);
  88         }
  89         bool q {};
  90         for (auto b : seq_contains) {
  91           q ^= coll.contains(b);
  92         }
  93         doNotOptimizeAway(q);
  94       }
  95   });
  96 }
  97
  98 void setup_rand_bench() {
  99   vector<pair<size_t, size_t>> rand_bench_params = {
 100     {4, 4},
 101     {4, 16},
 102     {4, 64},
 103     {4, 256},
 104     {16, 4},
 105     {16, 16},
 106     {16, 64},
 107     {16, 256},
 108     {64, 4},
 109     {64, 16},
 110     {64, 64},
 111     {64, 256},
 112     {256, 4},
 113     {256, 16},
 114     {256, 64},
 115     {256, 256},
 116   };
 117   for (auto kvp : rand_bench_params) {
 118     size_t size_add, size_contains;
 119     tie(size_add, size_contains) = kvp;
 120     addBenchmark(
 121         __FILE__,
 122         sformat("bitset_rand_bench({}, {})",
 123                 size_add, size_contains).c_str(),
 124         [=](int iters) {
 125           rand_bench<BitSetWrapper>(iters, size_add, size_contains);
 126           return iters;
 127         });
 128     addBenchmark(
 129         __FILE__,
 130         sformat("%bool_array_set_rand_bench({}, {})",
 131                 size_add, size_contains).c_str(),
 132         [=](int iters) {
 133           rand_bench<BoolArraySet>(iters, size_add, size_contains);
 134           return iters;
 135         });
 136     addBenchmark(
 137         __FILE__,
 138         sformat("%sparse_byte_set_rand_bench({}, {})",
 139                 size_add, size_contains).c_str(),
 140         [=](int iters) {
 141           rand_bench<SparseByteSet>(iters, size_add, size_contains);
 142           return iters;
 143         });
 144     addBenchmark(
 145         __FILE__,
 146         "-",
 147         [](int) { return 0; });
 148   }
 149 }
 150
 151 }
 152
 153 int main(int argc, char** argv) {
 154   gflags::ParseCommandLineFlags(&argc, &argv, true);
 155   setup_rand_bench();
 156   runBenchmarks();
 157   return 0;
 158 }