DevTools: n^2 -> n while loading heap snapshots and timeline files.

DevTools: n^2 -> n while loading heap snapshots and timeline files.

Committed: https://src.chromium.org/viewvc/blink?view=rev&revision=191070

[pfeldman, 2015-02-28 13:36:43]

pfeldman@chromium.org changed reviewers:
+ alph@chromium.org, caseq@chromium.org, yurys@chromium.org

[alph, 2015-03-01 11:30:14]

Cool! Thanks.

https://codereview.chromium.org/967853002/diff/1/LayoutTests/inspector/json-b...
File LayoutTests/inspector/json-balanced-tokenizer.html (right):

https://codereview.chromium.org/967853002/diff/1/LayoutTests/inspector/json-b...
LayoutTests/inspector/json-balanced-tokenizer.html:86: tokenizer = new
WebInspector.TextUtils.BalancedJSONTokenizer(InspectorTest.addResult.bind(InspectorTest),
true);
great place to have a loop over [3, 15, 50].

https://codereview.chromium.org/967853002/diff/1/Source/devtools/front_end/co...
File Source/devtools/front_end/common/TextUtils.js (right):

https://codereview.chromium.org/967853002/diff/1/Source/devtools/front_end/co...
Source/devtools/front_end/common/TextUtils.js:190: while (this._index <
lastIndex) {
this function seems to be performance sensitive ;-)
so could you please put this._index and _buffer to local vars?

