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 261 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;
   }
   delete histograms;
+  RangesMap* ranges = NULL;
+  {
+    base::AutoLock auto_lock(*lock_);
+    ranges = ranges_;
+    ranges_ = NULL;
+  }
+  delete ranges;

[jar (doing other things), 2011/10/04 22:32:38]

I'd suggest we explicity comment that we are going to leak the histograms, and
leak the ranges.  I'd suggest putting line 1029 next to line 1036, putting them
both in a comment, and note that we will leak them deliberately.

[ramant (doing other things), 2011/10/19 01:09:52]

Done.

   // 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* cached_ranges = histogram->cached_ranges();

[jar (doing other things), 2011/10/04 22:32:38]

nit: suggest name change for the local variable here:

cached_ranges -->> histogram_ranges

[ramant (doing other things), 2011/10/19 01:09:52]

Done.

+  DCHECK(cached_ranges);
+  uint32 checksum = histogram->range_checksum();
+  cached_ranges->SetRangeChecksum(checksum);
+
+  RangesMap::iterator ranges_it = ranges_->find(checksum);
+  if (ranges_->end() == ranges_it) {
+    // Register the new CachedRanges.
+    std::list<CachedRanges*>* ranges_list(new std::list<CachedRanges*>());

[jar (doing other things), 2011/10/04 22:32:38]

nit: suggest name change for local variable:

ranges_list   -->> checksum_matching_list

[ramant (doing other things), 2011/10/19 01:09:52]

Done.

+    ranges_list->push_front(cached_ranges);
+    (*ranges_)[checksum] = ranges_list;
+    return;
+  }
+
+  // Use the registered CachedRanges if the registered CachedRanges has same
+  // ranges_ as |histogram|'s CachedRanges.
+  std::list<CachedRanges*>* ranges_list = ranges_it->second;
+  std::list<CachedRanges*>::iterator ranges_list_it;
+  for (ranges_list_it = ranges_list->begin();
+       ranges_list_it != ranges_list->end();
+       ++ranges_list_it) {
+    CachedRanges* existing_cached_ranges = *ranges_list_it;
+    DCHECK(existing_cached_ranges);
+    if (existing_cached_ranges->Equals(cached_ranges)) {
+      histogram->set_cached_ranges(existing_cached_ranges);
+      ++number_of_vectors_saved_;
+      saved_ranges_size_ += cached_ranges->size();
+      delete cached_ranges;
+      return;
+    }
+  }
+
+  // We haven't found a CachedRanges which has the same ranges. Register the
+  // new CachedRanges.
+  DCHECK(ranges_list_it == ranges_list->end());
+  ranges_list->push_front(cached_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.FirstUpload.Count." + suffix,

[jar (doing other things), 2011/10/04 22:32:38]

For histogram naming, it is always nice to have similar histograms alphabetized
near each other.  To get this, you need the least consequential stuff at teh
tail of the name.  Hence better would be something like:

Histogram.SharedRange.Count.FirstUpload
Histogram.SharedRange.RangesSaved.FirstUpload
Histogram.SharedRange.ElementsSaved.FirstUpload

I think this will work nicely, putting the three histograms about Count near
each other, etc.

[ramant (doing other things), 2011/10/19 01:09:52]

Done.

+                               number_of_histograms_);
+    UMA_HISTOGRAM_COUNTS_10000("Histogram.FirstUpload.RangesSaved." + suffix,
+                               number_of_vectors_saved_);
+    UMA_HISTOGRAM_COUNTS("Histogram.FirstUpload.RangesElementsSaved." + 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.SecondUpload.Count." + suffix,
+                               number_of_histograms_);
+    UMA_HISTOGRAM_COUNTS_10000("Histogram.SecondUpload.RangesSaved." + suffix,
+                               number_of_vectors_saved_);
+    UMA_HISTOGRAM_COUNTS("Histogram.SecondUpload.RangesElementsSaved" + 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.RestOfUploads.Count." + suffix,
+                             number_of_histograms_);
+  UMA_HISTOGRAM_COUNTS_10000("Histogram.RestOfUploads.RangesSaved." + suffix,
+                             number_of_vectors_saved_);
+  UMA_HISTOGRAM_COUNTS("Histogram.RestOfUploads.RangesElementsSaved." + 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