libartbase/base/histogram-inl.h - LeafOS-Project/android_art - Gitiles

 /*
  * 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_
	/*
	* 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_