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