1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
|
// Copyright (c) 2011-present, Facebook, Inc. All rights reserved.
// This source code is licensed under both the GPLv2 (found in the
// COPYING file in the root directory) and Apache 2.0 License
// (found in the LICENSE.Apache file in the root directory).
// this is a simple micro-benchmark for compare ribbon filter vs. other filter
// for more comprehensive, please check the dedicate util/filter_bench.
#include "benchmark/benchmark.h"
#include "table/block_based/filter_policy_internal.h"
#include "table/block_based/mock_block_based_table.h"
namespace ROCKSDB_NAMESPACE {
struct KeyMaker {
explicit KeyMaker(size_t avg_size)
: smallest_size_(avg_size),
buf_size_(avg_size + 11), // pad to vary key size and alignment
buf_(new char[buf_size_]) {
memset(buf_.get(), 0, buf_size_);
assert(smallest_size_ > 8);
}
size_t smallest_size_;
size_t buf_size_;
std::unique_ptr<char[]> buf_;
// Returns a unique(-ish) key based on the given parameter values. Each
// call returns a Slice from the same buffer so previously returned
// Slices should be considered invalidated.
Slice Get(uint32_t filter_num, uint32_t val_num) const {
size_t start = val_num % 4;
size_t len = smallest_size_;
// To get range [avg_size - 2, avg_size + 2]
// use range [smallest_size, smallest_size + 4]
len += FastRange32((val_num >> 5) * 1234567891, 5);
char *data = buf_.get() + start;
// Populate key data such that all data makes it into a key of at
// least 8 bytes. We also don't want all the within-filter key
// variance confined to a contiguous 32 bits, because then a 32 bit
// hash function can "cheat" the false positive rate by
// approximating a perfect hash.
EncodeFixed32(data, val_num);
EncodeFixed32(data + 4, filter_num + val_num);
// ensure clearing leftovers from different alignment
EncodeFixed32(data + 8, 0);
return {data, len};
}
};
// benchmark arguments:
// 0. filter impl (like filter_bench -impl)
// 1. filter config bits_per_key
// 2. average data key length
// 3. data entry number
static void CustomArguments(benchmark::internal::Benchmark *b) {
const auto kImplCount =
static_cast<int>(BloomLikeFilterPolicy::GetAllFixedImpls().size());
for (int filter_impl = 0; filter_impl < kImplCount; ++filter_impl) {
for (int bits_per_key : {10, 20}) {
for (int key_len_avg : {10, 100}) {
for (int64_t entry_num : {1 << 10, 1 << 20}) {
b->Args({filter_impl, bits_per_key, key_len_avg, entry_num});
}
}
}
}
b->ArgNames({"filter_impl", "bits_per_key", "key_len_avg", "entry_num"});
}
static void FilterBuild(benchmark::State &state) {
// setup data
auto filter = BloomLikeFilterPolicy::Create(
BloomLikeFilterPolicy::GetAllFixedImpls().at(state.range(0)),
static_cast<double>(state.range(1)));
auto tester = std::make_unique<mock::MockBlockBasedTableTester>(filter);
KeyMaker km(state.range(2));
std::unique_ptr<const char[]> owner;
const int64_t kEntryNum = state.range(3);
auto rnd = Random32(12345);
uint32_t filter_num = rnd.Next();
// run the test
for (auto _ : state) {
std::unique_ptr<FilterBitsBuilder> builder(tester->GetBuilder());
for (uint32_t i = 0; i < kEntryNum; i++) {
builder->AddKey(km.Get(filter_num, i));
}
auto ret = builder->Finish(&owner);
state.counters["size"] = static_cast<double>(ret.size());
}
}
BENCHMARK(FilterBuild)->Apply(CustomArguments);
static void FilterQueryPositive(benchmark::State &state) {
// setup data
auto filter = BloomLikeFilterPolicy::Create(
BloomLikeFilterPolicy::GetAllFixedImpls().at(state.range(0)),
static_cast<double>(state.range(1)));
auto tester = std::make_unique<mock::MockBlockBasedTableTester>(filter);
KeyMaker km(state.range(2));
std::unique_ptr<const char[]> owner;
const int64_t kEntryNum = state.range(3);
auto rnd = Random32(12345);
uint32_t filter_num = rnd.Next();
std::unique_ptr<FilterBitsBuilder> builder(tester->GetBuilder());
for (uint32_t i = 0; i < kEntryNum; i++) {
builder->AddKey(km.Get(filter_num, i));
}
auto data = builder->Finish(&owner);
std::unique_ptr<FilterBitsReader> reader{filter->GetFilterBitsReader(data)};
// run test
uint32_t i = 0;
for (auto _ : state) {
i++;
i = i % kEntryNum;
reader->MayMatch(km.Get(filter_num, i));
}
}
BENCHMARK(FilterQueryPositive)->Apply(CustomArguments);
static void FilterQueryNegative(benchmark::State &state) {
// setup data
auto filter = BloomLikeFilterPolicy::Create(
BloomLikeFilterPolicy::GetAllFixedImpls().at(state.range(0)),
static_cast<double>(state.range(1)));
auto tester = std::make_unique<mock::MockBlockBasedTableTester>(filter);
KeyMaker km(state.range(2));
std::unique_ptr<const char[]> owner;
const int64_t kEntryNum = state.range(3);
auto rnd = Random32(12345);
uint32_t filter_num = rnd.Next();
std::unique_ptr<FilterBitsBuilder> builder(tester->GetBuilder());
for (uint32_t i = 0; i < kEntryNum; i++) {
builder->AddKey(km.Get(filter_num, i));
}
auto data = builder->Finish(&owner);
std::unique_ptr<FilterBitsReader> reader{filter->GetFilterBitsReader(data)};
// run test
uint32_t i = 0;
double fp_cnt = 0;
for (auto _ : state) {
i++;
auto result = reader->MayMatch(km.Get(filter_num + 1, i));
if (result) {
fp_cnt++;
}
}
state.counters["fp_pct"] =
benchmark::Counter(fp_cnt * 100, benchmark::Counter::kAvgIterations);
}
BENCHMARK(FilterQueryNegative)->Apply(CustomArguments);
} // namespace ROCKSDB_NAMESPACE
BENCHMARK_MAIN();
|
