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_owner<void> 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   uint64_t duration = 0;
  70   auto tend = std::chrono::steady_clock::now();
  71   duration = std::chrono::duration_cast<std::chrono::nanoseconds>(tend - tbegin)
  72                  .count();
  73   return duration;
  74 }
  75
  76 inline uint64_t bench(std::string name, int nthreads, int size, uint64_t base) {
  77   int reps = 10;
  78   int ops = 100000;
  79   uint64_t min = UINTMAX_MAX;
  80   uint64_t max = 0;
  81   uint64_t sum = 0;
  82
  83   run_once(nthreads, size, ops); // sometimes first run is outlier
  84   for (int r = 0; r < reps; ++r) {
  85     uint64_t dur = run_once(nthreads, size, ops);
  86     sum += dur;
  87     min = std::min(min, dur);
  88     max = std::max(max, dur);
  89   }
  90
  91   uint64_t avg = sum / reps;
  92   uint64_t res = min;
  93   std::cout << name;
  94   std::cout << "   " << std::setw(4) << max / ops << " ns";
  95   std::cout << "   " << std::setw(4) << avg / ops << " ns";
  96   std::cout << "   " << std::setw(4) << res / ops << " ns";
  97   if (base) {
  98     std::cout << " " << std::setw(3) << 100 * base / res << "%";
  99   }
 100   std::cout << std::endl;
 101   return res;
 102 }
 103
 104 const int nthr[] = {1, 10};
 105 const int sizes[] = {10, 100};
 106 const std::string header = "Test_name, Max time, Avg time, Min time";
 107
 108 } // namespace folly {
 109 } // namespace hazptr {
 110
 111 /*
 112 ------------------------------------------- No AMB - No Tc
 113 1 threads -- 10-item list
 114 no amb - no tc                  756 ns    688 ns    674 ns
 115 no amb - no tc - dup            725 ns    688 ns    676 ns
 116 1 threads -- 100-item list
 117 no amb - no tc                 2469 ns   2366 ns   2334 ns
 118 no amb - no tc - dup           2404 ns   2353 ns   2328 ns
 119 10 threads -- 10-item list
 120 no amb - no tc                  802 ns    764 ns    750 ns
 121 no amb - no tc - dup            798 ns    776 ns    733 ns
 122 10 threads -- 100-item list
 123 no amb - no tc                 2209 ns   2157 ns   2118 ns
 124 no amb - no tc - dup           2266 ns   2152 ns   1993 ns
 125 ----------------------------------------------------------
 126 ---------------------------------------------- AMB - No TC
 127 1 threads -- 10-item list
 128 amb - no tc                     554 ns    538 ns    525 ns
 129 amb - no tc - dup               540 ns    530 ns    524 ns
 130 1 threads -- 100-item list
 131 amb - no tc                     731 ns    721 ns    715 ns
 132 amb - no tc - dup               745 ns    724 ns    714 ns
 133 10 threads -- 10-item list
 134 amb - no tc                     777 ns    717 ns    676 ns
 135 amb - no tc - dup               726 ns    669 ns    638 ns
 136 10 threads -- 100-item list
 137 amb - no tc                    1015 ns    985 ns    955 ns
 138 amb - no tc - dup              1000 ns    978 ns    952 ns
 139 ----------------------------------------------------------
 140 ---------------------------------------------- No AMB - TC
 141 1 threads -- 10-item list
 142 no amb - tc                     209 ns    203 ns    199 ns
 143 no amb - tc - dup               210 ns    202 ns    196 ns
 144 1 threads -- 100-item list
 145 no amb - tc                    1872 ns   1849 ns   1840 ns
 146 no amb - tc - dup              1902 ns   1865 ns   1838 ns
 147 10 threads -- 10-item list
 148 no amb - tc                     136 ns     50 ns     23 ns
 149 no amb - tc - dup               178 ns     85 ns     23 ns
 150 10 threads -- 100-item list
 151 no amb - tc                    1594 ns    651 ns    201 ns
 152 no amb - tc - dup              1492 ns    615 ns    203 ns
 153 ----------------------------------------------------------
 154 ------------------------------------------------- AMB - TC
 155 1 threads -- 10-item list
 156 amb - tc                         45 ns     44 ns     44 ns
 157 amb - tc - dup                   46 ns     46 ns     45 ns
 158 1 threads -- 100-item list
 159 amb - tc                        256 ns    246 ns    240 ns
 160 amb - tc - dup                  242 ns    240 ns    238 ns
 161 10 threads -- 10-item list
 162 amb - tc                        120 ns     35 ns     13 ns
 163 amb - tc - dup                  104 ns     34 ns      9 ns
 164 10 threads -- 100-item list
 165 amb - tc                        267 ns    129 ns     49 ns
 166 amb - tc - dup                  766 ns    147 ns     42 ns
 167 ----------------------------------------------------------
 168  */