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