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
|
/*
* Benchmarks for hb_set_t operations.
*/
#include "benchmark/benchmark.h"
#include <cassert>
#include <cstdlib>
#include "hb.h"
void RandomSet(unsigned size, unsigned max_value, hb_set_t* out) {
hb_set_clear(out);
srand(size * max_value);
for (unsigned i = 0; i < size; i++) {
while (true) {
unsigned next = rand() % max_value;
if (hb_set_has (out, next)) continue;
hb_set_add(out, next);
break;
}
}
}
// TODO(garretrieger): benchmark union/subtract/intersection etc.
/* Insert a 1000 values into set of varying sizes. */
static void BM_SetInsert_1000(benchmark::State& state) {
unsigned set_size = state.range(0);
unsigned max_value = state.range(0) * state.range(1);
hb_set_t* original = hb_set_create ();
RandomSet(set_size, max_value, original);
assert(hb_set_get_population(original) == set_size);
for (auto _ : state) {
state.PauseTiming ();
hb_set_t* data = hb_set_copy(original);
state.ResumeTiming ();
for (int i = 0; i < 1000; i++) {
hb_set_add(data, i * 2654435761u % max_value);
}
hb_set_destroy(data);
}
hb_set_destroy(original);
}
BENCHMARK(BM_SetInsert_1000)
->Unit(benchmark::kMicrosecond)
->Ranges(
{{1 << 10, 1 << 16}, // Set Size
{2, 512}}); // Density
/* Insert a 1000 values into set of varying sizes. */
static void BM_SetOrderedInsert_1000(benchmark::State& state) {
unsigned set_size = state.range(0);
unsigned max_value = state.range(0) * state.range(1);
hb_set_t* original = hb_set_create ();
RandomSet(set_size, max_value, original);
assert(hb_set_get_population(original) == set_size);
for (auto _ : state) {
state.PauseTiming ();
hb_set_t* data = hb_set_copy(original);
state.ResumeTiming ();
for (int i = 0; i < 1000; i++) {
hb_set_add(data, i);
}
hb_set_destroy(data);
}
hb_set_destroy(original);
}
BENCHMARK(BM_SetOrderedInsert_1000)
->Unit(benchmark::kMicrosecond)
->Ranges(
{{1 << 10, 1 << 16}, // Set Size
{2, 512}}); // Density
/* Single value lookup on sets of various sizes. */
static void BM_SetLookup(benchmark::State& state, unsigned interval) {
unsigned set_size = state.range(0);
unsigned max_value = state.range(0) * state.range(1);
hb_set_t* original = hb_set_create ();
RandomSet(set_size, max_value, original);
assert(hb_set_get_population(original) == set_size);
auto needle = max_value / 2;
for (auto _ : state) {
benchmark::DoNotOptimize(
hb_set_has (original, (needle += interval) % max_value));
}
hb_set_destroy(original);
}
BENCHMARK_CAPTURE(BM_SetLookup, ordered, 3)
->Ranges(
{{1 << 10, 1 << 16}, // Set Size
{2, 512}}); // Density
BENCHMARK_CAPTURE(BM_SetLookup, random, 12345)
->Ranges(
{{1 << 10, 1 << 16}, // Set Size
{2, 512}}); // Density
/* Full iteration of sets of varying sizes. */
static void BM_SetIteration(benchmark::State& state) {
unsigned set_size = state.range(0);
unsigned max_value = state.range(0) * state.range(1);
hb_set_t* original = hb_set_create ();
RandomSet(set_size, max_value, original);
assert(hb_set_get_population(original) == set_size);
hb_codepoint_t cp = HB_SET_VALUE_INVALID;
for (auto _ : state) {
hb_set_next (original, &cp);
}
hb_set_destroy(original);
}
BENCHMARK(BM_SetIteration)
->Ranges(
{{1 << 10, 1 << 16}, // Set Size
{2, 512}}); // Density
/* Set copy. */
static void BM_SetCopy(benchmark::State& state) {
unsigned set_size = state.range(0);
unsigned max_value = state.range(0) * state.range(1);
hb_set_t* original = hb_set_create ();
RandomSet(set_size, max_value, original);
assert(hb_set_get_population(original) == set_size);
for (auto _ : state) {
hb_set_t *s = hb_set_create ();
hb_set_set (s, original);
hb_set_destroy (s);
}
hb_set_destroy(original);
}
BENCHMARK(BM_SetCopy)
->Unit(benchmark::kMicrosecond)
->Ranges(
{{1 << 10, 1 << 16}, // Set Size
{2, 512}}); // Density
BENCHMARK_MAIN();
|
