folly/experimental/hazptr/bench/HazptrBench.h

   1 /*
   2  * Copyright 2017 Facebook, Inc.
   3  *
   4  * Licensed under the Apache License, Version 2.0 (the "License");
   5  * you may not use this file except in compliance with the License.
   6  * You may obtain a copy of the License at
   7  *
   8  *   http://www.apache.org/licenses/LICENSE-2.0
   9  *
  10  * Unless required by applicable law or agreed to in writing, software
  11  * distributed under the License is distributed on an "AS IS" BASIS,
  12  * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
  13  * See the License for the specific language governing permissions and
  14  * limitations under the License.
  15  */
  16 #pragma once
  17
  18 #include <folly/Benchmark.h>
  19 #include <folly/experimental/hazptr/example/SWMRList.h>
  20 #include <folly/portability/GTest.h>
  21
  22 #include <glog/logging.h>
  23
  24 #include <atomic>
  25 #include <thread>
  26
  27 namespace folly {
  28 namespace hazptr {
  29
  30 inline uint64_t run_once(int nthreads, int size, int ops) {
  31   folly::BenchmarkSuspender susp;
  32   SWMRListSet<uint64_t> s;
  33   std::atomic<bool> start{false};
  34   std::atomic<int> started{0};
  35
  36   hazptr_holder dummy_hptr[100];
  37
  38   for (int i = 0; i < size; ++i) {
  39     s.add(i);
  40   }
  41
  42   std::vector<std::thread> threads(nthreads);
  43   for (int tid = 0; tid < nthreads; ++tid) {
  44     threads[tid] = std::thread([&, tid] {
  45       started.fetch_add(1);
  46       while (!start.load())
  47         /* spin */;
  48
  49       for (int j = tid; j < ops; j += nthreads) {
  50         s.contains(j);
  51       }
  52     });
  53   }
  54
  55   while (started.load() < nthreads)
  56     /* spin */;
  57
  58   // begin time measurement
  59   auto tbegin = std::chrono::steady_clock::now();
  60   susp.dismiss();
  61   start.store(true);
  62
  63   for (auto& t : threads) {
  64     t.join();
  65   }
  66
  67   susp.rehire();
  68   // end time measurement
  69   auto tend = std::chrono::steady_clock::now();
  70   return std::chrono::duration_cast<std::chrono::nanoseconds>(tend - tbegin)
  71       .count();
  72 }
  73
  74 inline uint64_t bench(std::string name, int nthreads, int size, uint64_t base) {
  75   int reps = 10;
  76   int ops = 100000;
  77   uint64_t min = UINTMAX_MAX;
  78   uint64_t max = 0;
  79   uint64_t sum = 0;
  80
  81   run_once(nthreads, size, ops); // sometimes first run is outlier
  82   for (int r = 0; r < reps; ++r) {
  83     uint64_t dur = run_once(nthreads, size, ops);
  84     sum += dur;
  85     min = std::min(min, dur);
  86     max = std::max(max, dur);
  87   }
  88
  89   uint64_t avg = sum / reps;
  90   uint64_t res = min;
  91   std::cout << name;
  92   std::cout << "   " << std::setw(4) << max / ops << " ns";
  93   std::cout << "   " << std::setw(4) << avg / ops << " ns";
  94   std::cout << "   " << std::setw(4) << res / ops << " ns";
  95   if (base) {
  96     std::cout << " " << std::setw(3) << 100 * base / res << "%";
  97   }
  98   std::cout << std::endl;
  99   return res;
 100 }
 101
 102 const int nthr[] = {1, 10};
 103 const int sizes[] = {10, 100};
 104 const std::string header = "Test_name, Max time, Avg time, Min time";
 105
 106 } // namespace folly {
 107 } // namespace hazptr {
 108
 109 /*
 110 ------------------------------------------- No AMB - No Tc
 111 1 threads -- 10-item list
 112 no amb - no tc                  756 ns    688 ns    674 ns
 113 no amb - no tc - dup            725 ns    688 ns    676 ns
 114 1 threads -- 100-item list
 115 no amb - no tc                 2469 ns   2366 ns   2334 ns
 116 no amb - no tc - dup           2404 ns   2353 ns   2328 ns
 117 10 threads -- 10-item list
 118 no amb - no tc                  802 ns    764 ns    750 ns
 119 no amb - no tc - dup            798 ns    776 ns    733 ns
 120 10 threads -- 100-item list
 121 no amb - no tc                 2209 ns   2157 ns   2118 ns
 122 no amb - no tc - dup           2266 ns   2152 ns   1993 ns
 123 ----------------------------------------------------------
 124 ---------------------------------------------- AMB - No TC
 125 1 threads -- 10-item list
 126 amb - no tc                     554 ns    538 ns    525 ns
 127 amb - no tc - dup               540 ns    530 ns    524 ns
 128 1 threads -- 100-item list
 129 amb - no tc                     731 ns    721 ns    715 ns
 130 amb - no tc - dup               745 ns    724 ns    714 ns
 131 10 threads -- 10-item list
 132 amb - no tc                     777 ns    717 ns    676 ns
 133 amb - no tc - dup               726 ns    669 ns    638 ns
 134 10 threads -- 100-item list
 135 amb - no tc                    1015 ns    985 ns    955 ns
 136 amb - no tc - dup              1000 ns    978 ns    952 ns
 137 ----------------------------------------------------------
 138 ---------------------------------------------- No AMB - TC
 139 1 threads -- 10-item list
 140 no amb - tc                     209 ns    203 ns    199 ns
 141 no amb - tc - dup               210 ns    202 ns    196 ns
 142 1 threads -- 100-item list
 143 no amb - tc                    1872 ns   1849 ns   1840 ns
 144 no amb - tc - dup              1902 ns   1865 ns   1838 ns
 145 10 threads -- 10-item list
 146 no amb - tc                     136 ns     50 ns     23 ns
 147 no amb - tc - dup               178 ns     85 ns     23 ns
 148 10 threads -- 100-item list
 149 no amb - tc                    1594 ns    651 ns    201 ns
 150 no amb - tc - dup              1492 ns    615 ns    203 ns
 151 ----------------------------------------------------------
 152 ------------------------------------------------- AMB - TC
 153 1 threads -- 10-item list
 154 amb - tc                         45 ns     44 ns     44 ns
 155 amb - tc - dup                   46 ns     46 ns     45 ns
 156 1 threads -- 100-item list
 157 amb - tc                        256 ns    246 ns    240 ns
 158 amb - tc - dup                  242 ns    240 ns    238 ns
 159 10 threads -- 10-item list
 160 amb - tc                        120 ns     35 ns     13 ns
 161 amb - tc - dup                  104 ns     34 ns      9 ns
 162 10 threads -- 100-item list
 163 amb - tc                        267 ns    129 ns     49 ns
 164 amb - tc - dup                  766 ns    147 ns     42 ns
 165 ----------------------------------------------------------
 166  */