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   for (int i = 0; i < size; ++i) {
  37     s.add(i);
  38   }
  39
  40   std::vector<std::thread> threads(nthreads);
  41   for (int tid = 0; tid < nthreads; ++tid) {
  42     threads[tid] = std::thread([&, tid] {
  43       started.fetch_add(1);
  44       while (!start.load())
  45         /* spin */;
  46
  47       for (int j = tid; j < ops; j += nthreads) {
  48         s.contains(j);
  49       }
  50     });
  51   }
  52
  53   while (started.load() < nthreads)
  54     /* spin */;
  55
  56   // begin time measurement
  57   auto tbegin = std::chrono::steady_clock::now();
  58   susp.dismiss();
  59   start.store(true);
  60
  61   for (auto& t : threads) {
  62     t.join();
  63   }
  64
  65   susp.rehire();
  66   // end time measurement
  67   uint64_t duration = 0;
  68   auto tend = std::chrono::steady_clock::now();
  69   duration = std::chrono::duration_cast<std::chrono::nanoseconds>(tend - tbegin)
  70                  .count();
  71   return duration;
  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
 111 1 threads -- 10-item list
 112 no amb                          210 ns    204 ns    202 ns
 113 no amb - dup                    213 ns    207 ns    203 ns
 114 1 threads -- 100-item list
 115 no amb                         1862 ns   1810 ns   1778 ns
 116 no amb - dup                   1791 ns   1785 ns   1777 ns
 117 10 threads -- 10-item list
 118 no amb                          227 ns    161 ns    143 ns
 119 no amb - dup                    145 ns    144 ns    143 ns
 120 10 threads -- 100-item list
 121 no amb                          520 ns    518 ns    515 ns
 122 no amb - dup                    684 ns    536 ns    516 ns
 123 ----------------------------------------------------------
 124 ------------------------------------------------------ AMB
 125 1 threads -- 10-item list
 126 amb                              48 ns     46 ns     45 ns
 127 amb - dup                        47 ns     45 ns     45 ns
 128 1 threads -- 100-item list
 129 amb                             242 ns    236 ns    234 ns
 130 amb - dup                       243 ns    238 ns    234 ns
 131 10 threads -- 10-item list
 132 amb                             226 ns    130 ns    109 ns
 133 amb - dup                       161 ns    115 ns    109 ns
 134 10 threads -- 100-item list
 135 amb                             192 ns    192 ns    191 ns
 136 amb - dup                       416 ns    324 ns    192 ns
 137 ----------------------------------------------------------
 138  */