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 "statistics.h" |
17 | |
18 | #include <algorithm> |
19 | #include <cmath> |
20 | #include <numeric> |
21 | #include <string> |
22 | #include <vector> |
23 | |
24 | #include "benchmark/benchmark.h" |
25 | #include "check.h" |
26 | |
27 | namespace benchmark { |
28 | |
29 | auto StatisticsSum = [](const std::vector<double>& v) { |
30 | return std::accumulate(v.begin(), v.end(), 0.0); |
31 | }; |
32 | |
33 | double StatisticsMean(const std::vector<double>& v) { |
34 | if (v.empty()) return 0.0; |
35 | return StatisticsSum(v) * (1.0 / v.size()); |
36 | } |
37 | |
38 | double StatisticsMedian(const std::vector<double>& v) { |
39 | if (v.size() < 3) return StatisticsMean(v); |
40 | std::vector<double> copy(v); |
41 | |
42 | auto center = copy.begin() + v.size() / 2; |
43 | std::nth_element(copy.begin(), center, copy.end()); |
44 | |
45 | // did we have an odd number of samples? |
46 | // if yes, then center is the median |
47 | // it no, then we are looking for the average between center and the value |
48 | // before |
49 | if (v.size() % 2 == 1) return *center; |
50 | auto center2 = copy.begin() + v.size() / 2 - 1; |
51 | std::nth_element(copy.begin(), center2, copy.end()); |
52 | return (*center + *center2) / 2.0; |
53 | } |
54 | |
55 | // Return the sum of the squares of this sample set |
56 | auto SumSquares = [](const std::vector<double>& v) { |
57 | return std::inner_product(v.begin(), v.end(), v.begin(), 0.0); |
58 | }; |
59 | |
60 | auto Sqr = [](const double dat) { return dat * dat; }; |
61 | auto Sqrt = [](const double dat) { |
62 | // Avoid NaN due to imprecision in the calculations |
63 | if (dat < 0.0) return 0.0; |
64 | return std::sqrt(dat); |
65 | }; |
66 | |
67 | double StatisticsStdDev(const std::vector<double>& v) { |
68 | const auto mean = StatisticsMean(v); |
69 | if (v.empty()) return mean; |
70 | |
71 | // Sample standard deviation is undefined for n = 1 |
72 | if (v.size() == 1) 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 | |
78 | double StatisticsCV(const std::vector<double>& v) { |
79 | if (v.size() < 2) return 0.0; |
80 | |
81 | const auto stddev = StatisticsStdDev(v); |
82 | const auto mean = StatisticsMean(v); |
83 | |
84 | return stddev / mean; |
85 | } |
86 | |
87 | std::vector<BenchmarkReporter::Run> ComputeStats( |
88 | const std::vector<BenchmarkReporter::Run>& reports) { |
89 | typedef BenchmarkReporter::Run Run; |
90 | std::vector<Run> results; |
91 | |
92 | auto error_count = |
93 | std::count_if(reports.begin(), reports.end(), |
94 | [](Run const& run) { return run.error_occurred; }); |
95 | |
96 | if (reports.size() - error_count < 2) { |
97 | // We don't report aggregated data if there was a single run. |
98 | return results; |
99 | } |
100 | |
101 | // Accumulators. |
102 | std::vector<double> real_accumulated_time_stat; |
103 | std::vector<double> cpu_accumulated_time_stat; |
104 | |
105 | real_accumulated_time_stat.reserve(reports.size()); |
106 | cpu_accumulated_time_stat.reserve(reports.size()); |
107 | |
108 | // All repetitions should be run with the same number of iterations so we |
109 | // can take this information from the first benchmark. |
110 | const IterationCount run_iterations = reports.front().iterations; |
111 | // create stats for user counters |
112 | struct CounterStat { |
113 | Counter c; |
114 | std::vector<double> s; |
115 | }; |
116 | std::map<std::string, CounterStat> counter_stats; |
117 | for (Run const& r : reports) { |
118 | for (auto const& cnt : r.counters) { |
119 | auto it = counter_stats.find(cnt.first); |
120 | if (it == counter_stats.end()) { |
121 | counter_stats.insert({cnt.first, {cnt.second, std::vector<double>{}}}); |
122 | it = counter_stats.find(cnt.first); |
123 | it->second.s.reserve(reports.size()); |
124 | } else { |
125 | BM_CHECK_EQ(counter_stats[cnt.first].c.flags, cnt.second.flags); |
126 | } |
127 | } |
128 | } |
129 | |
130 | // Populate the accumulators. |
131 | for (Run const& run : reports) { |
132 | BM_CHECK_EQ(reports[0].benchmark_name(), run.benchmark_name()); |
133 | BM_CHECK_EQ(run_iterations, run.iterations); |
134 | if (run.error_occurred) continue; |
135 | real_accumulated_time_stat.emplace_back(run.real_accumulated_time); |
136 | cpu_accumulated_time_stat.emplace_back(run.cpu_accumulated_time); |
137 | // user counters |
138 | for (auto const& cnt : run.counters) { |
139 | auto it = counter_stats.find(cnt.first); |
140 | BM_CHECK_NE(it, counter_stats.end()); |
141 | it->second.s.emplace_back(cnt.second); |
142 | } |
143 | } |
144 | |
145 | // Only add label if it is same for all runs |
146 | std::string report_label = reports[0].report_label; |
147 | for (std::size_t i = 1; i < reports.size(); i++) { |
148 | if (reports[i].report_label != report_label) { |
149 | report_label = "" ; |
150 | break; |
151 | } |
152 | } |
153 | |
154 | const double iteration_rescale_factor = |
155 | double(reports.size()) / double(run_iterations); |
156 | |
157 | for (const auto& Stat : *reports[0].statistics) { |
158 | // Get the data from the accumulator to BenchmarkReporter::Run's. |
159 | Run data; |
160 | data.run_name = reports[0].run_name; |
161 | data.family_index = reports[0].family_index; |
162 | data.per_family_instance_index = reports[0].per_family_instance_index; |
163 | data.run_type = BenchmarkReporter::Run::RT_Aggregate; |
164 | data.threads = reports[0].threads; |
165 | data.repetitions = reports[0].repetitions; |
166 | data.repetition_index = Run::no_repetition_index; |
167 | data.aggregate_name = Stat.name_; |
168 | data.aggregate_unit = Stat.unit_; |
169 | data.report_label = report_label; |
170 | |
171 | // It is incorrect to say that an aggregate is computed over |
172 | // run's iterations, because those iterations already got averaged. |
173 | // Similarly, if there are N repetitions with 1 iterations each, |
174 | // an aggregate will be computed over N measurements, not 1. |
175 | // Thus it is best to simply use the count of separate reports. |
176 | data.iterations = reports.size(); |
177 | |
178 | data.real_accumulated_time = Stat.compute_(real_accumulated_time_stat); |
179 | data.cpu_accumulated_time = Stat.compute_(cpu_accumulated_time_stat); |
180 | |
181 | if (data.aggregate_unit == StatisticUnit::kTime) { |
182 | // We will divide these times by data.iterations when reporting, but the |
183 | // data.iterations is not necessarily the scale of these measurements, |
184 | // because in each repetition, these timers are sum over all the iters. |
185 | // And if we want to say that the stats are over N repetitions and not |
186 | // M iterations, we need to multiply these by (N/M). |
187 | data.real_accumulated_time *= iteration_rescale_factor; |
188 | data.cpu_accumulated_time *= iteration_rescale_factor; |
189 | } |
190 | |
191 | data.time_unit = reports[0].time_unit; |
192 | |
193 | // user counters |
194 | for (auto const& kv : counter_stats) { |
195 | // Do *NOT* rescale the custom counters. They are already properly scaled. |
196 | const auto uc_stat = Stat.compute_(kv.second.s); |
197 | auto c = Counter(uc_stat, counter_stats[kv.first].c.flags, |
198 | counter_stats[kv.first].c.oneK); |
199 | data.counters[kv.first] = c; |
200 | } |
201 | |
202 | results.push_back(data); |
203 | } |
204 | |
205 | return results; |
206 | } |
207 | |
208 | } // end namespace benchmark |
209 | |