Serialize Histograms more efficiently.

tracing/tracing/value/histogram.html

Index: tracing/tracing/value/histogram.html
diff --git a/tracing/tracing/value/histogram.html b/tracing/tracing/value/histogram.html
index 32c1a467228788b3085c5cc8f51a88ae38da1708..34bbb4a2ec9e469c386676f65910544cf428f59c 100644
--- a/tracing/tracing/value/histogram.html
+++ b/tracing/tracing/value/histogram.html
@@ -56,19 +56,42 @@ tr.exportTo('tr.v', function() {
     }
 
     fromDict(d) {
-      this.count = d.count;
-      for (var map of d.diagnosticMaps)
-        this.diagnosticMaps.push(tr.v.d.DiagnosticMap.fromDict(map));
+      if (d instanceof Array) {
+        this.count = d[0];
+        for (var map of d[1]) {
+          this.diagnosticMaps.push(tr.v.d.DiagnosticMap.fromDict(map));
+        }
+      } else {
+        this.count = d;
+      }
     }
 
     asDict() {
-      return {
-        count: this.count,
-        diagnosticMaps: this.diagnosticMaps.map(d => d.asDict())
-      };
+      if (!this.diagnosticMaps.length) {
+        // This may be 0, in which case Histogram.asDict() can elide it.
+        return this.count;

[nednguyen, 2016/09/27 18:48:54]

ping on not special casing on this?

[benjhayden, 2016/09/27 21:05:17]

Done.

+      }
+      // It's more efficient to serialize these 2 fields in an array. If you
+      // add any other fields, you should re-evaluate whether it would be more
+      // efficient to serialize as a dict.
+      return Object.freeze([
+          this.count,
+          this.diagnosticMaps.map(d => d.asDict())
+      ]);
     }
   }
 
