Add mutator utilization metric.

tracing/tracing/metrics/v8/utils.html

Index: tracing/tracing/metrics/v8/utils.html
diff --git a/tracing/tracing/metrics/v8/utils.html b/tracing/tracing/metrics/v8/utils.html
index cf9fae1e34644a40d98ce8ebbf895f7a8ab13e42..2f5607bca89a1f7abca6f287a0e67fa5a07a3568 100644
--- a/tracing/tracing/metrics/v8/utils.html
+++ b/tracing/tracing/metrics/v8/utils.html
@@ -17,6 +17,9 @@ tr.exportTo('tr.metrics.v8.utils', function() {
   // The title of the idle task event.
   var IDLE_TASK_EVENT = 'SingleThreadIdleTaskRunner::RunTask';
 
+  // V8 execution event.
+  var V8_EXECUTE = 'V8.Execute';
+
   // GC events start with this prefix.
   var GC_EVENT_PREFIX = 'V8.GC';
 
@@ -59,6 +62,14 @@ tr.exportTo('tr.metrics.v8.utils', function() {
     return event.title === LOW_MEMORY_EVENT;
   }
 
+  function isV8ExecuteEvent(event) {
+    return event.title === V8_EXECUTE;
+  }
+
+  function isTopV8ExecuteEvent(event) {
+    return isV8ExecuteEvent(event) && findParent(isV8ExecuteEvent) === null;
+  }
+
   function isGarbageCollectionEvent(event) {
     // Low memory notification is handled specially because it contains
     // several full mark compact events.
@@ -96,15 +107,239 @@ tr.exportTo('tr.metrics.v8.utils', function() {
     return prefix + '.' + name;
   }
 
+

[eakuefner, 2016/04/20 17:25:54]

You should look into base/ to see if there's math that you can reuse here.
https://github.com/catapult-project/catapult/tree/master/tracing/tracing/base

math and range_utils may be of particular interest. If there are any math basics
that base doesn't provide that you need, you should likely implement them there
instead of here.

[ulan, 2016/04/20 18:47:04]

Done. Moved PiecewiseLinearFunction to base and renamed Segment to Piece since
it is not a general math segment but representation of PLF piece.

+  /**
+  * A linear segment from (x1, y1) to (x2, y2).
+  * @constructor
+  */
+  function Segment(x1, y1, x2, y2) {
+    this.x1 = x1;
+    this.y1 = y1;
+    this.x2 = x2;
+    this.y2 = y2;
+  }
+
+  Segment.prototype = {
+    /**
+    * The total length of all x points such that f(x) < y.
+    * More formally:
+    * max(x2 - x1) such that for all x in [x1 .. x2]: f(x) < y.
+    */
+    partBelow: function(y) {
+      var width = this.width();
+      if (width == 0) return 0;
+      var minY = this.min();
+      var maxY = this.max();
+      if (y >= maxY)
+        return width;
+      if (y < minY)
+        return 0;
+      return (y - minY) / (maxY - minY) * width;
+    },
+
+    min: function() {
+      return Math.min(this.y1, this.y2);
+    },
+
+    max: function() {
+      return Math.max(this.y1, this.y2);
+    },
+
+    average: function() {
+      return (this.y1 + this.y2) / 2;
+    },
+
+    width: function() {
+      return this.x2 - this.x1;
+    }
+  };
+
+  /**
+  * A function that consists of linear pieces.
+  * See https://en.wikipedia.org/wiki/Piecewise_linear_function.
+  * @constructor
+  */
+  function PiecewiseLinearFunction() {
+    this.pieces = [];
+  }
+
+  PiecewiseLinearFunction.prototype = {
+    /**
+    * Push a linear piece defined by linear interpolation of
+    * (x1, y1) and (x2, y2).
+    */
+    push: function(x1, y1, x2, y2) {
+      if (x1 > x2)
+        throw 'Invalid segment';
+      if (x1 < x2)
+        this.pieces.push(new Segment(x1, y1, x2, y2));
+    },
+
+    /**
+    * The total length of all x points for which f(x) < y.
+    */
+    partBelow: function(y) {
+      return this.pieces.reduce((acc, x) => (acc + x.partBelow(y)), 0);
+    },
+
+    min: function() {
+      return this.pieces.reduce((acc, x) => Math.min(acc, x.min()), Infinity);
+    },
+
+    max: function() {
+      return this.pieces.reduce((acc, x) => Math.max(acc, x.max()), -Infinity);
+    },
+
+    average: function() {
+      var weightedSum = 0;
+      var totalWeight = 0;
+      this.pieces.forEach(function(piece) {
+        weightedSum += piece.width() * piece.average();
+        totalWeight += piece.width();
+      });
+      if (totalWeight == 0)
+        return 0;
+      return weightedSum / totalWeight;
+    },
+
+    /**
+    * Returns the minimum possible value y such that the percentage of x points
+    * that have f(x) <= y is equal to the given |percent|.
+    */
+    percentile: function(percent) {
+      if (!(percent >= 0 && percent <= 1))
+        throw new Error('percent must be [0,1]');
+      var lower = this.min();
+      var upper = this.max();
+      var total = this.partBelow(upper);
+      var PRECISION = 1e-7;
+      if (total == 0) return 0;
+      while (upper - lower > PRECISION) {
+        var middle = (lower + upper) / 2;
+        var below = this.partBelow(middle);
+        if (below / total < percent) {
+          lower = middle;
+        } else {
+          upper = middle;
+        }
+      }
+      return (lower + upper) / 2;
+    }
+  };
+
+  /**
+  * Given a list of intervals, returns a new list with all overalapping
+  * intervals merged into a single interval.
+  */
+  function unionOfIntervals(intervals) {
+    if (intervals.length == 0)
+      return intervals;
+    intervals.sort((a, b) => (a.start - b.start));
+    var result = [];
+    function copy(interval) {
+      return {start: interval.start, end: interval.end };
+    }
+    var last = copy(intervals[0]);
+    intervals.forEach(function(interval) {
+      if (last.end < interval.start) {
+        result.push(last);
+        last = copy(interval);
+      } else {
+        last.end = Math.max(last.end, interval.end);
+      }
+    });
+    result.push(last);
+    return result;
+  }
+
+  /**
+  * Returns mutator utilization as a piecewise linear function.
+  * See "A Parallel, Real-Time Garbage Collector" by Cheng et. al. for
+  * the definition of mutator utilization.
+  * @param {Number} start The start time of execution.
+  * @param {Number} end The end time of execution.
+  * @param {Number} timeWindow The size of the time window.
+  * @param {Array} intervals The list of GC pauses, where each interval
+  *   has start and end field.
+  */
+  function mutatorUtilization(start, end, timeWindow, intervals) {
+    var mu = new PiecewiseLinearFunction();
+    if (end - start <= timeWindow)
+      return mu;
+    if (intervals.length == 0) {
+      mu.push(start, 1.0, end - timeWindow, 1.0);
+      return mu;
+    }
+    intervals = unionOfIntervals(intervals);
+    var points = [];
+    intervals.forEach(function(interval) {
+      points.push({position: interval.start, delta: 1});
+      points.push({position: interval.end, delta: -1});
+    });
+    points.sort((a, b) => a.position - b.position);
+    points.push({position: end, delta: 0});
+    var left = {
+      index: -1,
+      position: start,
+      remainder: points[0].position - start,
+      pause: 0,
+      stack: 0
+    };
+    var right = {
+      index: -1,
+      position: start,
+      remainder: points[0].position - start,
+      pause: 0,
+      stack: 0
+    };
+    while (right.position - left.position < timeWindow) {
+      advance(right, timeWindow - (right.position - left.position));
+    }
+    while (right.index < points.length) {
+      var remainder = Math.min(left.remainder, right.remainder);
+      var position1 = left.position;
+      var value1 = right.pause - left.pause;
+      advance(left, remainder);
+      advance(right, remainder);
+      var position2 = left.position;
+      var value2 = right.pause - left.pause;
+      mu.push(position1, 1.0 - value1 / timeWindow,
+              position2, 1.0 - value2 / timeWindow);
+    }
+    function advance(point, delta) {
+      if (delta < point.remainder) {
+        point.position += delta;
+        point.pause += point.stack > 0 ? delta : 0;
+        point.remainder = points[point.index + 1].position - point.position;
+      } else {
+        point.position += point.remainder;
+        point.pause += point.stack > 0 ? point.remainder : 0;
+        point.remainder = 0;
+        point.index += 1;
+        if (point.index < points.length) {
+          point.stack += points[point.index].delta;
+          if (point.index + 1 < points.length)
+            point.remainder = points[point.index + 1].position - point.position;
+        }
+      }
+    }
+    return mu;
+  }
+
   return {
     findParent: findParent,
     isIdleTask: isIdleTask,
     isLowMemoryEvent: isLowMemoryEvent,
+    isV8ExecuteEvent: isV8ExecuteEvent,
+    isTopV8ExecuteEvent: isTopV8ExecuteEvent,
     isGarbageCollectionEvent: isGarbageCollectionEvent,
     isTopGarbageCollectionEvent: isTopGarbageCollectionEvent,
     isSubGarbageCollectionEvent: isSubGarbageCollectionEvent,
     topGarbageCollectionEventName: topGarbageCollectionEventName,
-    subGarbageCollectionEventName: subGarbageCollectionEventName
+    subGarbageCollectionEventName: subGarbageCollectionEventName,
+    PiecewiseLinearFunction: PiecewiseLinearFunction,
+    unionOfIntervals: unionOfIntervals,
+    mutatorUtilization: mutatorUtilization
   };
 });
 </script>