Bug 1383210 - Use precomputed histogram buckets r?gfritzsche draft
authorDoug Thayer <dothayer@mozilla.com>
Fri, 04 Aug 2017 10:02:28 -0700
changeset 642820 f080d418adcf695beff4914ddfbb3d08458baa64
parent 620862 32083f24a1bb2c33050b4c972783f066432194eb
child 725110 d1d84e4d2391acb8ee23e04f7cf18139f5d39df4
push id72876
push userbmo:dothayer@mozilla.com
push dateTue, 08 Aug 2017 19:49:47 +0000
reviewersgfritzsche
bugs1383210
milestone57.0a1
Bug 1383210 - Use precomputed histogram buckets r?gfritzsche The log and exp calls in base::Histogram::InitializeBucketRange() were showing up in profiles. This patch uses the precomputed buckets for exponential histograms instead of computing them at runtime. Though linear histograms do show up in the profile that prompted this change, they contribute much less, and due to the trivial nature of generating these, it's unlikely that a static cache would provide much if any speedup. MozReview-Commit-ID: IavFwoWjFhk
ipc/chromium/src/base/histogram.cc
ipc/chromium/src/base/histogram.h
toolkit/components/telemetry/TelemetryHistogram.cpp
toolkit/components/telemetry/gen-histogram-data.py
--- a/ipc/chromium/src/base/histogram.cc
+++ b/ipc/chromium/src/base/histogram.cc
@@ -79,42 +79,36 @@ 0x2d02ef8dL,
 typedef Histogram::Count Count;
 
 // static
 const size_t Histogram::kBucketCount_MAX = 16384u;
 
 Histogram* Histogram::FactoryGet(Sample minimum,
                                  Sample maximum,
                                  size_t bucket_count,
-                                 Flags flags) {
+                                 Flags flags,
+                                 const int* buckets) {
+  DCHECK(buckets);
   Histogram* histogram(NULL);
 
   // Defensive code.
   if (minimum < 1)
     minimum = 1;
   if (maximum > kSampleType_MAX - 1)
     maximum = kSampleType_MAX - 1;
 
   histogram = new Histogram(minimum, maximum, bucket_count);
-  histogram->InitializeBucketRange();
+  histogram->InitializeBucketRangeFromData(buckets);
   histogram->SetFlags(flags);
 
   DCHECK_EQ(HISTOGRAM, histogram->histogram_type());
   DCHECK(histogram->HasConstructorArguments(minimum, maximum, bucket_count));
   return histogram;
 }
 