+  var DEFAULT_SUMMARY_OPTIONS = new Map([

[nednguyen, 2016/09/27 18:48:54]

nits: Object.freeze(..) this?

[benjhayden, 2016/09/27 21:05:16]

Hm, it looks like Object.freeze doesn't work on Maps?
https://jsfiddle.net/11kuq8m3/
http://stackoverflow.com/questions/35747325/is-there-a-way-to-freeze-a-es6-map

Also, Object.freeze() impacts performance and is not necessary for these
asDict() methods. I only added them to see if they would reveal any hidden
places that might modify the dicts on their way out of vinn. There don't seem to
be any problems with removing them.

+    ['avg', true],
+    ['geometricMean', false],
+    ['std', true],
+    ['count', true],
+    ['sum', true],
+    ['min', true],
+    ['max', true],
+    ['nans', false],
+  ]);
+
   /**
    * This is basically a histogram, but so much more.
    * Histogram is serializable using asDict/fromDict.
@@ -99,6 +122,7 @@ tr.exportTo('tr.v', function() {
       this.guid_ = undefined;
 
       this.allBins = [];
+      this.binBoundariesBuilderDict_ = binBoundaries.asDict();

[nednguyen, 2016/09/27 18:48:54]

Oh, now I see that the API is binBoundaries.asDict() and not
binBoundaries.builder.asDict(). If you choose to hide the implementation details
of binBoundaries's serialization, keep binBoundariesDict_ is fine.

Though another question: why do we need to create this object right here? Isn't
it only needed for asDict() method? 

[benjhayden, 2016/09/27 21:05:17]

I added a comment. It's possible that binBoundaries can be modified after
creating this histogram.

       this.centralBins = [];
       this.description = '';
       this.diagnostics = new tr.v.d.DiagnosticMap();
@@ -109,33 +133,37 @@ tr.exportTo('tr.v', function() {
       this.running = new tr.b.RunningStatistics();
       this.sampleValues_ = [];
       this.shortName = undefined;
-      this.summaryOptions = {
-        avg: true,
-        geometricMean: false,
-        std: true,
-        count: true,
-        sum: true,
-        min: true,
-        max: true,
-        nans: false,
-        percentile: []
-      };
+      this.summaryOptions = new Map(DEFAULT_SUMMARY_OPTIONS);
+      this.summaryOptions.set('percentile', []);

[nednguyen, 2016/09/27 18:48:54]

Why not put 'percentile' in DEFAULT_SUMMARY_OPTIONS as well?

[benjhayden, 2016/09/27 21:05:17]

I added a comment to DEFAULT_SUMMARY_OPTIONS.
Its default value is [], which is modifiable, so clients can push() to it, so
each Histogram instance needs a separate Array instance.

       this.unit = unit;
 
       this.underflowBin = new HistogramBin(tr.b.Range.fromExplicitRange(
-          -Number.MAX_VALUE, binBoundaries.minBinBoundary));
+          -Number.MAX_VALUE, binBoundaries.range.min));
       this.overflowBin = new HistogramBin(tr.b.Range.fromExplicitRange(
-          binBoundaries.maxBinBoundary, Number.MAX_VALUE));
+          binBoundaries.range.max, Number.MAX_VALUE));
 
-      for (var range of binBoundaries)
+      for (var range of binBoundaries.binRanges()) {
         this.centralBins.push(new HistogramBin(range));
+      }
 
       this.allBins.push(this.underflowBin);
       for (var bin of this.centralBins)
         this.allBins.push(bin);
       this.allBins.push(this.overflowBin);
 
-      this.maxNumSampleValues = this.allBins.length * 10;
+      this.maxNumSampleValues_ = this.defaultMaxNumSampleValues_;
+    }
+
+    get maxNumSampleValues() {
+      return this.maxNumSampleValues_;
+    }
+
+    set maxNumSampleValues(n) {
+      this.maxNumSampleValues_ = n;
+      while (this.maxNumSampleValues < this.sampleValues_.length) {
+        var i = parseInt(Math.random() * this.sampleValues_.length);

[nednguyen, 2016/09/27 18:48:54]

Ping on refactor this to a helper method 

[benjhayden, 2016/09/27 21:05:17]

Done.

+        this.sampleValues_.splice(i, 1);
+      }
     }
 
     get name() {
@@ -156,36 +184,62 @@ tr.exportTo('tr.v', function() {
       this.guid_ = guid;
     }
 
-    static fromDict(d) {
-      var boundaries = HistogramBinBoundaries.createWithBoundaries(
-          d.binBoundaries);
-      var n = new Histogram(d.name, tr.b.Unit.fromJSON(d.unit), boundaries);
-      n.guid = d.guid;
-      n.shortName = d.shortName;
-      n.description = d.description;
-      n.diagnostics.addDicts(d.diagnostics);
-
-      n.underflowBin.fromDict(d.underflowBin);
-      for (var i = 0; i < d.centralBins.length; ++i)
-        n.centralBins[i].fromDict(d.centralBins[i]);
-      n.overflowBin.fromDict(d.overflowBin);
-
-      for (var bin of n.allBins)
-        n.maxCount_ = Math.max(n.maxCount_, bin.count);
-
-      if (d.running)
-        n.running = tr.b.RunningStatistics.fromDict(d.running);
-      if (d.summaryOptions)
-        n.customizeSummaryOptions(d.summaryOptions);
-
-      n.maxNumSampleValues = d.maxNumSampleValues;
-      n.sampleValues_ = d.sampleValues;
-
-      n.numNans = d.numNans;
-      for (var map of d.nanDiagnosticMaps)
-        n.nanDiagnosticMaps.push(tr.v.d.DiagnosticMap.fromDict(map));
-
-      return n;
+    static fromDict(dict) {
+      var hist = new Histogram(dict.name,
+          tr.b.Unit.fromJSON(dict.unit),
+          HistogramBinBoundaries.fromDict(
+              dict.binBoundaries));
+      hist.guid = dict.guid;
+      if (dict.shortName) {
+        hist.shortName = dict.shortName;
+      }
+      if (dict.description) {
+        hist.description = dict.description;
+      }
+      if (dict.diagnostics) {
+        hist.diagnostics.addDicts(dict.diagnostics);
+      }
+      if (dict.underflowBin) {
+        hist.underflowBin.fromDict(dict.underflowBin);
+      }
+      if (dict.overflowBin) {
+        hist.overflowBin.fromDict(dict.overflowBin);
+      }
+      if (dict.centralBins) {
+        if (dict.centralBins.length !== undefined) {
+          for (var i = 0; i < dict.centralBins.length; ++i) {
+            hist.centralBins[i].fromDict(dict.centralBins[i]);
+          }
+        } else {
+          tr.b.iterItems(dict.centralBins, (i, binDict) => {
+            hist.centralBins[i].fromDict(binDict);
+          });
+        }
+      }
+      for (var bin of hist.allBins) {
+        hist.maxCount_ = Math.max(hist.maxCount_, bin.count);
+      }
+      if (dict.running) {
+        hist.running = tr.b.RunningStatistics.fromDict(dict.running);
+      }
+      if (dict.summaryOptions) {
+        hist.customizeSummaryOptions(dict.summaryOptions);
+      }
+      if (dict.maxNumSampleValues !== undefined) {
+        hist.maxNumSampleValues = dict.maxNumSampleValues;
+      }
+      if (dict.sampleValues) {
+        hist.sampleValues_ = dict.sampleValues;
+      }
+      if (dict.numNans) {
+        hist.numNans = dict.numNans;
+      }
+      if (dict.nanDiagnostics) {
+        for (var map of dict.nanDiagnostics) {
+          hist.nanDiagnosticMaps.push(tr.v.d.DiagnosticMap.fromDict(map));
+        }
+      }
+      return hist;
     }
 
     /**
@@ -390,9 +444,8 @@ tr.exportTo('tr.v', function() {
      * The options not included in the |summaryOptions| will not change.
      */
     customizeSummaryOptions(summaryOptions) {
-      tr.b.iterItems(summaryOptions, function(key, value) {
-        this.summaryOptions[key] = value;
-      }, this);
+      tr.b.iterItems(summaryOptions, (key, value) =>
+          this.summaryOptions.set(key, value));
     }
 
     /**
@@ -441,16 +494,17 @@ tr.exportTo('tr.v', function() {
       }
 
       var results = new Map();
-      tr.b.iterItems(this.summaryOptions, function(stat, option) {
-        if (!option)
-          return;
+      for (var [stat, option] of this.summaryOptions) {
+        if (!option) {
+          continue;
+        }
 
         if (stat === 'percentile') {
-          option.forEach(function(percent) {
+          for (var percent of option) {
             var percentile = this.getApproximatePercentile(percent);
             results.set('pct_' + percentToString(percent),
                 new tr.v.ScalarNumeric(this.unit, percentile));
-          }, this);
+          }
         } else if (stat === 'nans') {
           results.set('nans', new tr.v.ScalarNumeric(
               tr.b.Unit.byName.count_smallerIsBetter, this.numNans));
@@ -464,7 +518,7 @@ tr.exportTo('tr.v', function() {
             results.set(stat, new tr.v.ScalarNumeric(statUnit, statValue));
           }
         }
-      }, this);
+      }
       return results;
     }
 
@@ -472,51 +526,143 @@ tr.exportTo('tr.v', function() {
       return this.sampleValues_;
     }
 
-    get binBoundaries() {
-      var boundaries = [];
-      for (var bin of this.centralBins)
-        boundaries.push(bin.range.min);
-      boundaries.push(this.overflowBin.range.min);
-      return boundaries;
-    }
-
+    /**
+     * Create a new Histogram object that is exactly the same as this one, with
+     * this Histogram's name, unit, and binBoundaries, guid, bin counts, and
+     * diagnostics.
+     * @return {!tr.v.Histogram}
+     */
     clone() {
       return Histogram.fromDict(this.asDict());
     }
 
