CPU profile displayed in three tables with a tree

runtime/observatory/lib/src/cpu_profile/cpu_profile.dart

 // Copyright (c) 2015, the Dart project authors.  Please see the AUTHORS file
 // for details. All rights reserved. Use of this source code is governed by a
 // BSD-style license that can be found in the LICENSE file.
 
 part of cpu_profiler;
 
 class CodeCallTreeNode {
   final ProfileCode profileCode;
   final int count;
   double get percentage => _percentage;
@@ skipping 23 matching lines @@
     }
     if (inclusive) {
       node._percentage = parentPercentage * (node.count / parentCount);
     } else {
       node._percentage = (node.count / parentCount);
     }
     for (var child in node.children) {
       _setCodePercentage(node, child);
     }
   }
+
+  _markCodeCallsInner(CodeCallTreeNode caller,
+                      CodeCallTreeNode callee) {
+    if (caller != null) {
+      caller.profileCode._noteCallee(callee.profileCode, callee.count);
+      callee.profileCode._noteCaller(caller.profileCode, callee.count);
+    }
+
+    for (var child in callee.children) {
+      _markCodeCallsInner(callee, child);
+    }
+  }
+
+  _markCodeCalls() {

[turnidge, 2015/04/07 21:24:31]

What does "marking" mean here?  Is there another name for this?  Maybe
"SetCallCounts" or maybe "RecordCalls".

BTW, What do you think of this class being named "CallTree" instead of
"CodeCallTree"?

[Cutch, 2015/04/14 21:45:15]

Went with _recordCallerAndCallees.

The class is named CodeCallTree because there is also a FunctionCallTree (Code
vs. Function).

+    for (var child in root.children) {
+      _markCodeCallsInner(null, child);
+    }
+  }
 }
 
 class FunctionCallTreeNodeCode {
   final ProfileCode code;
   final int ticks;
   FunctionCallTreeNodeCode(this.code, this.ticks);
 }
 
 class FunctionCallTreeNode {
   final ProfileFunction profileFunction;
@@ skipping 68 matching lines @@
     }
     if (hasUnoptimizedCode()) {
       attributes.add('unoptimized');
     }
     if (isInlined()) {
       attributes.add('inlined');
     }
   }
 }
 
