Bug 110696 - Web Inspector: Improve speed of Linkifier.reset operation.
Summary: Web Inspector: Improve speed of Linkifier.reset operation.
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:
 
Reported: 2013-02-23 13:32 PST by Ilya Tikhonovsky
Modified: 2013-02-25 01:52 PST (History)
13 users (show)

See Also:


Attachments
Patch (5.44 KB, patch)
2013-02-23 13:40 PST, Ilya Tikhonovsky
no flags Details | Formatted Diff | Diff
Patch (6.68 KB, patch)
2013-02-25 00:06 PST, Ilya Tikhonovsky
no flags Details | Formatted Diff | Diff
Patch (8.93 KB, patch)
2013-02-25 00:36 PST, Ilya Tikhonovsky
no flags Details | Formatted Diff | Diff
Patch (8.93 KB, patch)
2013-02-25 00:43 PST, 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 2013-02-23 13:32:22 PST
Linkifier.reset has complexity O(N^2) where N is the number of LiveLocation objects.
It indirectly calls Array.remove operation which scan entire array and does shift operation.
Comment 1 Ilya Tikhonovsky 2013-02-23 13:40:23 PST
Created attachment 189935 [details]
Patch
Comment 2 Pavel Feldman 2013-02-23 13:56:53 PST
You should use new Map() instead - it generates ids automatically.
Comment 3 Ilya Tikhonovsky 2013-02-23 14:12:41 PST
(In reply to comment #2)
> You should use new Map() instead - it generates ids automatically.

We have two different maps. One in Script.js the other in UISourceCode.js
So we need to have a guarantee that the identifiers are unique.
Also Map uses at least 50% more memory because actually it maps number to the array of two elements, Key and Value.

Probably we need to introduce Set.
Comment 4 Build Bot 2013-02-23 15:26:32 PST
Comment on attachment 189935 [details]
Patch

Attachment 189935 [details] did not pass mac-wk2-ews (mac-wk2):
Output: http://queues.webkit.org/results/16723855

New failing tests:
inspector/debugger/script-formatter-console.html
Comment 5 WebKit Review Bot 2013-02-23 16:22:10 PST
Comment on attachment 189935 [details]
Patch

Attachment 189935 [details] did not pass chromium-ews (chromium-xvfb):
Output: http://queues.webkit.org/results/16729030

New failing tests:
inspector/debugger/callstack-placards-discarded.html
inspector/debugger/script-formatter-console.html
inspector/debugger/script-formatter-breakpoints.html
inspector/debugger/linkifier.html
Comment 6 Build Bot 2013-02-24 01:45:14 PST
Comment on attachment 189935 [details]
Patch

Attachment 189935 [details] did not pass mac-ews (mac):
Output: http://queues.webkit.org/results/16737251

New failing tests:
platform/mac/editing/deleting/deletionUI-single-instance.html
inspector/debugger/script-formatter-console.html
inspector/debugger/script-formatter-breakpoints.html
Comment 7 Ilya Tikhonovsky 2013-02-25 00:06:30 PST
Created attachment 190006 [details]
Patch
Comment 8 Yury Semikhatsky 2013-02-25 00:29:26 PST
Comment on attachment 190006 [details]
Patch

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

> Source/WebCore/inspector/front-end/utilities.js:707
> +    // It has to be string for better performance.

Please explain that it is done to make sure that the object is not converted into an Array by VM because of consecutive integer keys.
Comment 9 Ilya Tikhonovsky 2013-02-25 00:36:39 PST
Created attachment 190011 [details]
Patch
Comment 10 Ilya Tikhonovsky 2013-02-25 00:43:16 PST
Created attachment 190012 [details]
Patch
Comment 11 Andrey Adaikin 2013-02-25 00:57:40 PST
Comment on attachment 190012 [details]
Patch

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

> Source/WebCore/inspector/front-end/UISourceCode.js:55
> +     * @type {Object.<number, WebInspector.LiveLocation>}

wrong @type?

> Source/WebCore/inspector/front-end/utilities.js:705
> +var createObjectIdentifier = function()

/** @return {string} */

> Source/WebCore/inspector/front-end/utilities.js:708
> +    return '_' + ++createObjectIdentifier._last;

' -> "

> Source/WebCore/inspector/front-end/utilities.js:718
> +    this._set = {};

plz add @type !Object.<...>

> Source/WebCore/inspector/front-end/utilities.js:739
> +     * @param {Object} item

{Object} -> {!Object}

> Source/WebCore/inspector/front-end/utilities.js:743
> +        if (this._set[item.__identifier]) {

maybe a check on item.__identifier for consistency with the #add method

> Source/WebCore/inspector/front-end/utilities.js:750
> +     * @return {Array.<Object>}

Array -> !Array

> Source/WebCore/inspector/front-end/utilities.js:762
> +     * @param {Object} item

@return is missing
Comment 12 Andrey Adaikin 2013-02-25 00:58:47 PST
Oops, I must have removed Pavel's r+ due to a collision.
Comment 13 Ilya Tikhonovsky 2013-02-25 01:12:09 PST
Committed r143889: <http://trac.webkit.org/changeset/143889>
Comment 14 Ilya Tikhonovsky 2013-02-25 01:52:01 PST
comments addressed