1 /* 2 * Copyright (C) 2013 The Android Open Source Project 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 17 #ifndef ART_RUNTIME_BASE_HISTOGRAM_INL_H_ 18 #define ART_RUNTIME_BASE_HISTOGRAM_INL_H_ 19 20 #include <algorithm> 21 #include <cmath> 22 #include <limits> 23 #include <ostream> 24 25 #include "histogram.h" 26 27 #include "base/bit_utils.h" 28 #include "base/time_utils.h" 29 #include "utils.h" 30 31 namespace art { 32 33 template <class Value> inline void Histogram<Value>::AddValue(Value value) { 34 CHECK_GE(value, static_cast<Value>(0)); 35 if (value >= max_) { 36 Value new_max = ((value + 1) / bucket_width_ + 1) * bucket_width_; 37 DCHECK_GT(new_max, max_); 38 GrowBuckets(new_max); 39 } 40 BucketiseValue(value); 41 } 42 43 template <class Value> inline void Histogram<Value>::AdjustAndAddValue(Value value) { 44 AddValue(value / kAdjust); 45 } 46 47 template <class Value> inline Histogram<Value>::Histogram(const char* name) 48 : kAdjust(0), 49 kInitialBucketCount(0), 50 name_(name), 51 max_buckets_(0) { 52 } 53 54 template <class Value> 55 inline Histogram<Value>::Histogram(const char* name, Value initial_bucket_width, 56 size_t max_buckets) 57 : kAdjust(1000), 58 kInitialBucketCount(8), 59 name_(name), 60 max_buckets_(max_buckets), 61 bucket_width_(initial_bucket_width) { 62 Reset(); 63 } 64 65 template <class Value> 66 inline void Histogram<Value>::GrowBuckets(Value new_max) { 67 while (max_ < new_max) { 68 // If we have reached the maximum number of buckets, merge buckets together. 69 if (frequency_.size() >= max_buckets_) { 70 CHECK_ALIGNED(frequency_.size(), 2); 71 // We double the width of each bucket to reduce the number of buckets by a factor of 2. 72 bucket_width_ *= 2; 73 const size_t limit = frequency_.size() / 2; 74 // Merge the frequencies by adding each adjacent two together. 75 for (size_t i = 0; i < limit; ++i) { 76 frequency_[i] = frequency_[i * 2] + frequency_[i * 2 + 1]; 77 } 78 // Remove frequencies in the second half of the array which were added to the first half. 79 while (frequency_.size() > limit) { 80 frequency_.pop_back(); 81 } 82 } 83 max_ += bucket_width_; 84 frequency_.push_back(0); 85 } 86 } 87 88 template <class Value> inline size_t Histogram<Value>::FindBucket(Value val) const { 89 // Since this is only a linear histogram, bucket index can be found simply with 90 // dividing the value by the bucket width. 91 DCHECK_GE(val, min_); 92 DCHECK_LE(val, max_); 93 const size_t bucket_idx = static_cast<size_t>((val - min_) / bucket_width_); 94 DCHECK_GE(bucket_idx, 0ul); 95 DCHECK_LE(bucket_idx, GetBucketCount()); 96 return bucket_idx; 97 } 98 99 template <class Value> 100 inline void Histogram<Value>::BucketiseValue(Value val) { 101 CHECK_LT(val, max_); 102 sum_ += val; 103 sum_of_squares_ += val * val; 104 ++sample_size_; 105 ++frequency_[FindBucket(val)]; 106 max_value_added_ = std::max(val, max_value_added_); 107 min_value_added_ = std::min(val, min_value_added_); 108 } 109 110 template <class Value> inline void Histogram<Value>::Initialize() { 111 for (size_t idx = 0; idx < kInitialBucketCount; idx++) { 112 frequency_.push_back(0); 113 } 114 // Cumulative frequency and ranges has a length of 1 over frequency. 115 max_ = bucket_width_ * GetBucketCount(); 116 } 117 118 template <class Value> inline size_t Histogram<Value>::GetBucketCount() const { 119 return frequency_.size(); 120 } 121 122 template <class Value> inline void Histogram<Value>::Reset() { 123 sum_of_squares_ = 0; 124 sample_size_ = 0; 125 min_ = 0; 126 sum_ = 0; 127 min_value_added_ = std::numeric_limits<Value>::max(); 128 max_value_added_ = std::numeric_limits<Value>::min(); 129 frequency_.clear(); 130 Initialize(); 131 } 132 133 template <class Value> inline Value Histogram<Value>::GetRange(size_t bucket_idx) const { 134 DCHECK_LE(bucket_idx, GetBucketCount()); 135 return min_ + bucket_idx * bucket_width_; 136 } 137 138 template <class Value> inline double Histogram<Value>::Mean() const { 139 DCHECK_GT(sample_size_, 0ull); 140 return static_cast<double>(sum_) / static_cast<double>(sample_size_); 141 } 142 143 template <class Value> inline double Histogram<Value>::Variance() const { 144 DCHECK_GT(sample_size_, 0ull); 145 // Using algorithms for calculating variance over a population: 146 // http://en.wikipedia.org/wiki/Algorithms_for_calculating_variance 147 Value sum_squared = sum_ * sum_; 148 double sum_squared_by_n_squared = 149 static_cast<double>(sum_squared) / 150 static_cast<double>(sample_size_ * sample_size_); 151 double sum_of_squares_by_n = 152 static_cast<double>(sum_of_squares_) / static_cast<double>(sample_size_); 153 return sum_of_squares_by_n - sum_squared_by_n_squared; 154 } 155 156 template <class Value> 157 inline void Histogram<Value>::PrintBins(std::ostream& os, const CumulativeData& data) const { 158 DCHECK_GT(sample_size_, 0ull); 159 for (size_t bin_idx = 0; bin_idx < data.freq_.size(); ++bin_idx) { 160 if (bin_idx > 0 && data.perc_[bin_idx] == data.perc_[bin_idx - 1]) { 161 bin_idx++; 162 continue; 163 } 164 os << GetRange(bin_idx) << ": " << data.freq_[bin_idx] << "\t" 165 << data.perc_[bin_idx] * 100.0 << "%\n"; 166 } 167 } 168 169 template <class Value> 170 inline void Histogram<Value>::DumpBins(std::ostream& os) const { 171 DCHECK_GT(sample_size_, 0ull); 172 bool dumped_one = false; 173 for (size_t bin_idx = 0; bin_idx < frequency_.size(); ++bin_idx) { 174 if (frequency_[bin_idx] != 0U) { 175 if (dumped_one) { 176 // Prepend a comma if not the first bin. 177 os << ","; 178 } else { 179 dumped_one = true; 180 } 181 os << GetRange(bin_idx) << ":" << frequency_[bin_idx]; 182 } 183 } 184 } 185 186 template <class Value> 187 inline void Histogram<Value>::PrintConfidenceIntervals(std::ostream &os, double interval, 188 const CumulativeData& data) const { 189 static constexpr size_t kFractionalDigits = 3; 190 DCHECK_GT(interval, 0); 191 DCHECK_LT(interval, 1.0); 192 const double per_0 = (1.0 - interval) / 2.0; 193 const double per_1 = per_0 + interval; 194 const TimeUnit unit = GetAppropriateTimeUnit(Mean() * kAdjust); 195 os << Name() << ":\tSum: " << PrettyDuration(Sum() * kAdjust) << " " 196 << (interval * 100) << "% C.I. " << FormatDuration(Percentile(per_0, data) * kAdjust, unit, 197 kFractionalDigits) 198 << "-" << FormatDuration(Percentile(per_1, data) * kAdjust, unit, kFractionalDigits) << " " 199 << "Avg: " << FormatDuration(Mean() * kAdjust, unit, kFractionalDigits) << " Max: " 200 << FormatDuration(Max() * kAdjust, unit, kFractionalDigits) << "\n"; 201 } 202 203 template <class Value> 204 inline void Histogram<Value>::PrintMemoryUse(std::ostream &os) const { 205 os << Name() 206 << ": Avg: " << PrettySize(Mean()) << " Max: " 207 << PrettySize(Max()) << " Min: " << PrettySize(Min()) << "\n"; 208 } 209 210 template <class Value> 211 inline void Histogram<Value>::CreateHistogram(CumulativeData* out_data) const { 212 DCHECK_GT(sample_size_, 0ull); 213 out_data->freq_.clear(); 214 out_data->perc_.clear(); 215 uint64_t accumulated = 0; 216 out_data->freq_.push_back(accumulated); 217 out_data->perc_.push_back(0.0); 218 for (size_t idx = 0; idx < frequency_.size(); idx++) { 219 accumulated += frequency_[idx]; 220 out_data->freq_.push_back(accumulated); 221 out_data->perc_.push_back(static_cast<double>(accumulated) / static_cast<double>(sample_size_)); 222 } 223 DCHECK_EQ(out_data->freq_.back(), sample_size_); 224 DCHECK_LE(std::abs(out_data->perc_.back() - 1.0), 0.001); 225 } 226 227 #if defined(__clang__) 228 #pragma clang diagnostic push 229 #pragma clang diagnostic ignored "-Wfloat-equal" 230 #endif 231 232 template <class Value> 233 inline double Histogram<Value>::Percentile(double per, const CumulativeData& data) const { 234 DCHECK_GT(data.perc_.size(), 0ull); 235 size_t upper_idx = 0, lower_idx = 0; 236 for (size_t idx = 0; idx < data.perc_.size(); idx++) { 237 if (per <= data.perc_[idx]) { 238 upper_idx = idx; 239 break; 240 } 241 242 if (per >= data.perc_[idx] && idx != 0 && data.perc_[idx] != data.perc_[idx - 1]) { 243 lower_idx = idx; 244 } 245 } 246 247 const double lower_perc = data.perc_[lower_idx]; 248 const double lower_value = static_cast<double>(GetRange(lower_idx)); 249 if (per == lower_perc) { 250 return lower_value; 251 } 252 253 const double upper_perc = data.perc_[upper_idx]; 254 const double upper_value = static_cast<double>(GetRange(upper_idx)); 255 if (per == upper_perc) { 256 return upper_value; 257 } 258 DCHECK_GT(upper_perc, lower_perc); 259 260 double value = lower_value + (upper_value - lower_value) * 261 (per - lower_perc) / (upper_perc - lower_perc); 262 263 if (value < min_value_added_) { 264 value = min_value_added_; 265 } else if (value > max_value_added_) { 266 value = max_value_added_; 267 } 268 269 return value; 270 } 271 272 #if defined(__clang__) 273 #pragma clang diagnostic pop 274 #endif 275 276 } // namespace art 277 #endif // ART_RUNTIME_BASE_HISTOGRAM_INL_H_ 278