+typedef bool FunctionCallTreeNodeFilter(FunctionCallTreeNode node);
+
+class _FilteredTreeBuilder {

[turnidge, 2015/04/07 21:24:31]

Can you make some of the functions in this class private so I can tell which
ones are external entry points?  Maybe add some one-line comments on the
functions too.

[Cutch, 2015/04/14 21:45:15]

Done.

+  final FunctionCallTreeNodeFilter filter;
+  final FunctionCallTree tree;
+  final FunctionCallTree filtered;
+  final List currentPath = [];
+
+  _FilteredTreeBuilder(this.filter, FunctionCallTree tree)
+      : tree = tree,
+        filtered =
+          new FunctionCallTree(
+              tree.inclusive,
+              new FunctionCallTreeNode(
+                  tree.root.profileFunction,
+                  tree.root.count));
+
+  FunctionCallTreeNode findFunctionInChildren(FunctionCallTreeNode current,
+                                              FunctionCallTreeNode needle) {
+    for (var child in current.children) {
+      if (child.profileFunction == needle.profileFunction) {
+        return child;
+      }
+    }
+    return null;
+  }
+
+  FunctionCallTreeNode addCurrentPath() {
+    FunctionCallTreeNode current = filtered.root;
+    // Tree root is always the first element of the current path.
+    assert(tree.root == currentPath[0]);
+    // Assert that tree and filtered are different.
+    assert(tree.root != current);
+    for (var i = 1; i < currentPath.length; i++) {
+      var toAdd = currentPath[i];
+      var child = findFunctionInChildren(current, toAdd);
+      if (child == null) {
+        child = new FunctionCallTreeNode(toAdd.profileFunction, toAdd.count);
+        current.children.add(child);
+      }
+      current = child;
+      assert(current.count == toAdd.count);
+    }
+    return current;
+  }
+
+  appendTree(FunctionCallTreeNode current, FunctionCallTreeNode next) {
+    if (next == null) {
+      return;
+    }
+    var child = findFunctionInChildren(current, next);
+    if (child == null) {
+      child = new FunctionCallTreeNode(next.profileFunction, next.count);
+      current.children.add(child);
+    }
+    current = child;
+    for (var nextChild in next.children) {
+      appendTree(current, nextChild);
+    }
+  }
+
+  addTree(FunctionCallTreeNode child) {
+    var current = addCurrentPath();
+    appendTree(current, child);
+  }
+
+  descend(FunctionCallTreeNode current) {
+    if (current == null) {
+      return;
+    }
+    currentPath.add(current);
+
+    if (filter(current)) {
+      // Filter matched.
+      if (current.children.length == 0) {
+        // Have no children. Add this path.
+        addTree(null);
+      } else {
+        // Add all child trees.
+        for (var child in current.children) {
+          addTree(child);
+        }
+      }
+    } else {
+      // Did not match, descend to each child.
+      for (var child in current.children) {
+        descend(child);
+      }
+    }
+
+    var last = currentPath.removeLast();
+    assert(current == last);
+  }
+
+  build() {
+    assert(filtered != null);
+    assert(filter != null);
+    assert(tree != null);
+    descend(tree.root);
+  }
+}
+
 class FunctionCallTree {
   final bool inclusive;
   final FunctionCallTreeNode root;
   FunctionCallTree(this.inclusive, this.root) {
     _setFunctionPercentage(null, root);
   }
 
+  FunctionCallTree filtered(FunctionCallTreeNodeFilter filter) {
+    var treeFilter = new _FilteredTreeBuilder(filter, this);
+    treeFilter.build();
+    _setFunctionPercentage(null, treeFilter.filtered.root);
+    return treeFilter.filtered;
+  }
+
   void _setFunctionPercentage(FunctionCallTreeNode parent,
                               FunctionCallTreeNode node) {
     assert(node != null);
     var parentPercentage = 1.0;
     var parentCount = node.count;
     if (parent != null) {
       parentPercentage = parent._percentage;
       parentCount = parent.count;
     }
     if (inclusive) {
       node._percentage = parentPercentage * (node.count / parentCount);
     } else {
       node._percentage = (node.count / parentCount);
     }
     for (var child in node.children) {
       _setFunctionPercentage(node, child);
     }
   }
+
+  _markFunctionCallsInner(FunctionCallTreeNode caller,
+                     FunctionCallTreeNode callee) {
+    if (caller != null) {
+      caller.profileFunction._noteCallee(callee.profileFunction, callee.count);
+      callee.profileFunction._noteCaller(caller.profileFunction, callee.count);
+    }
+    for (var child in callee.children) {
+      _markFunctionCallsInner(callee, child);
+    }
+  }
+
+  _markFunctionCalls() {
+    for (var child in root.children) {
+      _markFunctionCallsInner(null, child);
+    }
+  }
 }
 
 class CodeTick {
   final int exclusiveTicks;
   final int inclusiveTicks;
   CodeTick(this.exclusiveTicks, this.inclusiveTicks);
 }
 
 class InlineIntervalTick {
   final int startAddress;
@@ skipping 12 matching lines @@
   double normalizedExclusiveTicks = 0.0;
   double normalizedInclusiveTicks = 0.0;
   final addressTicks = new Map<int, CodeTick>();
   final intervalTicks = new Map<int, InlineIntervalTick>();
   String formattedInclusiveTicks = '';
   String formattedExclusiveTicks = '';
   String formattedExclusivePercent = '';
   String formattedCpuTime = '';
   String formattedOnStackTime = '';
   final Set<String> attributes = new Set<String>();
+  final Map<ProfileCode, int> callers = new Map<ProfileCode, int>();
+  final Map<ProfileCode, int> callees = new Map<ProfileCode, int>();
 
   void _processTicks(List<String> profileTicks) {
     assert(profileTicks != null);
     assert((profileTicks.length % 3) == 0);
     for (var i = 0; i < profileTicks.length; i += 3) {
       var address = int.parse(profileTicks[i], radix:16);
       var exclusive = int.parse(profileTicks[i + 1]);
       var inclusive = int.parse(profileTicks[i + 2]);
       var tick = new CodeTick(exclusive, inclusive);
       addressTicks[address] = tick;
@@ skipping 56 matching lines @@
             profile.approximateMillisecondsForCount(inclusiveTicks));
 
     formattedInclusiveTicks =
       '${Utils.formatPercent(inclusiveTicks, profile.sampleCount)} '
       '($inclusiveTicks)';
 
     formattedExclusiveTicks =
       '${Utils.formatPercent(exclusiveTicks, profile.sampleCount)} '
       '($exclusiveTicks)';
   }
+
+  _noteCaller(ProfileCode caller, int count) {

[turnidge, 2015/04/07 21:24:31]

Maybe _addCaller and _addCallee?

[Cutch, 2015/04/14 21:45:15]

Done.

+    var r = callers[caller];
+    if (r == null) {
+      r = 0;
+    }
+    callers[caller] = r + count;
+  }
+
+  _noteCallee(ProfileCode callee, int count) {
+    var r = callees[callee];
+    if (r == null) {
+      r = 0;
+    }
+    callees[callee] = r + count;
+  }
 }
 
 class ProfileFunction {
   final CpuProfile profile;
   final ServiceFunction function;
   // List of compiled code objects containing this function.
   final List<ProfileCode> profileCodes = new List<ProfileCode>();
+  final Map<ProfileFunction, int> callers = new Map<ProfileFunction, int>();
+  final Map<ProfileFunction, int> callees = new Map<ProfileFunction, int>();
+
   // Absolute ticks:
   int exclusiveTicks = 0;
   int inclusiveTicks = 0;
 
   // Global percentages:
   double normalizedExclusiveTicks = 0.0;
   double normalizedInclusiveTicks = 0.0;
 
   String formattedInclusiveTicks = '';
   String formattedExclusiveTicks = '';
@@ skipping 67 matching lines @@
     } else if (function.kind == FunctionKind.kNative) {
       attribs.add('native');
     } else if (function.kind.isSynthetic()) {
       attribs.add('synthetic');
     } else {
       attribs.add('dart');
     }
   }
 
   ProfileFunction.fromMap(this.profile, this.function, Map data) {
+    function.profile = this;
     for (var codeIndex in data['codes']) {
       var profileCode = profile.codes[codeIndex];
       profileCodes.add(profileCode);
     }
     profileCodes.sort(_sortCodes);
 
     if (hasOptimizedCode()) {
       attributes.add('optimized');
     }
     if (hasUnoptimizedCode()) {
@@ skipping 21 matching lines @@
             profile.approximateMillisecondsForCount(inclusiveTicks));
 
     formattedInclusiveTicks =
         '${Utils.formatPercent(inclusiveTicks, profile.sampleCount)} '
         '($inclusiveTicks)';
 
     formattedExclusiveTicks =
         '${Utils.formatPercent(exclusiveTicks, profile.sampleCount)} '
         '($exclusiveTicks)';
   }
