blob: ba2b75a29262605c74cb76cdf66d9c81219d8ac8 [file] [log] [blame]
/*
* 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 ART_LIBARTBASE_BASE_HISTOGRAM_INL_H_
#define ART_LIBARTBASE_BASE_HISTOGRAM_INL_H_
#include <algorithm>
#include <cmath>
#include <limits>
#include <ostream>
#include "histogram.h"
#include <android-base/logging.h>
#include "bit_utils.h"
#include "time_utils.h"
#include "utils.h"
namespace art {
template <class Value> inline void Histogram<Value>::AddValue(Value value) {
CHECK_GE(value, static_cast<Value>(0));
if (value >= max_) {
Value new_max = ((value + 1) / bucket_width_ + 1) * bucket_width_;
DCHECK_GT(new_max, max_);
GrowBuckets(new_max);
}
BucketiseValue(value);
}
template <class Value> inline void Histogram<Value>::AdjustAndAddValue(Value value) {
AddValue(value / kAdjust);
}
template <class Value> inline Histogram<Value>::Histogram(const char* name)
: kAdjust(0),
kInitialBucketCount(0),
name_(name),
max_buckets_(0),
sample_size_(0) {
}
template <class Value>
inline Histogram<Value>::Histogram(const char* name, Value initial_bucket_width,
size_t max_buckets)
: kAdjust(1000),
kInitialBucketCount(kMinBuckets),
name_(name),
max_buckets_(max_buckets),
bucket_width_(initial_bucket_width) {
CHECK_GE(max_buckets, kInitialBucketCount);
CHECK_EQ(max_buckets_ % 2, 0u);
Reset();
}
template <class Value>
inline void Histogram<Value>::GrowBuckets(Value new_max) {
while (max_ < new_max) {
// If we have reached the maximum number of buckets, merge buckets together.
DCHECK_LE(frequency_.size(), max_buckets_);
if (frequency_.size() == max_buckets_) {
DCHECK_EQ(frequency_.size() % 2, 0u);
// We double the width of each bucket to reduce the number of buckets by a factor of 2.
bucket_width_ *= 2;
const size_t limit = frequency_.size() / 2;
// Merge the frequencies by adding each adjacent two together.
for (size_t i = 0; i < limit; ++i) {
frequency_[i] = frequency_[i * 2] + frequency_[i * 2 + 1];
}
// Remove frequencies in the second half of the array which were added to the first half.
while (frequency_.size() > limit) {
frequency_.pop_back();
}
}
max_ += bucket_width_;
frequency_.push_back(0);
}
}
template <class Value> inline size_t Histogram<Value>::FindBucket(Value val) const {
// 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_);
const size_t bucket_idx = static_cast<size_t>((val - min_) / bucket_width_);
DCHECK_GE(bucket_idx, 0ul);
DCHECK_LE(bucket_idx, GetBucketCount());
return bucket_idx;
}
template <class Value>
inline void Histogram<Value>::BucketiseValue(Value val) {
CHECK_LT(val, max_);
sum_ += val;
sum_of_squares_ += val * val;
++sample_size_;
++frequency_[FindBucket(val)];
max_value_added_ = std::max(val, max_value_added_);
min_value_added_ = std::min(val, min_value_added_);
}
template <class Value> inline void Histogram<Value>::Initialize() {
for (size_t idx = 0; idx < kInitialBucketCount; idx++) {
frequency_.push_back(0);
}
// Cumulative frequency and ranges has a length of 1 over frequency.
max_ = bucket_width_ * GetBucketCount();
}
template <class Value> inline size_t Histogram<Value>::GetBucketCount() const {
return frequency_.size();
}
template <class Value> inline void Histogram<Value>::Reset() {
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();
frequency_.clear();
Initialize();
}
template <class Value> inline Value Histogram<Value>::GetRange(size_t bucket_idx) const {
DCHECK_LE(bucket_idx, GetBucketCount());
return min_ + bucket_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, const CumulativeData& data) const {
DCHECK_GT(sample_size_, 0ull);
for (size_t bin_idx = 0; bin_idx < data.freq_.size(); ++bin_idx) {
if (bin_idx > 0 && data.perc_[bin_idx] == data.perc_[bin_idx - 1]) {
bin_idx++;
continue;
}
os << GetRange(bin_idx) << ": " << data.freq_[bin_idx] << "\t"
<< data.perc_[bin_idx] * 100.0 << "%\n";
}
}
template <class Value>
inline void Histogram<Value>::DumpBins(std::ostream& os) const {
DCHECK_GT(sample_size_, 0ull);
bool dumped_one = false;
for (size_t bin_idx = 0; bin_idx < frequency_.size(); ++bin_idx) {
if (frequency_[bin_idx] != 0U) {
if (dumped_one) {
// Prepend a comma if not the first bin.
os << ",";
} else {
dumped_one = true;
}
os << GetRange(bin_idx) << ":" << frequency_[bin_idx];
}
}
}
template <class Value>
inline void Histogram<Value>::PrintConfidenceIntervals(std::ostream &os, double interval,
const CumulativeData& data) const {
static constexpr size_t kFractionalDigits = 3;
DCHECK_GT(interval, 0);
DCHECK_LT(interval, 1.0);
const double per_0 = (1.0 - interval) / 2.0;
const double per_1 = per_0 + interval;
const TimeUnit unit = GetAppropriateTimeUnit(Mean() * kAdjust);
os << Name() << ":\tSum: " << PrettyDuration(Sum() * kAdjust) << " "
<< (interval * 100) << "% C.I. " << FormatDuration(Percentile(per_0, data) * kAdjust, unit,
kFractionalDigits)
<< "-" << FormatDuration(Percentile(per_1, data) * kAdjust, unit, kFractionalDigits) << " "
<< "Avg: " << FormatDuration(Mean() * kAdjust, unit, kFractionalDigits) << " Max: "
<< FormatDuration(Max() * kAdjust, unit, kFractionalDigits) << std::endl;
}
template <class Value>
inline void Histogram<Value>::PrintMemoryUse(std::ostream &os) const {
os << Name();
if (sample_size_ != 0u) {
os << ": Avg: " << PrettySize(Mean()) << " Max: "
<< PrettySize(Max()) << " Min: " << PrettySize(Min()) << "\n";
} else {
os << ": <no data>\n";
}
}
template <class Value>
inline void Histogram<Value>::CreateHistogram(CumulativeData* out_data) const {
DCHECK_GT(sample_size_, 0ull);
out_data->freq_.clear();
out_data->perc_.clear();
uint64_t accumulated = 0;
out_data->freq_.push_back(accumulated);
out_data->perc_.push_back(0.0);
for (size_t idx = 0; idx < frequency_.size(); idx++) {
accumulated += frequency_[idx];
out_data->freq_.push_back(accumulated);
out_data->perc_.push_back(static_cast<double>(accumulated) / static_cast<double>(sample_size_));
}
DCHECK_EQ(out_data->freq_.back(), sample_size_);
DCHECK_LE(std::abs(out_data->perc_.back() - 1.0), 0.001);
}
#pragma clang diagnostic push
#pragma clang diagnostic ignored "-Wfloat-equal"
template <class Value>
inline double Histogram<Value>::Percentile(double per, const CumulativeData& data) const {
DCHECK_GT(data.perc_.size(), 0ull);
size_t upper_idx = 0, lower_idx = 0;
for (size_t idx = 0; idx < data.perc_.size(); idx++) {
if (per <= data.perc_[idx]) {
upper_idx = idx;
break;
}
if (per >= data.perc_[idx] && idx != 0 && data.perc_[idx] != data.perc_[idx - 1]) {
lower_idx = idx;
}
}
const double lower_perc = data.perc_[lower_idx];
const double lower_value = static_cast<double>(GetRange(lower_idx));
if (per == lower_perc) {
return lower_value;
}
const double upper_perc = data.perc_[upper_idx];
const double upper_value = static_cast<double>(GetRange(upper_idx));
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;
}
#pragma clang diagnostic pop
} // namespace art
#endif // ART_LIBARTBASE_BASE_HISTOGRAM_INL_H_