Cache the ranges_ vector and share the ranges_ vector

base/metrics/histogram.cc

Index: base/metrics/histogram.cc
===================================================================
--- base/metrics/histogram.cc	(revision 97408)
+++ base/metrics/histogram.cc	(working copy)
@@ -74,6 +74,13 @@
 // 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,
@@ -355,7 +362,7 @@
 }
 
 Histogram::Sample Histogram::ranges(size_t i) const {
-  return ranges_[i];
+  return cached_ranges_->ranges(i);
 }
 
 size_t Histogram::bucket_count() const {
@@ -395,7 +402,7 @@
     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();
@@ -408,7 +415,7 @@
     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();
@@ -429,7 +436,7 @@
 // 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.
@@ -525,22 +532,23 @@
 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;
@@ -557,8 +565,8 @@
   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
@@ -1000,6 +1008,7 @@
   }
   base::AutoLock auto_lock(*lock_);
   histograms_ = new HistogramMap;
+  ranges_ = new RangesMap;
 }
 
 StatisticsRecorder::~StatisticsRecorder() {
@@ -1018,6 +1027,13 @@
     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.
 }
@@ -1052,6 +1068,8 @@
   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;
@@ -1060,6 +1078,83 @@
 }
 
 // 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())
@@ -1140,11 +1235,38 @@
   }
 }
 
+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