Benchmarker.h 11.4 KB
Newer Older
1 2 3 4 5 6 7 8
//============================================================================
//  Copyright (c) Kitware, Inc.
//  All rights reserved.
//  See LICENSE.txt for details.
//  This software is distributed WITHOUT ANY WARRANTY; without even
//  the implied warranty of MERCHANTABILITY or FITNESS FOR A PARTICULAR
//  PURPOSE.  See the above copyright notice for more information.
//
9
//  Copyright 2014 National Technology & Engineering Solutions of Sandia, LLC (NTESS).
10 11 12
//  Copyright 2014 UT-Battelle, LLC.
//  Copyright 2014 Los Alamos National Security.
//
13
//  Under the terms of Contract DE-NA0003525 with NTESS,
14 15 16 17 18 19 20 21 22 23
//  the U.S. Government retains certain rights in this software.
//
//  Under the terms of Contract DE-AC52-06NA25396 with Los Alamos National
//  Laboratory (LANL), the U.S. Government retains certain rights in
//  this software.
//============================================================================

#ifndef vtk_m_benchmarking_Benchmarker_h
#define vtk_m_benchmarking_Benchmarker_h

24
#include <vtkm/ListTag.h>
25
#include <vtkm/Math.h>
26
#include <vtkm/cont/testing/Testing.h>
27 28 29

#include <algorithm>
#include <iostream>
30
#include <vector>
31 32 33 34 35 36 37 38 39 40 41 42 43 44 45

/*
 * Writing a Benchmark
 * -------------------
 * To write a benchmark you must provide a functor that will run the operations
 * you want to time and return the run time of those operations using the timer
 * for the device. The benchmark should also be templated on the value type being
 * operated on. Then use VTKM_MAKE_BENCHMARK to generate a maker functor and
 * VTKM_RUN_BENCHMARK to run the benchmark on a list of types.
 *
 * For Example:
 *
 * template<typename Value>
 * struct BenchSilly {
 *   // Setup anything that doesn't need to change per run in the constructor
46
 *   VTKM_CONT BenchSilly(){}
47 48 49
 *
 *   // The overloaded call operator will run the operations being timed and
 *   // return the execution time
50
 *   VTKM_CONT
51 52 53 54 55 56
 *   vtkm::Float64 operator()(){
 *     return 0.05;
 *   }
 *
 *   // The benchmark must also provide a method describing itself, this is
 *   // used when printing out run time statistics
57
 *   VTKM_CONT
58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 86 87 88 89
 *   std::string Description() const {
 *     return "A silly benchmark";
 *   }
 * };
 *
 * // Now use the VTKM_MAKE_BENCHMARK macro to generate a maker functor for
 * // your benchmark. This lets us generate the benchmark functor for each type
 * // we want to test
 * VTKM_MAKE_BENCHMARK(Silly, BenchSilly);
 *
 * // You can also optionally pass arguments to the constructor like so:
 * // VTKM_MAKE_BENCHMARK(Blah, BenchBlah, 1, 2, 3);
 * // Note that benchmark names (the first argument) must be unique so different
 * // parameters to the constructor should have different names
 *
 * // We can now run our benchmark using VTKM_RUN_BENCHMARK, passing the
 * // benchmark name and type list to run on
 * int main(int, char**){
 *   VTKM_RUN_BENCHMARK(Silly, vtkm::ListTagBase<vtkm::Float32>());
 *   return 0;
 * }
 *
 * Check out vtkm/benchmarking/BenchmarkDeviceAdapter.h for some example usage
 */

/*
 * Use the VTKM_MAKE_BENCHMARK macro to define a maker functor for your benchmark.
 * This is used to allow you to template the benchmark functor on the type being benchmarked
 * so you can write init code in the constructor. Then the maker will return a constructed
 * instance of your benchmark for the type being benchmarked. The VA_ARGS are used to
 * pass any extra arguments needed by your benchmark
 */
90 91 92 93 94 95 96 97
#define VTKM_MAKE_BENCHMARK(Name, Bench, ...)                                                      \
  struct MakeBench##Name                                                                           \
  {                                                                                                \
    template <typename Value>                                                                      \
    VTKM_CONT Bench<Value> operator()(const Value vtkmNotUsed(v)) const                            \
    {                                                                                              \
      return Bench<Value>(__VA_ARGS__);                                                            \
    }                                                                                              \
98 99 100 101 102 103 104
  }

/*
 * Use the VTKM_RUN_BENCHMARK macro to run your benchmark on the type list passed.
 * You must have previously defined a maker functor with VTKM_MAKE_BENCHMARK that this
 * macro will look for and use
 */
