Cache the ranges_ vector and share the ranges_ vector

across histograms if the ranges in the ranges_ vector
is same. This change saves around 100k of memory in the
browser (around 400 histograms sharing the same ranges_
vector and each ranges_ vector has around 50 elements).
In each renderer process we are sharing ranges_ vector
for around 30 histograms (a savings of 6k of memory).

R=jar
TEST=histogram unit tests.
Review URL: http://codereview.chromium.org/7696017

git-svn-id: svn://svn.chromium.org/chrome/trunk/src@106425 0039d316-1c4b-4281-b951-d872f2087c98

3 files changed, 257 insertions, 31 deletions

diff --git a/base/metrics/histogram.cc b/base/metrics/histogram.cc
index 8b11ee8..484d095 100644
--- a/base/metrics/histogram.cc
+++ b/base/metrics/histogram.cc
@@ -74,6 +74,13 @@ typedef Histogram::Count Count;
 // static
 const size_t Histogram::kBucketCount_MAX = 16384u;
 
+// Collect the number of histograms created.
+static uint32 number_of_histograms_ = 0;
+// Collect the number of vectors saved because of caching ranges.
+static uint32 number_of_vectors_saved_ = 0;
+// Collect the number of ranges_ elements saved because of caching ranges.
+static size_t saved_ranges_size_ = 0;
+
 Histogram* Histogram::FactoryGet(const std::string& name,
                                  Sample minimum,
                                  Sample maximum,
@@ -363,7 +370,7 @@ Histogram::ClassType Histogram::histogram_type() const {
 }
 
 Histogram::Sample Histogram::ranges(size_t i) const {
-  return ranges_[i];
+  return cached_ranges_->ranges(i);
 }
 
 size_t Histogram::bucket_count() const {
@@ -403,7 +410,7 @@ Histogram::Histogram(const std::string& name, Sample minimum,
     declared_max_(maximum),
     bucket_count_(bucket_count),
     flags_(kNoFlags),
-    ranges_(bucket_count + 1, 0),
+    cached_ranges_(new CachedRanges(bucket_count + 1, 0)),
     range_checksum_(0),
     sample_() {
   Initialize();
@@ -416,7 +423,7 @@ Histogram::Histogram(const std::string& name, TimeDelta minimum,
     declared_max_(static_cast<int> (maximum.InMilliseconds())),
     bucket_count_(bucket_count),
     flags_(kNoFlags),
-    ranges_(bucket_count + 1, 0),
+    cached_ranges_(new CachedRanges(bucket_count + 1, 0)),
     range_checksum_(0),
     sample_() {
   Initialize();
@@ -437,7 +444,7 @@ Histogram::~Histogram() {
 // We have to be careful that we don't pick a ratio between starting points in
 // consecutive buckets that is sooo small, that the integer bounds are the same
 // (effectively making one bucket get no values).  We need to avoid:
-//   ranges_[i] == ranges_[i + 1]
+//   ranges(i) == ranges(i + 1)
 // To avoid that, we just do a fine-grained bucket width as far as we need to
 // until we get a ratio that moves us along at least 2 units at a time.  From
 // that bucket onward we do use the exponential growth of buckets.
@@ -533,22 +540,23 @@ void Histogram::Accumulate(Sample value, Count count, size_t index) {
 void Histogram::SetBucketRange(size_t i, Sample value) {
   DCHECK_GT(bucket_count_, i);
   DCHECK_GE(value, 0);
-  ranges_[i] = value;
+  cached_ranges_->SetBucketRange(i, value);
 }
 
 bool Histogram::ValidateBucketRanges() const {
   // Standard assertions that all bucket ranges should satisfy.
-  DCHECK_EQ(bucket_count_ + 1, ranges_.size());
-  DCHECK_EQ(0, ranges_[0]);
-  DCHECK_EQ(declared_min(), ranges_[1]);
-  DCHECK_EQ(declared_max(), ranges_[bucket_count_ - 1]);
-  DCHECK_EQ(kSampleType_MAX, ranges_[bucket_count_]);
+  DCHECK_EQ(bucket_count_ + 1, cached_ranges_->size());
+  DCHECK_EQ(0, ranges(0));
+  DCHECK_EQ(declared_min(), ranges(1));
+  DCHECK_EQ(declared_max(), ranges(bucket_count_ - 1));
+  DCHECK_EQ(kSampleType_MAX, ranges(bucket_count_));
   return true;
 }
 
 uint32 Histogram::CalculateRangeChecksum() const {
-  DCHECK_EQ(ranges_.size(), bucket_count() + 1);
-  uint32 checksum = static_cast<uint32>(ranges_.size());  // Seed checksum.
+  DCHECK_EQ(cached_ranges_->size(), bucket_count() + 1);
+  // Seed checksum.
+  uint32 checksum = static_cast<uint32>(cached_ranges_->size());
   for (size_t index = 0; index < bucket_count(); ++index)
     checksum = Crc32(checksum, ranges(index));
   return checksum;
@@ -565,8 +573,8 @@ void Histogram::Initialize() {
   CHECK_LT(bucket_count_, kBucketCount_MAX);
   size_t maximal_bucket_count = declared_max_ - declared_min_ + 2;
   DCHECK_LE(bucket_count_, maximal_bucket_count);
-  DCHECK_EQ(0, ranges_[0]);
-  ranges_[bucket_count_] = kSampleType_MAX;
+  DCHECK_EQ(0, ranges(0));
+  cached_ranges_->SetBucketRange(bucket_count_, kSampleType_MAX);
 }
 
 // We generate the CRC-32 using the low order bits to select whether to XOR in
@@ -1008,6 +1016,7 @@ StatisticsRecorder::StatisticsRecorder() {
   }
   base::AutoLock auto_lock(*lock_);
   histograms_ = new HistogramMap;
+  ranges_ = new RangesMap;
 }
 
 StatisticsRecorder::~StatisticsRecorder() {
@@ -1025,7 +1034,15 @@ StatisticsRecorder::~StatisticsRecorder() {
     histograms = histograms_;
     histograms_ = NULL;
   }
+  RangesMap* ranges = NULL;
+  {
+    base::AutoLock auto_lock(*lock_);
+    ranges = ranges_;
+    ranges_ = NULL;
+  }
+  // We are going to leak the histograms and the ranges.
   delete histograms;
+  delete ranges;
   // We don't delete lock_ on purpose to avoid having to properly protect
   // against it going away after we checked for NULL in the static methods.
 }
@@ -1060,6 +1077,8 @@ Histogram* StatisticsRecorder::RegisterOrDeleteDuplicate(Histogram* histogram) {
   if (histograms_->end() == it) {
     (*histograms_)[name] = histogram;
     ANNOTATE_LEAKING_OBJECT_PTR(histogram);  // see crbug.com/79322
+    RegisterOrDeleteDuplicateRanges(histogram);
+    ++number_of_histograms_;
   } else {
     delete histogram;  // We already have one by this name.
     histogram = it->second;
@@ -1068,6 +1087,93 @@ Histogram* StatisticsRecorder::RegisterOrDeleteDuplicate(Histogram* histogram) {
 }
 
 // static
+void StatisticsRecorder::RegisterOrDeleteDuplicateRanges(Histogram* histogram) {
+  DCHECK(histogram);
+  CachedRanges* histogram_ranges = histogram->cached_ranges();
+  DCHECK(histogram_ranges);
+  uint32 checksum = histogram->range_checksum();
+  histogram_ranges->SetRangeChecksum(checksum);
+
+  RangesMap::iterator ranges_it = ranges_->find(checksum);
+  if (ranges_->end() == ranges_it) {
+    // Register the new CachedRanges.
+    std::list<CachedRanges*>* checksum_matching_list(
+        new std::list<CachedRanges*>());
+    checksum_matching_list->push_front(histogram_ranges);
+    (*ranges_)[checksum] = checksum_matching_list;
+    return;
+  }
+
+  // Use the registered CachedRanges if the registered CachedRanges has same
+  // ranges_ as |histogram|'s CachedRanges.
+  std::list<CachedRanges*>* checksum_matching_list = ranges_it->second;
+  std::list<CachedRanges*>::iterator checksum_matching_list_it;
+  for (checksum_matching_list_it = checksum_matching_list->begin();
+       checksum_matching_list_it != checksum_matching_list->end();
+       ++checksum_matching_list_it) {
+    CachedRanges* existing_histogram_ranges = *checksum_matching_list_it;
+    DCHECK(existing_histogram_ranges);
+    if (existing_histogram_ranges->Equals(histogram_ranges)) {
+      histogram->set_cached_ranges(existing_histogram_ranges);
+      ++number_of_vectors_saved_;
+      saved_ranges_size_ += histogram_ranges->size();
+      delete histogram_ranges;
+      return;
+    }
+  }
+
+  // We haven't found a CachedRanges which has the same ranges. Register the
+  // new CachedRanges.
+  DCHECK(checksum_matching_list_it == checksum_matching_list->end());
+  checksum_matching_list->push_front(histogram_ranges);
+}
+
+// static
+void StatisticsRecorder::CollectHistogramStats(const std::string& suffix) {
+  static int uma_upload_attempt = 0;
+  ++uma_upload_attempt;
+  if (uma_upload_attempt == 1) {
+    UMA_HISTOGRAM_COUNTS_10000(
+        "Histogram.SharedRange.Count.FirstUpload." + suffix,
+        number_of_histograms_);
+    UMA_HISTOGRAM_COUNTS_10000(
+        "Histogram.SharedRange.RangesSaved.FirstUpload." + suffix,
+        number_of_vectors_saved_);
+    UMA_HISTOGRAM_COUNTS(
+        "Histogram.SharedRange.ElementsSaved.FirstUpload." + suffix,
+        static_cast<int>(saved_ranges_size_));
+    number_of_histograms_ = 0;
+    number_of_vectors_saved_ = 0;
+    saved_ranges_size_ = 0;
+    return;
+  }
+  if (uma_upload_attempt == 2) {
+    UMA_HISTOGRAM_COUNTS_10000(
+        "Histogram.SharedRange.Count.SecondUpload." + suffix,
+        number_of_histograms_);
+    UMA_HISTOGRAM_COUNTS_10000(
+        "Histogram.SharedRange.RangesSaved.SecondUpload." + suffix,
+        number_of_vectors_saved_);
+    UMA_HISTOGRAM_COUNTS(
+        "Histogram.SharedRange.ElementsSaved.SecondUpload." + suffix,
+        static_cast<int>(saved_ranges_size_));
+    number_of_histograms_ = 0;
+    number_of_vectors_saved_ = 0;
+    saved_ranges_size_ = 0;
+    return;
+  }
+  UMA_HISTOGRAM_COUNTS_10000(
+      "Histogram.SharedRange.Count.RestOfUploads." + suffix,
+      number_of_histograms_);
+  UMA_HISTOGRAM_COUNTS_10000(
+      "Histogram.SharedRange.RangesSaved.RestOfUploads." + suffix,
+      number_of_vectors_saved_);
+  UMA_HISTOGRAM_COUNTS(
+      "Histogram.SharedRange.ElementsSaved.RestOfUploads." + suffix,
+      static_cast<int>(saved_ranges_size_));
+}
+
+// static
 void StatisticsRecorder::WriteHTMLGraph(const std::string& query,
                                         std::string* output) {
   if (!IsActive())
@@ -1148,11 +1254,38 @@ void StatisticsRecorder::GetSnapshot(const std::string& query,
   }
 }
 
+CachedRanges::CachedRanges(size_t bucket_count, int initial_value)
+    : ranges_(bucket_count, initial_value),
+      range_checksum_(0) {
+}
+
+CachedRanges::~CachedRanges() {
+}
+
+void CachedRanges::SetBucketRange(size_t i, Histogram::Sample value) {
+  DCHECK_LT(i, ranges_.size());
+  DCHECK_GE(value, 0);
+  ranges_[i] = value;
+}
+
+bool CachedRanges::Equals(CachedRanges* other) const {
+  if (range_checksum_ != other->range_checksum_)
+    return false;
+  if (ranges_.size() != other->ranges_.size())
+    return false;
+  for (size_t index = 0; index < ranges_.size(); ++index) {
+    if (ranges_[index] != other->ranges_[index])
+      return false;
+  }
+  return true;
+}
+
 // static
 StatisticsRecorder::HistogramMap* StatisticsRecorder::histograms_ = NULL;
 // static
+StatisticsRecorder::RangesMap* StatisticsRecorder::ranges_ = NULL;
+// static
 base::Lock* StatisticsRecorder::lock_ = NULL;
 // static
 bool StatisticsRecorder::dump_on_exit_ = false;
-
 }  // namespace base
diff --git a/base/metrics/histogram.h b/base/metrics/histogram.h
index e8f6364..e5f0d04 100644
--- a/base/metrics/histogram.h
+++ b/base/metrics/histogram.h
@@ -41,6 +41,7 @@
 #define BASE_METRICS_HISTOGRAM_H_
 #pragma once
 
+#include <list>
 #include <map>
 #include <string>
 #include <vector>
@@ -316,6 +317,7 @@ class Lock;
 //------------------------------------------------------------------------------
 
 class BooleanHistogram;
+class CachedRanges;
 class CustomHistogram;
 class Histogram;
 class LinearHistogram;
@@ -329,7 +331,6 @@ class BASE_EXPORT Histogram {
   static const size_t kBucketCount_MAX;
 
   typedef std::vector<Count> Counts;
-  typedef std::vector<Sample> Ranges;
 
   // These enums are used to facilitate deserialization of renderer histograms
   // into the browser.
@@ -503,6 +504,10 @@ class BASE_EXPORT Histogram {
   virtual Sample ranges(size_t i) const;
   uint32 range_checksum() const { return range_checksum_; }
   virtual size_t bucket_count() const;
+  CachedRanges* cached_ranges() const { return cached_ranges_; }
+  void set_cached_ranges(CachedRanges* cached_ranges) {
+    cached_ranges_ = cached_ranges;
+  }
   // Snapshot the current complete set of sample data.
   // Override with atomic/locked snapshot if needed.
   virtual void SnapshotSample(SampleSet* sample) const;
@@ -513,7 +518,8 @@ class BASE_EXPORT Histogram {
   virtual bool HasConstructorTimeDeltaArguments(TimeDelta minimum,
                                                 TimeDelta maximum,
                                                 size_t bucket_count);
-  // Return true iff the range_checksum_ matches current ranges_ vector.
+  // Return true iff the range_checksum_ matches current |ranges_| vector in
+  // |cached_ranges_|.
   bool HasValidRangeChecksum() const;
 
  protected:
@@ -524,7 +530,7 @@ class BASE_EXPORT Histogram {
 
   virtual ~Histogram();
 
-  // Initialize ranges_ mapping.
+  // Initialize ranges_ mapping in cached_ranges_.
   void InitializeBucketRange();
 
   // Method to override to skip the display of the i'th bucket if it's empty.
@@ -535,7 +541,7 @@ class BASE_EXPORT Histogram {
   //----------------------------------------------------------------------------
   // Find bucket to increment for sample value.
   virtual size_t BucketIndex(Sample value) const;
-  // Get normalized size, relative to the ranges_[i].
+  // Get normalized size, relative to the ranges(i).
   virtual double GetBucketSize(Count current, size_t i) const;
 
   // Recalculate range_checksum_.
@@ -557,8 +563,9 @@ class BASE_EXPORT Histogram {
   //----------------------------------------------------------------------------
   void SetBucketRange(size_t i, Sample value);
 
-  // Validate that ranges_ was created sensibly (top and bottom range
-  // values relate properly to the declared_min_ and declared_max_)..
+  // Validate that ranges_ in cached_ranges_ was created sensibly (top and
+  // bottom range values relate properly to the declared_min_ and
+  // declared_max_).
   bool ValidateBucketRanges() const;
 
   virtual uint32 CalculateRangeChecksum() const;
@@ -622,8 +629,8 @@ class BASE_EXPORT Histogram {
   // For each index, show the least value that can be stored in the
   // corresponding bucket. We also append one extra element in this array,
   // containing kSampleType_MAX, to make calculations easy.
-  // The dimension of ranges_ is bucket_count + 1.
-  Ranges ranges_;
+  // The dimension of ranges_ in cached_ranges_ is bucket_count + 1.
+  CachedRanges* cached_ranges_;
 
   // For redundancy, we store a checksum of all the sample ranges when ranges
   // are generated.  If ever there is ever a difference, then the histogram must
@@ -672,7 +679,7 @@ class BASE_EXPORT LinearHistogram : public Histogram {
   LinearHistogram(const std::string& name, TimeDelta minimum,
                   TimeDelta maximum, size_t bucket_count);
 
-  // Initialize ranges_ mapping.
+  // Initialize ranges_ mapping in cached_ranges_.
   void InitializeBucketRange();
   virtual double GetBucketSize(Count current, size_t i) const;
 
@@ -736,7 +743,7 @@ class BASE_EXPORT CustomHistogram : public Histogram {
   CustomHistogram(const std::string& name,
                   const std::vector<Sample>& custom_ranges);
 
-  // Initialize ranges_ mapping.
+  // Initialize ranges_ mapping in cached_ranges_.
   void InitializedCustomBucketRange(const std::vector<Sample>& custom_ranges);
   virtual double GetBucketSize(Count current, size_t i) const;
 
@@ -765,6 +772,19 @@ class BASE_EXPORT StatisticsRecorder {
   // histogram (either the argument, or the pre-existing registered histogram).
   static Histogram* RegisterOrDeleteDuplicate(Histogram* histogram);
 
+  // Register, or add a new cached_ranges_ of |histogram|. If an identical
+  // cached_ranges_ is already registered, then the cached_ranges_ of
+  // |histogram| is deleted and the |histogram|'s cached_ranges_ is reset to the
+  // registered cached_ranges_.  The cached_ranges_ of |histogram| is always the
+  // registered CachedRanges (either the argument's cached_ranges_, or the
+  // pre-existing registered cached_ranges_).
+  static void RegisterOrDeleteDuplicateRanges(Histogram* histogram);
+
+  // Method for collecting stats about histograms created in browser and
+  // renderer processes. |suffix| is appended to histogram names. |suffix| could
+  // be either browser or renderer.
+  static void CollectHistogramStats(const std::string& suffix);
+
   // Methods for printing histograms.  Only histograms which have query as
   // a substring are written to output (an empty string will process all
   // registered histograms).
@@ -794,8 +814,15 @@ class BASE_EXPORT StatisticsRecorder {
   // We keep all registered histograms in a map, from name to histogram.
   typedef std::map<std::string, Histogram*> HistogramMap;
 
+  // We keep all |cached_ranges_| in a map, from checksum to a list of
+  // |cached_ranges_|.  Checksum is calculated from the |ranges_| in
+  // |cached_ranges_|.
+  typedef std::map<uint32, std::list<CachedRanges*>*> RangesMap;
+
   static HistogramMap* histograms_;
 
+  static RangesMap* ranges_;
+
   // lock protects access to the above map.
   static base::Lock* lock_;
 
@@ -805,6 +832,46 @@ class BASE_EXPORT StatisticsRecorder {
   DISALLOW_COPY_AND_ASSIGN(StatisticsRecorder);
 };
 
+//------------------------------------------------------------------------------
+
+// CachedRanges stores the Ranges vector. Histograms that have same Ranges
+// vector will use the same CachedRanges object.
+class BASE_EXPORT CachedRanges {
+ public:
+  typedef std::vector<Histogram::Sample> Ranges;
+
+  CachedRanges(size_t bucket_count, int initial_value);
+  ~CachedRanges();
+
+  //----------------------------------------------------------------------------
+  // Accessors methods for ranges_ and range_checksum_.
+  //----------------------------------------------------------------------------
+  size_t size() const { return ranges_.size(); }
+  Histogram::Sample ranges(size_t i) const { return ranges_[i]; }
+  void SetBucketRange(size_t i, Histogram::Sample value);
+  uint32 range_checksum(uint32 checksum) const { return range_checksum_; }
+  void SetRangeChecksum(uint32 checksum) { range_checksum_ = checksum; }
+
+  // Return true iff |other| object has same ranges_ as |this| object's ranges_.
+  bool Equals(CachedRanges* other) const;
+
+ private:
+  // Allow tests to corrupt our innards for testing purposes.
+  FRIEND_TEST(HistogramTest, CorruptBucketBounds);
+
+  // A monotonically increasing list of values which determine which bucket to
+  // put a sample into.  For each index, show the smallest sample that can be
+  // added to the corresponding bucket.
+  Ranges ranges_;
+
+  // Checksum for the conntents of ranges_.  Used to detect random over-writes
+  // of our data, and to quickly see if some other CachedRanges instance is
+  // possibly Equal() to this instance.
+  uint32 range_checksum_;
+
+  DISALLOW_COPY_AND_ASSIGN(CachedRanges);
+};
+
 }  // namespace base
 
 #endif  // BASE_METRICS_HISTOGRAM_H_
diff --git a/base/metrics/histogram_unittest.cc b/base/metrics/histogram_unittest.cc
index 5237f33..bd8a427 100644
--- a/base/metrics/histogram_unittest.cc
+++ b/base/metrics/histogram_unittest.cc
@@ -387,25 +387,26 @@ TEST(HistogramTest, CorruptBucketBounds) {
   EXPECT_EQ(Histogram::NO_INCONSISTENCIES, 0);
   EXPECT_EQ(0, histogram->FindCorruption(snapshot));  // No default corruption.
 
-  std::swap(histogram->ranges_[1], histogram->ranges_[2]);
+  CachedRanges* cached_ranges = histogram->cached_ranges();
+  std::swap(cached_ranges->ranges_[1], cached_ranges->ranges_[2]);
   EXPECT_EQ(Histogram::BUCKET_ORDER_ERROR | Histogram::RANGE_CHECKSUM_ERROR,
             histogram->FindCorruption(snapshot));
 
-  std::swap(histogram->ranges_[1], histogram->ranges_[2]);
+  std::swap(cached_ranges->ranges_[1], cached_ranges->ranges_[2]);
   EXPECT_EQ(0, histogram->FindCorruption(snapshot));
 
-  ++histogram->ranges_[3];
+  ++cached_ranges->ranges_[3];
   EXPECT_EQ(Histogram::RANGE_CHECKSUM_ERROR,
             histogram->FindCorruption(snapshot));
 
   // Show that two simple changes don't offset each other
-  --histogram->ranges_[4];
+  --cached_ranges->ranges_[4];
   EXPECT_EQ(Histogram::RANGE_CHECKSUM_ERROR,
             histogram->FindCorruption(snapshot));
 
   // Repair histogram so that destructor won't DCHECK().
-  --histogram->ranges_[3];
-  ++histogram->ranges_[4];
+  --cached_ranges->ranges_[3];
+  ++cached_ranges->ranges_[4];
 }
 
 // Table was generated similarly to sample code for CRC-32 given on:
@@ -424,4 +425,29 @@ TEST(HistogramTest, Crc32TableTest) {
   }
 }
 
+// RangeTest, CustomRangeTest and CorruptBucketBounds test CachedRanges class.
+// The following tests sharing of CachedRanges object.
+TEST(HistogramTest, CachedRangesTest) {
+  StatisticsRecorder recorder;
+  StatisticsRecorder::Histograms histograms;
+
+  recorder.GetHistograms(&histograms);
+  EXPECT_EQ(0U, histograms.size());
+
+  Histogram* histogram1(Histogram::FactoryGet(
+      "Histogram", 1, 64, 8, Histogram::kNoFlags));
+
+  Histogram* histogram2(Histogram::FactoryGet(
+      "Histogram2", 1, 64, 8, Histogram::kNoFlags));
+
+  Histogram* histogram3(Histogram::FactoryGet(
+      "Histogram3", 1, 64, 16, Histogram::kNoFlags));
+
+  CachedRanges* cached_ranges1 = histogram1->cached_ranges();
+  CachedRanges* cached_ranges2 = histogram2->cached_ranges();
+  CachedRanges* cached_ranges3 = histogram3->cached_ranges();
+  EXPECT_TRUE(cached_ranges1->Equals(cached_ranges2));
+  EXPECT_FALSE(cached_ranges1->Equals(cached_ranges3));
+}
+
 }  // namespace base