1 /*
2 * Benchmarks for hb_set_t operations.
3 */
4 #include "benchmark/benchmark.h"
5
6 #include <cassert>
7 #include <cstdlib>
8 #include "hb.h"
9
RandomSet(unsigned size,unsigned max_value,hb_set_t * out)10 void RandomSet(unsigned size, unsigned max_value, hb_set_t* out) {
11 hb_set_clear(out);
12
13 srand(size * max_value);
14 for (unsigned i = 0; i < size; i++) {
15 while (true) {
16 unsigned next = rand() % max_value;
17 if (hb_set_has (out, next)) continue;
18
19 hb_set_add(out, next);
20 break;
21 }
22 }
23 }
24
25 // TODO(garretrieger): benchmark union/subtract/intersection etc.
26
27 /* Insert a 1000 values into set of varying sizes. */
BM_SetInsert_1000(benchmark::State & state)28 static void BM_SetInsert_1000(benchmark::State& state) {
29 unsigned set_size = state.range(0);
30 unsigned max_value = state.range(0) * state.range(1);
31
32 hb_set_t* original = hb_set_create ();
33 RandomSet(set_size, max_value, original);
34 assert(hb_set_get_population(original) == set_size);
35
36 for (auto _ : state) {
37 state.PauseTiming ();
38 hb_set_t* data = hb_set_copy(original);
39 state.ResumeTiming ();
40 for (int i = 0; i < 1000; i++) {
41 hb_set_add(data, i * 2654435761u % max_value);
42 }
43 hb_set_destroy(data);
44 }
45
46 hb_set_destroy(original);
47 }
48 BENCHMARK(BM_SetInsert_1000)
49 ->Unit(benchmark::kMicrosecond)
50 ->Ranges(
51 {{1 << 10, 1 << 16}, // Set Size
52 {2, 512}}); // Density
53
54 /* Insert a 1000 values into set of varying sizes. */
BM_SetOrderedInsert_1000(benchmark::State & state)55 static void BM_SetOrderedInsert_1000(benchmark::State& state) {
56 unsigned set_size = state.range(0);
57 unsigned max_value = state.range(0) * state.range(1);
58
59 hb_set_t* original = hb_set_create ();
60 RandomSet(set_size, max_value, original);
61 assert(hb_set_get_population(original) == set_size);
62
63 for (auto _ : state) {
64 state.PauseTiming ();
65 hb_set_t* data = hb_set_copy(original);
66 state.ResumeTiming ();
67 for (int i = 0; i < 1000; i++) {
68 hb_set_add(data, i);
69 }
70 hb_set_destroy(data);
71 }
72
73 hb_set_destroy(original);
74 }
75 BENCHMARK(BM_SetOrderedInsert_1000)
76 ->Unit(benchmark::kMicrosecond)
77 ->Ranges(
78 {{1 << 10, 1 << 16}, // Set Size
79 {2, 512}}); // Density
80
81 /* Single value lookup on sets of various sizes. */
BM_SetLookup(benchmark::State & state,unsigned interval)82 static void BM_SetLookup(benchmark::State& state, unsigned interval) {
83 unsigned set_size = state.range(0);
84 unsigned max_value = state.range(0) * state.range(1);
85
86 hb_set_t* original = hb_set_create ();
87 RandomSet(set_size, max_value, original);
88 assert(hb_set_get_population(original) == set_size);
89
90 auto needle = max_value / 2;
91 for (auto _ : state) {
92 benchmark::DoNotOptimize(
93 hb_set_has (original, (needle += interval) % max_value));
94 }
95
96 hb_set_destroy(original);
97 }
98 BENCHMARK_CAPTURE(BM_SetLookup, ordered, 3)
99 ->Ranges(
100 {{1 << 10, 1 << 16}, // Set Size
101 {2, 512}}); // Density
102 BENCHMARK_CAPTURE(BM_SetLookup, random, 12345)
103 ->Ranges(
104 {{1 << 10, 1 << 16}, // Set Size
105 {2, 512}}); // Density
106
107 /* Full iteration of sets of varying sizes. */
BM_SetIteration(benchmark::State & state)108 static void BM_SetIteration(benchmark::State& state) {
109 unsigned set_size = state.range(0);
110 unsigned max_value = state.range(0) * state.range(1);
111
112 hb_set_t* original = hb_set_create ();
113 RandomSet(set_size, max_value, original);
114 assert(hb_set_get_population(original) == set_size);
115
116 hb_codepoint_t cp = HB_SET_VALUE_INVALID;
117 for (auto _ : state) {
118 hb_set_next (original, &cp);
119 }
120
121 hb_set_destroy(original);
122 }
123 BENCHMARK(BM_SetIteration)
124 ->Ranges(
125 {{1 << 10, 1 << 16}, // Set Size
126 {2, 512}}); // Density
127
128 /* Set copy. */
BM_SetCopy(benchmark::State & state)129 static void BM_SetCopy(benchmark::State& state) {
130 unsigned set_size = state.range(0);
131 unsigned max_value = state.range(0) * state.range(1);
132
133 hb_set_t* original = hb_set_create ();
134 RandomSet(set_size, max_value, original);
135 assert(hb_set_get_population(original) == set_size);
136
137 for (auto _ : state) {
138 hb_set_t *s = hb_set_create ();
139 hb_set_set (s, original);
140 hb_set_destroy (s);
141 }
142
143 hb_set_destroy(original);
144 }
145 BENCHMARK(BM_SetCopy)
146 ->Unit(benchmark::kMicrosecond)
147 ->Ranges(
148 {{1 << 10, 1 << 16}, // Set Size
149 {2, 512}}); // Density
150
151 BENCHMARK_MAIN();
152