Cache the ranges_ vector and share the ranges_ vector

base/metrics/histogram.cc

 // Copyright (c) 2011 The Chromium Authors. All rights reserved.
 // Use of this source code is governed by a BSD-style license that can be
 // found in the LICENSE file.
 
 // Histogram is an object that aggregates statistics, and can summarize them in
 // various forms, including ASCII graphical, HTML, and numerically (as a
 // vector of numbers corresponding to each of the aggregating buckets).
 // See header file for details and examples.
 
 #include "base/metrics/histogram.h"
@@ skipping 56 matching lines @@
 0x24b4a3a6L, 0xbad03605L, 0xcdd70693L, 0x54de5729L, 0x23d967bfL, 0xb3667a2eL,
 0xc4614ab8L, 0x5d681b02L, 0x2a6f2b94L, 0xb40bbe37L, 0xc30c8ea1L, 0x5a05df1bL,
 0x2d02ef8dL,
 };
 
 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,
                                  size_t bucket_count,
                                  Flags flags) {
   Histogram* histogram(NULL);
 
   // Defensive code.
   if (minimum < 1)
     minimum = 1;
@@ skipping 269 matching lines @@
     }
   }
   return static_cast<Inconsistencies>(inconsistencies);
 }
 
 Histogram::ClassType Histogram::histogram_type() const {
   return HISTOGRAM;
 }
 
 Histogram::Sample Histogram::ranges(size_t i) const {
-  return ranges_[i];
+  return cached_ranges_->ranges(i);
 }
 
 size_t Histogram::bucket_count() const {
   return bucket_count_;
 }
 
 // Do a safe atomic snapshot of sample data.
 // This implementation assumes we are on a safe single thread.
 void Histogram::SnapshotSample(SampleSet* sample) const {
   // Note locking not done in this version!!!
@@ skipping 19 matching lines @@
   return CalculateRangeChecksum() == range_checksum_;
 }
 
 Histogram::Histogram(const std::string& name, Sample minimum,
                      Sample maximum, size_t bucket_count)
   : histogram_name_(name),
     declared_min_(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();
 }
 
 Histogram::Histogram(const std::string& name, TimeDelta minimum,
                      TimeDelta maximum, size_t bucket_count)
   : histogram_name_(name),
     declared_min_(static_cast<int> (minimum.InMilliseconds())),
     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();
 }
 
 Histogram::~Histogram() {
   if (StatisticsRecorder::dump_on_exit()) {
     std::string output;
     WriteAscii(true, "\n", &output);
     LOG(INFO) << output;
   }
 
   // Just to make sure most derived class did this properly...
   DCHECK(ValidateBucketRanges());
 }
 
 // Calculate what range of values are held in each bucket.
 // 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.
 void Histogram::InitializeBucketRange() {
   double log_max = log(static_cast<double>(declared_max()));
   double log_ratio;
   double log_next;
   size_t bucket_index = 1;
   Sample current = declared_min();
   SetBucketRange(bucket_index, current);
@@ skipping 75 matching lines @@
 
 // Update histogram data with new sample.
 void Histogram::Accumulate(Sample value, Count count, size_t index) {
   // Note locking not done in this version!!!
   sample_.Accumulate(value, count, 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;
 }
 
 void Histogram::Initialize() {
   sample_.Resize(*this);
   if (declared_min_ < 1)
     declared_min_ = 1;
   if (declared_max_ > kSampleType_MAX - 1)
     declared_max_ = kSampleType_MAX - 1;
   DCHECK_LE(declared_min_, declared_max_);
   DCHECK_GT(bucket_count_, 1u);
   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
 // the reversed polynomial 0xedb88320L.  This is nice and simple, and allows us
 // to keep the quotient in a uint32.  Since we're not concerned about the nature
 // of corruptions (i.e., we don't care about bit sequencing, since we are
 // handling memory changes, which are more grotesque) so we don't bother to
 // get the CRC correct for big-endian vs little-ending calculations.  All we
 // need is a nice hash, that tends to depend on all the bits of the sample, with
 // very little chance of changes in one place impacting changes in another
@@ skipping 421 matching lines @@
     // This will leak on purpose. It's the only way to make sure we won't race
     // against the static uninitialization of the module while one of our
     // static methods relying on the lock get called at an inappropriate time
     // during the termination phase. Since it's a static data member, we will
     // leak one per process, which would be similar to the instance allocated
     // during static initialization and released only on  process termination.
     lock_ = new base::Lock;
   }
   base::AutoLock auto_lock(*lock_);
   histograms_ = new HistogramMap;
+  ranges_ = new RangesMap;
 }
 
 StatisticsRecorder::~StatisticsRecorder() {
   DCHECK(histograms_ && lock_);
 
   if (dump_on_exit_) {
     std::string output;
     WriteGraph("", &output);
     LOG(INFO) << output;
   }
   // Clean up.
   HistogramMap* histograms = NULL;
   {
     base::AutoLock auto_lock(*lock_);
     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.
 }
 
 // static
 bool StatisticsRecorder::IsActive() {
   if (lock_ == NULL)
     return false;
   base::AutoLock auto_lock(*lock_);
   return NULL != histograms_;
@@ skipping 14 matching lines @@
   if (!histograms_) {
     ANNOTATE_LEAKING_OBJECT_PTR(histogram);  // see crbug.com/79322
     return histogram;
   }
   const std::string name = histogram->histogram_name();
   HistogramMap::iterator it = histograms_->find(name);
   // Avoid overwriting a previous registration.
   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;
   }
   return 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())
     return;
 
   Histograms snapshot;
   GetSnapshot(query, &snapshot);
   for (Histograms::iterator it = snapshot.begin();
        it != snapshot.end();
        ++it) {
@@ skipping 60 matching lines @@
   if (!histograms_)
     return;
   for (HistogramMap::iterator it = histograms_->begin();
        histograms_->end() != it;
        ++it) {
     if (it->first.find(query) != std::string::npos)
       snapshot->push_back(it->second);
   }
 }
 
+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