Bug 1383210 - Use precomputed histogram buckets r=gfritzsche
authorDoug Thayer <dothayer@mozilla.com>
Fri, 04 Aug 2017 10:02:28 -0700
changeset 425451 b8e78ebe648e320037bf5622faebbaea5fa4e29e
parent 425450 ed9ca12cb54d36f6189e24c7241e8e26a8c6a99f
child 425452 251857f1fb4be75beec78e370a05a33a55f67f8f
push id1567
push userjlorenzo@mozilla.com
push dateThu, 02 Nov 2017 12:36:05 +0000
treeherdermozilla-release@e512c14a0406 [default view] [failures only]
perfherder[talos] [build metrics] [platform microbench] (compared to previous push)
reviewersgfritzsche
bugs1383210
milestone57.0a1
first release with
nightly linux32
nightly linux64
nightly mac
nightly win32
nightly win64
last release without
nightly linux32
nightly linux64
nightly mac
nightly win32
nightly win64
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:])