summaryrefslogtreecommitdiff
path: root/xdelta3/cpp-btree/btree_bench.cc
diff options
context:
space:
mode:
Diffstat (limited to 'xdelta3/cpp-btree/btree_bench.cc')
-rw-r--r--xdelta3/cpp-btree/btree_bench.cc593
1 files changed, 593 insertions, 0 deletions
diff --git a/xdelta3/cpp-btree/btree_bench.cc b/xdelta3/cpp-btree/btree_bench.cc
new file mode 100644
index 0000000..6eaed99
--- /dev/null
+++ b/xdelta3/cpp-btree/btree_bench.cc
@@ -0,0 +1,593 @@
1// Copyright 2013 Google Inc. All Rights Reserved.
2//
3// Licensed under the Apache License, Version 2.0 (the "License");
4// you may not use this file except in compliance with the License.
5// You may obtain a copy of the License at
6//
7// http://www.apache.org/licenses/LICENSE-2.0
8//
9// Unless required by applicable law or agreed to in writing, software
10// distributed under the License is distributed on an "AS IS" BASIS,
11// WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
12// See the License for the specific language governing permissions and
13// limitations under the License.
14
15#include <stdint.h>
16#include <stdlib.h>
17#include <algorithm>
18#include <functional>
19#include <map>
20#include <set>
21#include <string>
22#include <sys/time.h>
23#include <type_traits>
24#include <vector>
25
26#include "gflags/gflags.h"
27#include "btree_map.h"
28#include "btree_set.h"
29#include "btree_test.h"
30
31DEFINE_int32(test_random_seed, 123456789, "Seed for srand()");
32DEFINE_int32(benchmark_max_iters, 10000000, "Maximum test iterations");
33DEFINE_int32(benchmark_min_iters, 100, "Minimum test iterations");
34DEFINE_int32(benchmark_target_seconds, 1,
35 "Attempt to benchmark for this many seconds");
36
37using std::allocator;
38using std::less;
39using std::map;
40using std::max;
41using std::min;
42using std::multimap;
43using std::multiset;
44using std::set;
45using std::string;
46using std::vector;
47
48namespace btree {
49namespace {
50
51struct RandGen {
52 typedef ptrdiff_t result_type;
53 RandGen(result_type seed) {
54 srand(seed);
55 }
56 result_type operator()(result_type l) {
57 return rand() % l;
58 }
59};
60
61struct BenchmarkRun {
62 BenchmarkRun(const char *name, void (*func)(int));
63 void Run();
64 void Stop();
65 void Start();
66 void Reset();
67
68 BenchmarkRun *next_benchmark;
69 const char *benchmark_name;
70 void (*benchmark_func)(int);
71 int64_t accum_micros;
72 int64_t last_started;
73};
74
75BenchmarkRun *first_benchmark;
76BenchmarkRun *current_benchmark;
77
78int64_t get_micros () {
79 timeval tv;
80 gettimeofday(&tv, NULL);
81 return tv.tv_sec * 1000000 + tv.tv_usec;
82}
83
84BenchmarkRun::BenchmarkRun(const char *name, void (*func)(int))
85 : next_benchmark(first_benchmark),
86 benchmark_name(name),
87 benchmark_func(func),
88 accum_micros(0),
89 last_started(0) {
90 first_benchmark = this;
91}
92
93#define BTREE_BENCHMARK(name) \
94 BTREE_BENCHMARK2(#name, name, __COUNTER__)
95#define BTREE_BENCHMARK2(name, func, counter) \
96 BTREE_BENCHMARK3(name, func, counter)
97#define BTREE_BENCHMARK3(name, func, counter) \
98 BenchmarkRun bench ## counter (name, func)
99
100void StopBenchmarkTiming() {
101 current_benchmark->Stop();
102}
103
104void StartBenchmarkTiming() {
105 current_benchmark->Start();
106}
107
108void RunBenchmarks() {
109 for (BenchmarkRun *bench = first_benchmark; bench;
110 bench = bench->next_benchmark) {
111 bench->Run();
112 }
113}
114
115void BenchmarkRun::Start() {
116 assert(!last_started);
117 last_started = get_micros();
118}
119
120void BenchmarkRun::Stop() {
121 if (last_started == 0) {
122 return;
123 }
124 accum_micros += get_micros() - last_started;
125 last_started = 0;
126}
127
128void BenchmarkRun::Reset() {
129 last_started = 0;
130 accum_micros = 0;
131}
132
133void BenchmarkRun::Run() {
134 assert(current_benchmark == NULL);
135 current_benchmark = this;
136 int iters = FLAGS_benchmark_min_iters;
137 for (;;) {
138 Reset();
139 Start();
140 benchmark_func(iters);
141 Stop();
142 if (accum_micros > FLAGS_benchmark_target_seconds * 1000000 ||
143 iters >= FLAGS_benchmark_max_iters) {
144 break;
145 } else if (accum_micros == 0) {
146 iters *= 100;
147 } else {
148 int64_t target_micros = FLAGS_benchmark_target_seconds * 1000000;
149 iters = target_micros * iters / accum_micros;
150 }
151 iters = min(iters, FLAGS_benchmark_max_iters);
152 }
153 std::cout << benchmark_name << "\t"
154 << accum_micros * 1000 / iters << "\t"
155 << iters;
156 current_benchmark = NULL;
157}
158
159// Used to avoid compiler optimizations for these benchmarks.
160template <typename T>
161void sink(const T& t0) {
162 volatile T t = t0;
163}
164
165// Benchmark insertion of values into a container.
166template <typename T>
167void BM_Insert(int n) {
168 typedef typename std::remove_const<typename T::value_type>::type V;
169 typename KeyOfValue<typename T::key_type, V>::type key_of_value;
170
171 // Disable timing while we perform some initialization.
172 StopBenchmarkTiming();
173
174 T container;
175 vector<V> values = GenerateValues<V>(FLAGS_benchmark_values);
176 for (int i = 0; i < values.size(); i++) {
177 container.insert(values[i]);
178 }
179
180 for (int i = 0; i < n; ) {
181 // Remove and re-insert 10% of the keys
182 int m = min(n - i, FLAGS_benchmark_values / 10);
183
184 for (int j = i; j < i + m; j++) {
185 int x = j % FLAGS_benchmark_values;
186 container.erase(key_of_value(values[x]));
187 }
188
189 StartBenchmarkTiming();
190
191 for (int j = i; j < i + m; j++) {
192 int x = j % FLAGS_benchmark_values;
193 container.insert(values[x]);
194 }
195
196 StopBenchmarkTiming();
197
198 i += m;
199 }
200}
201
202// Benchmark lookup of values in a container.
203template <typename T>
204void BM_Lookup(int n) {
205 typedef typename std::remove_const<typename T::value_type>::type V;
206 typename KeyOfValue<typename T::key_type, V>::type key_of_value;
207
208 // Disable timing while we perform some initialization.
209 StopBenchmarkTiming();
210
211 T container;
212 vector<V> values = GenerateValues<V>(FLAGS_benchmark_values);
213
214 for (int i = 0; i < values.size(); i++) {
215 container.insert(values[i]);
216 }
217
218 V r = V();
219
220 StartBenchmarkTiming();
221
222 for (int i = 0; i < n; i++) {
223 int m = i % values.size();
224 r = *container.find(key_of_value(values[m]));
225 }
226
227 StopBenchmarkTiming();
228
229 sink(r); // Keep compiler from optimizing away r.
230}
231
232// Benchmark lookup of values in a full container, meaning that values
233// are inserted in-order to take advantage of biased insertion, which
234// yields a full tree.
235template <typename T>
236void BM_FullLookup(int n) {
237 typedef typename std::remove_const<typename T::value_type>::type V;
238 typename KeyOfValue<typename T::key_type, V>::type key_of_value;
239
240 // Disable timing while we perform some initialization.
241 StopBenchmarkTiming();
242
243 T container;
244 vector<V> values = GenerateValues<V>(FLAGS_benchmark_values);
245 vector<V> sorted(values);
246 sort(sorted.begin(), sorted.end());
247
248 for (int i = 0; i < sorted.size(); i++) {
249 container.insert(sorted[i]);
250 }
251
252 V r = V();
253
254 StartBenchmarkTiming();
255
256 for (int i = 0; i < n; i++) {
257 int m = i % values.size();
258 r = *container.find(key_of_value(values[m]));
259 }
260
261 StopBenchmarkTiming();
262
263 sink(r); // Keep compiler from optimizing away r.
264}
265
266// Benchmark deletion of values from a container.
267template <typename T>
268void BM_Delete(int n) {
269 typedef typename std::remove_const<typename T::value_type>::type V;
270 typename KeyOfValue<typename T::key_type, V>::type key_of_value;
271
272 // Disable timing while we perform some initialization.
273 StopBenchmarkTiming();
274
275 T container;
276 vector<V> values = GenerateValues<V>(FLAGS_benchmark_values);
277 for (int i = 0; i < values.size(); i++) {
278 container.insert(values[i]);
279 }
280
281 for (int i = 0; i < n; ) {
282 // Remove and re-insert 10% of the keys
283 int m = min(n - i, FLAGS_benchmark_values / 10);
284
285 StartBenchmarkTiming();
286
287 for (int j = i; j < i + m; j++) {
288 int x = j % FLAGS_benchmark_values;
289 container.erase(key_of_value(values[x]));
290 }
291
292 StopBenchmarkTiming();
293
294 for (int j = i; j < i + m; j++) {
295 int x = j % FLAGS_benchmark_values;
296 container.insert(values[x]);
297 }
298
299 i += m;
300 }
301}
302
303// Benchmark steady-state insert (into first half of range) and remove
304// (from second second half of range), treating the container
305// approximately like a queue with log-time access for all elements.
306// This benchmark does not test the case where insertion and removal
307// happen in the same region of the tree. This benchmark counts two
308// value constructors.
309template <typename T>
310void BM_QueueAddRem(int n) {
311 typedef typename std::remove_const<typename T::value_type>::type V;
312 typename KeyOfValue<typename T::key_type, V>::type key_of_value;
313
314 // Disable timing while we perform some initialization.
315 StopBenchmarkTiming();
316 assert(FLAGS_benchmark_values % 2 == 0);
317
318 T container;
319
320 const int half = FLAGS_benchmark_values / 2;
321 vector<int> remove_keys(half);
322 vector<int> add_keys(half);
323
324 for (int i = 0; i < half; i++) {
325 remove_keys[i] = i;
326 add_keys[i] = i;
327 }
328
329 RandGen rand(FLAGS_test_random_seed);
330
331 random_shuffle(remove_keys.begin(), remove_keys.end(), rand);
332 random_shuffle(add_keys.begin(), add_keys.end(), rand);
333
334 Generator<V> g(FLAGS_benchmark_values + FLAGS_benchmark_max_iters);
335
336 for (int i = 0; i < half; i++) {
337 container.insert(g(add_keys[i]));
338 container.insert(g(half + remove_keys[i]));
339 }
340
341 // There are three parts each of size "half":
342 // 1 is being deleted from [offset - half, offset)
343 // 2 is standing [offset, offset + half)
344 // 3 is being inserted into [offset + half, offset + 2 * half)
345 int offset = 0;
346
347 StartBenchmarkTiming();
348
349 for (int i = 0; i < n; i++) {
350 int idx = i % half;
351
352 if (idx == 0) {
353 StopBenchmarkTiming();
354 random_shuffle(remove_keys.begin(), remove_keys.end(), rand);
355 random_shuffle(add_keys.begin(), add_keys.end(), rand);
356 offset += half;
357 StartBenchmarkTiming();
358 }
359
360 int e = container.erase(key_of_value(g(offset - half + remove_keys[idx])));
361 assert(e == 1);
362 container.insert(g(offset + half + add_keys[idx]));
363 }
364
365 StopBenchmarkTiming();
366}
367
368// Mixed insertion and deletion in the same range using pre-constructed values.
369template <typename T>
370void BM_MixedAddRem(int n) {
371 typedef typename std::remove_const<typename T::value_type>::type V;
372 typename KeyOfValue<typename T::key_type, V>::type key_of_value;
373
374 // Disable timing while we perform some initialization.
375 StopBenchmarkTiming();
376 assert(FLAGS_benchmark_values % 2 == 0);
377
378 T container;
379 RandGen rand(FLAGS_test_random_seed);
380
381 vector<V> values = GenerateValues<V>(FLAGS_benchmark_values * 2);
382
383 // Create two random shuffles
384 vector<int> remove_keys(FLAGS_benchmark_values);
385 vector<int> add_keys(FLAGS_benchmark_values);
386
387 // Insert the first half of the values (already in random order)
388 for (int i = 0; i < FLAGS_benchmark_values; i++) {
389 container.insert(values[i]);
390
391 // remove_keys and add_keys will be swapped before each round,
392 // therefore fill add_keys here w/ the keys being inserted, so
393 // they'll be the first to be removed.
394 remove_keys[i] = i + FLAGS_benchmark_values;
395 add_keys[i] = i;
396 }
397
398 StartBenchmarkTiming();
399
400 for (int i = 0; i < n; i++) {
401 int idx = i % FLAGS_benchmark_values;
402
403 if (idx == 0) {
404 StopBenchmarkTiming();
405 remove_keys.swap(add_keys);
406 random_shuffle(remove_keys.begin(), remove_keys.end(), rand);
407 random_shuffle(add_keys.begin(), add_keys.end(), rand);
408 StartBenchmarkTiming();
409 }
410
411 int e = container.erase(key_of_value(values[remove_keys[idx]]));
412 assert(e == 1);
413 container.insert(values[add_keys[idx]]);
414 }
415
416 StopBenchmarkTiming();
417}
418
419// Insertion at end, removal from the beginning. This benchmark
420// counts two value constructors.
421template <typename T>
422void BM_Fifo(int n) {
423 typedef typename std::remove_const<typename T::value_type>::type V;
424
425 // Disable timing while we perform some initialization.
426 StopBenchmarkTiming();
427
428 T container;
429 Generator<V> g(FLAGS_benchmark_values + FLAGS_benchmark_max_iters);
430
431 for (int i = 0; i < FLAGS_benchmark_values; i++) {
432 container.insert(g(i));
433 }
434
435 StartBenchmarkTiming();
436
437 for (int i = 0; i < n; i++) {
438 container.erase(container.begin());
439 container.insert(container.end(), g(i + FLAGS_benchmark_values));
440 }
441
442 StopBenchmarkTiming();
443}
444
445// Iteration (forward) through the tree
446template <typename T>
447void BM_FwdIter(int n) {
448 typedef typename std::remove_const<typename T::value_type>::type V;
449
450 // Disable timing while we perform some initialization.
451 StopBenchmarkTiming();
452
453 T container;
454 vector<V> values = GenerateValues<V>(FLAGS_benchmark_values);
455
456 for (int i = 0; i < FLAGS_benchmark_values; i++) {
457 container.insert(values[i]);
458 }
459
460 typename T::iterator iter;
461
462 V r = V();
463
464 StartBenchmarkTiming();
465
466 for (int i = 0; i < n; i++) {
467 int idx = i % FLAGS_benchmark_values;
468
469 if (idx == 0) {
470 iter = container.begin();
471 }
472 r = *iter;
473 ++iter;
474 }
475
476 StopBenchmarkTiming();
477
478 sink(r); // Keep compiler from optimizing away r.
479}
480
481typedef set<int32_t> stl_set_int32;
482typedef set<int64_t> stl_set_int64;
483typedef set<string> stl_set_string;
484
485typedef map<int32_t, intptr_t> stl_map_int32;
486typedef map<int64_t, intptr_t> stl_map_int64;
487typedef map<string, intptr_t> stl_map_string;
488
489typedef multiset<int32_t> stl_multiset_int32;
490typedef multiset<int64_t> stl_multiset_int64;
491typedef multiset<string> stl_multiset_string;
492
493typedef multimap<int32_t, intptr_t> stl_multimap_int32;
494typedef multimap<int64_t, intptr_t> stl_multimap_int64;
495typedef multimap<string, intptr_t> stl_multimap_string;
496
497#define MY_BENCHMARK_TYPES2(value, name, size) \
498 typedef btree ## _set<value, less<value>, allocator<value>, size> \
499 btree ## _ ## size ## _set_ ## name; \
500 typedef btree ## _map<value, int, less<value>, allocator<value>, size> \
501 btree ## _ ## size ## _map_ ## name; \
502 typedef btree ## _multiset<value, less<value>, allocator<value>, size> \
503 btree ## _ ## size ## _multiset_ ## name; \
504 typedef btree ## _multimap<value, int, less<value>, allocator<value>, size> \
505 btree ## _ ## size ## _multimap_ ## name
506
507#define MY_BENCHMARK_TYPES(value, name) \
508 MY_BENCHMARK_TYPES2(value, name, 128); \
509 MY_BENCHMARK_TYPES2(value, name, 160); \
510 MY_BENCHMARK_TYPES2(value, name, 192); \
511 MY_BENCHMARK_TYPES2(value, name, 224); \
512 MY_BENCHMARK_TYPES2(value, name, 256); \
513 MY_BENCHMARK_TYPES2(value, name, 288); \
514 MY_BENCHMARK_TYPES2(value, name, 320); \
515 MY_BENCHMARK_TYPES2(value, name, 352); \
516 MY_BENCHMARK_TYPES2(value, name, 384); \
517 MY_BENCHMARK_TYPES2(value, name, 416); \
518 MY_BENCHMARK_TYPES2(value, name, 448); \
519 MY_BENCHMARK_TYPES2(value, name, 480); \
520 MY_BENCHMARK_TYPES2(value, name, 512); \
521 MY_BENCHMARK_TYPES2(value, name, 1024); \
522 MY_BENCHMARK_TYPES2(value, name, 1536); \
523 MY_BENCHMARK_TYPES2(value, name, 2048)
524
525MY_BENCHMARK_TYPES(int32_t, int32);
526MY_BENCHMARK_TYPES(int64_t, int64);
527MY_BENCHMARK_TYPES(string, string);
528
529#define MY_BENCHMARK4(type, name, func) \
530 void BM_ ## type ## _ ## name(int n) { BM_ ## func <type>(n); } \
531 BTREE_BENCHMARK(BM_ ## type ## _ ## name)
532
533// Define NODESIZE_TESTING when running btree_perf.py.
534
535#ifdef NODESIZE_TESTING
536#define MY_BENCHMARK3(tree, type, name, func) \
537 MY_BENCHMARK4(tree ## _128_ ## type, name, func); \
538 MY_BENCHMARK4(tree ## _160_ ## type, name, func); \
539 MY_BENCHMARK4(tree ## _192_ ## type, name, func); \
540 MY_BENCHMARK4(tree ## _224_ ## type, name, func); \
541 MY_BENCHMARK4(tree ## _256_ ## type, name, func); \
542 MY_BENCHMARK4(tree ## _288_ ## type, name, func); \
543 MY_BENCHMARK4(tree ## _320_ ## type, name, func); \
544 MY_BENCHMARK4(tree ## _352_ ## type, name, func); \
545 MY_BENCHMARK4(tree ## _384_ ## type, name, func); \
546 MY_BENCHMARK4(tree ## _416_ ## type, name, func); \
547 MY_BENCHMARK4(tree ## _448_ ## type, name, func); \
548 MY_BENCHMARK4(tree ## _480_ ## type, name, func); \
549 MY_BENCHMARK4(tree ## _512_ ## type, name, func); \
550 MY_BENCHMARK4(tree ## _1024_ ## type, name, func); \
551 MY_BENCHMARK4(tree ## _1536_ ## type, name, func); \
552 MY_BENCHMARK4(tree ## _2048_ ## type, name, func)
553#else
554#define MY_BENCHMARK3(tree, type, name, func) \
555 MY_BENCHMARK4(tree ## _256_ ## type, name, func); \
556 MY_BENCHMARK4(tree ## _2048_ ## type, name, func)
557#endif
558
559#define MY_BENCHMARK2(type, name, func) \
560 MY_BENCHMARK4(stl_ ## type, name, func); \
561 MY_BENCHMARK3(btree, type, name, func)
562
563#define MY_BENCHMARK(type) \
564 MY_BENCHMARK2(type, insert, Insert); \
565 MY_BENCHMARK2(type, lookup, Lookup); \
566 MY_BENCHMARK2(type, fulllookup, FullLookup); \
567 MY_BENCHMARK2(type, delete, Delete); \
568 MY_BENCHMARK2(type, queueaddrem, QueueAddRem); \
569 MY_BENCHMARK2(type, mixedaddrem, MixedAddRem); \
570 MY_BENCHMARK2(type, fifo, Fifo); \
571 MY_BENCHMARK2(type, fwditer, FwdIter)
572
573MY_BENCHMARK(set_int32);
574MY_BENCHMARK(map_int32);
575MY_BENCHMARK(set_int64);
576MY_BENCHMARK(map_int64);
577MY_BENCHMARK(set_string);
578MY_BENCHMARK(map_string);
579
580MY_BENCHMARK(multiset_int32);
581MY_BENCHMARK(multimap_int32);
582MY_BENCHMARK(multiset_int64);
583MY_BENCHMARK(multimap_int64);
584MY_BENCHMARK(multiset_string);
585MY_BENCHMARK(multimap_string);
586
587} // namespace
588} // namespace btree
589
590int main(int argc, char **argv) {
591 btree::RunBenchmarks();
592 return 0;
593}