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..0a14dd4db5aaa332b2efb2499efab2794819008f 100644
--- a/tracing/tracing/metrics/v8/utils.html
+++ b/tracing/tracing/metrics/v8/utils.html
@@ -4,7 +4,9 @@ Copyright 2016 The Chromium Authors. All rights reserved.
 Use of this source code is governed by a BSD-style license that can be
 found in the LICENSE file.
 -->
+<link rel="import" href="/tracing/base/piecewise_linear_function.html">
 <link rel="import" href="/tracing/base/range.html">
+<link rel="import" href="/tracing/base/range_utils.html">
 <link rel="import" href="/tracing/metrics/metric_registry.html">
 <link rel="import" href="/tracing/value/numeric.html">
 <link rel="import" href="/tracing/value/unit.html">
@@ -17,6 +19,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';
 
@@ -38,8 +43,8 @@ tr.exportTo('tr.metrics.v8.utils', function() {
   };
 
   /**
-  * Finds the first parent of the |event| for which the |predicate| holds.
-  */
+   * Finds the first parent of the |event| for which the |predicate| holds.
+   */
   function findParent(event, predicate) {
     var parent = event.parentSlice;
     while (parent) {
@@ -59,6 +64,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 +109,146 @@ tr.exportTo('tr.metrics.v8.utils', function() {
     return prefix + '.' + name;
   }
 
+  /**
+  * 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 [];
+    return tr.b.mergeRanges(
+      intervals.map(x => ({min: x.start, max: x.end})), 1e-6,
+      function(ranges) {
+        return {
+          start: ranges.reduce((acc, x) => Math.min(acc, x.min), ranges[0].min),
+          end: ranges.reduce((acc, x) => Math.max(acc, x.max), ranges[0].max)
+        };
+      }
+    );
+  }
+
+  /**
+   * An end-point of a window that is sliding from left to right
+   * over |points| starting from time |start|.
+   * It is intended to be used only by the |mutatorUtilization| function.
+   * @constructor
+   */
+  function WindowEndpoint(start, points) {
+    this.points = points;
+    // The index of the last passed point.
+    this.lastIndex = -1;
+    // The position of the end-point in the time line.
+    this.position = start;
+    // The distance until the next point.
+    this.distanceUntilNextPoint = points[0].position - start;
+    // The cumulative duration of GC pauses until this position.
+    this.cummulativePause = 0;
+    // The number of entered GC intervals.
+    this.stackDepth = 0;
+  }
+
+  WindowEndpoint.prototype = {
+    // Advance the end-point by the given |delta|.
+    advance: function(delta) {
+      var points = this.points;
+      if (delta < this.distanceUntilNextPoint) {
+        this.position += delta;
+        this.cummulativePause += this.stackDepth > 0 ? delta : 0;
+        this.distanceUntilNextPoint =
+            points[this.lastIndex + 1].position - this.position;
+      } else {
+        this.position += this.distanceUntilNextPoint;
+        this.cummulativePause +=
+            this.stackDepth > 0 ? this.distanceUntilNextPoint : 0;
+        this.distanceUntilNextPoint = 0;
+        this.lastIndex++;
+        if (this.lastIndex < points.length) {
+          this.stackDepth += points[this.lastIndex].delta;
+          if (this.lastIndex + 1 < points.length)
+            this.distanceUntilNextPoint =
+                points[this.lastIndex + 1].position - this.position;
+        }
+      }
+    }
+  };
+
+  /**
+   * Returns mutator utilization as a piecewise linear function.
+   * Mutator utilization for a window size w is a function of time mu_w(t)
+   * that shows how much time in [t, t+w] is left for the mutator relative
+   * to the time window size.
+   * More formally:
+   * mu_w(t) = (w - total_time_spent_in_gc_in(t, t + w)) / w.
+   * The range of mu_w(t) is [0..1].
+   * See "A Parallel, Real-Time Garbage Collector" by Cheng et. al. for
+   * more info [https://www.cs.cmu.edu/~guyb/papers/gc2001.pdf].
+   *
+   * All parameters must use the same time unit.
+   * @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<!{start: number, end: number}>} intervals The list of
+   *     GC pauses.
+   */
+  function mutatorUtilization(start, end, timeWindow, intervals) {
+    var mu = new tr.b.PiecewiseLinearFunction();
+    // If the interval is smaller than the time window, then the function is
+    // empty.
+    if (end - start <= timeWindow)
+      return mu;
+    // If there are GC pauses then the mutator utilization is 1.0.
+    if (intervals.length === 0) {
+      mu.push(start, 1.0, end - timeWindow, 1.0);
+      return mu;
+    }
+    intervals = unionOfIntervals(intervals);
+    // Create a point for the start and the end of each interval.
+    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});
+    // The left and the right limit of the sliding window.
+    var left = new WindowEndpoint(start, points);
+    var right = new WindowEndpoint(start, points);
+    // Advance the right end-point until we get the correct window size.
+    while (right.position - left.position < timeWindow)
+      right.advance(timeWindow - (right.position - left.position));
+    while (right.lastIndex < points.length) {
+      // Advance the window end-points by the largest possible amount
+      // without jumping over a point.
+      var distanceUntilNextPoint =
+          Math.min(left.distanceUntilNextPoint, right.distanceUntilNextPoint);
+      var position1 = left.position;
+      var value1 = right.cummulativePause - left.cummulativePause;
+      left.advance(distanceUntilNextPoint);
+      right.advance(distanceUntilNextPoint);
+      // Add a new mutator utilization segment only if it is non-trivial.
+      if (distanceUntilNextPoint > 0) {
+        var position2 = left.position;
+        var value2 = right.cummulativePause - left.cummulativePause;
+        mu.push(position1, 1.0 - value1 / timeWindow,
+                position2, 1.0 - value2 / timeWindow);
+      }
+    }
+    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,
+    unionOfIntervals: unionOfIntervals,
+    mutatorUtilization: mutatorUtilization
   };
 });
 </script>