2 * Copyright 2016 Facebook, Inc.
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
8 * http://www.apache.org/licenses/LICENSE-2.0
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.
18 * A benchmark comparing SparseByteSet to bitset<256> and bool[256].
21 #include <folly/Benchmark.h>
22 #include <folly/Format.h>
23 #include <folly/SparseByteSet.h>
24 #include <folly/portability/GFlags.h>
30 using namespace folly;
34 // Interface-identical to SparseByteSet. So that we can do compile-time
38 inline bool add(uint8_t i) {
39 auto r = !contains(i);
45 inline bool contains(uint8_t i) {
54 memset(rep_, 0, sizeof(rep_));
56 inline bool add(uint8_t i) {
57 auto r = !contains(i);
63 inline bool contains(uint8_t i) {
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;
76 uniform_int_distribution<uint8_t> dist;
77 for (size_t i = 0; i < size_add; ++i) {
78 seq_add.push_back(dist(rng));
80 for (size_t i = 0; i < size_contains; ++i) {
81 seq_contains.push_back(dist(rng));
83 braces.dismissing([&] {
86 for (auto b : seq_add) {
90 for (auto b : seq_contains) {
91 q ^= coll.contains(b);
98 void setup_rand_bench() {
99 vector<pair<size_t, size_t>> rand_bench_params = {
117 for (auto kvp : rand_bench_params) {
118 size_t size_add, size_contains;
119 tie(size_add, size_contains) = kvp;
122 sformat("bitset_rand_bench({}, {})",
123 size_add, size_contains).c_str(),
125 rand_bench<BitSetWrapper>(iters, size_add, size_contains);
130 sformat("%bool_array_set_rand_bench({}, {})",
131 size_add, size_contains).c_str(),
133 rand_bench<BoolArraySet>(iters, size_add, size_contains);
138 sformat("%sparse_byte_set_rand_bench({}, {})",
139 size_add, size_contains).c_str(),
141 rand_bench<SparseByteSet>(iters, size_add, size_contains);
147 [](int) { return 0; });
153 int main(int argc, char** argv) {
154 google::ParseCommandLineFlags(&argc, &argv, true);