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