Bug 86640 - Web Inspector: upstream build dominators tree procedure from v8
Summary: Web Inspector: upstream build dominators tree procedure from v8
Status: RESOLVED FIXED
Alias: None
Product: WebKit
Classification: Unclassified
Component: Web Inspector (Deprecated) (show other bugs)
Version: 528+ (Nightly build)
Hardware: All All
: P2 Normal
Assignee: Ilya Tikhonovsky
URL:
Keywords:
Depends on:
Blocks: 87089
  Show dependency treegraph
 
Reported: 2012-05-16 09:37 PDT by Ilya Tikhonovsky
Modified: 2012-05-22 00:01 PDT (History)
11 users (show)

See Also:


Attachments
Patch (17.46 KB, patch)
2012-05-16 09:44 PDT, Ilya Tikhonovsky
no flags Details | Formatted Diff | Diff
Patch (16.84 KB, patch)
2012-05-16 09:56 PDT, Ilya Tikhonovsky
no flags Details | Formatted Diff | Diff
Patch (17.85 KB, patch)
2012-05-17 01:46 PDT, Ilya Tikhonovsky
no flags Details | Formatted Diff | Diff
Patch (23.48 KB, patch)
2012-05-18 04:36 PDT, Ilya Tikhonovsky
no flags Details | Formatted Diff | Diff
Patch (23.91 KB, patch)
2012-05-18 06:51 PDT, Ilya Tikhonovsky
no flags Details | Formatted Diff | Diff
Patch (24.57 KB, patch)
2012-05-18 11:48 PDT, Ilya Tikhonovsky
yurys: review+
Details | Formatted Diff | Diff

Note You need to log in before you can comment on or make changes to this bug.
Description Ilya Tikhonovsky 2012-05-16 09:37:22 PDT
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
Comment 1 Ilya Tikhonovsky 2012-05-16 09:44:43 PDT
Created attachment 142281 [details]
Patch
Comment 2 Ilya Tikhonovsky 2012-05-16 09:56:41 PDT
Created attachment 142285 [details]
Patch
Comment 3 Ilya Tikhonovsky 2012-05-17 01:46:17 PDT
Created attachment 142443 [details]
Patch
Comment 4 Alexei Filippov 2012-05-17 03:23:19 PDT
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).
Comment 5 Ilya Tikhonovsky 2012-05-18 04:36:52 PDT
Created attachment 142685 [details]
Patch
Comment 6 Ilya Tikhonovsky 2012-05-18 06:51:05 PDT
Created attachment 142707 [details]
Patch
Comment 7 Yury Semikhatsky 2012-05-18 08:30:21 PDT
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?
Comment 8 Yury Semikhatsky 2012-05-18 08:42:51 PDT
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.
Comment 9 Alexei Filippov 2012-05-18 09:02:41 PDT
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?
Comment 10 Ilya Tikhonovsky 2012-05-18 11:48:05 PDT
Created attachment 142753 [details]
Patch
Comment 11 Ilya Tikhonovsky 2012-05-18 11:57:32 PDT
(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
Comment 12 Ilya Tikhonovsky 2012-05-21 01:52:55 PDT
Committed r117749: <http://trac.webkit.org/changeset/117749>