cobalt/base/c_val_collection_entry_stats.h - cobalt - Git at Google

 // Copyright 2017 The Cobalt Authors. 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_COLLECTION_ENTRY_STATS_H_
 #define COBALT_BASE_C_VAL_COLLECTION_ENTRY_STATS_H_

 #include <algorithm>
 #include <cmath>
 #include <memory>
 #include <numeric>
 #include <sstream>
 #include <string>
 #include <vector>

 #include "base/callback.h"
 #include "base/logging.h"
 #include "base/strings/stringprintf.h"
 #include "base/time/time.h"
 #include "cobalt/base/c_val.h"

 namespace base {
 namespace CValDetail {

 // This struct contains the data generated by flushes of
 // CValCollectionEntryStats for use with callbacks.
 template <typename EntryType>
 struct CValCollectionEntryStatsFlushResults {
   typedef base::Callback<void(const CValCollectionEntryStatsFlushResults&)>
       OnFlushCallback;

   CValCollectionEntryStatsFlushResults(size_t sample_count, EntryType average,
                                        EntryType minimum, EntryType maximum,
                                        EntryType standard_deviation,
                                        EntryType percentile_25th,
                                        EntryType percentile_50th,
                                        EntryType percentile_75th,
                                        EntryType percentile_95th)
       : sample_count(sample_count),
         average(average),
         minimum(minimum),
         maximum(maximum),
         standard_deviation(standard_deviation),
         percentile_25th(percentile_25th),
         percentile_50th(percentile_50th),
         percentile_75th(percentile_75th),
         percentile_95th(percentile_95th) {}

   size_t sample_count;
   EntryType average;
   EntryType minimum;
   EntryType maximum;
   EntryType standard_deviation;
   EntryType percentile_25th;
   EntryType percentile_50th;
   EntryType percentile_75th;
   EntryType percentile_95th;
 };

 // This class tracks a collection of entries, which it retains in memory. When
 // either the max size of the collection is reached or Flush() is manually
 // called, the count, average, minimum, maximum, 25th, 50th, 75th and 95th
 // percentiles, and standard deviation of the collection are recorded with
 // CVals, and the tracking resets in preparation for the next collection of
 // entries.
 // NOTE1: By default there is no max size and the collection will continue to
 //        grow indefinitely until Flush() is called.
 // NOTE2: This class keeps all of the entries in memory until flush is called so
 //        that percentiles can be determined. In cases where the number of
 //        entries is extremely large, |CValTimeIntervalEntryStats| is more
 //        appropriate, as it does its tracking without keeping entries in memory
 //        (at the cost of not being able to provide percentiles);
 // NOTE3: This class provides the ability to record all entries within a single
 //        string CVal when |enable_entry_list_c_val| is set to true in the
 //        constructor. By default, this CVal is not used.
 template <typename EntryType, typename Visibility = CValDebug>
 class CValCollectionEntryStatsImpl {
  public:
   static const size_t kNoMaxSize = 0;

   typedef CValCollectionEntryStatsFlushResults<EntryType> FlushResults;
   typedef typename FlushResults::OnFlushCallback OnFlushCallback;

   CValCollectionEntryStatsImpl(
       const std::string& name, size_t max_size = kNoMaxSize,
       bool enable_entry_list_c_val = false,
       const OnFlushCallback& on_flush = OnFlushCallback());

   // Add an entry to the collection. This may trigger a Flush() if adding the
   // entry causes the max size to be reached.
   void AddEntry(const EntryType& value);
   // Manually flush the collection's entries. This updates the stat cvals and
   // clears the entries.
   void Flush();

  private:
   typedef std::vector<EntryType> CollectionType;

   static EntryType CalculatePercentile(const CollectionType& sorted_collection,
                                        int percentile);
   static double CalculateStandardDeviation(const CollectionType& collection,
                                            double mean);

   // Constructs a string representing the entries within the collection and
   // populates |entry_list_| with it if the entry list CVal was enabled during
   // construction.
   void PopulateEntryList();

   // The maximum size of the collection before Flush() is automatically called.
   const size_t max_size_;

   // Callback to call whenever the values are flushed.
   const OnFlushCallback on_flush_;

   // The current collection of entries. These will be used to generate the cval
   // stats during the next call of Flush().
   CollectionType collection_;

   // CVals of the stats for the previous collection.
   base::CVal<size_t, Visibility> count_;
   base::CVal<EntryType, Visibility> average_;
   base::CVal<EntryType, Visibility> minimum_;
   base::CVal<EntryType, Visibility> maximum_;
   base::CVal<EntryType, Visibility> percentile_25th_;
   base::CVal<EntryType, Visibility> percentile_50th_;
   base::CVal<EntryType, Visibility> percentile_75th_;
   base::CVal<EntryType, Visibility> percentile_95th_;
   base::CVal<EntryType, Visibility> standard_deviation_;
   // |entry_list_| is only non-NULL when it is enabled.
   std::unique_ptr<base::CVal<std::string, Visibility> > entry_list_;
 };

 template <typename EntryType, typename Visibility>
 CValCollectionEntryStatsImpl<EntryType, Visibility>::
     CValCollectionEntryStatsImpl(
         const std::string& name, size_t max_size /*=kNoMaxSize*/,
         bool enable_entry_list_c_val /*=false*/,
         const OnFlushCallback& on_flush /*=OnFlushCallback()*/)
     : max_size_(max_size),
       on_flush_(on_flush),
       count_(base::StringPrintf("%s.Cnt", name.c_str()), 0, "Total entries."),
       average_(base::StringPrintf("%s.Avg", name.c_str()), EntryType(),
                "Average value."),
       minimum_(base::StringPrintf("%s.Min", name.c_str()), EntryType(),
                "Minimum value."),
       maximum_(base::StringPrintf("%s.Max", name.c_str()), EntryType(),
                "Maximum value."),
       percentile_25th_(base::StringPrintf("%s.Pct.25th", name.c_str()),
                        EntryType(), "25th percentile value."),
       percentile_50th_(base::StringPrintf("%s.Pct.50th", name.c_str()),
                        EntryType(), "50th percentile value."),
       percentile_75th_(base::StringPrintf("%s.Pct.75th", name.c_str()),
                        EntryType(), "75th percentile value."),
       percentile_95th_(base::StringPrintf("%s.Pct.95th", name.c_str()),
                        EntryType(), "95th percentile value."),
       standard_deviation_(base::StringPrintf("%s.Std", name.c_str()),
                           EntryType(), "Standard deviation of values.") {
   if (enable_entry_list_c_val) {
     entry_list_.reset(new base::CVal<std::string, Visibility>(
         base::StringPrintf("%s.EntryList", name.c_str()), "[]",
         "The list of entries in the collection."));
   }
 }

 template <typename EntryType, typename Visibility>
 void CValCollectionEntryStatsImpl<EntryType, Visibility>::AddEntry(
     const EntryType& value) {
   collection_.push_back(value);
   if (collection_.size() == max_size_) {
     Flush();
   }
 }

 template <typename EntryType, typename Visibility>
 void CValCollectionEntryStatsImpl<EntryType, Visibility>::Flush() {
   if (collection_.size() == 0) {
     return;
   }

   // Populate the entry list cval before the collection is sorted.
   PopulateEntryList();

   // Sort the collection. This allows min, max, and percentiles to be easily
   // determined.
   std::sort(collection_.begin(), collection_.end());

   // Calculate the mean of the collection.
   EntryType sum = std::accumulate(collection_.begin(), collection_.end(),
                                   CValDetail::FromDouble<EntryType>(0));
   double mean = CValDetail::ToDouble<EntryType>(sum) / collection_.size();

   // Update the collection stat cvals.
   size_t count = collection_.size();
   EntryType average = CValDetail::FromDouble<EntryType>(mean);
   EntryType minimum = collection_.front();
   EntryType maximum = collection_.back();
   EntryType percentile_25th = CalculatePercentile(collection_, 25);
   EntryType percentile_50th = CalculatePercentile(collection_, 50);
   EntryType percentile_75th = CalculatePercentile(collection_, 75);
   EntryType percentile_95th = CalculatePercentile(collection_, 95);
   EntryType standard_deviation = CValDetail::FromDouble<EntryType>(
       CalculateStandardDeviation(collection_, mean));

   // Flush the computed values out to the CVals.
   count_ = count;
   average_ = average;
   minimum_ = minimum;
   maximum_ = maximum;
   percentile_25th_ = percentile_25th;
   percentile_50th_ = percentile_50th;
   percentile_75th_ = percentile_75th;
   percentile_95th_ = percentile_95th;
   standard_deviation_ = standard_deviation;

   collection_.clear();

   // Callback to any listeners with the flush values.
   if (!on_flush_.is_null()) {
     on_flush_.Run(FlushResults(
         count, average, minimum, maximum, standard_deviation, percentile_25th,
         percentile_50th, percentile_75th, percentile_95th));
   }
 }

 template <typename EntryType, typename Visibility>
 EntryType
 CValCollectionEntryStatsImpl<EntryType, Visibility>::CalculatePercentile(
     const CollectionType& sorted_collection, int percentile) {
   DCHECK_GT(sorted_collection.size(), 0);
   DCHECK(percentile >= 0 && percentile <= 100);

   // Determine the position of the percentile within the collection.
   double percentile_position =
       (sorted_collection.size() - 1) * static_cast<double>(percentile) * 0.01;

   // Split out the integral and fractional parts of the percentile position.
   double percentile_integral_position, percentile_fractional_position;
   percentile_fractional_position =
       std::modf(percentile_position, &percentile_integral_position);

   int percentile_first_index = static_cast<int>(percentile_integral_position);

   // If |percentile_first_index| maps to the last entry, then there is no
   // second entry and there's nothing to interpolate; simply use the last entry.
   if (sorted_collection.size() == percentile_first_index + 1) {
     return sorted_collection.back();
   }

   // Interpolate between the two entries that the percentile falls between.
   double first_data_point = CValDetail::ToDouble<EntryType>(
                                 sorted_collection[percentile_first_index]) *
                             (1.0 - percentile_fractional_position);
   double second_data_point =
       CValDetail::ToDouble<EntryType>(
           sorted_collection[percentile_first_index + 1]) *
       percentile_fractional_position;

   return CValDetail::FromDouble<EntryType>(first_data_point +
                                            second_data_point);
 }

 template <typename EntryType, typename Visibility>
 double
 CValCollectionEntryStatsImpl<EntryType, Visibility>::CalculateStandardDeviation(
     const CollectionType& collection, double mean) {
   if (collection.size() <= 1) {
     return 0;
   }

   double dif_squared_sum = 0;
   for (size_t i = 0; i < collection.size(); ++i) {
     double dif = CValDetail::ToDouble<EntryType>(collection[i]) - mean;
     dif_squared_sum += dif * dif;
   }

   double variance =
       dif_squared_sum / static_cast<double>(collection.size() - 1);

   return std::sqrt(variance);
 }

 template <typename EntryType, typename Visibility>
 void CValCollectionEntryStatsImpl<EntryType, Visibility>::PopulateEntryList() {
   // If the entry list was not enabled, then |entry_list_| will be NULL and
   // there is nothing to do. Simply return.
   if (!entry_list_) {
     return;
   }

   // Construct a string containing a list representation of the collection
   // entries and set the entry list CVal to it.
   std::ostringstream oss;
   oss << "[";
   for (size_t i = 0; i < collection_.size(); ++i) {
     if (i > 0) {
       oss << ", ";
     }
     oss << CValDetail::ValToString<EntryType>(collection_[i]);
   }
   oss << "]";
   *entry_list_ = oss.str();
 }

 #if !defined(ENABLE_DEBUG_C_VAL)
 // This is a stub class that disables CValCollectionEntryStats when
 // ENABLE_DEBUG_C_VAL is not defined.
 template <typename EntryType>
 class CValCollectionEntryStatsStub {
  public:
   typedef CValCollectionEntryStatsFlushResults<EntryType> FlushResults;
   typedef typename FlushResults::OnFlushCallback OnFlushCallback;

   explicit CValCollectionEntryStatsStub(const std::string& name) {}
   CValCollectionEntryStatsStub(
       const std::string& name, size_t max_size, bool enable_entry_list_c_val,
       const OnFlushCallback& on_flush = OnFlushCallback()) {}

   void AddEntry(const EntryType& value) {}
   void Flush() {}
 };
 #endif  // ENABLE_DEBUG_C_VAL

 }  // namespace CValDetail

 template <typename EntryType, typename Visibility = CValDebug>
 class CValCollectionEntryStats {};

 template <typename EntryType>
 #if defined(ENABLE_DEBUG_C_VAL)
 // When ENABLE_DEBUG_C_VAL is defined, CVals with Visibility set to CValDebug
 // are tracked through the CVal system.
 class CValCollectionEntryStats<EntryType, CValDebug>
     : public CValDetail::CValCollectionEntryStatsImpl<EntryType, CValDebug> {
   typedef CValDetail::CValCollectionEntryStatsImpl<EntryType, CValDebug>
       CValParent;
 #else   // ENABLE_DEBUG_C_VAL
 // When ENABLE_DEBUG_C_VAL is not defined, CVals with Visibility set to
 // CValDebug are not tracked though the CVal system and
 // CValCollectionEntryStats can be stubbed out.
 class CValCollectionEntryStats<EntryType, CValDebug>
     : public CValDetail::CValCollectionEntryStatsStub<EntryType> {
   typedef CValDetail::CValCollectionEntryStatsStub<EntryType> CValParent;
 #endif  // ENABLE_DEBUG_C_VAL

  public:
   typedef typename CValParent::OnFlushCallback OnFlushCallback;
   typedef typename CValParent::FlushResults FlushResults;

   explicit CValCollectionEntryStats(const std::string& name)
       : CValParent(name) {}
   CValCollectionEntryStats(const std::string& name, size_t max_size,
                            bool enable_entry_list_c_val,
                            const OnFlushCallback& on_flush = OnFlushCallback())
       : CValParent(name, max_size, enable_entry_list_c_val, on_flush) {}
 };

 // CVals with visibility set to CValPublic are always tracked though the CVal
 // system, regardless of the ENABLE_DEBUG_C_VAL state.
 template <typename EntryType>
 class CValCollectionEntryStats<EntryType, CValPublic>
     : public CValDetail::CValCollectionEntryStatsImpl<EntryType, CValPublic> {
   typedef CValDetail::CValCollectionEntryStatsImpl<EntryType, CValPublic>
       CValParent;

  public:
   typedef typename CValParent::OnFlushCallback OnFlushCallback;
   typedef typename CValParent::FlushResults FlushResults;

   explicit CValCollectionEntryStats(const std::string& name)
       : CValParent(name) {}
   CValCollectionEntryStats(const std::string& name, size_t max_size,
                            bool enable_entry_list_c_val,
                            const OnFlushCallback& on_flush = OnFlushCallback())
       : CValParent(name, max_size, enable_entry_list_c_val, on_flush) {}
 };

 }  // namespace base

 #endif  // COBALT_BASE_C_VAL_COLLECTION_ENTRY_STATS_H_
	// Copyright 2017 The Cobalt Authors. 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_COLLECTION_ENTRY_STATS_H_
	#define COBALT_BASE_C_VAL_COLLECTION_ENTRY_STATS_H_

	#include <algorithm>
	#include <cmath>
	#include <memory>
	#include <numeric>
	#include <sstream>
	#include <string>
	#include <vector>

	#include "base/callback.h"
	#include "base/logging.h"
	#include "base/strings/stringprintf.h"
	#include "base/time/time.h"
	#include "cobalt/base/c_val.h"

	namespace base {
	namespace CValDetail {

	// This struct contains the data generated by flushes of
	// CValCollectionEntryStats for use with callbacks.
	template <typename EntryType>
	struct CValCollectionEntryStatsFlushResults {
	typedef base::Callback<void(const CValCollectionEntryStatsFlushResults&)>
	OnFlushCallback;

	CValCollectionEntryStatsFlushResults(size_t sample_count, EntryType average,
	EntryType minimum, EntryType maximum,
	EntryType standard_deviation,
	EntryType percentile_25th,
	EntryType percentile_50th,
	EntryType percentile_75th,
	EntryType percentile_95th)
	: sample_count(sample_count),
	average(average),
	minimum(minimum),
	maximum(maximum),
	standard_deviation(standard_deviation),
	percentile_25th(percentile_25th),
	percentile_50th(percentile_50th),
	percentile_75th(percentile_75th),
	percentile_95th(percentile_95th) {}

	size_t sample_count;
	EntryType average;
	EntryType minimum;
	EntryType maximum;
	EntryType standard_deviation;
	EntryType percentile_25th;
	EntryType percentile_50th;
	EntryType percentile_75th;
	EntryType percentile_95th;
	};

	// This class tracks a collection of entries, which it retains in memory. When
	// either the max size of the collection is reached or Flush() is manually
	// called, the count, average, minimum, maximum, 25th, 50th, 75th and 95th
	// percentiles, and standard deviation of the collection are recorded with
	// CVals, and the tracking resets in preparation for the next collection of
	// entries.
	// NOTE1: By default there is no max size and the collection will continue to
	// grow indefinitely until Flush() is called.
	// NOTE2: This class keeps all of the entries in memory until flush is called so
	// that percentiles can be determined. In cases where the number of
	// entries is extremely large, \|CValTimeIntervalEntryStats\| is more
	// appropriate, as it does its tracking without keeping entries in memory
	// (at the cost of not being able to provide percentiles);
	// NOTE3: This class provides the ability to record all entries within a single
	// string CVal when \|enable_entry_list_c_val\| is set to true in the
	// constructor. By default, this CVal is not used.
	template <typename EntryType, typename Visibility = CValDebug>
	class CValCollectionEntryStatsImpl {
	public:
	static const size_t kNoMaxSize = 0;

	typedef CValCollectionEntryStatsFlushResults<EntryType> FlushResults;
	typedef typename FlushResults::OnFlushCallback OnFlushCallback;

	CValCollectionEntryStatsImpl(
	const std::string& name, size_t max_size = kNoMaxSize,
	bool enable_entry_list_c_val = false,
	const OnFlushCallback& on_flush = OnFlushCallback());

	// Add an entry to the collection. This may trigger a Flush() if adding the
	// entry causes the max size to be reached.
	void AddEntry(const EntryType& value);
	// Manually flush the collection's entries. This updates the stat cvals and
	// clears the entries.
	void Flush();

	private:
	typedef std::vector<EntryType> CollectionType;

	static EntryType CalculatePercentile(const CollectionType& sorted_collection,
	int percentile);
	static double CalculateStandardDeviation(const CollectionType& collection,
	double mean);

	// Constructs a string representing the entries within the collection and
	// populates \|entry_list_\| with it if the entry list CVal was enabled during
	// construction.
	void PopulateEntryList();

	// The maximum size of the collection before Flush() is automatically called.
	const size_t max_size_;

	// Callback to call whenever the values are flushed.
	const OnFlushCallback on_flush_;

	// The current collection of entries. These will be used to generate the cval
	// stats during the next call of Flush().
	CollectionType collection_;

	// CVals of the stats for the previous collection.
	base::CVal<size_t, Visibility> count_;
	base::CVal<EntryType, Visibility> average_;
	base::CVal<EntryType, Visibility> minimum_;
	base::CVal<EntryType, Visibility> maximum_;
	base::CVal<EntryType, Visibility> percentile_25th_;
	base::CVal<EntryType, Visibility> percentile_50th_;
	base::CVal<EntryType, Visibility> percentile_75th_;
	base::CVal<EntryType, Visibility> percentile_95th_;
	base::CVal<EntryType, Visibility> standard_deviation_;
	// \|entry_list_\| is only non-NULL when it is enabled.
	std::unique_ptr<base::CVal<std::string, Visibility> > entry_list_;
	};

	template <typename EntryType, typename Visibility>
	CValCollectionEntryStatsImpl<EntryType, Visibility>::
	CValCollectionEntryStatsImpl(
	const std::string& name, size_t max_size /=kNoMaxSize/,
	bool enable_entry_list_c_val /=false/,
	const OnFlushCallback& on_flush /=OnFlushCallback()/)
	: max_size_(max_size),
	on_flush_(on_flush),
	count_(base::StringPrintf("%s.Cnt", name.c_str()), 0, "Total entries."),
	average_(base::StringPrintf("%s.Avg", name.c_str()), EntryType(),
	"Average value."),
	minimum_(base::StringPrintf("%s.Min", name.c_str()), EntryType(),
	"Minimum value."),
	maximum_(base::StringPrintf("%s.Max", name.c_str()), EntryType(),
	"Maximum value."),
	percentile_25th_(base::StringPrintf("%s.Pct.25th", name.c_str()),
	EntryType(), "25th percentile value."),
	percentile_50th_(base::StringPrintf("%s.Pct.50th", name.c_str()),
	EntryType(), "50th percentile value."),
	percentile_75th_(base::StringPrintf("%s.Pct.75th", name.c_str()),
	EntryType(), "75th percentile value."),
	percentile_95th_(base::StringPrintf("%s.Pct.95th", name.c_str()),
	EntryType(), "95th percentile value."),
	standard_deviation_(base::StringPrintf("%s.Std", name.c_str()),
	EntryType(), "Standard deviation of values.") {
	if (enable_entry_list_c_val) {
	entry_list_.reset(new base::CVal<std::string, Visibility>(
	base::StringPrintf("%s.EntryList", name.c_str()), "[]",
	"The list of entries in the collection."));
	}
	}

	template <typename EntryType, typename Visibility>
	void CValCollectionEntryStatsImpl<EntryType, Visibility>::AddEntry(
	const EntryType& value) {
	collection_.push_back(value);
	if (collection_.size() == max_size_) {
	Flush();
	}
	}

	template <typename EntryType, typename Visibility>
	void CValCollectionEntryStatsImpl<EntryType, Visibility>::Flush() {
	if (collection_.size() == 0) {
	return;
	}

	// Populate the entry list cval before the collection is sorted.
	PopulateEntryList();

	// Sort the collection. This allows min, max, and percentiles to be easily
	// determined.
	std::sort(collection_.begin(), collection_.end());

	// Calculate the mean of the collection.
	EntryType sum = std::accumulate(collection_.begin(), collection_.end(),
	CValDetail::FromDouble<EntryType>(0));
	double mean = CValDetail::ToDouble<EntryType>(sum) / collection_.size();

	// Update the collection stat cvals.
	size_t count = collection_.size();
	EntryType average = CValDetail::FromDouble<EntryType>(mean);
	EntryType minimum = collection_.front();
	EntryType maximum = collection_.back();
	EntryType percentile_25th = CalculatePercentile(collection_, 25);
	EntryType percentile_50th = CalculatePercentile(collection_, 50);
	EntryType percentile_75th = CalculatePercentile(collection_, 75);
	EntryType percentile_95th = CalculatePercentile(collection_, 95);
	EntryType standard_deviation = CValDetail::FromDouble<EntryType>(
	CalculateStandardDeviation(collection_, mean));

	// Flush the computed values out to the CVals.
	count_ = count;
	average_ = average;
	minimum_ = minimum;
	maximum_ = maximum;
	percentile_25th_ = percentile_25th;
	percentile_50th_ = percentile_50th;
	percentile_75th_ = percentile_75th;
	percentile_95th_ = percentile_95th;
	standard_deviation_ = standard_deviation;

	collection_.clear();

	// Callback to any listeners with the flush values.
	if (!on_flush_.is_null()) {
	on_flush_.Run(FlushResults(
	count, average, minimum, maximum, standard_deviation, percentile_25th,
	percentile_50th, percentile_75th, percentile_95th));
	}
	}

	template <typename EntryType, typename Visibility>
	EntryType
	CValCollectionEntryStatsImpl<EntryType, Visibility>::CalculatePercentile(
	const CollectionType& sorted_collection, int percentile) {
	DCHECK_GT(sorted_collection.size(), 0);
	DCHECK(percentile >= 0 && percentile <= 100);

	// Determine the position of the percentile within the collection.
	double percentile_position =
	(sorted_collection.size() - 1) * static_cast<double>(percentile) * 0.01;

	// Split out the integral and fractional parts of the percentile position.
	double percentile_integral_position, percentile_fractional_position;
	percentile_fractional_position =
	std::modf(percentile_position, &percentile_integral_position);

	int percentile_first_index = static_cast<int>(percentile_integral_position);

	// If \|percentile_first_index\| maps to the last entry, then there is no
	// second entry and there's nothing to interpolate; simply use the last entry.
	if (sorted_collection.size() == percentile_first_index + 1) {
	return sorted_collection.back();
	}

	// Interpolate between the two entries that the percentile falls between.
	double first_data_point = CValDetail::ToDouble<EntryType>(
	sorted_collection[percentile_first_index]) *
	(1.0 - percentile_fractional_position);
	double second_data_point =
	CValDetail::ToDouble<EntryType>(
	sorted_collection[percentile_first_index + 1]) *
	percentile_fractional_position;

	return CValDetail::FromDouble<EntryType>(first_data_point +
	second_data_point);
	}

	template <typename EntryType, typename Visibility>
	double
	CValCollectionEntryStatsImpl<EntryType, Visibility>::CalculateStandardDeviation(
	const CollectionType& collection, double mean) {
	if (collection.size() <= 1) {
	return 0;
	}

	double dif_squared_sum = 0;
	for (size_t i = 0; i < collection.size(); ++i) {
	double dif = CValDetail::ToDouble<EntryType>(collection[i]) - mean;
	dif_squared_sum += dif * dif;
	}

	double variance =
	dif_squared_sum / static_cast<double>(collection.size() - 1);

	return std::sqrt(variance);
	}

	template <typename EntryType, typename Visibility>
	void CValCollectionEntryStatsImpl<EntryType, Visibility>::PopulateEntryList() {
	// If the entry list was not enabled, then \|entry_list_\| will be NULL and
	// there is nothing to do. Simply return.
	if (!entry_list_) {
	return;
	}

	// Construct a string containing a list representation of the collection
	// entries and set the entry list CVal to it.
	std::ostringstream oss;
	oss << "[";
	for (size_t i = 0; i < collection_.size(); ++i) {
	if (i > 0) {
	oss << ", ";
	}
	oss << CValDetail::ValToString<EntryType>(collection_[i]);
	}
	oss << "]";
	*entry_list_ = oss.str();
	}

	#if !defined(ENABLE_DEBUG_C_VAL)
	// This is a stub class that disables CValCollectionEntryStats when
	// ENABLE_DEBUG_C_VAL is not defined.
	template <typename EntryType>
	class CValCollectionEntryStatsStub {
	public:
	typedef CValCollectionEntryStatsFlushResults<EntryType> FlushResults;
	typedef typename FlushResults::OnFlushCallback OnFlushCallback;

	explicit CValCollectionEntryStatsStub(const std::string& name) {}
	CValCollectionEntryStatsStub(
	const std::string& name, size_t max_size, bool enable_entry_list_c_val,
	const OnFlushCallback& on_flush = OnFlushCallback()) {}

	void AddEntry(const EntryType& value) {}
	void Flush() {}
	};
	#endif // ENABLE_DEBUG_C_VAL

	} // namespace CValDetail

	template <typename EntryType, typename Visibility = CValDebug>
	class CValCollectionEntryStats {};

	template <typename EntryType>
	#if defined(ENABLE_DEBUG_C_VAL)
	// When ENABLE_DEBUG_C_VAL is defined, CVals with Visibility set to CValDebug
	// are tracked through the CVal system.
	class CValCollectionEntryStats<EntryType, CValDebug>
	: public CValDetail::CValCollectionEntryStatsImpl<EntryType, CValDebug> {
	typedef CValDetail::CValCollectionEntryStatsImpl<EntryType, CValDebug>
	CValParent;
	#else // ENABLE_DEBUG_C_VAL
	// When ENABLE_DEBUG_C_VAL is not defined, CVals with Visibility set to
	// CValDebug are not tracked though the CVal system and
	// CValCollectionEntryStats can be stubbed out.
	class CValCollectionEntryStats<EntryType, CValDebug>
	: public CValDetail::CValCollectionEntryStatsStub<EntryType> {
	typedef CValDetail::CValCollectionEntryStatsStub<EntryType> CValParent;
	#endif // ENABLE_DEBUG_C_VAL

	public:
	typedef typename CValParent::OnFlushCallback OnFlushCallback;
	typedef typename CValParent::FlushResults FlushResults;

	explicit CValCollectionEntryStats(const std::string& name)
	: CValParent(name) {}
	CValCollectionEntryStats(const std::string& name, size_t max_size,
	bool enable_entry_list_c_val,
	const OnFlushCallback& on_flush = OnFlushCallback())
	: CValParent(name, max_size, enable_entry_list_c_val, on_flush) {}
	};

	// CVals with visibility set to CValPublic are always tracked though the CVal
	// system, regardless of the ENABLE_DEBUG_C_VAL state.
	template <typename EntryType>
	class CValCollectionEntryStats<EntryType, CValPublic>
	: public CValDetail::CValCollectionEntryStatsImpl<EntryType, CValPublic> {
	typedef CValDetail::CValCollectionEntryStatsImpl<EntryType, CValPublic>
	CValParent;

	public:
	typedef typename CValParent::OnFlushCallback OnFlushCallback;
	typedef typename CValParent::FlushResults FlushResults;

	explicit CValCollectionEntryStats(const std::string& name)
	: CValParent(name) {}
	CValCollectionEntryStats(const std::string& name, size_t max_size,
	bool enable_entry_list_c_val,
	const OnFlushCallback& on_flush = OnFlushCallback())
	: CValParent(name, max_size, enable_entry_list_c_val, on_flush) {}
	};

	} // namespace base

	#endif // COBALT_BASE_C_VAL_COLLECTION_ENTRY_STATS_H_