+    /**
+     * Create a new Histogram with this Histogram's name, unit, and
+     * binBoundaries, but not its guid, bin counts, or diagnostics.
+     * @return {!tr.v.Histogram}
+     */
+    cloneEmpty() {
+      var binBoundaries = HistogramBinBoundaries.fromDict(
+          this.binBoundariesBuilderDict_);
+      return new Histogram(this.name, this.unit, binBoundaries);
+    }
+
     asDict() {
-      return {
-        name: this.name,
-        guid: this.guid,
-        shortName: this.shortName,
-        description: this.description,
-        diagnostics: this.diagnostics.asDict(),
-        unit: this.unit.asJSON(),
-        binBoundaries: this.binBoundaries,
+      var dict = {};
+      dict.binBoundaries = this.binBoundariesBuilderDict_;
+      dict.name = this.name;
+      dict.unit = this.unit.asJSON();
+      dict.guid = this.guid;
+      if (this.shortName) {
+        dict.shortName = this.shortName;
+      }
+      if (this.description) {
+        dict.description = this.description;
+      }
+      if (this.diagnostics.size) {
+        dict.diagnostics = this.diagnostics.asDict();
+      }
+      if (this.maxNumSampleValues !== this.defaultMaxNumSampleValues_) {
+        dict.maxNumSampleValues = this.maxNumSampleValues;
+      }
+      if (this.numNans) {
+        dict.numNans = this.numNans;
+      }
+      if (this.nanDiagnosticMaps.length) {
+        dict.nanDiagnostics = this.nanDiagnosticMaps.map(
+            dm => dm.asDict());
+      }
+      var underflowBin = this.underflowBin.asDict();
+      if (tr.b.dictionaryLength(underflowBin)) {
+        dict.underflowBin = underflowBin;
+      }
+      var overflowBin = this.overflowBin.asDict();
+      if (tr.b.dictionaryLength(overflowBin)) {
+        dict.overflowBin = overflowBin;
+      }
 
-        underflowBin: this.underflowBin.asDict(),
-        centralBins: this.centralBins.map(bin => bin.asDict()),
-        overflowBin: this.overflowBin.asDict(),
+      if (this.numValues) {
+        dict.sampleValues = this.sampleValues.slice();
+        dict.running = this.running.asDict();
+
+        // If all centralBins are empty, then don't serialize anything for them.
+        var anyCentralBins = false;
+
+        // CENTRAL_BINS may be either an array or a dict, whichever is more
+        // efficient.

[nednguyen, 2016/09/27 18:48:54]

Can you factor the logic of serializing CENTRAL_BINS to a separate method? this
asDict() method is getting too long..

[benjhayden, 2016/09/27 21:05:16]

Done.

+        var centralBinsArray = [];
+        var centralBinsDict = {};
+
+        // Compute which of centralBinsArray or centralBinsDict is more
+        // efficient. Both contain begin/end brackets and non-empty bins, so
+        // ignore those.
+        var centralBinsArrayOverhead = 0;

[nednguyen, 2016/09/27 18:48:54]

I think this is a bit too complicated. Since the only extra overhead of the
dictionary form is the index (should not exceeds 10k) plus the colon and comma
which is very negligible, I think it's ok to just use the dict form over the
array form.

I would choose code simplicity, except when efficiency win is huge.

In addition, a problem with "try both & pick the less overhead" strategy is that
it increases peak heap memory usage.

[benjhayden, 2016/09/27 21:05:16]

If a histogram has 1000 bins and they are all non-empty, dictOverhead=4890 and
arrayOverhead=1000.

[nednguyen, 2016/09/27 21:46:29]

You convinced me with your number that this is needed. Though can you find a
simpler heuristic, s.t like if 50% bin are non empty, then use array form? I
think the problem with heap space growing as we try both is still there.

[benjhayden, 2016/09/27 22:47:50]

I didn't expect the tipping point to actually be at 50% since the overhead
calculation is so complex, but I ran a simulation, and the tipping point drops
exponentially from 100% at 2 bins to 55% at 20 bins to 50.5% at 200 bins to
50.1% at 1000 bins. So I'll just go with 50%.

I still need to iterate over all centralBins twice, though, in order to avoid
computing both the array and dictionary forms, since Histogram doesn't keep
track of empty bins as it's being built.

+        var centralBinsDictOverhead = 0;
+
+        for (var bin of this.centralBins) {
+          var binDict = bin.asDict();
+          if (binDict) {
+            anyCentralBins = true;
+            centralBinsDict[centralBinsArray.length] = binDict;
+            // centralBinsDict only contains overhead for non-empty bins.
+            // The overhead is the length of the index plus the colon and comma.
+            centralBinsDictOverhead +=
+                2 + (centralBinsArray.length + '').length;
+          } else {
+            // centralBinsArray contains overhead for empty bins.
+            // The length of the value (that HistogramBin.asDict() returns when
+            // count === 0) is 1.
+            centralBinsArrayOverhead += 1;
+          }
+          // centralBinsArray contains a comma for every bin.
+          centralBinsArrayOverhead += 1;
+          centralBinsArray.push(binDict);
+        }
+
+        if (anyCentralBins) {
+          if (centralBinsDictOverhead >= centralBinsArrayOverhead) {
+            dict.centralBins = Object.freeze(centralBinsArray);
+          } else {
+            dict.centralBins = Object.freeze(centralBinsDict);
+          }
+        }
+      }
 
-        running: this.running.asDict(),
-        summaryOptions: this.summaryOptions,
+      var summaryOptions = {};
+      var anyOverriddenSummaryOptions = false;
+      for (var [name, option] of this.summaryOptions) {
+        if (name === 'percentile') {
+          if (option.length === 0) {
+            continue;
+          }
+          option = option.slice();
+        } else if (option === DEFAULT_SUMMARY_OPTIONS.get(name)) {
+          continue;
+        }
+        summaryOptions[name] = option;
+        anyOverriddenSummaryOptions = true;
+      }
+      if (anyOverriddenSummaryOptions) {
+        dict.summaryOptions = Object.freeze(summaryOptions);
+      }
 
-        maxNumSampleValues: this.maxNumSampleValues,
-        sampleValues: this.sampleValues,
+      return Object.freeze(dict);
+    }
 
-        numNans: this.numNans,
-        nanDiagnosticMaps: this.nanDiagnosticMaps.map(dm => dm.asDict()),
-      };
+    get defaultMaxNumSampleValues_() {
+      return this.allBins.length * 10;
     }
   }
 