105
#define VTKM_RUN_BENCHMARK(Name, Types)                                                            \
106 107
  vtkm::benchmarking::BenchmarkTypes(MakeBench##Name(), (Types))

108 109 110 111 112 113
namespace vtkm
{
namespace benchmarking
{
namespace stats
{
114 115
// Checks that the sequence is sorted, returns true if it's sorted, false
// otherwise
116 117 118
template <typename ForwardIt>
bool is_sorted(ForwardIt first, ForwardIt last)
{
119 120
  ForwardIt next = first;
  ++next;
121 122 123 124
  for (; next != last; ++next, ++first)
  {
    if (*first > *next)
    {
125 126 127 128 129
      return false;
    }
  }
  return true;
}
130 131 132

// Get the value representing the `percent` percentile of the
// sorted samples using linear interpolation
133 134 135
vtkm::Float64 PercentileValue(const std::vector<vtkm::Float64>& samples,
                              const vtkm::Float64 percent)
{
136
  VTKM_ASSERT(!samples.empty());
137 138
  if (samples.size() == 1)
  {
139 140
    return samples.front();
  }
141 142
  VTKM_ASSERT(percent >= 0.0);
  VTKM_ASSERT(percent <= 100.0);
143 144 145
  VTKM_ASSERT(vtkm::benchmarking::stats::is_sorted(samples.begin(), samples.end()));
  if (percent == 100.0)
  {
146 147 148 149 150 151 152 153 154 155 156 157 158 159 160 161
    return samples.back();
  }
  // Find the two nearest percentile values and linearly
  // interpolate between them
  const vtkm::Float64 rank = percent / 100.0 * (static_cast<vtkm::Float64>(samples.size()) - 1.0);
  const vtkm::Float64 low_rank = vtkm::Floor(rank);
  const vtkm::Float64 dist = rank - low_rank;
  const size_t k = static_cast<size_t>(low_rank);
  const vtkm::Float64 low = samples[k];
  const vtkm::Float64 high = samples[k + 1];
  return low + (high - low) * dist;
}
// Winsorize the samples to clean up any very extreme outliers
// Will replace all samples below `percent` and above 100 - `percent` percentiles
// with the value at the percentile
// NOTE: Assumes the samples have been sorted, as we make use of PercentileValue
162 163
void Winsorize(std::vector<vtkm::Float64>& samples, const vtkm::Float64 percent)
{
164 165
  const vtkm::Float64 low_percentile = PercentileValue(samples, percent);
  const vtkm::Float64 high_percentile = PercentileValue(samples, 100.0 - percent);
166 167 168 169
  for (std::vector<vtkm::Float64>::iterator it = samples.begin(); it != samples.end(); ++it)
  {
    if (*it < low_percentile)
    {
170 171
      *it = low_percentile;
    }
172 173
    else if (*it > high_percentile)
    {
174 175 176 177 178
      *it = high_percentile;
    }
  }
}
// Compute the mean value of the dataset
179 180
vtkm::Float64 Mean(const std::vector<vtkm::Float64>& samples)
{
181
  vtkm::Float64 mean = 0;
182 183
  for (std::vector<vtkm::Float64>::const_iterator it = samples.begin(); it != samples.end(); ++it)
  {
184 185 186 187 188
    mean += *it;
  }
  return mean / static_cast<vtkm::Float64>(samples.size());
}
// Compute the sample variance of the samples
189 190
vtkm::Float64 Variance(const std::vector<vtkm::Float64>& samples)
{
191 192
  vtkm::Float64 mean = Mean(samples);
  vtkm::Float64 square_deviations = 0;
193 194
  for (std::vector<vtkm::Float64>::const_iterator it = samples.begin(); it != samples.end(); ++it)
  {
195 196 197 198 199
    square_deviations += vtkm::Pow(*it - mean, 2.0);
  }
  return square_deviations / (static_cast<vtkm::Float64>(samples.size()) - 1.0);
}
// Compute the standard deviation of the samples
200 201
vtkm::Float64 StandardDeviation(const std::vector<vtkm::Float64>& samples)
{
202 203 204
  return vtkm::Sqrt(Variance(samples));
}
// Compute the median absolute deviation of the dataset
205 206
vtkm::Float64 MedianAbsDeviation(const std::vector<vtkm::Float64>& samples)
{
207 208 209
  std::vector<vtkm::Float64> abs_deviations;
  abs_deviations.reserve(samples.size());
  const vtkm::Float64 median = PercentileValue(samples, 50.0);
210 211
  for (std::vector<vtkm::Float64>::const_iterator it = samples.begin(); it != samples.end(); ++it)
  {
212 213
    abs_deviations.push_back(vtkm::Abs(*it - median));
  }
214
  std::sort(abs_deviations.begin(), abs_deviations.end());
215 216 217 218 219 220 221 222 223 224 225
  return PercentileValue(abs_deviations, 50.0);
}
} // stats

/*
 * The benchmarker takes a functor to benchmark and runs it multiple times,
 * printing out statistics of the run time at the end.
 * The functor passed should return the run time of the thing being benchmarked
 * in seconds, this lets us avoid including any per-run setup time in the benchmark.
 * However any one-time setup should be done in the functor's constructor
 */
226
class Benchmarker
227
{
228 229
  std::vector<vtkm::Float64> Samples;
  std::string BenchmarkName;
230

231 232 233 234 235 236 237 238
  const vtkm::Float64 MaxRuntime;
  const size_t MaxIterations;

public:
  VTKM_CONT
  Benchmarker(vtkm::Float64 maxRuntime = 30, std::size_t maxIterations = 100)
    : MaxRuntime(maxRuntime)
    , MaxIterations(maxIterations)
239 240
  {
  }
241

242
  template <typename Functor>
243
  VTKM_CONT void GatherSamples(Functor func)
244
  {
245 246 247
    this->Samples.clear();
    this->BenchmarkName = func.Description();

248 249 250 251 252
    // Do a warm-up run. If the benchmark allocates any additional memory
    // eg. storage for output results, this will let it do that and
    // allow us to avoid measuring the allocation time in the actual benchmark run
    func();

253 254
    this->Samples.reserve(this->MaxIterations);

255
    // Run each benchmark for MAX_RUNTIME seconds or MAX_ITERATIONS iterations, whichever
256
    // takes less time. This kind of assumes that running for 500 iterations or 30s will give
257 258 259
    // good statistics, but if median abs dev and/or std dev are too high both these limits
    // could be increased
    size_t iter = 0;
260 261
    for (vtkm::Float64 elapsed = 0.0; elapsed < this->MaxRuntime && iter < this->MaxIterations;
         elapsed += this->Samples.back(), ++iter)
262
    {
263
      this->Samples.push_back(func());
264
    }
265 266 267 268 269 270 271 272 273 274 275 276 277 278 279 280 281 282 283 284 285 286 287 288 289 290 291 292 293 294 295 296 297 298 299 300 301

    std::sort(this->Samples.begin(), this->Samples.end());
    stats::Winsorize(this->Samples, 5.0);
  }

  VTKM_CONT void PrintSummary(std::ostream& out = std::cout)
  {
    out << "Benchmark \'" << this->BenchmarkName << "\' results:\n";

    if (this->Samples.empty())
    {
      out << "\tNo samples gathered!\n";
      return;
    }

    out << "\tnumSamples = " << this->Samples.size() << "\n"
        << "\tmedian = " << stats::PercentileValue(this->Samples, 50.0) << "s\n"
        << "\tmedian abs dev = " << stats::MedianAbsDeviation(this->Samples) << "s\n"
        << "\tmean = " << stats::Mean(this->Samples) << "s\n"
        << "\tstd dev = " << stats::StandardDeviation(this->Samples) << "s\n"
        << "\tmin = " << this->Samples.front() << "s\n"
        << "\tmax = " << this->Samples.back() << "s\n";
  }

  template <typename Functor>
  VTKM_CONT void operator()(Functor func)
  {
    this->GatherSamples(func);
    this->PrintSummary();
  }

  VTKM_CONT const std::vector<vtkm::Float64>& GetSamples() const { return this->Samples; }

  VTKM_CONT void Reset()
  {
    this->Samples.clear();
    this->BenchmarkName.clear();
302 303 304
  }
};

305 306 307
template <typename MakerFunctor>
class InternalPrintTypeAndBench
{
308 309 310
  MakerFunctor Maker;

public:
311
  VTKM_CONT
312 313 314 315
  InternalPrintTypeAndBench(MakerFunctor maker)
    : Maker(maker)
  {
  }
316

317 318 319 320
  template <typename T>
  VTKM_CONT void operator()(T t) const
  {
    std::cout << "*** " << vtkm::testing::TypeName<T>::Name() << " ***************" << std::endl;
321 322 323 324 325
    Benchmarker bench;
    bench(Maker(t));
  }
};

326 327 328
template <class MakerFunctor, class TypeList>
VTKM_CONT void BenchmarkTypes(const MakerFunctor& maker, TypeList)
{
329 330 331 332 333 334
  vtkm::ListForEach(InternalPrintTypeAndBench<MakerFunctor>(maker), TypeList());
}
}
}

#endif