diff options
Diffstat (limited to 'runtime/base/histogram-inl.h')
| -rw-r--r-- | runtime/base/histogram-inl.h | 255 |
1 files changed, 255 insertions, 0 deletions
diff --git a/runtime/base/histogram-inl.h b/runtime/base/histogram-inl.h new file mode 100644 index 000000000..9514209c1 --- /dev/null +++ b/runtime/base/histogram-inl.h @@ -0,0 +1,255 @@ +/* + * Copyright (C) 2013 The Android Open Source Project + * + * Licensed under the Apache License, Version 2.0 (the "License"); + * you may not use this file except in compliance with the License. + * You may obtain a copy of the License at + * + * http://www.apache.org/licenses/LICENSE-2.0 + * + * Unless required by applicable law or agreed to in writing, software + * distributed under the License is distributed on an "AS IS" BASIS, + * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied. + * See the License for the specific language governing permissions and + * limitations under the License. + */ + +#ifndef SRC_BASE_HISTOGRAM_INL_H_ +#define SRC_BASE_HISTOGRAM_INL_H_ + +#include "histogram.h" + +#include "utils.h" + +#include <algorithm> +#include <cmath> +#include <limits> +#include <ostream> + +namespace art { + +template <class Value> inline void Histogram<Value>::AddValue(Value value) { + CHECK_GE(value, 0.0); + if (value >= max_) { + Value new_max = ((value + 1) / bucket_width_ + 1) * bucket_width_; + DCHECK_GT(new_max, max_); + GrowBuckets(new_max); + } + + BucketiseValue(value); + new_values_added_ = true; +} + +template <class Value> +inline Histogram<Value>::Histogram(const std::string name) + : kAdjust(1000), + kBucketWidth(5), + kInitialBucketCount(10), + bucket_width_(kBucketWidth), + bucket_count_(kInitialBucketCount) { + name_ = name; + Reset(); +} + +template <class Value> +inline void Histogram<Value>::GrowBuckets(Value new_max) { + while (max_ < new_max) { + max_ += bucket_width_; + ranges_.push_back(max_); + frequency_.push_back(0); + bucket_count_++; + } +} + +template <class Value> inline size_t Histogram<Value>::FindBucket(Value val) { + // Since this is only a linear histogram, bucket index can be found simply with + // dividing the value by the bucket width. + DCHECK_GE(val, min_); + DCHECK_LE(val, max_); + size_t bucket_idx = static_cast<size_t>((double)(val - min_) / bucket_width_); + DCHECK_GE(bucket_idx, 0ul); + DCHECK_LE(bucket_idx, bucket_count_); + return bucket_idx; +} + +template <class Value> +inline void Histogram<Value>::BucketiseValue(Value value) { + CHECK_LT(value, max_); + sum_ += value; + sum_of_squares_ += value * value; + size_t bucket_idx = FindBucket(value); + sample_size_++; + if (value > max_value_added_) { + max_value_added_ = value; + } + if (value < min_value_added_) { + min_value_added_ = value; + } + frequency_[bucket_idx]++; +} + +template <class Value> inline void Histogram<Value>::Initialize() { + DCHECK_GT(bucket_count_, 0ul); + size_t idx = 0; + for (; idx < bucket_count_; idx++) { + ranges_.push_back(min_ + static_cast<Value>(idx) * (bucket_width_)); + frequency_.push_back(0); + } + // Cumulative frequency and ranges has a length of 1 over frequency. + ranges_.push_back(min_ + idx * bucket_width_); + max_ = bucket_width_ * bucket_count_; +} + +template <class Value> inline void Histogram<Value>::Reset() { + bucket_width_ = kBucketWidth; + bucket_count_ = kInitialBucketCount; + max_ = bucket_width_ * bucket_count_; + sum_of_squares_ = 0; + sample_size_ = 0; + min_ = 0; + sum_ = 0; + min_value_added_ = std::numeric_limits<Value>::max(); + max_value_added_ = std::numeric_limits<Value>::min(); + new_values_added_ = false; + ranges_.clear(); + frequency_.clear(); + cumulative_freq_.clear(); + cumulative_perc_.clear(); + Initialize(); +} + +template <class Value> inline void Histogram<Value>::BuildRanges() { + for (size_t idx = 0; idx < bucket_count_; ++idx) { + ranges_.push_back(min_ + idx * bucket_width_); + } +} + +template <class Value> inline double Histogram<Value>::Mean() const { + DCHECK_GT(sample_size_, 0ull); + return static_cast<double>(sum_) / static_cast<double>(sample_size_); +} + +template <class Value> inline double Histogram<Value>::Variance() const { + DCHECK_GT(sample_size_, 0ull); + // Using algorithms for calculating variance over a population: + // http://en.wikipedia.org/wiki/Algorithms_for_calculating_variance + Value sum_squared = sum_ * sum_; + double sum_squared_by_n_squared = + static_cast<double>(sum_squared) / + static_cast<double>(sample_size_ * sample_size_); + double sum_of_squares_by_n = + static_cast<double>(sum_of_squares_) / static_cast<double>(sample_size_); + return sum_of_squares_by_n - sum_squared_by_n_squared; +} + +template <class Value> +inline void Histogram<Value>::PrintBins(std::ostream &os) { + DCHECK_GT(sample_size_, 0ull); + DCHECK(!new_values_added_); + size_t bin_idx = 0; + while (bin_idx < cumulative_freq_.size()) { + if (bin_idx > 0 && + cumulative_perc_[bin_idx] == cumulative_perc_[bin_idx - 1]) { + bin_idx++; + continue; + } + os << ranges_[bin_idx] << ": " << cumulative_freq_[bin_idx] << "\t" + << cumulative_perc_[bin_idx] * 100.0 << "%\n"; + bin_idx++; + } +} + +template <class Value> +inline void Histogram<Value>::PrintConfidenceIntervals(std::ostream &os, + double interval) const { + DCHECK_GT(interval, 0); + DCHECK_LT(interval, 1.0); + + double per_0 = (1.0 - interval) / 2.0; + double per_1 = per_0 + interval; + os << Name() << ":\t"; + TimeUnit unit = GetAppropriateTimeUnit(Mean() * kAdjust); + os << (interval * 100) << "% C.I. " + << FormatDuration(Percentile(per_0) * kAdjust, unit); + os << "-" << FormatDuration(Percentile(per_1) * kAdjust, unit) << " "; + os << "Avg: " << FormatDuration(Mean() * kAdjust, unit) << " Max: "; + os << FormatDuration(Max() * kAdjust, unit) << "\n"; +} + +template <class Value> inline void Histogram<Value>::BuildCDF() { + DCHECK_EQ(cumulative_freq_.size(), 0ull); + DCHECK_EQ(cumulative_perc_.size(), 0ull); + uint64_t accumulated = 0; + + cumulative_freq_.push_back(accumulated); + cumulative_perc_.push_back(0.0); + for (size_t idx = 0; idx < frequency_.size(); idx++) { + accumulated += frequency_[idx]; + cumulative_freq_.push_back(accumulated); + cumulative_perc_.push_back(static_cast<double>(accumulated) / + static_cast<double>(sample_size_)); + } + DCHECK_EQ(*(cumulative_freq_.end() - 1), sample_size_); + DCHECK_EQ(*(cumulative_perc_.end() - 1), 1.0); +} + +template <class Value> inline void Histogram<Value>::CreateHistogram() { + DCHECK_GT(sample_size_, 0ull); + + // Create a histogram only if new values are added. + if (!new_values_added_) + return; + + // Reset cumulative values in case this is not the first time creating histogram. + cumulative_freq_.clear(); + cumulative_perc_.clear(); + BuildCDF(); + new_values_added_ = false; +} + +template <class Value> +inline double Histogram<Value>::Percentile(double per) const { + DCHECK_GT(cumulative_perc_.size(), 0ull); + size_t idx, upper_idx = 0, lower_idx = 0; + for (idx = 0; idx < cumulative_perc_.size(); idx++) { + + if (per <= cumulative_perc_[idx]) { + upper_idx = idx; + break; + } + + if (per >= cumulative_perc_[idx] && idx != 0 && + cumulative_perc_[idx] != cumulative_perc_[idx - 1]) { + lower_idx = idx; + } + } + + double upper_value = static_cast<double>(ranges_[upper_idx]); + double lower_value = static_cast<double>(ranges_[lower_idx]); + + double lower_perc = cumulative_perc_[lower_idx]; + double upper_perc = cumulative_perc_[upper_idx]; + + if (per == lower_perc) { + return lower_value; + } + if (per == upper_perc) { + return upper_value; + } + DCHECK_GT(upper_perc, lower_perc); + + double value = lower_value + (upper_value - lower_value) * + (per - lower_perc) / (upper_perc - lower_perc); + + if (value < min_value_added_) { + value = min_value_added_; + } else if (value > max_value_added_) { + value = max_value_added_; + } + + return value; +} + +} // namespace art +#endif // SRC_BASE_HISTOGRAM_INL_H_ + |