1 /*
2 * Benchmarks for hb_map_t operations.
3 */
4 #include "benchmark/benchmark.h"
5
6 #include <cassert>
7 #include <cstdlib>
8 #include "hb.h"
9
RandomMap(unsigned size,hb_map_t * out,hb_set_t * key_sample)10 void RandomMap(unsigned size, hb_map_t* out, hb_set_t* key_sample) {
11 hb_map_clear(out);
12
13 unsigned sample_denom = 1;
14 if (size > 10000)
15 sample_denom = size / 10000;
16
17 srand(size);
18 for (unsigned i = 0; i < size; i++) {
19 while (true) {
20 hb_codepoint_t next = rand();
21 if (hb_map_has (out, next)) continue;
22
23 hb_codepoint_t val = rand();
24 if (key_sample && val % sample_denom == 0)
25 hb_set_add (key_sample, next);
26 hb_map_set (out, next, val);
27 break;
28 }
29 }
30 }
31
32 /* Insert a single value into map of varying sizes. */
BM_MapInsert(benchmark::State & state)33 static void BM_MapInsert(benchmark::State& state) {
34 unsigned map_size = state.range(0);
35
36 hb_map_t* original = hb_map_create ();
37 RandomMap(map_size, original, nullptr);
38 assert(hb_map_get_population(original) == map_size);
39
40 unsigned mask = 1;
41 while (mask < map_size)
42 mask <<= 1;
43 mask--;
44
45 auto needle = 0u;
46 for (auto _ : state) {
47 // TODO(garretrieger): create a copy of the original map.
48 // Needs a hb_map_copy(..) in public api.
49
50 hb_map_set (original, needle++ & mask, 1);
51 }
52
53 hb_map_destroy(original);
54 }
55 BENCHMARK(BM_MapInsert)
56 ->Range(1 << 4, 1 << 20);
57
58 /* Single value lookup on map of various sizes where the key is not present. */
BM_MapLookupMiss(benchmark::State & state)59 static void BM_MapLookupMiss(benchmark::State& state) {
60 unsigned map_size = state.range(0);
61
62 hb_map_t* original = hb_map_create ();
63 RandomMap(map_size, original, nullptr);
64 assert(hb_map_get_population(original) == map_size);
65
66 auto needle = map_size / 2;
67
68 for (auto _ : state) {
69 benchmark::DoNotOptimize(
70 hb_map_get (original, needle++));
71 }
72
73 hb_map_destroy(original);
74 }
75 BENCHMARK(BM_MapLookupMiss)
76 ->Range(1 << 4, 1 << 20); // Map size
77
78 /* Single value lookup on map of various sizes. */
BM_MapLookupHit(benchmark::State & state)79 static void BM_MapLookupHit(benchmark::State& state) {
80 unsigned map_size = state.range(0);
81
82 hb_map_t* original = hb_map_create ();
83 hb_set_t* key_set = hb_set_create ();
84 RandomMap(map_size, original, key_set);
85 assert(hb_map_get_population(original) == map_size);
86
87 unsigned num_keys = hb_set_get_population (key_set);
88 hb_codepoint_t* key_array =
89 (hb_codepoint_t*) calloc (num_keys, sizeof(hb_codepoint_t));
90
91 hb_codepoint_t cp = HB_SET_VALUE_INVALID;
92 unsigned i = 0;
93 while (hb_set_next (key_set, &cp))
94 key_array[i++] = cp;
95
96 i = 0;
97 for (auto _ : state) {
98 benchmark::DoNotOptimize(
99 hb_map_get (original, key_array[i++ % num_keys]));
100 }
101
102 hb_set_destroy (key_set);
103 free (key_array);
104 hb_map_destroy(original);
105 }
106 BENCHMARK(BM_MapLookupHit)
107 ->Range(1 << 4, 1 << 20); // Map size
108
109
110 BENCHMARK_MAIN();
111