[WIP] [DEFINITELY NOT READY TO LAND] Cpu time metric implementation

tracing/tracing/extras/chrome/cpu_time.html

Index: tracing/tracing/extras/chrome/cpu_time.html
diff --git a/tracing/tracing/extras/chrome/cpu_time.html b/tracing/tracing/extras/chrome/cpu_time.html
index 341e75c7e3ff206238f57e87d6d1f2865629cf14..348e70061c8511d3c02624bbf2ba066a85f6786d 100644
--- a/tracing/tracing/extras/chrome/cpu_time.html
+++ b/tracing/tracing/extras/chrome/cpu_time.html
@@ -6,6 +6,7 @@ found in the LICENSE file.
 -->
 
 <link rel="import" href="/tracing/base/multi_dimensional_view.html">
+<link rel="import" href="/tracing/extras/chrome/chrome_processes.html">
 <link rel="import" href="/tracing/model/helpers/chrome_model_helper.html">
 <link rel="import" href="/tracing/model/helpers/chrome_renderer_helper.html">
 
@@ -40,8 +41,165 @@ tr.exportTo('tr.e.chrome.cpuTime', function() {
     return totalCpuTime;
   }
 
+  /**
+   * Returns two level map of rail stage to initiator type to set of bounds of
+   * associated segments, intersected with |rangeOfInterest|.
+   *
+   * For each rail stage, we additionally have a key 'all_initiators' that
+   * returns all the segment bounds associated with that rail stage across all
+   * initiator types. For completeness, there is an additional rail stage
+   * 'all_stages' that has all the segment bounds across all rail stages.
+   *
+   * If a segment is not contained within |rangeOfInterest| it is not included.
+   *
+   * There is a unique segment bound for each segment in the map. For example,
+   * assume
+   * - |segmentA| is associated with both Click Response and Scroll Animation
+   * - |bound1| is the interesting bound of |segmentA| in Response -> Click set.
+   * - |bound2| is the interesting bound of |segmentA| in Animation -> Scroll
+        set.
+   * Then bound1 === bound2. These segment bounds can therefore be used as keys
+   * in a map to represent the segment.
+   *
+   * Example return value (all bounds are intersected with |rangeOfInterest|):
+   *
+   * {
+   *   'Animation': {
+   *     'CSS': {Segment bounds for CSS Animation},
+   *     'Video': {Segment bounds for Video Animation},
+   *     ...
+   *     'all_initiators': {All Animation segment bounds}
+   *   },
+   *   'Response': {
+   *     'Click': {Segment bounds for Click Response},
+   *     'Scroll': {Segment bounds for Scroll Response},
+   *     ...
+   *     'all_initiators': {All Response segment bounds}
+   *   },
+   *   ...
+   *   'all_stages': {
+   *     'all_initiators': {All segment bounds}
+   *   }
+   * }
+   *
+   * @param {!Array.<!tr.model.um.Segment>} segments
+   * @param {!Array.<!tr.b.math.Range>} rangeOfInterest
+   * @returns {!Map.<string, Map.<string, Set.<!tr.b.math.Range>>}
+   */
+  function getStageToInitiatorToSegmentBounds(segments, rangeOfInterest) {
+    const stageToInitiatorToRanges = new Map();
+    stageToInitiatorToRanges.set('all_stages',
+        new Map([['all_initiators', new Set()]]));
+    const allRanges =
+        stageToInitiatorToRanges.get('all_stages').get('all_initiators');
+
+    for (const segment of segments) {
+      if (!rangeOfInterest.intersectsRangeInclusive(segment.range)) continue;
+      const intersectingRange = rangeOfInterest.findIntersection(segment.range);
+      allRanges.add(intersectingRange);
+
+      for (const expectation of segment.expectations) {
+        const stageTitle = expectation.stageTitle;
+        if (!stageToInitiatorToRanges.has(stageTitle)) {
+          stageToInitiatorToRanges.set(stageTitle,
+              new Map([['all_initiators', new Set()]]));
+        }
+
+        const initiatorToRanges = stageToInitiatorToRanges.get(stageTitle);
+        initiatorToRanges.get('all_initiators').add(intersectingRange);
+
+        const initiatorType = expectation.initiatorType;
+        if (initiatorType) {
+          if (!initiatorToRanges.has(initiatorType)) {
+            initiatorToRanges.set(initiatorType, new Set());
+          }
+          initiatorToRanges.get(initiatorType).add(intersectingRange);
+        }
+      }
+    }
+    return stageToInitiatorToRanges;
+  }
+
+  /**
+   * Returns a map of range in |ranges| to total cpu time used by |thread|
+   * during that range.
+   * @param {!Iterable.<!tr.b.math.Range>} ranges
+   * @param {!Iterable.<!tr.model.Thread>} thread
+   * @returns {!Map.<!tr.b.math.Range, !tr.model.Thread>}
+   */
+  function computeCpuTimesForRanges_(ranges, thread) {
+    const rangeToCpuTime = new Map();
+    for (const range of ranges) {
+      rangeToCpuTime.set(range, getCpuTimeForThread(thread, range));
+    }
+    return rangeToCpuTime;
+  }
+
+  /**
+   * Returns the root node of a MultiDimensionalView in TopDownTreeView for cpu
+   * time.
+   *
+   * The returned tree view is three dimensional (processType, threadType, and
+   * railStage + initiator). Rail stage and initiator are not separate
+   * dimensions because they are not independent - there is no such thing as CSS
+   * Response or Scroll Load.
+   *
+   * Each node in the tree view contains two values - cpuUsage and cpuTotal.
+   *
+   * See cpu_time_multidimensinoal_view.md for more details about the returned
+   * multidimensional view.
+   *
+   * @param {!tr.Model} model
+   * @param {!tr.b.math.Range} rangeOfInterest
+   * @returns {!tr.b.MultiDimensionalViewNode}
+   */
+  function constructMultiDimensionalView(model, rangeOfInterest) {
+    const mdvBuilder = new tr.b.MultiDimensionalViewBuilder(
+      3 /* dimensions (process, thread and rail stage / initiator) */,
+      2 /* valueCount (cpuUsage and cpuTotal) */);
+
+    const stageToInitiatorToRanges =
+        getStageToInitiatorToSegmentBounds(
+            model.userModel.segments, rangeOfInterest);
+
+    const allSegmentBoundsInRange =
+        stageToInitiatorToRanges.get('all_stages').get('all_initiators');
+
+    for (const pid in model.processes) {
+      const process = model.processes[pid];
+      const processType =
+          tr.e.chrome.chrome_processes.canonicalizeProcessName(process.name);
+      for (const tid in process.threads) {
+        const thread = process.threads[tid];
+        const threadType = thread.type;
+
+        // Cache cpuTime for each segment bound.
+        const rangeToCpuTime = computeCpuTimesForRanges_(
+            allSegmentBoundsInRange, thread);
+
+        for (const [stage, initiatorToRanges] of stageToInitiatorToRanges) {
+          for (const [initiator, ranges] of initiatorToRanges) {
+            const cpuTime = tr.b.math.Statistics.sum(ranges,
+                range => rangeToCpuTime.get(range));
+            const duration = tr.b.math.Statistics.sum(ranges,
+                range => range.duration);
+            const cpuTimePerSecond = cpuTime / duration;
+            mdvBuilder.addPath(
+                [[processType], [threadType], [stage, initiator]],
+                [cpuTimePerSecond, cpuTime],
+                tr.b.MultiDimensionalViewBuilder.ValueKind.TOTAL);
+          }
+        }
+      }
+    }
+
+    return mdvBuilder.buildTopDownTreeView();
+  }
+
   return {
     getCpuTimeForThread,
+    getStageToInitiatorToSegmentBounds,
+    constructMultiDimensionalView,
   };
 });
 </script>