1// Copyright 2016 Ismael Jimenez Martinez. All rights reserved.
2// Copyright 2017 Roman Lebedev. All rights reserved.
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#include "benchmark/benchmark.h"
17
18#include <algorithm>
19#include <cmath>
20#include <string>
21#include <vector>
22#include <numeric>
23#include "check.h"
24#include "statistics.h"
25
26namespace benchmark {
27
28auto StatisticsSum = [](const std::vector<double>& v) {
29  return std::accumulate(v.begin(), v.end(), 0.0);
30};
31
32double StatisticsMean(const std::vector<double>& v) {
33  if (v.empty()) return 0.0;
34  return StatisticsSum(v) * (1.0 / v.size());
35}
36
37double StatisticsMedian(const std::vector<double>& v) {
38  if (v.size() < 3) return StatisticsMean(v);
39  std::vector<double> copy(v);
40
41  auto center = copy.begin() + v.size() / 2;
42  std::nth_element(copy.begin(), center, copy.end());
43
44  // did we have an odd number of samples?
45  // if yes, then center is the median
46  // it no, then we are looking for the average between center and the value before
47  if(v.size() % 2 == 1)
48    return *center;
49  auto center2 = copy.begin() + v.size() / 2 - 1;
50  std::nth_element(copy.begin(), center2, copy.end());
51  return (*center + *center2) / 2.0;
52}
53
54// Return the sum of the squares of this sample set
55auto SumSquares = [](const std::vector<double>& v) {
56  return std::inner_product(v.begin(), v.end(), v.begin(), 0.0);
57};
58
59auto Sqr = [](const double dat) { return dat * dat; };
60auto Sqrt = [](const double dat) {
61  // Avoid NaN due to imprecision in the calculations
62  if (dat < 0.0) return 0.0;
63  return std::sqrt(dat);
64};
65
66double StatisticsStdDev(const std::vector<double>& v) {
67  const auto mean = StatisticsMean(v);
68  if (v.empty()) return mean;
69
70  // Sample standard deviation is undefined for n = 1
71  if (v.size() == 1)
72    return 0.0;
73
74  const double avg_squares = SumSquares(v) * (1.0 / v.size());
75  return Sqrt(v.size() / (v.size() - 1.0) * (avg_squares - Sqr(mean)));
76}
77
78std::vector<BenchmarkReporter::Run> ComputeStats(
79    const std::vector<BenchmarkReporter::Run>& reports) {
80  typedef BenchmarkReporter::Run Run;
81  std::vector<Run> results;
82
83  auto error_count =
84      std::count_if(reports.begin(), reports.end(),
85                    [](Run const& run) { return run.error_occurred; });
86
87  if (reports.size() - error_count < 2) {
88    // We don't report aggregated data if there was a single run.
89    return results;
90  }
91
92  // Accumulators.
93  std::vector<double> real_accumulated_time_stat;
94  std::vector<double> cpu_accumulated_time_stat;
95  std::vector<double> bytes_per_second_stat;
96  std::vector<double> items_per_second_stat;
97
98  real_accumulated_time_stat.reserve(reports.size());
99  cpu_accumulated_time_stat.reserve(reports.size());
100  bytes_per_second_stat.reserve(reports.size());
101  items_per_second_stat.reserve(reports.size());
102
103  // All repetitions should be run with the same number of iterations so we
104  // can take this information from the first benchmark.
105  int64_t const run_iterations = reports.front().iterations;
106  // create stats for user counters
107  struct CounterStat {
108    Counter c;
109    std::vector<double> s;
110  };
111  std::map< std::string, CounterStat > counter_stats;
112  for(Run const& r : reports) {
113    for(auto const& cnt : r.counters) {
114      auto it = counter_stats.find(cnt.first);
115      if(it == counter_stats.end()) {
116        counter_stats.insert({cnt.first, {cnt.second, std::vector<double>{}}});
117        it = counter_stats.find(cnt.first);
118        it->second.s.reserve(reports.size());
119      } else {
120        CHECK_EQ(counter_stats[cnt.first].c.flags, cnt.second.flags);
121      }
122    }
123  }
124
125  // Populate the accumulators.
126  for (Run const& run : reports) {
127    CHECK_EQ(reports[0].benchmark_name, run.benchmark_name);
128    CHECK_EQ(run_iterations, run.iterations);
129    if (run.error_occurred) continue;
130    real_accumulated_time_stat.emplace_back(run.real_accumulated_time);
131    cpu_accumulated_time_stat.emplace_back(run.cpu_accumulated_time);
132    items_per_second_stat.emplace_back(run.items_per_second);
133    bytes_per_second_stat.emplace_back(run.bytes_per_second);
134    // user counters
135    for(auto const& cnt : run.counters) {
136      auto it = counter_stats.find(cnt.first);
137      CHECK_NE(it, counter_stats.end());
138      it->second.s.emplace_back(cnt.second);
139    }
140  }
141
142  // Only add label if it is same for all runs
143  std::string report_label = reports[0].report_label;
144  for (std::size_t i = 1; i < reports.size(); i++) {
145    if (reports[i].report_label != report_label) {
146      report_label = "";
147      break;
148    }
149  }
150
151  for(const auto& Stat : *reports[0].statistics) {
152    // Get the data from the accumulator to BenchmarkReporter::Run's.
153    Run data;
154    data.benchmark_name = reports[0].benchmark_name + "_" + Stat.name_;
155    data.report_label = report_label;
156    data.iterations = run_iterations;
157
158    data.real_accumulated_time = Stat.compute_(real_accumulated_time_stat);
159    data.cpu_accumulated_time = Stat.compute_(cpu_accumulated_time_stat);
160    data.bytes_per_second = Stat.compute_(bytes_per_second_stat);
161    data.items_per_second = Stat.compute_(items_per_second_stat);
162
163    data.time_unit = reports[0].time_unit;
164
165    // user counters
166    for(auto const& kv : counter_stats) {
167      const auto uc_stat = Stat.compute_(kv.second.s);
168      auto c = Counter(uc_stat, counter_stats[kv.first].c.flags);
169      data.counters[kv.first] = c;
170    }
171
172    results.push_back(data);
173  }
174
175  return results;
176}
177
178}  // end namespace benchmark
179