Web Inspector: upstream build dominators tree procedure from v8

• Component: Web Inspector (Deprecated)
• Status: RESOLVED FIXED

[Ilya Tikhonovsky]

The idea is to reduce transfer size and move all the post-processing steps to the front-end.
The speed is nearly the same.

Native speed vs JS speed

HeapSnapshotGenerator::FillPostorderIndexes 74ms
HeapSnapshotGenerator::SetEntriesDominators 255ms

vs

RESULT heap-snapshot: _buildPostOrderIndex= 135 ms
RESULT heap-snapshot: _buildDominatorTree= 360 ms

[Ilya Tikhonovsky]

Created attachment 142281 [details]
Patch

[Ilya Tikhonovsky]

Created attachment 142285 [details]
Patch

[Ilya Tikhonovsky]

Created attachment 142443 [details]
Patch

[Alexei Filippov]

Comment on attachment 142443 [details]
Patch

View in context: https://bugs.webkit.org/attachment.cgi?id=142443&action=review

> Source/WebCore/inspector/front-end/HeapSnapshot.js:1097
> +                var endEdgeIndex =  nodeOrdinal < nodeCount - 1 ? nodes[nodeIndex + firstEdgeIndexOffset + nodeFieldCount] : containmentEdgesLength;

nit: there's an extra space after =

