blob: 4ea30ada24d9cf2783c038734ce655732b6e53b6 [file] [log] [blame]
/*
* Copyright 2016 Google Inc. All Rights Reserved.
*
* 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 COBALT_BASE_C_VAL_TIME_INTERVAL_ENTRY_STATS_H_
#define COBALT_BASE_C_VAL_TIME_INTERVAL_ENTRY_STATS_H_
#include <algorithm>
#include <cmath>
#include <limits>
#include <string>
#include "base/logging.h"
#include "base/stringprintf.h"
#include "base/time.h"
#include "cobalt/base/c_val.h"
namespace base {
namespace detail {
template <typename T>
double ToDouble(T value) {
return static_cast<double>(value);
}
template <>
inline double ToDouble<base::TimeDelta>(base::TimeDelta value) {
return static_cast<double>(value.InMicroseconds());
}
template <typename T>
T FromDouble(double value) {
return static_cast<T>(value);
}
template <>
inline base::TimeDelta FromDouble<base::TimeDelta>(double value) {
return base::TimeDelta::FromMicroseconds(static_cast<int64>(value));
}
template <typename T>
T Max() {
return std::numeric_limits<T>::max();
}
template <>
inline base::TimeDelta Max<base::TimeDelta>() {
return base::TimeDelta::Max();
}
template <typename T>
T Min() {
return std::numeric_limits<T>::min();
}
template <>
inline base::TimeDelta Min<base::TimeDelta>() {
return -base::TimeDelta::Max();
}
} // namespace detail
// This class tracks entries over a specified time period. When the time period
// has elapsed, the average, minimum, maximum, and standard deviation of that
// time period are recorded with CVals, and the tracking resets for the next
// time period.
template <typename EntryType, typename Visibility = CValDebug>
class CValTimeIntervalEntryStats {
public:
CValTimeIntervalEntryStats(const std::string& name,
int64 time_interval_in_ms);
void AddEntry(const EntryType& value);
void AddEntry(const EntryType& value, const base::TimeTicks& now);
private:
void AddToActiveEntryStats(const EntryType& value);
void ResetActiveEntryStats();
const int64 time_interval_in_ms_;
// CVals of the stats for the previously completed time interval.
base::CVal<EntryType, Visibility> average_;
base::CVal<EntryType, Visibility> minimum_;
base::CVal<EntryType, Visibility> maximum_;
base::CVal<EntryType, Visibility> standard_deviation_;
// Active time interval-related
base::TimeTicks active_start_time_;
// Variance calculations are based upon the following:
// https://en.wikipedia.org/wiki/Algorithms_for_calculating_variance#Computing_shifted_data
// Each value is shifted by an estimated mean when calculating the variance.
// This increases accuracy in cases where the variance is small but the values
// involved are extremely large.
// The following article provides a more detailed discussion on the topic:
// http://www.cs.yale.edu/publications/techreports/tr222.pdf
// During the first time interval, the initial entry acts as the estimated
// mean. All subsequent loops use the mean of the previous time interval.
double active_estimated_mean_;
// Stats updated with each new entry.
int64 active_count_;
double active_shifted_sum_;
double active_shifted_sum_squares_;
EntryType active_minimum_;
EntryType active_maximum_;
};
template <typename EntryType, typename Visibility>
CValTimeIntervalEntryStats<EntryType, Visibility>::CValTimeIntervalEntryStats(
const std::string& name, int64 time_interval_in_ms)
: time_interval_in_ms_(time_interval_in_ms),
average_(StringPrintf("%s.Avg", name.c_str()), EntryType(),
"Average time."),
minimum_(StringPrintf("%s.Min", name.c_str()), EntryType(),
"Minimum time."),
maximum_(StringPrintf("%s.Max", name.c_str()), EntryType(),
"Maximum time."),
standard_deviation_(StringPrintf("%s.Std", name.c_str()), EntryType(),
"Standard deviation of times."),
active_estimated_mean_(0) {
ResetActiveEntryStats();
}
template <typename EntryType, typename Visibility>
void CValTimeIntervalEntryStats<EntryType, Visibility>::AddEntry(
const EntryType& value) {
base::TimeTicks now = base::TimeTicks::Now();
AddEntry(value, now);
}
template <typename EntryType, typename Visibility>
void CValTimeIntervalEntryStats<EntryType, Visibility>::AddEntry(
const EntryType& value, const base::TimeTicks& now) {
// Check to see if the timer hasn't started yet. This happens when this is
// the first entry ever added. In this case, the timer is simply started and
// the estimated mean is set to the passed in value.
if (active_start_time_.is_null()) {
active_start_time_ = now;
active_estimated_mean_ = detail::ToDouble(value);
// Otherwise, check for the time interval having ended. If it has, then the
// CVals are updated using the active stats, the active stats are reset, and
// the timer restarted.
} else if ((now - active_start_time_).InMilliseconds() >
time_interval_in_ms_) {
// The active count can never be 0 when a time interval has ended. There
// must always be at least one entry when the time is non-null.
DCHECK_GT(active_count_, 0);
double active_shifted_mean = active_shifted_sum_ / active_count_;
average_ = detail::FromDouble<EntryType>(active_estimated_mean_ +
active_shifted_mean);
// The equation comes from the following:
// https://en.wikipedia.org/wiki/Algorithms_for_calculating_variance#Computing_shifted_data
double variance =
(active_shifted_sum_squares_ -
((active_shifted_sum_ * active_shifted_sum_) / active_count_)) /
active_count_;
variance = std::max(variance, 0.0);
standard_deviation_ = detail::FromDouble<EntryType>(std::sqrt(variance));
minimum_ = active_minimum_;
maximum_ = active_maximum_;
// Prepare the active data for the next time interval, including updating
// the estimated mean with the calculated mean of the previous time
// interval.
active_start_time_ = now;
active_estimated_mean_ += active_shifted_mean;
ResetActiveEntryStats();
}
AddToActiveEntryStats(value);
}
template <typename EntryType, typename Visibility>
void CValTimeIntervalEntryStats<EntryType, Visibility>::AddToActiveEntryStats(
const EntryType& value) {
++active_count_;
double shifted_value_as_double =
detail::ToDouble(value) - active_estimated_mean_;
active_shifted_sum_ += shifted_value_as_double;
active_shifted_sum_squares_ +=
shifted_value_as_double * shifted_value_as_double;
if (value < active_minimum_) {
active_minimum_ = value;
}
if (value > active_maximum_) {
active_maximum_ = value;
}
}
template <typename EntryType, typename Visibility>
void CValTimeIntervalEntryStats<EntryType,
Visibility>::ResetActiveEntryStats() {
active_count_ = 0;
active_shifted_sum_ = 0;
active_shifted_sum_squares_ = 0;
active_minimum_ = detail::Max<EntryType>();
active_maximum_ = detail::Min<EntryType>();
}
} // namespace base
#endif // COBALT_BASE_C_VAL_TIME_INTERVAL_ENTRY_STATS_H_