+  var HISTOGRAM_BIN_BOUNDARIES_CACHE = new Map();
+
   /**
    * Reusable builder for tr.v.Histogram objects.
    *
    * The bins of the numeric are specified by adding the desired boundaries
    * between bins. Initially, the builder has only a single boundary:
    *
-   *       minBinBoundary=maxBinBoundary
+   *            range.min=range.max
    *                     |
    *                     |
    *   -MAX_INT <--------|------------------------------------------> +MAX_INT
@@ -527,7 +673,7 @@ tr.exportTo('tr.v', function() {
    * More boundaries can be added (in increasing order) using addBinBoundary,
    * addLinearBins and addExponentialBins:
    *
-   *              minBinBoundary                      maxBinBoundary
+   *                range.min                           range.max
    *                     |         |         |     |         |
    *                     |         |         |     |         |
    *   -MAX_INT <--------|---------|---------|-----|---------|------> +MAX_INT
@@ -538,11 +684,6 @@ tr.exportTo('tr.v', function() {
    * An important feature of the builder is that it's reusable, i.e. it can be
    * used to build multiple numerics with the same unit and bin structure.
    *
-   * @constructor
-   * @param {!tr.b.Unit} unit Unit of the resulting Histogram(s).
-   * @param {number} minBinBoundary The minimum boundary between bins, namely
-   *     the underflow bin and the first central bin (or the overflow bin if
-   *     no other boundaries are added later).
    */
   class HistogramBinBoundaries {
     /**
@@ -603,46 +744,141 @@ tr.exportTo('tr.v', function() {
     }
 
     /**
-     * @param {number} minBinBoundary
+     * @param {number} minBinBoundary The minimum boundary between bins, namely
+     *     the underflow bin and the first central bin (or the overflow bin if
+     *     no other boundaries are added later).
      */
     constructor(minBinBoundary) {
-      this.boundaries_ = [minBinBoundary];
+      this.boundaries_ = undefined;
+      this.builder_ = [minBinBoundary];
+      this.range_ = new tr.b.Range();
+      this.range_.addValue(minBinBoundary);
     }
 
-    get minBinBoundary() {
-      return this.boundaries_[0];
+    get range() {
+      return this.range_;
     }
 
-    get maxBinBoundary() {
-      return this.boundaries_[this.boundaries_.length - 1];
+    asDict() {
+      // Deep-copy builder_ in case ours is modified later.
+      var dict = [];
+      for (var slice of this.builder_) {
+        if (slice instanceof Array) {
+          dict.push(Object.freeze(slice.slice()));
+        } else {
+          dict.push(slice);
+        }
+      }
+      return Object.freeze(dict);
+    }
+
+    static fromDict(dict) {
+      // When loading a results2.html with many Histograms with the same bin
+      // boundaries, caching the HistogramBinBoundaries not only speeds up
+      // loading, but also prevents a bug where build_ is occasionally
+      // non-deterministic, which causes similar Histograms to be unmergeable.
+      var cacheKey = JSON.stringify(dict);
+      if (HISTOGRAM_BIN_BOUNDARIES_CACHE.has(cacheKey)) {
+        return HISTOGRAM_BIN_BOUNDARIES_CACHE.get(cacheKey);
+      }
+
+      var binBoundaries = new HistogramBinBoundaries(dict[0]);
+      for (var slice of dict.slice(1)) {
+        if (!(slice instanceof Array)) {
+          binBoundaries.addBinBoundary(slice);
+          continue;
+        }
+        switch (slice[0]) {
+          case HistogramBinBoundaries.SLICE_TYPE.LINEAR:
+            binBoundaries.addLinearBins(slice[1], slice[2]);
+            break;
+
+          case HistogramBinBoundaries.SLICE_TYPE.EXPONENTIAL:
+            binBoundaries.addExponentialBins(slice[1], slice[2]);
+            break;
+
+          default:
+            throw new Error('Unrecognized HistogramBinBoundaries slice type');
+        }
+      }
+      HISTOGRAM_BIN_BOUNDARIES_CACHE.set(cacheKey, binBoundaries);
+      return binBoundaries;
     }
 
     /**
      * Yield Ranges of adjacent boundaries.
      */
-    *[Symbol.iterator]() {
+    *binRanges() {
+      if (this.boundaries_ === undefined) {
+        this.build_();
+      }
       for (var i = 0; i < this.boundaries_.length - 1; ++i) {
         yield tr.b.Range.fromExplicitRange(
             this.boundaries_[i], this.boundaries_[i + 1]);
       }
     }
 
+    build_() {
+      if (typeof this.builder_[0] !== 'number') {
+        throw new Error('Invalid start of builder_');
+      }
+      this.boundaries_ = [this.builder_[0]];
+
+      for (var slice of this.builder_.slice(1)) {
+        if (!(slice instanceof Array)) {
+          this.boundaries_.push(slice);
+          continue;
+        }
+        var nextMaxBinBoundary = slice[1];
+        var binCount = slice[2];
+        var curMaxBinBoundary = this.boundaries_[
+            this.boundaries_.length - 1];
+
+        switch (slice[0]) {
+          case HistogramBinBoundaries.SLICE_TYPE.LINEAR:
+            var binWidth = (nextMaxBinBoundary - curMaxBinBoundary) / binCount;
+            for (var i = 1; i < binCount; i++) {
+              var boundary = curMaxBinBoundary + i * binWidth;
+              this.boundaries_.push(boundary);
+            }
+            break;
+
+          case HistogramBinBoundaries.SLICE_TYPE.EXPONENTIAL:
+            var binExponentWidth =
+                Math.log(nextMaxBinBoundary / curMaxBinBoundary) / binCount;
+            for (var i = 1; i < binCount; i++) {
+              var boundary = curMaxBinBoundary * Math.exp(i * binExponentWidth)
+              this.boundaries_.push(boundary);
+            }
+            break;
+
+          default:
+            throw new Error('Unrecognized HistogramBinBoundaries slice type');
+        }
+        this.boundaries_.push(nextMaxBinBoundary);
+      }
+    }
+
     /**
      * Add a bin boundary |nextMaxBinBoundary| to the builder.
      *
      * This operation effectively corresponds to appending a new central bin
-     * with the range [this.maxBinBoundary*, nextMaxBinBoundary].
+     * with the range [this.range.max, nextMaxBinBoundary].
      *
      * @param {number} nextMaxBinBoundary The added bin boundary (must be
      *     greater than |this.maxMinBoundary|).
      */
     addBinBoundary(nextMaxBinBoundary) {
-      if (nextMaxBinBoundary <= this.maxBinBoundary) {
+      if (nextMaxBinBoundary <= this.range.max) {
         throw new Error('The added max bin boundary must be larger than ' +
             'the current max boundary');
       }
-      this.boundaries_.push(nextMaxBinBoundary);
 
+      // If boundaries_ had been built, then clear them.
+      this.boundaries_ = undefined;
+
+      this.builder_.push(nextMaxBinBoundary);
+      this.range.addValue(nextMaxBinBoundary);
       return this;
     }
 
@@ -652,7 +888,7 @@ tr.exportTo('tr.v', function() {
      *
      * This operation corresponds to appending |binCount| central bins of
      * constant range width
-     * W = ((|nextMaxBinBoundary| - |this.maxBinBoundary|) / |binCount|)
+     * W = ((|nextMaxBinBoundary| - |this.range.max|) / |binCount|)
      * with the following ranges:
      *
      *   [|this.maxMinBoundary|, |this.maxMinBoundary| + W]
@@ -672,17 +908,17 @@ tr.exportTo('tr.v', function() {
       if (binCount <= 0)
         throw new Error('Bin count must be positive');
 
-      var curMaxBinBoundary = this.maxBinBoundary;
-      if (curMaxBinBoundary >= nextMaxBinBoundary) {
+      if (nextMaxBinBoundary <= this.range.max) {
         throw new Error('The new max bin boundary must be greater than ' +
             'the previous max bin boundary');
       }
 
-      var binWidth = (nextMaxBinBoundary - curMaxBinBoundary) / binCount;
-      for (var i = 1; i < binCount; i++)
-        this.addBinBoundary(curMaxBinBoundary + i * binWidth);
-      this.addBinBoundary(nextMaxBinBoundary);
+      // If boundaries_ had been built, then clear them.
+      this.boundaries_ = undefined;
 
+      this.builder_.push([HistogramBinBoundaries.SLICE_TYPE.LINEAR,
+          nextMaxBinBoundary, binCount]);
+      this.range.addValue(nextMaxBinBoundary);
       return this;
     }
 
@@ -692,7 +928,7 @@ tr.exportTo('tr.v', function() {
      *
      * This operation corresponds to appending |binCount| central bins with
      * a constant difference between the logarithms of their range min and max
-     * D = ((ln(|nextMaxBinBoundary|) - ln(|this.maxBinBoundary|)) / |binCount|)
+     * D = ((ln(|nextMaxBinBoundary|) - ln(|this.range.max|)) / |binCount|)
      * with the following ranges:
      *
      *   [|this.maxMinBoundary|, |this.maxMinBoundary| * exp(D)]
@@ -711,29 +947,32 @@ tr.exportTo('tr.v', function() {
      * @param {number} binCount Number of bins to be added (must be positive).
      */
     addExponentialBins(nextMaxBinBoundary, binCount) {
-      if (binCount <= 0)
+      if (binCount <= 0) {
         throw new Error('Bin count must be positive');
-
-      var curMaxBinBoundary = this.maxBinBoundary;
-      if (curMaxBinBoundary <= 0)
+      }
+      if (this.range.max <= 0) {
         throw new Error('Current max bin boundary must be positive');
-      if (curMaxBinBoundary >= nextMaxBinBoundary) {
+      }
+      if (this.range.max >= nextMaxBinBoundary) {
         throw new Error('The last added max boundary must be greater than ' +
             'the current max boundary boundary');
       }
 
-      var binExponentWidth =
-          Math.log(nextMaxBinBoundary / curMaxBinBoundary) / binCount;
-      for (var i = 1; i < binCount; i++) {
-        this.addBinBoundary(
-            curMaxBinBoundary * Math.exp(i * binExponentWidth));
-      }
-      this.addBinBoundary(nextMaxBinBoundary);
+      // If boundaries_ had been built, then clear them.

[nednguyen, 2016/09/27 18:48:54]

This seems like a big change to existing API of histogram? On the left, I don't
find any logic that clear existing boundaries

[benjhayden, 2016/09/27 21:05:17]

The existing boundaries are preserved in builder_.

+      this.boundaries_ = undefined;
 
+      this.builder_.push([HistogramBinBoundaries.SLICE_TYPE.EXPONENTIAL,
+          nextMaxBinBoundary, binCount]);
+      this.range.addValue(nextMaxBinBoundary);

[nednguyen, 2016/09/27 18:48:54]

why not this.addBinBoundary(nextMaxBinBoundary) here?

[benjhayden, 2016/09/27 21:05:17]

That's not how it works.
Callers call addBinBoundary/addLinearBins/addExponentialBins. Those methods add
elements to builder_, not boundaries_.
When a Histogram calls binRanges(), HBB builds boundaries_ from builder_.
There are several HBBs created statically in metrics and in this file. Many of
them might never be used, so we can speed up loading trace-viewer by delaying
computing boundaries_ until they are needed.
Many Histograms can re-use the same HBB, so it is useful to cache boundaries_ in
HBB. And Histograms need the builder_, so HBB must keep both its builder_ and
its boundaries_.
But if an HBB is modified after a Histogram uses its boundaries_, then the
boundaries_ must be updated. The same logic applies for a never-used HBB as an
HBB that was modified after it was used: its updated boundaries_ might never be
needed.
Now, if you're suggesting that, since an HBB was used once, then it will
probably be used again after it was modified, then I can refactor build_ so that
it can be called either all at once or iteratively as clients modify it, and it
would behave differently based on whether it had ever been used, so that it
wouldn't need to re-compute old boundaries for old builder slices.
I can do that. But it would be complicated, and I feel like I might already be
over-optimizing just a bit.

       return this;
     }
   }
 
+  HistogramBinBoundaries.SLICE_TYPE = {
+    LINEAR: 0,
+    EXPONENTIAL: 1,
+  };
+
   DEFAULT_BOUNDARIES_FOR_UNIT.set(
       tr.b.Unit.byName.timeDurationInMs.unitName,
       HistogramBinBoundaries.createExponential(1e-3, 1e6, 1e2));