Bug 87863 – Web Inspector: speed up _calculateRetainedSizes function

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

[Alexei Filippov]

Rewrite the algorithm to be O(n) instead of O(n*log(n)).

Before:
RESULT heap-snapshot: _calculateRetainedSizes= 86 ms

After:
RESULT heap-snapshot: _calculateRetainedSizes= 31 ms

[Alexei Filippov]

Created attachment 144845 [details]
Patch

[Yury Semikhatsky]

Comment on attachment 144845 [details]
Patch

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

> Source/WebCore/inspector/front-end/HeapSnapshot.js:1253
> +        var nodesSelfSize = this._nodes.subarray(this._nodeSelfSizeOffset);

You don't need subarray here, adding this._nodeSelfSizeOffset would probably be more clear to the reader.

> Source/WebCore/inspector/front-end/HeapSnapshot.js:1263
> +        nodeStack[nodeStackTop] = rootNodeOrdinal;

Now that we anyways have postorder index we could go though it and update each nodes retained size sequentially. This way you wouldn't need this stack. WDYT?

[Yury Semikhatsky]

(In reply to comment #0)
> Rewrite the algorithm to be O(n) instead of O(n*log(n)).
> 
> Before:
> RESULT heap-snapshot: _calculateRetainedSizes= 86 ms
> 
> After:
> RESULT heap-snapshot: _calculateRetainedSizes= 31 ms

What's the point in optimizing this given that it is such a small fraction of the overall time?

[Yury Semikhatsky]

Comment on attachment 144845 [details]
Patch

Clearing r? until the comments are addressed.

[Alexei Filippov]

(In reply to comment #2)
> (From update of attachment 144845 [details])
> View in context: https://bugs.webkit.org/attachment.cgi?id=144845&action=review
> 
> > Source/WebCore/inspector/front-end/HeapSnapshot.js:1253
> > +        var nodesSelfSize = this._nodes.subarray(this._nodeSelfSizeOffset);
> 
> You don't need subarray here, adding this._nodeSelfSizeOffset would probably be more clear to the reader.

I've done that to eliminate extra addition from the loop. But if you think the code became too complicated, I'll change it back.

> 
> > Source/WebCore/inspector/front-end/HeapSnapshot.js:1263
> > +        nodeStack[nodeStackTop] = rootNodeOrdinal;
> 
> Now that we anyways have postorder index we could go though it and update each nodes retained size sequentially. This way you wouldn't need this stack. WDYT?

Cool idea. Done that. The time has reduced to 10ms.

(In reply to comment #3)
> (In reply to comment #0)
> > Rewrite the algorithm to be O(n) instead of O(n*log(n)).
> > 
> > Before:
> > RESULT heap-snapshot: _calculateRetainedSizes= 86 ms
> > 
> > After:
> > RESULT heap-snapshot: _calculateRetainedSizes= 31 ms
> 
> What's the point in optimizing this given that it is such a small fraction of the overall time?

This fraction is small for this particular performance test. You know the current algorithm has O(n*n) for the worst case (e.g. a linked list structure).
I checked it on a worst case test having 50k objects. The time it spends in this function has dropped from 10000ms to 2ms.

[Yury Semikhatsky]

(In reply to comment #5)
> (In reply to comment #2)
> > (From update of attachment 144845 [details] [details])
> > View in context: https://bugs.webkit.org/attachment.cgi?id=144845&action=review
> > 
> > > Source/WebCore/inspector/front-end/HeapSnapshot.js:1253
> > > +        var nodesSelfSize = this._nodes.subarray(this._nodeSelfSizeOffset);
> > 
> > You don't need subarray here, adding this._nodeSelfSizeOffset would probably be more clear to the reader.
> 
> I've done that to eliminate extra addition from the loop. But if you think the code became too complicated, I'll change it back.
> 
> > 
> > > Source/WebCore/inspector/front-end/HeapSnapshot.js:1263
> > > +        nodeStack[nodeStackTop] = rootNodeOrdinal;
> > 
> > Now that we anyways have postorder index we could go though it and update each nodes retained size sequentially. This way you wouldn't need this stack. WDYT?
> 
> Cool idea. Done that. The time has reduced to 10ms.
> 
Mind uploading new patch?

> (In reply to comment #3)
> > (In reply to comment #0)
> > > Rewrite the algorithm to be O(n) instead of O(n*log(n)).
> > > 
> > > Before:
> > > RESULT heap-snapshot: _calculateRetainedSizes= 86 ms
> > > 
> > > After:
> > > RESULT heap-snapshot: _calculateRetainedSizes= 31 ms
> > 
> > What's the point in optimizing this given that it is such a small fraction of the overall time?
> 
> This fraction is small for this particular performance test. You know the current algorithm has O(n*n) for the worst case (e.g. a linked list structure).
> I checked it on a worst case test having 50k objects. The time it spends in this function has dropped from 10000ms to 2ms.
Can you convert that into a layout test/performance test?

[Alexei Filippov]

Created attachment 145061 [details]
Patch

[Alexei Filippov]

Created attachment 145079 [details]
Patch

[Alexei Filippov]

Added the performance test.

[Yury Semikhatsky]

Comment on attachment 145079 [details]
Patch

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

> PerformanceTests/inspector/performance-test.js:148
> +    InspectorTest.measureFunction(WebInspector.HeapSnapshot.prototype, "_buildRetainers");

This file is used not only by profiler.

[Ilya Tikhonovsky]

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

> PerformanceTests/inspector/performance-test.js:211
> +            timer.done("heap-snapshot");

heap-snapshot is a page name. You have to calculate it from the url or transfer it as an argument.

[Alexei Filippov]

Created attachment 145276 [details]
Patch

[Yury Semikhatsky]

Comment on attachment 145276 [details]
Patch

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

> PerformanceTests/inspector/heap-performance-test.js:1
> +function test()

heap-performance-test.js -> heap-profiler-performance-test.js or heap-snapshot-performance-test.js

[Alexei Filippov]

Created attachment 145280 [details]
Patch

[Ilya Tikhonovsky]

Comment on attachment 145280 [details]
Patch

looks good to me

[Alexei Filippov]

Created attachment 145283 [details]
Patch

[WebKit Review Bot]

Comment on attachment 145283 [details]
Patch

Rejecting attachment 145283 [details] from commit-queue.

[e-mail] does not have committer permissions according to http://trac.webkit.org/browser/trunk/Tools/Scripts/webkitpy/common/config/committers.py.

- If you do not have committer rights please read http://webkit.org/coding/contributing.html for instructions on how to use bugzilla flags.

- If you have committer rights please correct the error in Tools/Scripts/webkitpy/common/config/committers.py by adding yourself to the file (no review needed).  The commit-queue restarts itself every 2 hours.  After restart the commit-queue will correctly respect your committer rights.

[Ilya Tikhonovsky]

Comment on attachment 145283 [details]
Patch

Clearing flags on attachment: 145283

Committed r119389: <http://trac.webkit.org/changeset/119389>

[Ilya Tikhonovsky]

All reviewed patches have been landed.  Closing bug.