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