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
Created attachment 144845 [details] Patch
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?
(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?
Comment on attachment 144845 [details] Patch Clearing r? until the comments are addressed.
(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.
(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?
Created attachment 145061 [details] Patch
Created attachment 145079 [details] Patch
Added the performance test.
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.
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.
Created attachment 145276 [details] Patch
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
Created attachment 145280 [details] Patch
Comment on attachment 145280 [details] Patch looks good to me
Created attachment 145283 [details] Patch
Comment on attachment 145283 [details] Patch Rejecting attachment 145283 [details] from commit-queue. alexeif@chromium.org 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.
Comment on attachment 145283 [details] Patch Clearing flags on attachment: 145283 Committed r119389: <http://trac.webkit.org/changeset/119389>
All reviewed patches have been landed. Closing bug.