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