> Source/WebCore/inspector/front-end/HeapSnapshot.js:1153
> +        {// manually inlined due to inline source size limit.

Why inline here? It doesn't seem to be performance critical.

> Source/WebCore/inspector/front-end/HeapSnapshot.js:1172
> +                var nodeOrdinal = postOrderIndex2NodeIndex[postOrderIndex] / nodeFieldCount;

This code line can be moved past the if-continue below.

> Source/WebCore/inspector/front-end/HeapSnapshot.js:1219
> +                            affected[nodeOrdinal2PostOrderIndex[childNodeOrdinal]] = 1;

If you haven't checked that already, I'd suggest to see if it makes sense to base affected array on node ordinals rather than postorder indexes. It may be faster as it removes one array lookup here (which is one per edge), but adds one in the beginning of the loop (which is one per node).

[Ilya Tikhonovsky]

Created attachment 142685 [details]
Patch

[Ilya Tikhonovsky]

Created attachment 142707 [details]
Patch

[Yury Semikhatsky]

Comment on attachment 142707 [details]
Patch

View in context: https://bugs.webkit.org/attachment.cgi?id=142707&action=review

> Source/WebCore/ChangeLog:11
> +        Covered by existing tests and performance tests.

Can we upstream dominator tests as well? Or if there is no such tests, we need new ones.

> Source/WebCore/inspector/front-end/HeapSnapshot.js:713
> +            visitedMarkerMask: 65535, // bits: 0,1111,1111,1111,1111

0x0FFFF and 0x10000 ?

> Source/WebCore/inspector/front-end/HeapSnapshot.js:1082
> +        var kShortcut = this._edgeShortcutType;

kShortcut -> edgeShortcutType for consistency with the rest code.

> Source/WebCore/inspector/front-end/HeapSnapshot.js:1096
> +        var kGrey = 1;

Simply grey and black as we don't use any prefixes for constants in WebCore.

> Source/WebCore/inspector/front-end/HeapSnapshot.js:1113
> +                    if (nodeIndex != rootNodeIndex && containmentEdges[edgeIndex + edgeTypeOffset] === kShortcut)

nodeIndex !== rootNodeIndex

> Source/WebCore/inspector/front-end/HeapSnapshot.js:1375
> +        for (var edgeIndex = nodes[firstEdgeIndexOffset], endEdgeIndex = nodes[nodeFieldCount + firstEdgeIndexOffset];

Please add _rootNodeIndex explicitly so that it is clear that you iterate through the root links.

> Source/WebCore/inspector/front-end/HeapSnapshot.js:1379
> +                var nodeIndex = containmentEdges[edgeIndex + edgeToNodeOffset]

missing ;

> Source/WebCore/inspector/front-end/HeapSnapshot.js:1385
> +        while (nodesToVisitLength) {

Can we reuse existing _bfs here?

[Yury Semikhatsky]

Comment on attachment 142707 [details]
Patch

View in context: https://bugs.webkit.org/attachment.cgi?id=142707&action=review

> Source/WebCore/inspector/front-end/HeapSnapshot.js:1118
> +                    if (nodeIndex != rootNodeIndex && childNodeFlag && !nodeFlag)

nodeIndex !== rootNodeIndex, also please add a comment explaining this condition.

> Source/WebCore/inspector/front-end/HeapSnapshot.js:1162
> +        var kNoEntry = nodesCount;

No kXXX prefix for constants please.

[Alexei Filippov]

Comment on attachment 142707 [details]
Patch

View in context: https://bugs.webkit.org/attachment.cgi?id=142707&action=review

> Source/WebCore/inspector/front-end/HeapSnapshot.js:1352
> +    _markPageOwnedNodes: function()

markUserReachableNodes?

> Source/WebCore/inspector/front-end/HeapSnapshot.js:1392
> +            if ((nodeOrdinal) < nodesCount - 1)

nit: why extra parentheses?

[Ilya Tikhonovsky]

Created attachment 142753 [details]
Patch

[Ilya Tikhonovsky]

(In reply to comment #7)
> (From update of attachment 142707 [details])
> View in context: https://bugs.webkit.org/attachment.cgi?id=142707&action=review
> 
> > Source/WebCore/ChangeLog:11
> > +        Covered by existing tests and performance tests.
> 
> Can we upstream dominator tests as well? Or if there is no such tests, we need new ones.

There is one dominator test in v8. I made the same in this patch for the postOrder and dominatorsTree functions.


> 
> > Source/WebCore/inspector/front-end/HeapSnapshot.js:713
> > +            visitedMarkerMask: 65535, // bits: 0,1111,1111,1111,1111
> 
> 0x0FFFF and 0x10000 ?

done

> 
> > Source/WebCore/inspector/front-end/HeapSnapshot.js:1082
> > +        var kShortcut = this._edgeShortcutType;
> 
> kShortcut -> edgeShortcutType for consistency with the rest code.

done

> 
> > Source/WebCore/inspector/front-end/HeapSnapshot.js:1096
> > +        var kGrey = 1;
> 
> Simply grey and black as we don't use any prefixes for constants in WebCore.

done

> 
> > Source/WebCore/inspector/front-end/HeapSnapshot.js:1113
> > +                    if (nodeIndex != rootNodeIndex && containmentEdges[edgeIndex + edgeTypeOffset] === kShortcut)
> 
> nodeIndex !== rootNodeIndex

done

> 
> > Source/WebCore/inspector/front-end/HeapSnapshot.js:1375
> > +        for (var edgeIndex = nodes[firstEdgeIndexOffset], endEdgeIndex = nodes[nodeFieldCount + firstEdgeIndexOffset];
> 
> Please add _rootNodeIndex explicitly so that it is clear that you iterate through the root links.

done


> 
> > Source/WebCore/inspector/front-end/HeapSnapshot.js:1379
> > +                var nodeIndex = containmentEdges[edgeIndex + edgeToNodeOffset]
> 
> missing ;

done

> 
> > Source/WebCore/inspector/front-end/HeapSnapshot.js:1385
> > +        while (nodesToVisitLength) {
> 
> Can we reuse existing _bfs here?

it is twice slower than this implementation.

(In reply to comment #8)
> (From update of attachment 142707 [details])
> View in context: https://bugs.webkit.org/attachment.cgi?id=142707&action=review
> 
> > Source/WebCore/inspector/front-end/HeapSnapshot.js:1118
> > +                    if (nodeIndex != rootNodeIndex && childNodeFlag && !nodeFlag)
> 
> nodeIndex !== rootNodeIndex, also please add a comment explaining this condition.

done

> 
> > Source/WebCore/inspector/front-end/HeapSnapshot.js:1162
> > +        var kNoEntry = nodesCount;
> 
> No kXXX prefix for constants please.

done

(In reply to comment #9)
> (From update of attachment 142707 [details])
> View in context: https://bugs.webkit.org/attachment.cgi?id=142707&action=review
> 
> > Source/WebCore/inspector/front-end/HeapSnapshot.js:1352
> > +    _markPageOwnedNodes: function()
> 
> markUserReachableNodes?

I'm not sure that this is good name. I'm trying to mark all the nodes that owned by page
and left unmarked all the nodes that owned by a debugger object. Not all the objects owned
by the page can be reached by the user. That's why I selected this name.

> 
> > Source/WebCore/inspector/front-end/HeapSnapshot.js:1392
> > +            if ((nodeOrdinal) < nodesCount - 1)
> 
> nit: why extra parentheses?

done

[Ilya Tikhonovsky]

Committed r117749: <http://trac.webkit.org/changeset/117749>