+
+  _noteCaller(ProfileFunction caller, int count) {
+    var r = callers[caller];
+    if (r == null) {
+      r = 0;
+    }
+    callers[caller] = r + count;
+  }
+
+  _noteCallee(ProfileFunction callee, int count) {
+    var r = callees[callee];
+    if (r == null) {
+      r = 0;
+    }
+    callees[callee] = r + count;
+  }
 }
 
 
 class CpuProfile {
   final double MICROSECONDS_PER_SECOND = 1000000.0;
   final double displayThreshold = 0.0002; // 0.02%.
 
   Isolate isolate;
 
   int sampleCount = 0;
   int samplePeriod = 0;
   double sampleRate = 0.0;
 
   int stackDepth = 0;
 
   double timeSpan = 0.0;
 
   final Map<String, List> tries = <String, List>{};
   final List<ProfileCode> codes = new List<ProfileCode>();
+  bool _markedCodeCalls = false;
   final List<ProfileFunction> functions = new List<ProfileFunction>();
+  bool _markedFunctionCalls = false;
 
   CodeCallTree loadCodeTree(String name) {
     if (name == 'inclusive') {
       return _loadCodeTree(true, tries['inclusiveCodeTrie']);
     } else {
       return _loadCodeTree(false, tries['exclusiveCodeTrie']);
     }
   }
 
   FunctionCallTree loadFunctionTree(String name) {
     if (name == 'inclusive') {
       return _loadFunctionTree(true, tries['inclusiveFunctionTrie']);
     } else {
       return _loadFunctionTree(false, tries['exclusiveFunctionTrie']);
     }
   }
 
-  void clear() {
+  markCodeCalls() {
+    if (_markedCodeCalls) {
+      return;
+    }
+    _markedCodeCalls = true;
+    var tree = loadCodeTree('inclusive');
+    tree._markCodeCalls();
+  }
+
+  markFunctionCalls() {
+    if (_markedFunctionCalls) {
+      return;
+    }
+    _markedFunctionCalls = true;
+    var tree = loadFunctionTree('inclusive');
+    tree._markFunctionCalls();
+  }
+
+  clear() {
     sampleCount = 0;
     samplePeriod = 0;
     sampleRate = 0.0;
     stackDepth = 0;
     timeSpan = 0.0;
     codes.clear();
     functions.clear();
     tries.clear();
+    _markedCodeCalls = false;
+    _markedFunctionCalls = false;
   }
 
-  void load(Isolate isolate, ServiceMap profile) {
+  load(Isolate isolate, ServiceMap profile) {
     clear();
     if ((isolate == null) || (profile == null)) {
       return;
     }
 
     this.isolate = isolate;
     isolate.resetCachedProfileData();
 
     sampleCount = profile['sampleCount'];
     samplePeriod = profile['samplePeriod'];
@@ skipping 198 matching lines @@
   int approximateMillisecondsForCount(count) {
     var MICROSECONDS_PER_MILLISECOND = 1000.0;
     return (count * samplePeriod) ~/ MICROSECONDS_PER_MILLISECOND;
   }
 
   double approximateSecondsForCount(count) {
     var MICROSECONDS_PER_SECOND = 1000000.0;
     return (count * samplePeriod) / MICROSECONDS_PER_SECOND;
   }
 }