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 
26 namespace benchmark {
27 
__anonc70b07770102(const std::vector<double>& v) 28 auto StatisticsSum = [](const std::vector<double>& v) {
29   return std::accumulate(v.begin(), v.end(), 0.0);
30 };
31 
StatisticsMean(const std::vector<double> & v)32 double StatisticsMean(const std::vector<double>& v) {
33   if (v.empty()) return 0.0;
34   return StatisticsSum(v) * (1.0 / v.size());
35 }
36 
StatisticsMedian(const std::vector<double> & v)37 double 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
__anonc70b07770202(const std::vector<double>& v) 55 auto SumSquares = [](const std::vector<double>& v) {
56   return std::inner_product(v.begin(), v.end(), v.begin(), 0.0);
57 };
58 
__anonc70b07770302(const double dat) 59 auto Sqr = [](const double dat) { return dat * dat; };
__anonc70b07770402(const double dat) 60 auto 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 
StatisticsStdDev(const std::vector<double> & v)66 double 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 
ComputeStats(const std::vector<BenchmarkReporter::Run> & reports)78 std::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