Bug 1226879 - Fix census tree sorting issue with inverted allocation stack breakdown; r=jimb
authorNick Fitzgerald <fitzgen@gmail.com>
Wed, 24 Feb 2016 13:11:00 +0100
changeset 322072 5be7d7b889b7a0e8808bb6521633313a14624553
parent 322070 daf17f7cf7f61da7e44ebd2814b01fb5eb4cf036
child 322073 48d839aa329bff5d22f47b394aeb03cb3e2533e7
push id5913
push userjlund@mozilla.com
push dateMon, 25 Apr 2016 16:57:49 +0000
treeherdermozilla-beta@dcaf0a6fa115 [default view] [failures only]
perfherder[talos] [build metrics] [platform microbench] (compared to previous push)
reviewersjimb
bugs1226879
milestone47.0a1
first release with
nightly linux32
nightly linux64
nightly mac
nightly win32
nightly win64
last release without
nightly linux32
nightly linux64
nightly mac
nightly win32
nightly win64
Bug 1226879 - Fix census tree sorting issue with inverted allocation stack breakdown; r=jimb
devtools/shared/heapsnapshot/CensusUtils.js
devtools/shared/heapsnapshot/census-tree-node.js
devtools/shared/heapsnapshot/tests/unit/test_census_filtering_05.js
devtools/shared/heapsnapshot/tests/unit/xpcshell.ini
--- a/devtools/shared/heapsnapshot/CensusUtils.js
+++ b/devtools/shared/heapsnapshot/CensusUtils.js
@@ -354,17 +354,17 @@ DiffVisitor.prototype.results = function
  *                                        census.
  *            - {Number} basisTotalCount: the total count in the start census.
  */
 function diff(breakdown, startCensus, endCensus) {
   const visitor = new DiffVisitor(endCensus);
   walk(breakdown, startCensus, visitor);
   return visitor.results();
 };
-exports.diff = diff
+exports.diff = diff;
 
 /**
  * Creates a hash map mapping node IDs to its parent node.
  *
  * @param {CensusTreeNode} node
  * @param {Object<number, TreeNode>} aggregator
  *
  * @return {Object<number, TreeNode>}
--- a/devtools/shared/heapsnapshot/census-tree-node.js
+++ b/devtools/shared/heapsnapshot/census-tree-node.js
@@ -515,28 +515,16 @@ function invert(tree) {
       for (let i = path.length - 1; i >= 0; i--) {
         currentCacheValue = insertOrMergeNode(currentCacheValue, path[i]);
       }
     }
 
     path.pop();
   }(tree));
 
-  // Next, do a depth-first search of the inverted tree and ensure that siblings
-  // are sorted by their self bytes/count.
-
-  (function ensureSorted(node) {
-    if (node.children) {
-      node.children.sort(compareBySelf);
-      for (let i = 0, length = node.children.length; i < length; i++) {
-        ensureSorted(node.children[i]);
-      }
-    }
-  }(inverted.node));
-
   // Ensure that the root node always has the totals.
   inverted.node.totalBytes = tree.totalBytes;
   inverted.node.totalCount = tree.totalCount;
 
   return inverted.node;
 }
 
 /**
@@ -672,10 +660,22 @@ exports.censusReportToCensusTreeNode = f
   // If the report is a delta report that was generated by diffing two other
   // reports, make sure to use the basis totals rather than the totals of the
   // difference.
   if (typeof report[basisTotalBytes] === "number") {
     result.totalBytes = report[basisTotalBytes];
     result.totalCount = report[basisTotalCount];
   }
 
+  // Inverting and filtering could have messed up the sort order, so do a
+  // depth-first search of the tree and ensure that siblings are sorted.
+  const comparator = options.invert ? compareBySelf : compareByTotal;
+  (function ensureSorted(node) {
+    if (node.children) {
+      node.children.sort(comparator);
+      for (let i = 0, length = node.children.length; i < length; i++) {
+        ensureSorted(node.children[i]);
+      }
+    }
+  }(result));
+
   return result;
 };
new file mode 100644
--- /dev/null
+++ b/devtools/shared/heapsnapshot/tests/unit/test_census_filtering_05.js
@@ -0,0 +1,71 @@
+/* Any copyright is dedicated to the Public Domain.
+   http://creativecommons.org/publicdomain/zero/1.0/ */
+
+// Test that filtered and inverted allocation stack census trees are sorted
+// properly.
+
+function run_test() {
+  const countBreakdown = { by: "count", count: true, bytes: true };
+
+  const BREAKDOWN = {
+    by: "allocationStack",
+    then: countBreakdown,
+    noStack: countBreakdown,
+  };
+
+  const stacks = [];
+
+  function foo(depth = 1) {
+    stacks.push(saveStack(depth));
+    bar(depth + 1);
+    baz(depth + 1);
+    stacks.push(saveStack(depth));
+  }
+
+  function bar(depth = 1) {
+    stacks.push(saveStack(depth));
+    stacks.push(saveStack(depth));
+  }
+
+  function baz(depth = 1) {
+    stacks.push(saveStack(depth));
+    bang(depth + 1);
+    stacks.push(saveStack(depth));
+  }
+
+  function bang(depth = 1) {
+    stacks.push(saveStack(depth));
+    stacks.push(saveStack(depth));
+    stacks.push(saveStack(depth));
+  }
+
+  foo();
+  bar();
+  baz();
+  bang();
+
+  const REPORT = new Map(stacks.map((s, i) => {
+    return [s, {
+      count: i + 1,
+      bytes: (i + 1) * 10
+    }];
+  }));
+
+  const tree = censusReportToCensusTreeNode(BREAKDOWN, REPORT, {
+    filter: "baz",
+    invert: true
+  });
+
+  dumpn("tree = " + JSON.stringify(tree, savedFrameReplacer, 4));
+
+  (function assertSortedBySelf(node) {
+    if (node.children) {
+      let lastSelfBytes = Infinity;
+      for (let child of node.children) {
+        ok(child.bytes <= lastSelfBytes, `${child.bytes} <= ${lastSelfBytes}`);
+        lastSelfBytes = child.bytes;
+        assertSortedBySelf(child);
+      }
+    }
+  }(tree));
+}
--- a/devtools/shared/heapsnapshot/tests/unit/xpcshell.ini
+++ b/devtools/shared/heapsnapshot/tests/unit/xpcshell.ini
@@ -16,16 +16,17 @@ support-files =
 [test_census_diff_03.js]
 [test_census_diff_04.js]
 [test_census_diff_05.js]
 [test_census_diff_06.js]
 [test_census_filtering_01.js]
 [test_census_filtering_02.js]
 [test_census_filtering_03.js]
 [test_census_filtering_04.js]
+[test_census_filtering_05.js]
 [test_census-tree-node-01.js]
 [test_census-tree-node-02.js]
 [test_census-tree-node-03.js]
 [test_census-tree-node-04.js]
 [test_census-tree-node-05.js]
 [test_census-tree-node-06.js]
 [test_census-tree-node-07.js]
 [test_census-tree-node-08.js]