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