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