https://codereview.chromium.org/967853002/diff/1/Source/devtools/front_end/co...
Source/devtools/front_end/common/TextUtils.js:201: if (!this._findMultiple) {
That behavior seems strange.
You report a single balanced substring per chunk. In the case when there are
several per chunk it will be lagging behind more and more with each chunk.
So you will have to call write("") at the end several times to extract all the
pending balanced strings.

https://codereview.chromium.org/967853002/diff/1/Source/devtools/front_end/co...
Source/devtools/front_end/common/TextUtils.js:212: // This part seeks the
closing double quote which could have even number of back slashes prefix.
Mind to move this part right under the if (character === "\"")
you should be able to get rid of nested loops then.

https://codereview.chromium.org/967853002/diff/1/Source/devtools/front_end/he...
File Source/devtools/front_end/heap_snapshot_worker/HeapSnapshotLoader.js
(right):

https://codereview.chromium.org/967853002/diff/1/Source/devtools/front_end/he...
Source/devtools/front_end/heap_snapshot_worker/HeapSnapshotLoader.js:125: if
(this._state === "parse-snapshot-info") {
looks like a hack to the state machine.
why not just put it into the corresponding case block?
you can set this._json to null to specify that it shouldn't be accumulated.
wdyt?

https://codereview.chromium.org/967853002/diff/1/Source/devtools/front_end/he...
Source/devtools/front_end/heap_snapshot_worker/HeapSnapshotLoader.js:148:
console.assert(false, "This should nevet happen.")
typo

https://codereview.chromium.org/967853002/diff/1/Source/devtools/front_end/ti...
File Source/devtools/front_end/timeline/TimelineModel.js (right):

https://codereview.chromium.org/967853002/diff/1/Source/devtools/front_end/ti...
Source/devtools/front_end/timeline/TimelineModel.js:1543:
this._progress.setTotalWork(100000);  // Unknown, will loop the values.
mind to a define a const for it plz.

https://codereview.chromium.org/967853002/diff/1/Source/devtools/front_end/ti...
Source/devtools/front_end/timeline/TimelineModel.js:1565:
this._progress.setWorked(this._loadedBytes % 100000,
WebInspector.UIString("Loaded %s bytes",
Number.bytesToString(this._loadedBytes)));
Drop extra "bytes" word.

https://codereview.chromium.org/967853002/diff/1/Source/devtools/front_end/ti...
Source/devtools/front_end/timeline/TimelineModel.js:1614: if (messsage)
two 's'-es should be enough

https://codereview.chromium.org/967853002/diff/1/Source/devtools/front_end/ti...
Source/devtools/front_end/timeline/TimelineModel.js:1631: close: function()
shouldn't there be a check that the remainder is empty?

[pfeldman, 2015-03-01 12:18:54]

Thank you for your wonderful review, it did help simplifying the code both in
the nested loop and in the state machine!

https://codereview.chromium.org/967853002/diff/1/LayoutTests/inspector/json-b...
File LayoutTests/inspector/json-balanced-tokenizer.html (right):

https://codereview.chromium.org/967853002/diff/1/LayoutTests/inspector/json-b...
LayoutTests/inspector/json-balanced-tokenizer.html:86: tokenizer = new
WebInspector.TextUtils.BalancedJSONTokenizer(InspectorTest.addResult.bind(InspectorTest),
true);
On 2015/03/01 11:30:13, alph wrote:
> great place to have a loop over [3, 15, 50].

Done.

https://codereview.chromium.org/967853002/diff/1/Source/devtools/front_end/co...
File Source/devtools/front_end/common/TextUtils.js (right):

https://codereview.chromium.org/967853002/diff/1/Source/devtools/front_end/co...
Source/devtools/front_end/common/TextUtils.js:190: while (this._index <
lastIndex) {
On 2015/03/01 11:30:13, alph wrote:
> this function seems to be performance sensitive ;-)
> so could you please put this._index and _buffer to local vars?

Done.

https://codereview.chromium.org/967853002/diff/1/Source/devtools/front_end/co...
Source/devtools/front_end/common/TextUtils.js:201: if (!this._findMultiple) {
On 2015/03/01 11:30:13, alph wrote:
> That behavior seems strange.
> You report a single balanced substring per chunk. In the case when there are
> several per chunk it will be lagging behind more and more with each chunk.
> So you will have to call write("") at the end several times to extract all the
> pending balanced strings.

This is a "one shot" operation, there is no accumulated wait. Heap profiler only
wants the first chunk, then it discards this tokenizer.

https://codereview.chromium.org/967853002/diff/1/Source/devtools/front_end/co...
Source/devtools/front_end/common/TextUtils.js:212: // This part seeks the
closing double quote which could have even number of back slashes prefix.
This is a great idea! Done.

https://codereview.chromium.org/967853002/diff/1/Source/devtools/front_end/he...
File Source/devtools/front_end/heap_snapshot_worker/HeapSnapshotLoader.js
(right):

https://codereview.chromium.org/967853002/diff/1/Source/devtools/front_end/he...
Source/devtools/front_end/heap_snapshot_worker/HeapSnapshotLoader.js:125: if
(this._state === "parse-snapshot-info") {
On 2015/03/01 11:30:13, alph wrote:
> looks like a hack to the state machine.
> why not just put it into the corresponding case block?
> you can set this._json to null to specify that it shouldn't be accumulated.
> wdyt?

Done.

https://codereview.chromium.org/967853002/diff/1/Source/devtools/front_end/he...
Source/devtools/front_end/heap_snapshot_worker/HeapSnapshotLoader.js:148:
console.assert(false, "This should nevet happen.")
On 2015/03/01 11:30:14, alph wrote:
> typo

Done.

https://codereview.chromium.org/967853002/diff/1/Source/devtools/front_end/ti...
File Source/devtools/front_end/timeline/TimelineModel.js (right):

https://codereview.chromium.org/967853002/diff/1/Source/devtools/front_end/ti...
Source/devtools/front_end/timeline/TimelineModel.js:1543:
this._progress.setTotalWork(100000);  // Unknown, will loop the values.
On 2015/03/01 11:30:14, alph wrote:
> mind to a define a const for it plz.

Done.

https://codereview.chromium.org/967853002/diff/1/Source/devtools/front_end/ti...
Source/devtools/front_end/timeline/TimelineModel.js:1565:
this._progress.setWorked(this._loadedBytes % 100000,
WebInspector.UIString("Loaded %s bytes",
Number.bytesToString(this._loadedBytes)));
On 2015/03/01 11:30:14, alph wrote:
> Drop extra "bytes" word.

Done.

https://codereview.chromium.org/967853002/diff/1/Source/devtools/front_end/ti...
Source/devtools/front_end/timeline/TimelineModel.js:1614: if (messsage)
On 2015/03/01 11:30:14, alph wrote:
> two 's'-es should be enough

Done.

https://codereview.chromium.org/967853002/diff/1/Source/devtools/front_end/ti...
Source/devtools/front_end/timeline/TimelineModel.js:1631: close: function()
On 2015/03/01 11:30:14, alph wrote:
> shouldn't there be a check that the remainder is empty?

There was not previously.

[alph, 2015-03-01 13:26:33]

Thank you. lgtm

https://codereview.chromium.org/967853002/diff/20001/LayoutTests/inspector/js...
File LayoutTests/inspector/json-balanced-tokenizer.html (right):

https://codereview.chromium.org/967853002/diff/20001/LayoutTests/inspector/js...
LayoutTests/inspector/json-balanced-tokenizer.html:86: var samples = [3, 15,
50];
nuke

https://codereview.chromium.org/967853002/diff/20001/Source/devtools/front_en...
File Source/devtools/front_end/common/TextUtils.js (right):

https://codereview.chromium.org/967853002/diff/20001/Source/devtools/front_en...
Source/devtools/front_end/common/TextUtils.js:189: // This does speed things up
5 times.
That's strange provided you're not using buffer in the loop. ;-)

https://codereview.chromium.org/967853002/diff/20001/Source/devtools/front_en...
Source/devtools/front_end/common/TextUtils.js:203: if (!this._findMultiple) {
break;

https://codereview.chromium.org/967853002/diff/20001/Source/devtools/front_en...
Source/devtools/front_end/common/TextUtils.js:216: if (this._lastBalancedIndex)
{
nit: if (!...) return;

[pfeldman, 2015-03-01 14:04:59]

https://codereview.chromium.org/967853002/diff/20001/LayoutTests/inspector/js...
File LayoutTests/inspector/json-balanced-tokenizer.html (right):

https://codereview.chromium.org/967853002/diff/20001/LayoutTests/inspector/js...
LayoutTests/inspector/json-balanced-tokenizer.html:86: var samples = [3, 15,
50];
On 2015/03/01 13:26:32, alph wrote:
> nuke

Done.

https://codereview.chromium.org/967853002/diff/20001/Source/devtools/front_en...
File Source/devtools/front_end/common/TextUtils.js (right):

https://codereview.chromium.org/967853002/diff/20001/Source/devtools/front_en...
Source/devtools/front_end/common/TextUtils.js:189: // This does speed things up
5 times.
On 2015/03/01 13:26:33, alph wrote:
> That's strange provided you're not using buffer in the loop. ;-)

I was testing it with and without locals and was getting 150ms vs 750ms. Now no
matter how I run it is 150.

https://codereview.chromium.org/967853002/diff/20001/Source/devtools/front_en...
Source/devtools/front_end/common/TextUtils.js:203: if (!this._findMultiple) {
On 2015/03/01 13:26:33, alph wrote:
> break;

Done.

https://codereview.chromium.org/967853002/diff/20001/Source/devtools/front_en...
Source/devtools/front_end/common/TextUtils.js:216: if (this._lastBalancedIndex)
{
On 2015/03/01 13:26:33, alph wrote:
> nit: if (!...) return;

Done.

[pfeldman, 2015-03-01 14:11:48]

The CQ bit was checked by pfeldman@chromium.org

[pfeldman, 2015-03-01 14:11:49]

The patchset sent to the CQ was uploaded after l-g-t-m from alph@chromium.org
Link to the patchset: https://codereview.chromium.org/967853002/#ps40001 (title:
"for landing")

[commit-bot: I haz the power, 2015-03-01 14:12:36]

CQ is trying da patch. Follow status at
 https://chromium-cq-status.appspot.com/patch-status/967853002/40001

[commit-bot: I haz the power, 2015-03-01 19:39:49]

The CQ bit was unchecked by commit-bot@chromium.org

[commit-bot: I haz the power, 2015-03-01 19:39:50]

Try jobs failed on following builders:
  linux_blink_rel on tryserver.blink (JOB_FAILED,
http://build.chromium.org/p/tryserver.blink/builders/linux_blink_rel/builds/4...)

[pfeldman, 2015-03-01 20:44:04]

@yurys: could you look into this? testing harness for the heap profiler is
broken:

- Expectation files are empty
- Any failure is any of the tests result in a total failure w/ timeout
- Worker tests have no harness to produce debug output

[pfeldman, 2015-03-01 20:53:36]

(i did find my bug after all, but the tests were not helping)

[pfeldman, 2015-03-01 21:14:39]

The CQ bit was checked by pfeldman@chromium.org

[pfeldman, 2015-03-01 21:14:39]

The patchset sent to the CQ was uploaded after l-g-t-m from alph@chromium.org
Link to the patchset: https://codereview.chromium.org/967853002/#ps60001 (title:
"fixed the load test.")

[commit-bot: I haz the power, 2015-03-01 21:15:01]

CQ is trying da patch. Follow status at
 https://chromium-cq-status.appspot.com/patch-status/967853002/60001

[commit-bot: I haz the power, 2015-03-02 00:53:25]

Committed patchset #4 (id:60001) as
https://src.chromium.org/viewvc/blink?view=rev&revision=191070