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