-Histogram* Histogram::FactoryTimeGet(TimeDelta minimum,
-                                     TimeDelta maximum,
-                                     size_t bucket_count,
-                                     Flags flags) {
-  return FactoryGet(minimum.InMilliseconds(), maximum.InMilliseconds(),
-                    bucket_count, flags);
-}
-
 void Histogram::Add(int value) {
   if (value > kSampleType_MAX - 1)
     value = kSampleType_MAX - 1;
   if (value < 0)
     value = 0;
   size_t index = BucketIndex(value);
   DCHECK_GE(value, ranges(index));
   DCHECK_LT(value, ranges(index + 1));
@@ -273,49 +267,20 @@ Histogram::Histogram(TimeDelta minimum, 
   Initialize();
 }
 
 Histogram::~Histogram() {
   // 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]
-// 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);
-  while (bucket_count() > ++bucket_index) {
-    double log_current;
-    log_current = log(static_cast<double>(current));
-    // Calculate the count'th root of the range.
-    log_ratio = (log_max - log_current) / (bucket_count() - bucket_index);
-    // See where the next bucket would start.
-    log_next = log_current + log_ratio;
-    int next;
-    next = static_cast<int>(floor(exp(log_next) + 0.5));
-    if (next > current)
-      current = next;
-    else
-      ++current;  // Just do a narrow bucket, and keep trying.
-    SetBucketRange(bucket_index, current);
-  }
+void Histogram::InitializeBucketRangeFromData(const int* buckets) {
+  ranges_.assign(buckets, buckets + bucket_count());
   ResetRangeChecksum();
-
-  DCHECK_EQ(bucket_count(), bucket_index);
+  DCHECK(ValidateBucketRanges());
 }
 
 bool Histogram::PrintEmptyBucket(size_t index) const {
   return true;
 }
 
 size_t Histogram::BucketIndex(Sample value) const {
   // Use simple binary search.  This is very general, but there are better
--- a/ipc/chromium/src/base/histogram.h
+++ b/ipc/chromium/src/base/histogram.h
@@ -175,21 +175,18 @@ class Histogram {
   };
 
   //----------------------------------------------------------------------------
   // minimum should start from 1. 0 is invalid as a minimum. 0 is an implicit
   // default underflow bucket.
   static Histogram* FactoryGet(Sample minimum,
                                Sample maximum,
                                size_t bucket_count,
-                               Flags flags);
-  static Histogram* FactoryTimeGet(base::TimeDelta minimum,
-                                   base::TimeDelta maximum,
-                                   size_t bucket_count,
-                                   Flags flags);
+                               Flags flags,
+                               const int* buckets);
 
   virtual ~Histogram();
 
   void Add(int value);
   void Subtract(int value);
 
   // This method is an interface, used only by BooleanHistogram.
   virtual void AddBoolean(bool value);
@@ -243,18 +240,18 @@ class Histogram {
                                                 size_t bucket_count);
   // Return true iff the range_checksum_ matches current ranges_ vector.
   bool HasValidRangeChecksum() const;
 
  protected:
   Histogram(Sample minimum, Sample maximum, size_t bucket_count);
   Histogram(TimeDelta minimum, TimeDelta maximum, size_t bucket_count);
 
-  // Initialize ranges_ mapping.
-  void InitializeBucketRange();
+  // Initialize ranges_ mapping from raw data.
+  void InitializeBucketRangeFromData(const int* buckets);
 
   // Method to override to skip the display of the i'th bucket if it's empty.
   virtual bool PrintEmptyBucket(size_t index) const;
 
   //----------------------------------------------------------------------------
   // Methods to override to create histogram with different bucket widths.
   //----------------------------------------------------------------------------
   // Find bucket to increment for sample value.
--- a/toolkit/components/telemetry/TelemetryHistogram.cpp
+++ b/toolkit/components/telemetry/TelemetryHistogram.cpp
@@ -235,17 +235,17 @@ const HistogramID kRecordingInitiallyDis
 //
 // The core storage access functions.
 // They wrap access to the histogram storage and lookup caches.
 
 namespace {
 
 // Factory function for histogram instances.
 Histogram*
-internal_CreateHistogramInstance(const HistogramInfo& info);
+internal_CreateHistogramInstance(const HistogramInfo& info, int bucketsOffset);
 
 bool
 internal_IsHistogramEnumId(HistogramID aID)
 {
   static_assert(((HistogramID)-1 > 0), "ID should be unsigned.");
   return aID < HistogramCount;
 }
 
@@ -260,17 +260,18 @@ internal_GetHistogramById(HistogramID hi
   MOZ_ASSERT(sessionType < SessionType::Count);
 
   Histogram* h = gHistogramStorage[histogramId][uint32_t(processId)][uint32_t(sessionType)];
   if (h || !instantiate) {
     return h;
   }
 
   const HistogramInfo& info = gHistogramInfos[histogramId];
-  h = internal_CreateHistogramInstance(info);
+  const int bucketsOffset = gExponentialBucketLowerBoundIndex[histogramId];
+  h = internal_CreateHistogramInstance(info, bucketsOffset);
   MOZ_ASSERT(h);
   gHistogramStorage[histogramId][uint32_t(processId)][uint32_t(sessionType)] = h;
   return h;
 }
 
 // Look up a keyed histogram by id.
 KeyedHistogram*
 internal_GetKeyedHistogramById(HistogramID histogramId, ProcessID processId,
@@ -451,17 +452,17 @@ internal_CheckHistogramArguments(const H
       return NS_ERROR_ILLEGAL_VALUE;
     }
   }
 
   return NS_OK;
 }
 
 Histogram*
-internal_CreateHistogramInstance(const HistogramInfo& passedInfo)
+internal_CreateHistogramInstance(const HistogramInfo& passedInfo, int bucketsOffset)
 {
   if (NS_FAILED(internal_CheckHistogramArguments(passedInfo))) {
     MOZ_ASSERT(false, "Failed histogram argument checks.");
     return nullptr;
   }
 
   // To keep the code simple we map all the calls to expired histograms to the same histogram instance.
   // We create that instance lazily when needed.
@@ -478,17 +479,18 @@ internal_CreateHistogramInstance(const H
     info.bucketCount = 3;
     info.histogramType = nsITelemetry::HISTOGRAM_LINEAR;
   }
 
   Histogram::Flags flags = Histogram::kNoFlags;
   Histogram* h = nullptr;
   switch (info.histogramType) {
   case nsITelemetry::HISTOGRAM_EXPONENTIAL:
-    h = Histogram::FactoryGet(info.min, info.max, info.bucketCount, flags);
+    h = Histogram::FactoryGet(info.min, info.max, info.bucketCount, flags,
+                              &gExponentialBucketLowerBounds[bucketsOffset]);
     break;
   case nsITelemetry::HISTOGRAM_LINEAR:
   case nsITelemetry::HISTOGRAM_CATEGORICAL:
     h = LinearHistogram::FactoryGet(info.min, info.max, info.bucketCount, flags);
     break;
   case nsITelemetry::HISTOGRAM_BOOLEAN:
     h = BooleanHistogram::FactoryGet(flags);
     break;
@@ -674,17 +676,18 @@ KeyedHistogram::GetHistogram(const nsCSt
   KeyedHistogramMapType& map = mHistogramMap;
 #endif
   KeyedHistogramEntry* entry = map.GetEntry(key);
   if (entry) {
     *histogram = entry->mData;
     return NS_OK;
   }
 
-  Histogram* h = internal_CreateHistogramInstance(mHistogramInfo);
+  int bucketsOffset = gExponentialBucketLowerBoundIndex[mId];
+  Histogram* h = internal_CreateHistogramInstance(mHistogramInfo, bucketsOffset);
   if (!h) {
     return NS_ERROR_FAILURE;
   }
 
   h->ClearFlags(Histogram::kUmaTargetedHistogramFlag);
   *histogram = h;
 
   entry = map.PutEntry(key);
--- a/toolkit/components/telemetry/gen-histogram-data.py
+++ b/toolkit/components/telemetry/gen-histogram-data.py
@@ -131,16 +131,47 @@ def write_histogram_static_asserts(outpu
     for histogram in histograms:
         kind = histogram.kind()
         if kind not in table:
             raise Exception('Unknown kind "%s" for histogram "%s".' % (kind, histogram.name()))
         fn = table[kind]
         fn(output, histogram)
 
 
+def write_exponential_histogram_ranges(output, histograms):
+    # For now we use this as a special cache only for exponential histograms,
+    # which require exp and log calls that show up in profiles. Initialization
+    # of other histograms also shows up in profiles, but it's unlikely that we
+    # would see much speedup since calculating their buckets is fairly trivial,
+    # and grabbing them from static data would likely incur a CPU cache miss.
+    print("const int gExponentialBucketLowerBounds[] = {", file=output)
+    for histogram in histograms:
+        if histogram.kind() == 'exponential':
+            ranges = histogram.ranges()
+            print(','.join(map(str, ranges)), ',', file=output)
+    print("};", file=output)
+
+    print("const int gExponentialBucketLowerBoundIndex[] = {", file=output)
+    offset = 0
+    for histogram in histograms:
+        cpp_guard = histogram.cpp_guard()
+        if cpp_guard:
+            print("#if defined(%s)" % cpp_guard, file=output)
+
+        if histogram.kind() == 'exponential':
+            print("%d," % offset, file=output)
+            offset += histogram.n_buckets()
+        else:
+            print("-1,", file=output)
+
+        if cpp_guard:
+            print("#endif", file=output)
+    print("};", file=output)
+
+
 def write_debug_histogram_ranges(output, histograms):
     ranges_lengths = []
 
     # Collect all the range information from individual histograms.
     # Write that information out as well.
     print("#ifdef DEBUG", file=output)
     print("const int gBucketLowerBounds[] = {", file=output)
     for histogram in histograms:
@@ -185,14 +216,15 @@ def main(output, *filenames):
     try:
         histograms = list(histogram_tools.from_files(filenames))
     except ParserError as ex:
         print("\nError processing histograms:\n" + str(ex) + "\n")
         sys.exit(1)
 
     print(banner, file=output)
     write_histogram_table(output, histograms)
+    write_exponential_histogram_ranges(output, histograms)
     write_histogram_static_asserts(output, histograms)
     write_debug_histogram_ranges(output, histograms)
 
 
 if __name__ == '__main__':
     main(sys.stdout, *sys.argv[1:])