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 const int ops = 1000000;
  99
 100 inline uint64_t listBench(std::string name, int nthreads, int size) {
 101   auto repFn = [&] {
 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   auto repFn = [&] {
 121     auto init = [] {};
 122     auto fn = [&](int tid) {
 123       for (int j = tid; j < ops; j += nthreads) {
 124         hazptr_holder a[10];
 125       }
 126     };
 127     auto endFn = [] {};
 128     return run_once(nthreads, init, fn, endFn);
 129   };
 130   return bench(name, ops, repFn);
 131 }
 132
 133 template <size_t M>
 134 inline uint64_t arrayBench(std::string name, int nthreads) {
 135   auto repFn = [&] {
 136     auto init = [] {};
 137     auto fn = [&](int tid) {
 138       for (int j = tid; j < 10 * ops; j += nthreads) {
 139         hazptr_array<M> a;
 140       }
 141     };
 142     auto endFn = [] {};
 143     return run_once(nthreads, init, fn, endFn);
 144   };
 145   return bench(name, ops, repFn);
 146 }
 147
 148 template <size_t M>
 149 inline uint64_t localBench(std::string name, int nthreads) {
 150   auto repFn = [&] {
 151     auto init = [] {};
 152     auto fn = [&](int tid) {
 153       for (int j = tid; j < 10 * ops; j += nthreads) {
 154         hazptr_local<10> a;
 155       }
 156     };
 157     auto endFn = [] {};
 158     return run_once(nthreads, init, fn, endFn);
 159   };
 160   return bench(name, ops, repFn);
 161 }
 162
 163 inline uint64_t retireBench(std::string name, int nthreads) {
 164   struct Foo : hazptr_obj_base<Foo> {
 165     int x;
 166   };
 167   auto repFn = [&] {
 168     auto init = [] {};
 169     auto fn = [&](int tid) {
 170       for (int j = tid; j < ops; j += nthreads) {
 171         Foo* p = new Foo;
 172         p->retire();
 173       }
 174     };
 175     auto endFn = [] {};
 176     return run_once(nthreads, init, fn, endFn);
 177   };
 178   return bench(name, ops, repFn);
 179 }
 180
 181 const int nthr[] = {1, 10};
 182 const int sizes[] = {10, 100};
 183
 184 inline void benches(std::string name) {
 185   std::cout << "------------------------------------------- " << name << "\n";
 186   for (int i : nthr) {
 187     std::cout << i << " threads -- 10x construct/destruct hazptr_holder"
 188               << std::endl;
 189     holderBench(name + "              ", i);
 190     holderBench(name + " - dup        ", i);
 191     std::cout << i << " threads -- 10x construct/destruct hazptr_array<10>"
 192               << std::endl;
 193     arrayBench<10>(name + "              ", i);
 194     arrayBench<10>(name + " - dup        ", i);
 195     std::cout << i << " threads -- 10x construct/destruct hazptr_array<3>"
 196               << std::endl;
 197     arrayBench<3>(name + "              ", i);
 198     arrayBench<3>(name + " - dup        ", i);
 199     std::cout << i << " threads -- 10x construct/destruct hazptr_local<10>"
 200               << std::endl;
 201     localBench<10>(name + "              ", i);
 202     localBench<10>(name + " - dup        ", i);
 203     std::cout << i << " threads -- 10x construct/destruct hazptr_local<1>"
 204               << std::endl;
 205     localBench<1>(name + "              ", i);
 206     localBench<1>(name + " - dup        ", i);
 207     std::cout << i << " threads -- allocate/retire/reclaim object" << std::endl;
 208     retireBench(name + "              ", i);
 209     retireBench(name + " - dup        ", i);
 210     for (int j : sizes) {
 211       std::cout << i << " threads -- " << j << "-item list" << std::endl;
 212       listBench(name + "              ", i, j);
 213       listBench(name + " - dup        ", i, j);
 214     }
 215   }
 216   std::cout << "----------------------------------------------------------\n";
 217 }
 218
 219 } // namespace hazptr
 220 } // namespace folly
 221
 222 /*
 223 -------------------------------------------    amb -    tc
 224 1 threads -- 10x construct/destruct hazptr_holder
 225    amb -    tc                   49 ns     46 ns     44 ns
 226    amb -    tc - dup             47 ns     45 ns     44 ns
 227 1 threads -- 10x construct/destruct hazptr_array<10>
 228    amb -    tc                  132 ns    122 ns    117 ns
 229    amb -    tc - dup            130 ns    122 ns    117 ns
 230 1 threads -- 10x construct/destruct hazptr_array<3>
 231    amb -    tc                   66 ns     64 ns     63 ns
 232    amb -    tc - dup             64 ns     64 ns     63 ns
 233 1 threads -- 10x construct/destruct hazptr_local<10>
 234    amb -    tc                   29 ns     27 ns     27 ns
 235    amb -    tc - dup             28 ns     27 ns     27 ns
 236 1 threads -- 10x construct/destruct hazptr_local<1>
 237    amb -    tc                   27 ns     27 ns     27 ns
 238    amb -    tc - dup             28 ns     28 ns     27 ns
 239 1 threads -- allocate/retire/reclaim object
 240    amb -    tc                   65 ns     62 ns     60 ns
 241    amb -    tc - dup             65 ns     60 ns     59 ns
 242 1 threads -- 10-item list
 243    amb -    tc                   21 ns     21 ns     20 ns
 244    amb -    tc - dup             22 ns     21 ns     21 ns
 245 1 threads -- 100-item list
 246    amb -    tc                  229 ns    224 ns    220 ns
 247    amb -    tc - dup            223 ns    219 ns    216 ns
 248 10 threads -- 10x construct/destruct hazptr_holder
 249    amb -    tc                    9 ns      8 ns      7 ns
 250    amb -    tc - dup              9 ns      8 ns      8 ns
 251 10 threads -- 10x construct/destruct hazptr_array<10>
 252    amb -    tc                   27 ns     23 ns     15 ns
 253    amb -    tc - dup             26 ns     20 ns     13 ns
 254 10 threads -- 10x construct/destruct hazptr_array<3>
 255    amb -    tc                   11 ns     11 ns      7 ns
 256    amb -    tc - dup             11 ns      9 ns      7 ns
 257 10 threads -- 10x construct/destruct hazptr_local<10>
 258    amb -    tc                    5 ns      3 ns      3 ns
 259    amb -    tc - dup              3 ns      3 ns      3 ns
 260 10 threads -- 10x construct/destruct hazptr_local<1>
 261    amb -    tc                    3 ns      3 ns      3 ns
 262    amb -    tc - dup              5 ns      4 ns      3 ns
 263 10 threads -- allocate/retire/reclaim object
 264    amb -    tc                   17 ns     15 ns     14 ns
 265    amb -    tc - dup             17 ns     15 ns     14 ns
 266 10 threads -- 10-item list
 267    amb -    tc                    4 ns      4 ns      2 ns
 268    amb -    tc - dup              4 ns      4 ns      3 ns
 269 10 threads -- 100-item list
 270    amb -    tc                   33 ns     31 ns     24 ns
 271    amb -    tc - dup             33 ns     32 ns     30 ns
 272 ----------------------------------------------------------
 273 ------------------------------------------- no amb - no tc
 274 1 threads -- construct/destruct 10 hazptr_holder-s
 275 no amb - no tc                 2518 ns   2461 ns   2431 ns
 276 no amb - no tc - dup           2499 ns   2460 ns   2420 ns
 277 1 threads -- allocate/retire/reclaim object
 278 no amb - no tc                   85 ns     83 ns     81 ns
 279 no amb - no tc - dup             83 ns     82 ns     81 ns
 280 1 threads -- 10-item list
 281 no amb - no tc                  655 ns    644 ns    639 ns
 282 no amb - no tc - dup            658 ns    645 ns    641 ns
 283 1 threads -- 100-item list
 284 no amb - no tc                 2175 ns   2142 ns   2124 ns
 285 no amb - no tc - dup           2294 ns   2228 ns   2138 ns
 286 10 threads -- construct/destruct 10 hazptr_holder-s
 287 no amb - no tc                 3893 ns   2932 ns   1391 ns
 288 no amb - no tc - dup           3157 ns   2927 ns   2726 ns
 289 10 threads -- allocate/retire/reclaim object
 290 no amb - no tc                  152 ns    134 ns    127 ns
 291 no amb - no tc - dup            141 ns    133 ns    128 ns
 292 10 threads -- 10-item list
 293 no amb - no tc                  532 ns    328 ns    269 ns
 294 no amb - no tc - dup            597 ns    393 ns    271 ns
 295 10 threads -- 100-item list
 296 no amb - no tc                  757 ns    573 ns    412 ns
 297 no amb - no tc - dup            819 ns    643 ns    420 ns
 298 ----------------------------------------------------------
 299 -------------------------------------------    amb - no tc
 300 1 threads -- construct/destruct 10 hazptr_holder-s
 301    amb - no tc                 2590 ns   2481 ns   2422 ns
 302    amb - no tc - dup           2519 ns   2468 ns   2424 ns
 303 1 threads -- allocate/retire/reclaim object
 304    amb - no tc                   69 ns     68 ns     67 ns
 305    amb - no tc - dup             69 ns     68 ns     67 ns
 306 1 threads -- 10-item list
 307    amb - no tc                  524 ns    510 ns    492 ns
 308    amb - no tc - dup            514 ns    507 ns    496 ns
 309 1 threads -- 100-item list
 310    amb - no tc                  761 ns    711 ns    693 ns
 311    amb - no tc - dup            717 ns    694 ns    684 ns
 312 10 threads -- construct/destruct 10 hazptr_holder-s
 313    amb - no tc                 3302 ns   2908 ns   1612 ns
 314    amb - no tc - dup           3220 ns   2909 ns   1641 ns
 315 10 threads -- allocate/retire/reclaim object
 316    amb - no tc                  129 ns    123 ns    110 ns
 317    amb - no tc - dup            135 ns    127 ns    120 ns
 318 10 threads -- 10-item list
 319    amb - no tc                  512 ns    288 ns    256 ns
 320    amb - no tc - dup            275 ns    269 ns    263 ns
 321 10 threads -- 100-item list
 322    amb - no tc                  297 ns    289 ns    284 ns
 323    amb - no tc - dup            551 ns    358 ns    282 ns
 324 ----------------------------------------------------------
 325 ------------------------------------------- no amb -    tc
 326 1 threads -- construct/destruct 10 hazptr_holder-s
 327 no amb -    tc                   56 ns     55 ns     55 ns
 328 no amb -    tc - dup             56 ns     54 ns     54 ns
 329 1 threads -- allocate/retire/reclaim object
 330 no amb -    tc                   63 ns     62 ns     62 ns
 331 no amb -    tc - dup             64 ns     63 ns     62 ns
 332 1 threads -- 10-item list
 333 no amb -    tc                  190 ns    188 ns    187 ns
 334 no amb -    tc - dup            193 ns    186 ns    182 ns
 335 1 threads -- 100-item list
 336 no amb -    tc                 1859 ns   1698 ns   1666 ns
 337 no amb -    tc - dup           1770 ns   1717 ns   1673 ns
 338 10 threads -- construct/destruct 10 hazptr_holder-s
 339 no amb -    tc                   19 ns     11 ns      7 ns
 340 no amb -    tc - dup             11 ns      8 ns      7 ns
 341 10 threads -- allocate/retire/reclaim object
 342 no amb -    tc                    9 ns      8 ns      8 ns
 343 no amb -    tc - dup             10 ns      9 ns      8 ns
 344 10 threads -- 10-item list
 345 no amb -    tc                   40 ns     25 ns     21 ns
 346 no amb -    tc - dup             24 ns     23 ns     21 ns
 347 10 threads -- 100-item list
 348 no amb -    tc                  215 ns    208 ns    188 ns
 349 no amb -    tc - dup            215 ns    209 ns    197 ns
 350 ----------------------------------------------------------
 351  */