Changeset 112271 in webkit


Ignore:
Timestamp:
Mar 27, 2012 8:15:18 AM (12 years ago)
Author:
yurys@chromium.org
Message:

Web Inspector: Speed up snapshot parsing.
https://bugs.webkit.org/show_bug.cgi?id=82325

Replacing the iterators with raw nodes/edges access speeds up
some phases phasses up to 10 times, taking down the whole init
time to less than 6 sec.

Patch by Alexei Filippov <alexeif@chromium.org> on 2012-03-27
Reviewed by Yury Semikhatsky.

  • inspector/front-end/HeapSnapshot.js:

(WebInspector.HeapSnapshot.prototype._buildNodeIndex):
(WebInspector.HeapSnapshot.prototype._buildDominatedNodes):
(WebInspector.HeapSnapshot.prototype._markQueriableHeapObjects):

Location:
trunk/Source/WebCore
Files:
2 edited

Legend:

Unmodified
Added
Removed
  • trunk/Source/WebCore/ChangeLog

    r112269 r112271  
     12012-03-27  Alexei Filippov  <alexeif@chromium.org>
     2
     3        Web Inspector: Speed up snapshot parsing.
     4        https://bugs.webkit.org/show_bug.cgi?id=82325
     5
     6        Replacing the iterators with raw nodes/edges access speeds up
     7        some phases phasses up to 10 times, taking down the whole init
     8        time to less than 6 sec.
     9
     10        Reviewed by Yury Semikhatsky.
     11
     12        * inspector/front-end/HeapSnapshot.js:
     13        (WebInspector.HeapSnapshot.prototype._buildNodeIndex):
     14        (WebInspector.HeapSnapshot.prototype._buildDominatedNodes):
     15        (WebInspector.HeapSnapshot.prototype._markQueriableHeapObjects):
     16
    1172012-03-27  Antti Koivisto  <antti@apple.com>
    218
  • trunk/Source/WebCore/inspector/front-end/HeapSnapshot.js

    r112268 r112271  
    10301030    },
    10311031
    1032     _buildReverseIndex: function(indexArrayName, backRefsArrayName, indexCallback, dataCallback)
    1033     {
     1032    _buildRetainers: function()
     1033    {
     1034        var nodeIndexes = this.nodeIndexes;
     1035        var nodePositions = this._nodePosition;
     1036        var nodeCount = this.nodeCount;
     1037        var nodes = this._nodes;
     1038
    10341039        // Builds up two arrays:
    10351040        //  - "backRefsArray" is a continuous array, where each node owns an
     
    10371042        //  - "indexArray" is an array of indexes in the "backRefsArray"
    10381043        //    with the same positions as in the _nodeIndex.
    1039         var indexArray = this[indexArrayName] = new Uint32Array(this._nodeIndex.length);
    1040         var nodeIndexes = this.nodeIndexes;
    1041         var nodeCount = this.nodeCount;
    1042         var node = new WebInspector.HeapSnapshotNode(this, nodeIndexes[0]);
    1043         for (var i = 0; i < nodeCount; ++i) {
    1044             node.nodeIndex = nodeIndexes[i];
    1045             indexCallback(node, function (position) { ++indexArray[position]; });
    1046         }
    1047         var backRefsCount = 0;
    1048         for (i = 0, l = indexArray.length; i < l; ++i)
    1049             backRefsCount += indexArray[i];
    1050         var backRefsArray = this[backRefsArrayName] = new Uint32Array(backRefsCount + 1);
    1051         // Put in the first slot of each backRefsArray slice the count of entries
    1052         // that will be filled.
    1053         var backRefsPosition = 0;
    1054         for (i = 0, l = indexArray.length; i < l; ++i) {
    1055             backRefsCount = backRefsArray[backRefsPosition] = indexArray[i];
    1056             indexArray[i] = backRefsPosition;
    1057             backRefsPosition += backRefsCount;
    1058         }
    1059         for (var i = 0; i < nodeCount; ++i) {
    1060             node.nodeIndex = nodeIndexes[i];
    1061             dataCallback(node,
    1062                          function (backRefIndex) { return backRefIndex + (--backRefsArray[backRefIndex]); },
    1063                          function (backRefIndex, destIndex) { backRefsArray[backRefIndex] = destIndex; });
    1064         }
    1065     },
    1066 
    1067     _buildRetainers: function()
    1068     {
    1069         var nodeIndexes = this.nodeIndexes;
    1070         var nodePositions = this._nodePosition;
    1071         var nodeCount = this.nodeCount;
    1072         var nodes = this._nodes;
    1073 
    1074         // Builds up two arrays:
    1075         //  - "backRefsArray" is a continuous array, where each node owns an
    1076         //    interval (can be empty) with corresponding back references.
    1077         //  - "indexArray" is an array of indexes in the "backRefsArray"
    1078         //    with the same positions as in the _nodeIndex.
    1079         var indexArray = this._retainerIndex = new Int32Array(nodeCount + 1);
     1044        var indexArray = this._retainerIndex = new Uint32Array(nodeCount + 1);
    10801045        var edgesCountOffset = this._edgesCountOffset;
    10811046        var firstEdgeOffset = this._firstEdgeOffset;
     
    10941059            }
    10951060        }
    1096         var backRefsArray = this._retainers = new Int32Array(backRefsCount);
     1061        var backRefsArray = this._retainers = new Uint32Array(backRefsCount);
    10971062        // Put in the first slot of each backRefsArray slice the count of entries
    10981063        // that will be filled.
     
    12571222    {
    12581223        var count = 0;
    1259         for (var nodesIter = this._allNodes; nodesIter.hasNext(); nodesIter.next(), ++count);
     1224        for (var i = this._rootNodeIndex, l = this._nodes.length; i < l; ++count) {
     1225            var edgesCount = this._nodes[i + this._edgesCountOffset];
     1226            i += this._firstEdgeOffset + edgesCount * this._edgeFieldsCount;
     1227        }
    12601228        var nodeIndex = new Uint32Array(count + 1);
    12611229        var nodePosition = {};
    12621230        count = 0;
    1263         for (var nodesIter = this._allNodes; nodesIter.hasNext(); nodesIter.next(), ++count) {
    1264             nodeIndex[count] = nodesIter.index;
    1265             nodePosition[nodesIter.index] = count;
     1231        for (var i = this._rootNodeIndex, l = this._nodes.length; i < l; ++count) {
     1232            nodeIndex[count] = i;
     1233            nodePosition[i] = count;
     1234            var edgesCount = this._nodes[i + this._edgesCountOffset];
     1235            i += this._firstEdgeOffset + edgesCount * this._edgeFieldsCount;
    12661236        }
    12671237        nodeIndex[count] = this._nodes.length;
     
    12931263    _buildDominatedNodes: function()
    12941264    {
    1295         this._buildReverseIndex(
    1296             "_dominatedIndex",
    1297             "_dominatedNodes",
    1298             (function (node, callback)
    1299              {
    1300                  var dominatorIndex = node.dominatorIndex;
    1301                  if (dominatorIndex !== node.nodeIndex)
    1302                      callback(this._nodePosition[dominatorIndex]);
    1303              }).bind(this),
    1304             (function (node, indexCallback, dataCallback)
    1305              {
    1306                  var dominatorIndex = node.dominatorIndex;
    1307                  if (dominatorIndex !== node.nodeIndex) {
    1308                      var dominatedIndex = this._getDominatedIndex(dominatorIndex);
    1309                      dataCallback(indexCallback(dominatedIndex), node.nodeIndex);
    1310                  }
    1311              }).bind(this));
     1265        var nodeCount = this.nodeCount;
     1266        // Builds up two arrays:
     1267        //  - "dominatedNodes" is a continuous array, where each node owns an
     1268        //    interval (can be empty) with corresponding dominated nodes.
     1269        //  - "indexArray" is an array of indexes in the "dominatedNodes"
     1270        //    with the same positions as in the _nodeIndex.
     1271        var indexArray = this._dominatedIndex = new Uint32Array(nodeCount + 1);
     1272        // Count the number of retainers for each node
     1273        for (var i = 0; i < nodeCount; ++i) {
     1274            var nodeIndex = this.nodeIndexes[i];
     1275            var dominatorIndex = this._nodes[nodeIndex + this._dominatorOffset];
     1276            if (nodeIndex === dominatorIndex) continue;
     1277            ++indexArray[this._nodePosition[dominatorIndex]];
     1278        }
     1279        var dominatedNodes = this._dominatedNodes = new Uint32Array(nodeCount - 1);
     1280        // Put in the first slot of each dominatedNodes slice the count of entries
     1281        // that will be filled.
     1282        var dominatedPosition = 0;
     1283        for (i = 0; i <= nodeCount; ++i) {
     1284            var dominatedCount = dominatedNodes[dominatedPosition] = indexArray[i];
     1285            indexArray[i] = dominatedPosition;
     1286            dominatedPosition += dominatedCount;
     1287        }
     1288        // Fill up the dominatedNodes array with indexes of dominated nodes.
     1289        for (var i = 0; i < nodeCount; ++i) {
     1290            var nodeIndex = this.nodeIndexes[i];
     1291            var dominatorIndex = this._nodes[nodeIndex + this._dominatorOffset];
     1292            if (nodeIndex === dominatorIndex) continue;
     1293            var dominatorPos = this._nodePosition[dominatorIndex];
     1294            var dominatedRefIndex = indexArray[dominatorPos];
     1295            dominatedRefIndex += (--dominatedNodes[dominatedRefIndex]);
     1296            dominatedNodes[dominatedRefIndex] = nodeIndex;
     1297        }
    13121298    },
    13131299
     
    13841370        for (var iter = this.rootNode.edges; iter.hasNext(); iter.next()) {
    13851371            if (iter.edge.node.isWindow)
    1386                 list.push(iter.edge.node);
    1387         }
    1388 
     1372                list.push(iter.edge.node.nodeIndex);
     1373        }
     1374
     1375        var edge = new WebInspector.HeapSnapshotEdge(this);
     1376        var node = new WebInspector.HeapSnapshotNode(this);
    13891377        while (list.length) {
    1390             var node = list.pop();
    1391             if (this._flags[node.nodeIndex] & flag)
     1378            var nodeIndex = list.pop();
     1379            if (this._flags[nodeIndex] & flag)
    13921380                continue;
    1393             this._flags[node.nodeIndex] |= flag;
    1394             for (var iter = node.edges; iter.hasNext(); iter.next()) {
    1395                 var edge = iter.edge;
    1396                 var node = edge.node;
    1397                 if (this._flags[node.nodeIndex] & flag)
     1381            node.nodeIndex = nodeIndex;
     1382            this._flags[nodeIndex] |= flag;
     1383            var edgesOffset = nodeIndex + this._firstEdgeOffset;
     1384            var edgesCount = this._nodes[nodeIndex + this._edgesCountOffset];
     1385            edge._edges = node.rawEdges;
     1386            for (var j = 0; j < edgesCount; ++j) {
     1387                edge.edgeIndex = j * this._edgeFieldsCount;
     1388                var nodeIndex = this._nodes[edgesOffset + edge.edgeIndex + this._edgeToNodeOffset];
     1389                if (this._flags[nodeIndex] & flag)
    13981390                    continue;
    13991391                if (edge.isHidden || edge.isInvisible)
     1392                    continue;
     1393                if (edge.isInternal)
    14001394                    continue;
    14011395                var name = edge.name;
    14021396                if (!name)
    14031397                    continue;
    1404                 if (edge.isInternal)
    1405                     continue;
    1406                 list.push(node);
     1398                list.push(nodeIndex);
    14071399            }
    14081400        }
Note: See TracChangeset for help on using the changeset viewer.