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 template <typename InitFunc, typename Func, typename EndFunc>
  31 inline uint64_t run_once(
  32     int nthreads,
  33     const InitFunc& init,
  34     const Func& fn,
  35     const EndFunc& endFn) {
  36   folly::BenchmarkSuspender susp;
  37   std::atomic<bool> start{false};
  38   std::atomic<int> started{0};
  39
  40   init();
  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       fn(tid);
  49     });
  50   }
  51
  52   while (started.load() < nthreads)
  53     /* spin */;
  54
  55   // begin time measurement
  56   auto tbegin = std::chrono::steady_clock::now();
  57   susp.dismiss();
  58   start.store(true);
  59
  60   for (auto& t : threads) {
  61     t.join();
  62   }
  63
  64   susp.rehire();
  65   // end time measurement
  66   auto tend = std::chrono::steady_clock::now();
  67   endFn();
  68   return std::chrono::duration_cast<std::chrono::nanoseconds>(tend - tbegin)
  69       .count();
  70 }
  71
  72 template <typename RepFunc>
  73 inline uint64_t bench(std::string name, int ops, const RepFunc& repFn) {
  74   int reps = 10;
  75   uint64_t min = UINTMAX_MAX;
  76   uint64_t max = 0;
  77   uint64_t sum = 0;
  78
  79   repFn(); // sometimes first run is outlier
  80   for (int r = 0; r < reps; ++r) {
  81     uint64_t dur = repFn();
  82     sum += dur;
  83     min = std::min(min, dur);
  84     max = std::max(max, dur);
  85   }
  86
  87   const std::string unit = " ns";
  88   uint64_t avg = sum / reps;
  89   uint64_t res = min;
  90   std::cout << name;
  91   std::cout << "   " << std::setw(4) << max / ops << unit;
  92   std::cout << "   " << std::setw(4) << avg / ops << unit;
  93   std::cout << "   " << std::setw(4) << res / ops << unit;
  94   std::cout << std::endl;
  95   return res;
  96 }
  97
  98 inline uint64_t listBench(std::string name, int nthreads, int size) {
  99   int ops = 100000;
 100   auto repFn = [&] {
 101     hazptr_holder dummy[100];
 102     SWMRListSet<uint64_t> s;
 103     auto init = [&] {
 104       for (int i = 0; i < size; ++i) {
 105         s.add(i);
 106       }
 107     };
 108     auto fn = [&](int tid) {
 109       for (int j = tid; j < ops; j += nthreads) {
 110         s.contains(size);
 111       }
 112     };
 113     auto endFn = [] {};
 114     return run_once(nthreads, init, fn, endFn);
 115   };
 116   return bench(name, ops, repFn);
 117 }
 118
 119 inline uint64_t holderBench(std::string name, int nthreads) {
 120   int ops = 100000;
 121   auto repFn = [&] {
 122     hazptr_holder dummy[100];
 123     auto init = [] {};
 124     auto fn = [&](int tid) {
 125       for (int j = tid; j < ops; j += nthreads) {
 126         hazptr_holder a[10];
 127       }
 128     };
 129     auto endFn = [] {};
 130     return run_once(nthreads, init, fn, endFn);
 131   };
 132   return bench(name, ops, repFn);
 133 }
 134
 135 inline uint64_t retireBench(std::string name, int nthreads) {
 136   struct Foo : hazptr_obj_base<Foo> {
 137     int x;
 138   };
 139   int ops = 100000;
 140   auto repFn = [&] {
 141     hazptr_holder dummy[100];
 142     auto init = [] {};
 143     auto fn = [&](int tid) {
 144       for (int j = tid; j < ops; j += nthreads) {
 145         Foo* p = new Foo;
 146         p->retire();
 147       }
 148     };
 149     auto endFn = [] {};
 150     return run_once(nthreads, init, fn, endFn);
 151   };
 152   return bench(name, ops, repFn);
 153 }
 154
 155 const int nthr[] = {1, 10};
 156 const int sizes[] = {10, 100};
 157
 158 inline void benches(std::string name) {
 159   std::cout << "------------------------------------------- " << name << "\n";
 160   for (int i : nthr) {
 161     std::cout << i << " threads -- construct/destruct 10 hazptr_holder-s"
 162               << std::endl;
 163     holderBench(name + "              ", i);
 164     holderBench(name + " - dup        ", i);
 165     std::cout << i << " threads -- allocate/retire/reclaim object" << std::endl;
 166     retireBench(name + "              ", i);
 167     retireBench(name + " - dup        ", i);
 168     for (int j : sizes) {
 169       std::cout << i << " threads -- " << j << "-item list" << std::endl;
 170       listBench(name + "              ", i, j);
 171       listBench(name + " - dup        ", i, j);
 172     }
 173   }
 174   std::cout << "----------------------------------------------------------\n";
 175 }
 176
 177 } // namespace hazptr {
 178 } // namespace folly {
 179
 180 /*
 181 ------------------------------------------- no amb - no tc
 182 1 threads -- construct/destruct 10 hazptr_holder-s
 183 no amb - no tc                 2518 ns   2461 ns   2431 ns
 184 no amb - no tc - dup           2499 ns   2460 ns   2420 ns
 185 1 threads -- allocate/retire/reclaim object
 186 no amb - no tc                   85 ns     83 ns     81 ns
 187 no amb - no tc - dup             83 ns     82 ns     81 ns
 188 1 threads -- 10-item list
 189 no amb - no tc                  655 ns    644 ns    639 ns
 190 no amb - no tc - dup            658 ns    645 ns    641 ns
 191 1 threads -- 100-item list
 192 no amb - no tc                 2175 ns   2142 ns   2124 ns
 193 no amb - no tc - dup           2294 ns   2228 ns   2138 ns
 194 10 threads -- construct/destruct 10 hazptr_holder-s
 195 no amb - no tc                 3893 ns   2932 ns   1391 ns
 196 no amb - no tc - dup           3157 ns   2927 ns   2726 ns
 197 10 threads -- allocate/retire/reclaim object
 198 no amb - no tc                  152 ns    134 ns    127 ns
 199 no amb - no tc - dup            141 ns    133 ns    128 ns
 200 10 threads -- 10-item list
 201 no amb - no tc                  532 ns    328 ns    269 ns
 202 no amb - no tc - dup            597 ns    393 ns    271 ns
 203 10 threads -- 100-item list
 204 no amb - no tc                  757 ns    573 ns    412 ns
 205 no amb - no tc - dup            819 ns    643 ns    420 ns
 206 ----------------------------------------------------------
 207 -------------------------------------------    amb - no tc
 208 1 threads -- construct/destruct 10 hazptr_holder-s
 209    amb - no tc                 2590 ns   2481 ns   2422 ns
 210    amb - no tc - dup           2519 ns   2468 ns   2424 ns
 211 1 threads -- allocate/retire/reclaim object
 212    amb - no tc                   69 ns     68 ns     67 ns
 213    amb - no tc - dup             69 ns     68 ns     67 ns
 214 1 threads -- 10-item list
 215    amb - no tc                  524 ns    510 ns    492 ns
 216    amb - no tc - dup            514 ns    507 ns    496 ns
 217 1 threads -- 100-item list
 218    amb - no tc                  761 ns    711 ns    693 ns
 219    amb - no tc - dup            717 ns    694 ns    684 ns
 220 10 threads -- construct/destruct 10 hazptr_holder-s
 221    amb - no tc                 3302 ns   2908 ns   1612 ns
 222    amb - no tc - dup           3220 ns   2909 ns   1641 ns
 223 10 threads -- allocate/retire/reclaim object
 224    amb - no tc                  129 ns    123 ns    110 ns
 225    amb - no tc - dup            135 ns    127 ns    120 ns
 226 10 threads -- 10-item list
 227    amb - no tc                  512 ns    288 ns    256 ns
 228    amb - no tc - dup            275 ns    269 ns    263 ns
 229 10 threads -- 100-item list
 230    amb - no tc                  297 ns    289 ns    284 ns
 231    amb - no tc - dup            551 ns    358 ns    282 ns
 232 ----------------------------------------------------------
 233 ------------------------------------------- no amb -    tc
 234 1 threads -- construct/destruct 10 hazptr_holder-s
 235 no amb -    tc                   56 ns     55 ns     55 ns
 236 no amb -    tc - dup             56 ns     54 ns     54 ns
 237 1 threads -- allocate/retire/reclaim object
 238 no amb -    tc                   63 ns     62 ns     62 ns
 239 no amb -    tc - dup             64 ns     63 ns     62 ns
 240 1 threads -- 10-item list
 241 no amb -    tc                  190 ns    188 ns    187 ns
 242 no amb -    tc - dup            193 ns    186 ns    182 ns
 243 1 threads -- 100-item list
 244 no amb -    tc                 1859 ns   1698 ns   1666 ns
 245 no amb -    tc - dup           1770 ns   1717 ns   1673 ns
 246 10 threads -- construct/destruct 10 hazptr_holder-s
 247 no amb -    tc                   19 ns     11 ns      7 ns
 248 no amb -    tc - dup             11 ns      8 ns      7 ns
 249 10 threads -- allocate/retire/reclaim object
 250 no amb -    tc                    9 ns      8 ns      8 ns
 251 no amb -    tc - dup             10 ns      9 ns      8 ns
 252 10 threads -- 10-item list
 253 no amb -    tc                   40 ns     25 ns     21 ns
 254 no amb -    tc - dup             24 ns     23 ns     21 ns
 255 10 threads -- 100-item list
 256 no amb -    tc                  215 ns    208 ns    188 ns
 257 no amb -    tc - dup            215 ns    209 ns    197 ns
 258 ----------------------------------------------------------
 259 -------------------------------------------    amb -    tc
 260 1 threads -- construct/destruct 10 hazptr_holder-s
 261    amb -    tc                   56 ns     54 ns     54 ns
 262    amb -    tc - dup             55 ns     54 ns     53 ns
 263 1 threads -- allocate/retire/reclaim object
 264    amb -    tc                   62 ns     61 ns     61 ns
 265    amb -    tc - dup             62 ns     61 ns     61 ns
 266 1 threads -- 10-item list
 267    amb -    tc                   36 ns     35 ns     33 ns
 268    amb -    tc - dup             37 ns     35 ns     34 ns
 269 1 threads -- 100-item list
 270    amb -    tc                  262 ns    247 ns    230 ns
 271    amb -    tc - dup            249 ns    238 ns    230 ns
 272 10 threads -- construct/destruct 10 hazptr_holder-s
 273    amb -    tc                   14 ns     12 ns     11 ns
 274    amb -    tc - dup             12 ns     11 ns     11 ns
 275 10 threads -- allocate/retire/reclaim object
 276    amb -    tc                   18 ns     17 ns     15 ns
 277    amb -    tc - dup             18 ns     17 ns     15 ns
 278 10 threads -- 10-item list
 279    amb -    tc                    9 ns      8 ns      8 ns
 280    amb -    tc - dup              8 ns      8 ns      7 ns
 281 10 threads -- 100-item list
 282    amb -    tc                   52 ns     42 ns     28 ns
 283    amb -    tc - dup             44 ns     37 ns     28 ns
 284 ----------------------------------------------------------
 285 -------------------------------------------     one domain
 286 1 threads -- construct/destruct 10 hazptr_holder-s
 287     one domain                   57 ns     56 ns     55 ns
 288     one domain - dup             56 ns     54 ns     53 ns
 289 1 threads -- allocate/retire/reclaim object
 290     one domain                   87 ns     71 ns     64 ns
 291     one domain - dup             69 ns     68 ns     68 ns
 292 1 threads -- 10-item list
 293     one domain                   32 ns     30 ns     29 ns
 294     one domain - dup             31 ns     30 ns     29 ns
 295 1 threads -- 100-item list
 296     one domain                  269 ns    238 ns    226 ns
 297     one domain - dup            237 ns    232 ns    227 ns
 298 10 threads -- construct/destruct 10 hazptr_holder-s
 299     one domain                   16 ns     12 ns     10 ns
 300     one domain - dup             11 ns     10 ns     10 ns
 301 10 threads -- allocate/retire/reclaim object
 302     one domain                   19 ns     17 ns     16 ns
 303     one domain - dup             19 ns     17 ns     15 ns
 304 10 threads -- 10-item list
 305     one domain                    6 ns      5 ns      5 ns
 306     one domain - dup              6 ns      5 ns      5 ns
 307 10 threads -- 100-item list
 308     one domain                   40 ns     39 ns     35 ns
 309     one domain - dup             40 ns     39 ns     35 ns
 310 ----------------------------------------------------------
 311  */