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