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
AddValue(Value value)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>
Histogram(const char * name,Value initial_bucket_width,size_t max_buckets)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>
GrowBuckets(Value new_max)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
FindBucket(Value val)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>
BucketiseValue(Value val)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
Initialize()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
GetBucketCount()106 template <class Value> inline size_t Histogram<Value>::GetBucketCount() const {
107 return frequency_.size();
108 }
109
Reset()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
GetRange(size_t bucket_idx)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
Mean()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
Variance()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>
PrintBins(std::ostream & os,const CumulativeData & data)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>
PrintConfidenceIntervals(std::ostream & os,double interval,const CumulativeData & data)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
CreateHistogram(CumulativeData & out_data)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>
Percentile(double per,const CumulativeData & data)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