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