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