perf/benchmark-map.cc

   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
  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. */
  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. */
  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. */
  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();