Bug 152422 – Web Inspector: WebInspector.Object.addEventListener is O(n), make it O(1)

• Status: RESOLVED
• Resolution: FIXED
• Component: Web Inspector

[Nikita Vasilyev]

This code is the main reason our console is slow:

    // Prevent registering multiple times.
    for (var i = 0; i < listeners.length; ++i) {
        if (listeners[i].listener === listener && listeners[i].thisObject === thisObject)
            return;
    }

https://github.com/WebKit/webkit/blob/master/Source/WebInspectorUI/UserInterface/Base/Object.js#L49-L53

Registering the same event handler twice is most likely a bug.
In fact, I haven't found a case when we do that.

If we do need to check this for some reason, we could use Set (or better WeakSet) to do it in O(1) time.

[Nikita Vasilyev]

I tried to find why this code was added:

    git log --follow UserInterface/Base/Object.js

(--follow is to track file renames)

When Web Inspector was re-opensourced again in 2013, it already had those lines.

https://github.com/WebKit/webkit/blob/27b08c9a0911814354471b33be88b78ee883e5e9/Source/WebInspectorUI/UserInterface/Object.js#L72-L76

[Nikita Vasilyev]

I looked at Chrome DevTools' Object.addEventListener.
It doesn't have this code.

https://chromium.googlesource.com/chromium/src/+/f41b74417b24c8104f260e0bff15b5bfddcadb51/third_party/WebKit/Source/WebCore/inspector/front-end/Object.js

I looked at the whole file's history and, in fact, it never had this code!
It must have been added during closed-source Web Inspector times.

[Nikita Vasilyev]

Created attachment 267619 [details]
WIP

[Nikita Vasilyev]

Comment on attachment 267619 [details]
WIP

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

> Source/WebInspectorUI/ChangeLog:6
> +        Theoretically, this makes adding 1000 console messages 500 times faster.

https://en.wikipedia.org/wiki/Triangular_number =)
(1000 + 1) / 2 = 500.5

I'll replace this with actual numbers once I've done more profiling.

> Source/WebInspectorUI/UserInterface/Base/Object.js:57
> +            console.warn("Object.addEventListener: " + JSON.stringify(eventType) + " already exist");

I was wrong. This happens very often:

[Warning] Object.addEventListener: "dom-tree-manager-character-data-modified" already exist (Object.js, line 57)
[Warning] Object.addEventListener: "resource-loading-did-fail" already exist (Object.js, line 57)
[Warning] Object.addEventListener: "resource-url-did-change" already exist (Object.js, line 57)
[Warning] Object.addEventListener: "resource-type-did-change" already exist (Object.js, line 57)
[Warning] Object.addEventListener: "resource-loading-did-finish" already exist (Object.js, line 57)
[Warning] Object.addEventListener: "resource-loading-did-fail" already exist (Object.js, line 57, x3)
[Warning] Object.addEventListener: "content-view-supplemental-represented-objects-did-change" already exist (Object.js, line 57)
[Warning] Object.addEventListener: "content-view-number-of-search-results-did-change" already exist (Object.js, line 57)
[Warning] Object.addEventListener: "breakpoint-auto-continue-did-change" already exist (Object.js, line 57)
[Warning] Object.addEventListener: "breakpoint-resolved-state-did-change" already exist (Object.js, line 57)
[Warning] Object.addEventListener: "breakpoint-location-did-change" already exist (Object.js, line 57)
[Warning] Object.addEventListener: "debugger-manager-breakpoint-added" already exist (Object.js, line 57)
[Warning] Object.addEventListener: "debugger-manager-breakpoint-removed" already exist (Object.js, line 57)
[Warning] Object.addEventListener: "debugger-manager-active-call-frame-did-change" already exist (Object.js, line 57)
[Warning] Object.addEventListener: "debugger-manager-paused" already exist (Object.js, line 57)
[Warning] Object.addEventListener: "debugger-manager-resumed" already exist (Object.js, line 57)
[Warning] Object.addEventListener: "probe-manager-probe-set-removed" already exist (Object.js, line 57)
[Warning] Object.addEventListener: "dom-node-styles-needs-refresh" already exist (Object.js, line 57, x2)
[Warning] Object.addEventListener: "source-code-formatter-did-change" already exist (Object.js, line 57)
[Warning] Object.addEventListener: "stylesheet-content-did-change" already exist (Object.js, line 57)
[Warning] Object.addEventListener: "source-code-formatter-did-change" already exist (Object.js, line 57)
[Warning] Object.addEventListener: "stylesheet-content-did-change" already exist (Object.js, line 57)
[Warning] Object.addEventListener: "stylesheet-content-did-change" already exist (Object.js, line 57)
[Warning] Object.addEventListener: "source-code-formatter-did-change" already exist (Object.js, line 57)
[Warning] Object.addEventListener: "source-code-formatter-did-change" already exist (Object.js, line 57)
[Warning] Object.addEventListener: "stylesheet-content-did-change" already exist (Object.js, line 57, x2)
[Warning] Object.addEventListener: "stylesheet-content-did-change" already exist (Object.js, line 57)
[Warning] Object.addEventListener: "source-code-formatter-did-change" already exist (Object.js, line 57)
[Warning] Object.addEventListener: "source-code-formatter-did-change" already exist (Object.js, line 57)
[Warning] Object.addEventListener: "source-code-formatter-did-change" already exist (Object.js, line 57)
[Warning] Object.addEventListener: "source-code-formatter-did-change" already exist (Object.js, line 57)
[Warning] Object.addEventListener: "source-code-formatter-did-change" already exist (Object.js, line 57)
[Warning] Object.addEventListener: "source-code-formatter-did-change" already exist (Object.js, line 57)
[Warning] Object.addEventListener: "stylesheet-content-did-change" already exist (Object.js, line 57)
[Warning] Object.addEventListener: "css-property-overridden-status-changed" already exist (Object.js, line 57, x5)
[Warning] Object.addEventListener: "resource-cached-did-change" already exist (Object.js, line 57)

Maybe I should just remove this console.warn.

[Nikita Vasilyev]

(In reply to comment #4)
> Comment on attachment 267619 [details]
> WIP
> 
> View in context:
> https://bugs.webkit.org/attachment.cgi?id=267619&action=review
> 
> > Source/WebInspectorUI/ChangeLog:6
> > +        Theoretically, this makes adding 1000 console messages 500 times faster.
> 
> https://en.wikipedia.org/wiki/Triangular_number =)
> (1000 + 1) / 2 = 500.5
> 
> I'll replace this with actual numbers once I've done more profiling.

Preliminary testing shows that initialization time for 1001st ConsoleMessageView
decreased from 30ms to 2ms.

    1 second / 60 frames = 16.67ms

To put this into perspective, we were to slow to add one console message per frame
and how we can add 8.

[Build Bot]

Comment on attachment 267619 [details]
WIP

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

New failing tests:
imported/w3c/web-platform-tests/streams-api/readable-streams/garbage-collection.html

[Build Bot]

Created attachment 267621 [details]
Archive of layout-test-results from ews116 for mac-yosemite

The attached test failures were seen while running run-webkit-tests on the mac-debug-ews.
Bot: ews116  Port: mac-yosemite  Platform: Mac OS X 10.10.5

[Nikita Vasilyev]

Comment on attachment 267619 [details]
WIP

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

>>> Source/WebInspectorUI/ChangeLog:6
>>> +        Theoretically, this makes adding 1000 console messages 500 times faster.
>> 
>> https://en.wikipedia.org/wiki/Triangular_number =)
>> (1000 + 1) / 2 = 500.5
>> 
>> I'll replace this with actual numbers once I've done more profiling.
> 
> Preliminary testing shows that initialization time for 1001st ConsoleMessageView
> decreased from 30ms to 2ms.
> 
>     1 second / 60 frames = 16.67ms
> 
> To put this into perspective, we were to slow to add one console message per frame
> and how we can add 8.

Err, it should have been:
"Theoretically, this makes adding 1000 EVENT LISTENERS 500 times faster."

[Devin Rousso]

Comment on attachment 267619 [details]
WIP

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

> Source/WebInspectorUI/UserInterface/Base/Object.js:53
> +        if (!this._listenersSet)

So is the main reason for adding this._listenersSet to avoid having to loop through the entirety of this._listeners (specifically the array for that event type) whenever adding an event listener?  If so, is there any way to try make everything revolve around this._listenersSet?  Having this._listenersSet AND this._listeners seems very confusing as to what each is needed for (also, remove is running O(n) right now because it has to search through the whole list, and that could definitely be improved like add)...  Maybe have this._listenersSet be a WeakSet of WeakSets (where each child-WeakSet is the new form of the array being used to hold all the listeners)?

>> Source/WebInspectorUI/UserInterface/Base/Object.js:57
>> +            console.warn("Object.addEventListener: " + JSON.stringify(eventType) + " already exist");
> 
> I was wrong. This happens very often:
> 
> [Warning] Object.addEventListener: "dom-tree-manager-character-data-modified" already exist (Object.js, line 57)
> [Warning] Object.addEventListener: "resource-loading-did-fail" already exist (Object.js, line 57)
> [Warning] Object.addEventListener: "resource-url-did-change" already exist (Object.js, line 57)
> [Warning] Object.addEventListener: "resource-type-did-change" already exist (Object.js, line 57)
> [Warning] Object.addEventListener: "resource-loading-did-finish" already exist (Object.js, line 57)
> [Warning] Object.addEventListener: "resource-loading-did-fail" already exist (Object.js, line 57, x3)
> [Warning] Object.addEventListener: "content-view-supplemental-represented-objects-did-change" already exist (Object.js, line 57)
> [Warning] Object.addEventListener: "content-view-number-of-search-results-did-change" already exist (Object.js, line 57)
> [Warning] Object.addEventListener: "breakpoint-auto-continue-did-change" already exist (Object.js, line 57)
> [Warning] Object.addEventListener: "breakpoint-resolved-state-did-change" already exist (Object.js, line 57)
> [Warning] Object.addEventListener: "breakpoint-location-did-change" already exist (Object.js, line 57)
> [Warning] Object.addEventListener: "debugger-manager-breakpoint-added" already exist (Object.js, line 57)
> [Warning] Object.addEventListener: "debugger-manager-breakpoint-removed" already exist (Object.js, line 57)
> [Warning] Object.addEventListener: "debugger-manager-active-call-frame-did-change" already exist (Object.js, line 57)
> [Warning] Object.addEventListener: "debugger-manager-paused" already exist (Object.js, line 57)
> [Warning] Object.addEventListener: "debugger-manager-resumed" already exist (Object.js, line 57)
> [Warning] Object.addEventListener: "probe-manager-probe-set-removed" already exist (Object.js, line 57)
> [Warning] Object.addEventListener: "dom-node-styles-needs-refresh" already exist (Object.js, line 57, x2)
> [Warning] Object.addEventListener: "source-code-formatter-did-change" already exist (Object.js, line 57)
> [Warning] Object.addEventListener: "stylesheet-content-did-change" already exist (Object.js, line 57)
> [Warning] Object.addEventListener: "source-code-formatter-did-change" already exist (Object.js, line 57)
> [Warning] Object.addEventListener: "stylesheet-content-did-change" already exist (Object.js, line 57)
> [Warning] Object.addEventListener: "stylesheet-content-did-change" already exist (Object.js, line 57)
> [Warning] Object.addEventListener: "source-code-formatter-did-change" already exist (Object.js, line 57)
> [Warning] Object.addEventListener: "source-code-formatter-did-change" already exist (Object.js, line 57)
> [Warning] Object.addEventListener: "stylesheet-content-did-change" already exist (Object.js, line 57, x2)
> [Warning] Object.addEventListener: "stylesheet-content-did-change" already exist (Object.js, line 57)
> [Warning] Object.addEventListener: "source-code-formatter-did-change" already exist (Object.js, line 57)
> [Warning] Object.addEventListener: "source-code-formatter-did-change" already exist (Object.js, line 57)
> [Warning] Object.addEventListener: "source-code-formatter-did-change" already exist (Object.js, line 57)
> [Warning] Object.addEventListener: "source-code-formatter-did-change" already exist (Object.js, line 57)
> [Warning] Object.addEventListener: "source-code-formatter-did-change" already exist (Object.js, line 57)
> [Warning] Object.addEventListener: "source-code-formatter-did-change" already exist (Object.js, line 57)
> [Warning] Object.addEventListener: "stylesheet-content-did-change" already exist (Object.js, line 57)
> [Warning] Object.addEventListener: "css-property-overridden-status-changed" already exist (Object.js, line 57, x5)
> [Warning] Object.addEventListener: "resource-cached-did-change" already exist (Object.js, line 57)
> 
> Maybe I should just remove this console.warn.

AFAIK, default addEventListener just ignores duplicates, so maybe we should just follow that pattern too.

[Nikita Vasilyev]

(In reply to comment #9)
> Comment on attachment 267619 [details]
> WIP
> 
> View in context:
> https://bugs.webkit.org/attachment.cgi?id=267619&action=review
> 
> > Source/WebInspectorUI/UserInterface/Base/Object.js:53
> > +        if (!this._listenersSet)
> 
> So is the main reason for adding this._listenersSet to avoid having to loop
> through the entirety of this._listeners (specifically the array for that
> event type) whenever adding an event listener?

Yes.

> If so, is there any way to
> try make everything revolve around this._listenersSet?  Having
> this._listenersSet AND this._listeners seems very confusing as to what each
> is needed for (also, remove is running O(n) right now because it has to
> search through the whole list, and that could definitely be improved like
> add)...

Yes, good catch. I haven't touched removeEventListener yet. 

> Maybe have this._listenersSet be a WeakSet of WeakSets (where each
> child-WeakSet is the new form of the array being used to hold all the
> listeners)?

We need to be able to iterate over all listeners of certain type.
We do that in dispatchEventToListeners. We can't ONLY use WeakSets since,
well, they are weak and don't allow to iterate over their keys.

However, I still think it could be simplified if we remove thisObject argument.

    addEventListener(eventType, listener, thisObject)

Having thisObject as a third argument is odd because the third argument
of the native addEventListener is useCapture, a boolean parameter. We could
use Function#bind instead:

    addEventListener(eventType, listener.bind(thisObject))

If we remove thisObject, we could do:

    this._listeners[eventType] = new Set
    this._listeners[eventType].add(listener) // O(1)
    this._listeners[eventType].has(listener) // O(1)
    this._listeners[eventType].delete(listener) // O(1)

The thing I'm not certain is how much slower iterating over a set would be
compared to an array:

    this._listeners[eventType].keys()

I'll do more tests tomorrow.

[Joseph Pecoraro]

Comment on attachment 267619 [details]
WIP

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

>>> Source/WebInspectorUI/UserInterface/Base/Object.js:57
>>> +            console.warn("Object.addEventListener: " + JSON.stringify(eventType) + " already exist");
>> 
>> I was wrong. This happens very often:
>> 
>> [Warning] Object.addEventListener: "dom-tree-manager-character-data-modified" already exist (Object.js, line 57)
>> [Warning] Object.addEventListener: "resource-loading-did-fail" already exist (Object.js, line 57)
>> [Warning] Object.addEventListener: "resource-url-did-change" already exist (Object.js, line 57)
>> [Warning] Object.addEventListener: "resource-type-did-change" already exist (Object.js, line 57)
>> [Warning] Object.addEventListener: "resource-loading-did-finish" already exist (Object.js, line 57)
>> [Warning] Object.addEventListener: "resource-loading-did-fail" already exist (Object.js, line 57, x3)
>> [Warning] Object.addEventListener: "content-view-supplemental-represented-objects-did-change" already exist (Object.js, line 57)
>> [Warning] Object.addEventListener: "content-view-number-of-search-results-did-change" already exist (Object.js, line 57)
>> [Warning] Object.addEventListener: "breakpoint-auto-continue-did-change" already exist (Object.js, line 57)
>> [Warning] Object.addEventListener: "breakpoint-resolved-state-did-change" already exist (Object.js, line 57)
>> [Warning] Object.addEventListener: "breakpoint-location-did-change" already exist (Object.js, line 57)
>> [Warning] Object.addEventListener: "debugger-manager-breakpoint-added" already exist (Object.js, line 57)
>> [Warning] Object.addEventListener: "debugger-manager-breakpoint-removed" already exist (Object.js, line 57)
>> [Warning] Object.addEventListener: "debugger-manager-active-call-frame-did-change" already exist (Object.js, line 57)
>> [Warning] Object.addEventListener: "debugger-manager-paused" already exist (Object.js, line 57)
>> [Warning] Object.addEventListener: "debugger-manager-resumed" already exist (Object.js, line 57)
>> [Warning] Object.addEventListener: "probe-manager-probe-set-removed" already exist (Object.js, line 57)
>> [Warning] Object.addEventListener: "dom-node-styles-needs-refresh" already exist (Object.js, line 57, x2)
>> [Warning] Object.addEventListener: "source-code-formatter-did-change" already exist (Object.js, line 57)
>> [Warning] Object.addEventListener: "stylesheet-content-did-change" already exist (Object.js, line 57)
>> [Warning] Object.addEventListener: "source-code-formatter-did-change" already exist (Object.js, line 57)
>> [Warning] Object.addEventListener: "stylesheet-content-did-change" already exist (Object.js, line 57)
>> [Warning] Object.addEventListener: "stylesheet-content-did-change" already exist (Object.js, line 57)
>> [Warning] Object.addEventListener: "source-code-formatter-did-change" already exist (Object.js, line 57)
>> [Warning] Object.addEventListener: "source-code-formatter-did-change" already exist (Object.js, line 57)
>> [Warning] Object.addEventListener: "stylesheet-content-did-change" already exist (Object.js, line 57, x2)
>> [Warning] Object.addEventListener: "stylesheet-content-did-change" already exist (Object.js, line 57)
>> [Warning] Object.addEventListener: "source-code-formatter-did-change" already exist (Object.js, line 57)
>> [Warning] Object.addEventListener: "source-code-formatter-did-change" already exist (Object.js, line 57)
>> [Warning] Object.addEventListener: "source-code-formatter-did-change" already exist (Object.js, line 57)
>> [Warning] Object.addEventListener: "source-code-formatter-did-change" already exist (Object.js, line 57)
>> [Warning] Object.addEventListener: "source-code-formatter-did-change" already exist (Object.js, line 57)
>> [Warning] Object.addEventListener: "source-code-formatter-did-change" already exist (Object.js, line 57)
>> [Warning] Object.addEventListener: "stylesheet-content-did-change" already exist (Object.js, line 57)
>> [Warning] Object.addEventListener: "css-property-overridden-status-changed" already exist (Object.js, line 57, x5)
>> [Warning] Object.addEventListener: "resource-cached-did-change" already exist (Object.js, line 57)
>> 
>> Maybe I should just remove this console.warn.
> 
> AFAIK, default addEventListener just ignores duplicates, so maybe we should just follow that pattern too.

I don't think this comparison right. All this is checking is "did we have this listener on this object" and "did we have this thisObject on this object" but really we should be checking "did we have this (eventType, listener, thisObject) tuple on this object".

For example right now I think this would warn, but it is not at all problematic:

    let obj = new WebInspector.Object;
    let handler = function() {};
    let thisObject = {};
    obj.addEventListener("event-1", handler, thisObject);
    obj.addEventListener("event-2", handler, thisObject);

You could compare this to the original warning and put a console.warn in the original code's bail and see if you get any warnings.

[Joseph Pecoraro]

(In reply to comment #0)
> This code is the main reason our console is slow:
> 
>     // Prevent registering multiple times.
>     for (var i = 0; i < listeners.length; ++i) {
>         if (listeners[i].listener === listener && listeners[i].thisObject
> === thisObject)
>             return;
>     }

Good find!

We could just drop this code. It is just trying to be safe, but really it is the registerer's fault. This could be turned into an assert (but would still affect Release/Debug builds). Ultimately this just works around addEventListener mis-use, without warning about it and apparently impacting performance.

My guess is this became a problem with SourceCodeLocation objects? Each console message will likely have a SourceCodeLocation and register for an event when the SourceCodeLocation object changes, to update the display location.

[Joseph Pecoraro]

> My guess is this became a problem with SourceCodeLocation objects? Each
> console message will likely have a SourceCodeLocation and register for an
> event when the SourceCodeLocation object changes, to update the display
> location.

I suppose this brings up a possible leak. When the Console is cleared, the ConsoleMessageView / elements are removed, but some things could be held around. If something called with an element `elem`:

    SourceCodeLocation.populateLiveDisplayLocationTooltip
    SourceCodeLocation.populateLiveDisplayLocationString

Then `elem` will continue to be retained by the closures and event listeners created inside these methods. `elem` and the event listener will only get GC'd when the SourceCodeLocation itself can be GC'd (hopefully page navigation / reload).

[Nikita Vasilyev]

(In reply to comment #11)
> ...
> I don't think this comparison right. All this is checking is "did we have
> this listener on this object" and "did we have this thisObject on this
> object" but really we should be checking "did we have this (eventType,
> listener, thisObject) tuple on this object".

Oh, duh! I don't know how I didn't see it.

I added console.warn inside of the old for loop and found the following cases:

[Warning] Object.addEventListener: "stylesheet-content-did-change" already exist (2) (Object.js, line 54)
[Warning] Object.addEventListener: "timeline-times-updated" already exist (2) (Object.js, line 54)


(In reply to comment #12)
> ...
> We could just drop this code. It is just trying to be safe, but really it is
> the registerer's fault. This could be turned into an assert (but would still
> affect Release/Debug builds). Ultimately this just works around
> addEventListener mis-use, without warning about it and apparently impacting
> performance.

I also think it's registerer's fault. We should investigate when this happens
and fix it outside of addEventListener.


> My guess is this became a problem with SourceCodeLocation objects? Each
> console message will likely have a SourceCodeLocation and register for an
> event when the SourceCodeLocation object changes, to update the display
> location.

Correct. A screenshot of Timelines from the defendant bug proves it:
https://bug-152418-attachments.webkit.org/attachment.cgi?id=267609

[Nikita Vasilyev]

(In reply to comment #10)
> 
>     addEventListener(eventType, listener, thisObject)
> 
> Having thisObject as a third argument is odd because the third argument
> of the native addEventListener is useCapture, a boolean parameter. We could
> use Function#bind instead:
> 
>     addEventListener(eventType, listener.bind(thisObject))
> 
> If we remove thisObject, we could do:
> 
>     this._listeners[eventType] = new Set
>     this._listeners[eventType].add(listener) // O(1)
>     this._listeners[eventType].has(listener) // O(1)
>     this._listeners[eventType].delete(listener) // O(1)
> 
> The thing I'm not certain is how much slower iterating over a set would be
> compared to an array:
> 
>     this._listeners[eventType].keys()
> 
> I'll do more tests tomorrow.

Joe, any thoughts on removing thisObject argument?

[Nikita Vasilyev]

(In reply to comment #10)
> ...
> The thing I'm not certain is how much slower iterating over a set would be
> compared to an array:
> 
>     this._listeners[eventType].keys()
> 
> I'll do more tests tomorrow.

Of course, somebody already measured that:
http://jsperf.com/iterating-over-a-set-vs-iterating-over-an-array

Set#forEach does only 4,428 operations per second in WebKit Nightly.
It's 0.22ms per iteration. It is...
10x slower than Array's forEach
20x slower than Array's for-of
100x slower than good ol' for loop

That's not great.

[Joseph Pecoraro]

> Joe, any thoughts on removing thisObject argument?

So we would have to addEventListeners with bound functions? I'm not sure if that is good.

[Joseph Pecoraro]

> [Warning] Object.addEventListener: "stylesheet-content-did-change" already exist (2) (Object.js, line 54)

Looks like a legit issue. DOMNodeStyles may want to be smarter about this:

Models/DOMNodeStyles.js
600:            styleSheet.addEventListener(WebInspector.CSSStyleSheet.Event.ContentDidChange, this._styleSheetContentDidChange, this);
714:            styleSheet.addEventListener(WebInspector.CSSStyleSheet.Event.ContentDidChange, this._styleSheetContentDidChange, this);


> [Warning] Object.addEventListener: "timeline-times-updated" already exist (2) (Object.js, line 54)

This one is trickier. A console.trace() when this happens would tell us the offending location.

[Timothy Hatcher]

(In reply to comment #17)
> > Joe, any thoughts on removing thisObject argument?
> 
> So we would have to addEventListeners with bound functions? I'm not sure if
> that is good.

We have thisObject so it is easier to add and later remove without having to store a bound function everywhere.

[Timothy Hatcher]

(In reply to comment #16)
> (In reply to comment #10)
> > ...
> > The thing I'm not certain is how much slower iterating over a set would be
> > compared to an array:
> > 
> >     this._listeners[eventType].keys()
> > 
> > I'll do more tests tomorrow.
> 
> Of course, somebody already measured that:
> http://jsperf.com/iterating-over-a-set-vs-iterating-over-an-array
> 
> Set#forEach does only 4,428 operations per second in WebKit Nightly.
> It's 0.22ms per iteration. It is...
> 10x slower than Array's forEach
> 20x slower than Array's for-of
> 100x slower than good ol' for loop
> 
> That's not great.

Yes, iterating with for(..of..) is known to be slow compared to for(var i...) on an array.

At one point I attempted to switch everything in Object over to WeakMaps and Sets. That would allow us to avoid retain leaks on listeners, but WeakMap/Set can't be iterated.

I abandoned that patch, but in theory we could have used it to use just Map and Set and keep the same listener retain policy we have now. But it seems iteration speed might have make things worse (not withstanding the check for redundant listeners.)

I agree the check for redundant listeners is likely too much and it really is a coding error to register multiple times. I forget why I added it, but yes it has existed for a long time. I do worry we might introduce other errors or worse performance if we allow multiple listener registrations. We need to be very careful in this code.

[Timothy Hatcher]

It looks like I attached that WIP event listener code to bug 123527: https://bug-123527-attachments.webkit.org/attachment.cgi?id=215559

[Timothy Hatcher]

Note: I used WeakMap in that code for the this object map. That does not work and could be changed to a Map. Also I used forEach in that code on the Sets and Maps because for(..of..) was not implemented for Maps and Sets yet! Maybe forEach is faster on Map/Set anyway?

[Timothy Hatcher]

We have also fixed some bugs since I converted that code, so please don't just copy and paste it. Namely Matt's fix to not dispatch multiple times. ;)

[Nikita Vasilyev]

The previous jsperf link didn't have a case with for-of for Set.
http://jsperf.com/iterating-over-a-set-vs-iterating-over-an-array/2
Turns out for-of for Set is 4x slower than Set#forEach.

[Nikita Vasilyev]

I have a patch in works that makes removeEventListener O(1), too.
It keeps the check for redundant listeners, but it's O(1).
It also doesn't change thisObject.

I hope to finish in a few hours.

[Nikita Vasilyev]

removeEventListener(null, null, this) — why do we do this?

It removes ALL event listeners of all types that have "this" as their thisObject.
Currently, it loops through ALL event listeners for ALL event types.
It's really bad for performance.

There are 51 occurrences of this code in UserInterface/Views:
https://github.com/WebKit/webkit/search?utf8=✓&q=removeEventListener%28null%2C+null%2C+this%29%3B+path%3ASource%2FWebInspectorUI%2FUserInterface%2FViews+language%3Ajavascript&type=Code

Can we use:

- removeAllListeners() to remove ALL listeners, no matter what thisObject is.
  removeAllListeners() is just "this._listeners = {}", so it is very fast.

- removeEventListener(eventType, listener, thisObject) to remove specific event listeners.
  Currently it's O(n), but I can make it O(1) by using Maps.

?

[Nikita Vasilyev]

Okay, I see removeEventListener(null, null, someObj) is somewhat convenient way
to remove all event handlers that use someObj. Once a view is disposed,
it makes sense to remove all its event listeners to prevent potential memory leaks.

However, the current implementation of removeEventListener(null, null, someObj)
is very inefficient. Essentially, this is what it does:

    for (eventType in this._listeners) {
        var listeners = this._listeners[eventType];
        for (let i = listeners.length - 1; i >= 0; --i) {
            if (listeners[i].thisObject === thisObject) {
                listeners.splice(i, 1);
            }
        }
    }

[Devin Rousso]

(In reply to comment #20)
> Yes, iterating with for(..of..) is known to be slow compared to for(var
> i...) on an array.

I'm actually very surprised by this.  If for-of iterations are slower, why is it that we prefer them over the index-based iterators?  Is it simply for the sake of readability, considering that most of the for-of's are not looping many times?

> At one point I attempted to switch everything in Object over to WeakMaps and
> Sets. That would allow us to avoid retain leaks on listeners, but
> WeakMap/Set can't be iterated.
> 
> I abandoned that patch, but in theory we could have used it to use just Map
> and Set and keep the same listener retain policy we have now. But it seems
> iteration speed might have make things worse (not withstanding the check for
> redundant listeners.)

So, just for my own knowledge, is the only reason that we don't use Set or Map because of the time needed to iterate (as well as the GC issue)?  As far as I understand, the add/has/remove operations of a Set/Map are supposed to be much faster than attempting to loop through an array, especially an unsorted one (O(log(n)) vs O(n)).  Is this not true in JS, or is the main issue here the fact that non-weak Sets/Maps cannot GC well?

Then again, my desire to use a set for this type of situation may just be a remnant from my Data Structures class this past semester...

[Blaze Burg]

(In reply to comment #0)
> This code is the main reason our console is slow:
> 
>     // Prevent registering multiple times.
>     for (var i = 0; i < listeners.length; ++i) {
>         if (listeners[i].listener === listener && listeners[i].thisObject
> === thisObject)
>             return;
>     }
> 
> https://github.com/WebKit/webkit/blob/master/Source/WebInspectorUI/
> UserInterface/Base/Object.js#L49-L53
> 
> Registering the same event handler twice is most likely a bug.
> In fact, I haven't found a case when we do that.
> 
> If we do need to check this for some reason, we could use Set (or better
> WeakSet) to do it in O(1) time.

I still don't believe this could ever be a bottleneck among all the things that happen when a console message is dispatched. Do you have a screenshot of a profile?

[Nikita Vasilyev]

(In reply to comment #29)
> (In reply to comment #0)
> > This code is the main reason our console is slow:
> > 
> >     // Prevent registering multiple times.
> >     for (var i = 0; i < listeners.length; ++i) {
> >         if (listeners[i].listener === listener && listeners[i].thisObject
> > === thisObject)
> >             return;
> >     }
> > 
> > https://github.com/WebKit/webkit/blob/master/Source/WebInspectorUI/
> > UserInterface/Base/Object.js#L49-L53
> > 
> > Registering the same event handler twice is most likely a bug.
> > In fact, I haven't found a case when we do that.
> > 
> > If we do need to check this for some reason, we could use Set (or better
> > WeakSet) to do it in O(1) time.
> 
> I still don't believe this could ever be a bottleneck among all the things
> that happen when a console message is dispatched. Do you have a screenshot
> of a profile?

https://bugs.webkit.org/show_bug.cgi?id=152418#c1

[Timothy Hatcher]

(In reply to comment #28)
> (In reply to comment #20)
> > Yes, iterating with for(..of..) is known to be slow compared to for(var
> > i...) on an array.
> 
> I'm actually very surprised by this.  If for-of iterations are slower, why
> is it that we prefer them over the index-based iterators?  Is it simply for
> the sake of readability, considering that most of the for-of's are not
> looping many times?
> 
> > At one point I attempted to switch everything in Object over to WeakMaps and
> > Sets. That would allow us to avoid retain leaks on listeners, but
> > WeakMap/Set can't be iterated.
> > 
> > I abandoned that patch, but in theory we could have used it to use just Map
> > and Set and keep the same listener retain policy we have now. But it seems
> > iteration speed might have make things worse (not withstanding the check for
> > redundant listeners.)
> 
> So, just for my own knowledge, is the only reason that we don't use Set or
> Map because of the time needed to iterate (as well as the GC issue)?  As far
> as I understand, the add/has/remove operations of a Set/Map are supposed to
> be much faster than attempting to loop through an array, especially an
> unsorted one (O(log(n)) vs O(n)).  Is this not true in JS, or is the main
> issue here the fact that non-weak Sets/Maps cannot GC well?
> 
> Then again, my desire to use a set for this type of situation may just be a
> remnant from my Data Structures class this past semester...

I just never finished the patch to convert to Set/Map after I hit that iteration limitation trying to use WeakMap. Set/Map have the same GC semantics as object key/value mappings.

I didn't know about the Set/Map iteration speed hit when I first attempted this. In general the Set/Map iteration speed is not much of a concern in normal code. We probably should be concerned some in Object.js or any hot code.

[Timothy Hatcher]

And yes, add/has/remove operations of Set/Map are a win.

[Nikita Vasilyev]

It's possible to implement an ordered Set/Map that is 12 times
faster to iterate than a native Set/Map by using a linked list.

http://jsperf.com/linked-list-vs-arraw-iteration-speed/3

In fact, that's what we used for event listeners at my previous job:
http://www.collectionsjs.com/set

This Ordered Set is backed by a doubly linked list and a set.
Linked list tracks insertion order. Set ensures uniqueness
and O(1) add/has/remove.

I'm working on a patch.

[Radar WebKit Bug Importer]

<rdar://problem/24038047>

[Blaze Burg]

(In reply to comment #33)
> It's possible to implement an ordered Set/Map that is 12 times
> faster to iterate than a native Set/Map by using a linked list.
> 
> http://jsperf.com/linked-list-vs-arraw-iteration-speed/3
> 
> In fact, that's what we used for event listeners at my previous job:
> http://www.collectionsjs.com/set
> 
> This Ordered Set is backed by a doubly linked list and a set.
> Linked list tracks insertion order. Set ensures uniqueness
> and O(1) add/has/remove.
> 
> I'm working on a patch.

I think it would be better to file a bug against JSC and see if there is something dumb happening here (like an unintentional deoptimization). We can guard this check inside a console.assert() for now, fix the doubly-added listeners, and then delete the check until JSC performance is better.

[Nikita Vasilyev]

Created attachment 268685 [details]
WIP

This is a work in progress patch. It has an extra logging statements for debugging and performance measurements.

This patch changes:
addEventListener from O(n) to O(1)
removeEventListener(eventType, listener, thisObject) from O(n) to O(1)
removeEventListener(null, null, thisObject) from O(n^2) to O(n)

addEventListener and removeEventListener now take < 1ms regardless of the number listeners attached.

This patch uses OrderedSet I wrote: https://github.com/NV/ordered-set
Tests: http://nv.github.io/ordered-set/spec/
Benchmarks: http://nv.github.io/ordered-set/benchmark/ (rdar://problem/24122210) and http://jsperf.com/ordered2dset-add-vs-array/2

[Joseph Pecoraro]

Comment on attachment 268685 [details]
WIP

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

> Source/WebInspectorUI/UserInterface/Base/LinkedList.js:69
> +    "delete"(node)

You should be able to use the keyword here. Looks like this is bug:
<https://webkit.org/b/144281> super() should be a valid method name

I'll provide a fix for that today.

[Timothy Hatcher]

Comment on attachment 268685 [details]
WIP

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

> Source/WebInspectorUI/UserInterface/Base/LinkedList.js:105
> +    toJSON()
> +    {
> +        return this.toArray();
> +    }

Not used.

> Source/WebInspectorUI/UserInterface/Base/LinkedList.js:162
> +        else {

No need for the else after a return.

> Source/WebInspectorUI/UserInterface/Base/Object.js:117
> +            this._listeners.forEach(function(listeners2DSet) {

for(..of..) since you have iterator support?

> Source/WebInspectorUI/UserInterface/Base/Object.js:149
> +            this._listeners.forEach(function(listener2DSet, eventType) {

for(..of..)?

> Source/WebInspectorUI/UserInterface/Base/Object.js:151
> +                let pairs = listener2DSet.toArray();
> +                pairs.forEach(function(pair) {

Why convert to an array? Can't you iterate the set?

> Source/WebInspectorUI/UserInterface/Base/Object.js:186
> +            let listeners = listeners2DSet.toArray().slice(0);

Seems like this could be solved via a helper and use an iterator.

> Source/WebInspectorUI/UserInterface/Base/Ordered2DSet.js:32
> +        // itemA -> mapB

Not a helpful comment as-is.

> Source/WebInspectorUI/UserInterface/Base/Ordered2DSet.js:115
> +    toJSON()
> +    {
> +        return this.toArray();
> +    }

Not used.

[Timothy Hatcher]

Comment on attachment 268685 [details]
WIP

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

> Source/WebInspectorUI/UserInterface/Base/LinkedList.js:90
> +    toArray()

I think this would be better called entries(), like Map and Set have.

> Source/WebInspectorUI/UserInterface/Base/Ordered2DSet.js:107
> +    toArray()

I think this would be better called entries(), like Map and Set have.

[Nikita Vasilyev]

(In reply to comment #38)
> > Source/WebInspectorUI/UserInterface/Base/Object.js:117
> > +            this._listeners.forEach(function(listeners2DSet) {
> 
> for(..of..) since you have iterator support?
> 
> > Source/WebInspectorUI/UserInterface/Base/Object.js:149
> > +            this._listeners.forEach(function(listener2DSet, eventType) {
> 
> for(..of..)?
> 
> > Source/WebInspectorUI/UserInterface/Base/Object.js:151
> > +                let pairs = listener2DSet.toArray();
> > +                pairs.forEach(function(pair) {
> 
> Why convert to an array? Can't you iterate the set?

The iterator is significantly slower since
it has to create an object on every iteration.
https://github.com/NV/ordered-set/blob/gh-pages/LinkedList.js#L135

I may want to remove since it's currently unused.

> 
> > Source/WebInspectorUI/UserInterface/Base/Object.js:186
> > +            let listeners = listeners2DSet.toArray().slice(0);
> 
> Seems like this could be solved via a helper and use an iterator.
> 
> > Source/WebInspectorUI/UserInterface/Base/Ordered2DSet.js:32
> > +        // itemA -> mapB
> 
> Not a helpful comment as-is.

It takes an itemA as a key and returns a map, which in turn
has itemB as a key and a LinkedListNode as a value.

What comment would you suggest?

[Nikita Vasilyev]

(In reply to comment #38)
> > Source/WebInspectorUI/UserInterface/Base/Ordered2DSet.js:115
> > +    toJSON()
> > +    {
> > +        return this.toArray();
> > +    }
> 
> Not used.

This is used by the tests, which I'm yet to rebaseline.

obj.toJSON affects JSON.stringify(obj) behavior.
https://developer.mozilla.org/en/docs/Web/JavaScript/Reference/Global_Objects/JSON/stringify#toJSON()_behavior

[Timothy Hatcher]

Comment on attachment 268685 [details]
WIP

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

> Source/WebInspectorUI/UserInterface/Base/LinkedList.js:2
> + * Copyright (C) 2015 Apple Inc. All rights reserved.

Should be 2016 now. Same for other new files.

[Joseph Pecoraro]

Comment on attachment 268685 [details]
WIP

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

> Source/WebInspectorUI/UserInterface/Base/Object.js:54
> +        this._listeners = new Map();

I think we should try and lazily create this map when the first addEventListener is added. We have lots and lots of WebInspector.Object subclasses that have no events and so would never need this Map.

[Nikita Vasilyev]

(In reply to comment #39)
> Comment on attachment 268685 [details]
> WIP
> 
> View in context:
> https://bugs.webkit.org/attachment.cgi?id=268685&action=review
> 
> > Source/WebInspectorUI/UserInterface/Base/LinkedList.js:90
> > +    toArray()
> 
> I think this would be better called entries(), like Map and Set have.
> 
> > Source/WebInspectorUI/UserInterface/Base/Ordered2DSet.js:107
> > +    toArray()
> 
> I think this would be better called entries(), like Map and Set have.

Map/Set's entries methods return an iterator, not an Array.

> set = new Set
> set.add("a").add("b")
> set.entries()
< Set Iterator [["a", "a"], ["b", "b"]]

I think it's better to keep it as "toArray".

[Nikita Vasilyev]

Created attachment 268946 [details]
Patch

[Nikita Vasilyev]

Comment on attachment 268946 [details]
Patch

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

> Source/WebInspectorUI/UserInterface/Base/Object.js:147
> +                console.assert(false, "object._listeners should be a Map but it isn't.\n`object` is most likely a WebInspector.EventListenerSet.");

I hit a case once when "object" was WebInspector.EventListenerSet and so "object._listeners" was an array.
Before this patch it would fail silently, e.g. object._listeners[eventType] would be undefined.
I haven't been able to reproduce it since but I'm sure the bug still there.

[Blaze Burg]

Comment on attachment 268946 [details]
Patch

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

> Source/WebInspectorUI/ChangeLog:19
> +        [1]: https://webkit.org/b/152418#c1

Not necessary. The full discussion can viewed by looking at the bug for this change, and things linked to it.

> Source/WebInspectorUI/ChangeLog:21
> +        Reviewed by NOBODY (OOPS!).

The Reviewed by line needs to be after <rdar:// and before the description of the patch.

> Source/WebInspectorUI/ChangeLog:23
> +        * UserInterface/Base/LinkedList.js: Added.

There are no per-function comments, which makes it difficult to understand at a high level what this patch does to change the complexity.

> Source/WebInspectorUI/UserInterface/Base/LinkedList.js:26
> +class LinkedList

This class needs some basic unit tests. You can use SyncTestSuite for this, since there's nothing asynchronous.

> Source/WebInspectorUI/UserInterface/Base/LinkedList.js:49
> +        this.last.addAfter(newNode);

This reads very poorly, like you are adding last after newNode, rather than the converse.

> Source/WebInspectorUI/UserInterface/Base/LinkedList.js:68
> +        for (var i = 0, length = this.length; i < length; i++) {

Here and elsewhere, you need to use 'let' unless it's causing a performance issue (which seems very unlikely).

> Source/WebInspectorUI/UserInterface/Base/LinkedList.js:90
> +class LinkedListNode

I don't see any reason to make the node partly responsible for maintaining prev and next pointers. LLNode.delete() and LLNode.addAfter() are only ever called from within the LinkedList class. Just inline these.

> Source/WebInspectorUI/UserInterface/Base/LinkedList.js:99
> +    delete()

Please rename this to 'remove'

> Source/WebInspectorUI/UserInterface/Base/LinkedList.js:105
> +    addAfter(node)

Please rename this to 'insertAfter'.

> Source/WebInspectorUI/UserInterface/Base/Object.js:30
> +        Object.defineProperty(this, "_listeners", {value: null, enumerable: false, configurable: false, writable: true});

You didn't explain anywhere in the Changelog why this is necessary instead of a symbol property or normal property. Do we actually enumerate properties of WebInspector.Object instances anywhere? That seems like a dumb thing to do.

> Source/WebInspectorUI/UserInterface/Base/Object.js:143
> +            if (!object || !object._listeners || event._stoppedPropagation)

Why is it ok to remove the hasOwnProperty check?

>> Source/WebInspectorUI/UserInterface/Base/Object.js:147
>> +                console.assert(false, "object._listeners should be a Map but it isn't.\n`object` is most likely a WebInspector.EventListenerSet.");
> 
> I hit a case once when "object" was WebInspector.EventListenerSet and so "object._listeners" was an array.
> Before this patch it would fail silently, e.g. object._listeners[eventType] would be undefined.
> I haven't been able to reproduce it since but I'm sure the bug still there.

This should be console.error.

> Source/WebInspectorUI/UserInterface/Base/Object.js:151
> +            let listeners2DSet = object._listeners.get(eventType);

Please use a variable not tied to the implementation, such as listenersTable or listenersForEvent.

> Source/WebInspectorUI/UserInterface/Base/Object.js:156
> +            let listeners = listeners2DSet.toArray().slice(0);

This slice call is now unnecessary since toArray() returns a copy. Keep the comment, though.

(I'm a little curious why allocating and building this array is cheaper than allocating an iterator in the implementation of native Map/Set.)

> Source/WebInspectorUI/UserInterface/Base/Ordered2DSet.js:26
> +class Ordered2DSet

This name is terribly confusing, and doesn't correspond to any standard data structure name. Further, I don't understand why we need to hard-code the value type in this key-value mapping to be a set. If it's purely to avoid the cost of allocating an iterator when iterating Map and Set instances, then you should definitely say that in the changelog and in a comment above the class.

This is closest to a ListMultimap, whose interface allows multiple values per key and duplicate values. I would use that name and link to another implementation. For example, the Guava class here: http://docs.guava-libraries.googlecode.com/git/javadoc/com/google/common/collect/SetMultimap.html

This needs unit tests, like LinkedList. Even more important here since there are more guarantees, such as iterating in insertion order.

> Source/WebInspectorUI/UserInterface/Base/Ordered2DSet.js:30
> +        this._list = new LinkedList;

rename: this._insertionOrderedEntries

> Source/WebInspectorUI/UserInterface/Base/Ordered2DSet.js:31
> +        this._map = new Map;

rename: this._entries or this._keyMap

> Source/WebInspectorUI/UserInterface/Base/Ordered2DSet.js:56
> +    delete(a, b)

a and b are not acceptable names. Use key, value.

> Source/WebInspectorUI/UserInterface/Base/Ordered2DSet.js:71
> +    deleteColumn(a)

I would rename this to deleteAll(key)

> Source/WebInspectorUI/UserInterface/Base/Ordered2DSet.js:82
> +        this._map.delete(a);

This function has inconsistent return type.

[Nikita Vasilyev]

Comment on attachment 268946 [details]
Patch

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

>> Source/WebInspectorUI/UserInterface/Base/LinkedList.js:49
>> +        this.last.addAfter(newNode);
> 
> This reads very poorly, like you are adding last after newNode, rather than the converse.

Agreed.

>> Source/WebInspectorUI/UserInterface/Base/LinkedList.js:99
>> +    delete()
> 
> Please rename this to 'remove'

Map and Set have delete so I though it would be more consistent this way. I have no strong opinion on this though.

>> Source/WebInspectorUI/UserInterface/Base/LinkedList.js:105
>> +    addAfter(node)
> 
> Please rename this to 'insertAfter'.

How about "append"? It seems more concise to me.

>> Source/WebInspectorUI/UserInterface/Base/Object.js:30
>> +        Object.defineProperty(this, "_listeners", {value: null, enumerable: false, configurable: false, writable: true});
> 
> You didn't explain anywhere in the Changelog why this is necessary instead of a symbol property or normal property. Do we actually enumerate properties of WebInspector.Object instances anywhere? That seems like a dumb thing to do.

Yes, in a few tests. I can rebaseline the tests if you want.

>> Source/WebInspectorUI/UserInterface/Base/Object.js:143
>> +            if (!object || !object._listeners || event._stoppedPropagation)
> 
> Why is it ok to remove the hasOwnProperty check?

Because now it's always defined in the constructor.

>> Source/WebInspectorUI/UserInterface/Base/Object.js:156
>> +            let listeners = listeners2DSet.toArray().slice(0);
> 
> This slice call is now unnecessary since toArray() returns a copy. Keep the comment, though.
> 
> (I'm a little curious why allocating and building this array is cheaper than allocating an iterator in the implementation of native Map/Set.)

Good catch.

>> Source/WebInspectorUI/UserInterface/Base/Ordered2DSet.js:26
>> +class Ordered2DSet
> 
> This name is terribly confusing, and doesn't correspond to any standard data structure name. Further, I don't understand why we need to hard-code the value type in this key-value mapping to be a set. If it's purely to avoid the cost of allocating an iterator when iterating Map and Set instances, then you should definitely say that in the changelog and in a comment above the class.
> 
> This is closest to a ListMultimap, whose interface allows multiple values per key and duplicate values. I would use that name and link to another implementation. For example, the Guava class here: http://docs.guava-libraries.googlecode.com/git/javadoc/com/google/common/collect/SetMultimap.html
> 
> This needs unit tests, like LinkedList. Even more important here since there are more guarantees, such as iterating in insertion order.

I don't like the name too much either. This is how I ended up with it:
At one stage of rewriting this I had a three-dimensional set, Ordered3DSet. I didn't want to call it multi as I wanted to stress the number of dimensions. Add/has/delete methods of that class would accept 3 arguments, which meant I couldn't use the usual "key" and "value" names—what would I call the third argument? Later, I realized I only need 2 dimensions and converted it to Ordered2DSet.

I'm not sure what you mean by "Further, I don't understand why we need to hard-code the value type in this key-value mapping to be a set."

Yes, iterating Map or Set is slow. Furthermore, Ordered2DSet is optimized for fast iteration speed as it iterates over a single list of pairs. I could have implemented Ordered2DSet using a Map of Sets, but to iterate over it, I'd have to go through the Map and through *every* Set. That would be significantly slower.

I have tests on http://nv.github.io/ordered-set/spec/, I can port them to WebKit tests.

[Nikita Vasilyev]

Comment on attachment 268946 [details]
Patch

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

>>> Source/WebInspectorUI/UserInterface/Base/Ordered2DSet.js:26
>>> +class Ordered2DSet
>> 
>> This name is terribly confusing, and doesn't correspond to any standard data structure name. Further, I don't understand why we need to hard-code the value type in this key-value mapping to be a set. If it's purely to avoid the cost of allocating an iterator when iterating Map and Set instances, then you should definitely say that in the changelog and in a comment above the class.
>> 
>> This is closest to a ListMultimap, whose interface allows multiple values per key and duplicate values. I would use that name and link to another implementation. For example, the Guava class here: http://docs.guava-libraries.googlecode.com/git/javadoc/com/google/common/collect/SetMultimap.html
>> 
>> This needs unit tests, like LinkedList. Even more important here since there are more guarantees, such as iterating in insertion order.
> 
> I don't like the name too much either. This is how I ended up with it:
> At one stage of rewriting this I had a three-dimensional set, Ordered3DSet. I didn't want to call it multi as I wanted to stress the number of dimensions. Add/has/delete methods of that class would accept 3 arguments, which meant I couldn't use the usual "key" and "value" names—what would I call the third argument? Later, I realized I only need 2 dimensions and converted it to Ordered2DSet.
> 
> I'm not sure what you mean by "Further, I don't understand why we need to hard-code the value type in this key-value mapping to be a set."
> 
> Yes, iterating Map or Set is slow. Furthermore, Ordered2DSet is optimized for fast iteration speed as it iterates over a single list of pairs. I could have implemented Ordered2DSet using a Map of Sets, but to iterate over it, I'd have to go through the Map and through *every* Set. That would be significantly slower.
> 
> I have tests on http://nv.github.io/ordered-set/spec/, I can port them to WebKit tests.

Calling it ListMultimap is fine with me. You linked to SetMultimap, though http://docs.guava-libraries.googlecode.com/git/javadoc/com/google/common/collect/SetMultimap.html.

[Nikita Vasilyev]

Comment on attachment 268946 [details]
Patch

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

>>> Source/WebInspectorUI/UserInterface/Base/LinkedList.js:105
>>> +    addAfter(node)
>> 
>> Please rename this to 'insertAfter'.
> 
> How about "append"? It seems more concise to me.

Above you said I should inline it. Even though it's used only in one place, I find it to be more readable as a separate method.

[Blaze Burg]

(In reply to comment #50)
> Comment on attachment 268946 [details]
> Patch
> 
> View in context:
> https://bugs.webkit.org/attachment.cgi?id=268946&action=review
> 
> >>> Source/WebInspectorUI/UserInterface/Base/LinkedList.js:105
> >>> +    addAfter(node)
> >> 
> >> Please rename this to 'insertAfter'.
> > 
> > How about "append"? It seems more concise to me.
> 
> Above you said I should inline it. Even though it's used only in one place,
> I find it to be more readable as a separate method.

Given the current use case, I think that all pointer-manipulating code should in the same class. There is no reason for the node to know about just a few operations.

[Nikita Vasilyev]

Created attachment 269206 [details]
Patch

[Nikita Vasilyev]

Created attachment 269207 [details]
Patch

[WebKit Commit Bot]

Comment on attachment 269207 [details]
Patch

Clearing flags on attachment: 269207

Committed r195305: <http://trac.webkit.org/changeset/195305>

[WebKit Commit Bot]

All reviewed patches have been landed.  Closing bug.

[Joseph Pecoraro]

Comment on attachment 269207 [details]
Patch

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

> LayoutTests/ChangeLog:12
> +        * inspector/model/remote-object-expected.txt:
> +        Rebaseline tests, add "_listeners: null" to all WebInspector.Object instances.

Why don't we only add it when there are listeners. Again, we have lots of Web Inspector objects that can't even dispatch events.

[Ryan Haddad]

inspector/model/remote-object.html is failing on Mac. Guess we missed a rebaseline of the platform specific expectation?

[Nikita Vasilyev]

Tim and I figured out that running:

$ run-webkit-tests LayoutTests/inspector/model/remote-object.html --new-baseline

creates platform/mac-wk2/inspector/model/remote-object-expected.txt.

However, this file isn't stored in the repository.
Any ideas on what should I do to rebaseline test expectations on Mac?

[Nikita Vasilyev]

(In reply to comment #58)
> Tim and I figured out that running:
> 
> $ run-webkit-tests LayoutTests/inspector/model/remote-object.html
> --new-baseline
> 
> creates platform/mac-wk2/inspector/model/remote-object-expected.txt.
> 
> However, this file isn't stored in the repository.
> Any ideas on what should I do to rebaseline test expectations on Mac?

LayoutTests/inspector/model/remote-object.html *is* in the repo
and it needs to be updated.

[Joseph Pecoraro]

(In reply to comment #46)
> Comment on attachment 268946 [details]
> Patch
> 
> View in context:
> https://bugs.webkit.org/attachment.cgi?id=268946&action=review
> 
> > Source/WebInspectorUI/UserInterface/Base/Object.js:147
> > +                console.assert(false, "object._listeners should be a Map but it isn't.\n`object` is most likely a WebInspector.EventListenerSet.");
> 
> I hit a case once when "object" was WebInspector.EventListenerSet and so
> "object._listeners" was an array.
> Before this patch it would fail silently, e.g. object._listeners[eventType]
> would be undefined.
> I haven't been able to reproduce it since but I'm sure the bug still there.

It would be very easy to find this. Just search for any assignment to "this._listeners =". BreakpointTreeElement is one example.

[Timothy Hatcher]

Comment on attachment 269207 [details]
Patch

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

> Source/WebInspectorUI/UserInterface/Base/Object.js:-137
> -            if (!object || !object.hasOwnProperty("_listeners") || event._stoppedPropagation)

We need to add the hasOwnProperty check back. I forgot to check for this in my earlier review. This was added by Matt recently to fix the case where event dispatch to constructors would dispatch the event multiple times as it walked the prototype chain.

[Nikita Vasilyev]

(In reply to comment #57)
> inspector/model/remote-object.html is failing on Mac. Guess we missed a
> rebaseline of the platform specific expectation?

Should be fixed in 
https://bugs.webkit.org/show_bug.cgi?id=153261


(In reply to comment #61)
> Comment on attachment 269207 [details]
> Patch
> 
> View in context:
> https://bugs.webkit.org/attachment.cgi?id=269207&action=review
> 
> > Source/WebInspectorUI/UserInterface/Base/Object.js:-137
> > -            if (!object || !object.hasOwnProperty("_listeners") || event._stoppedPropagation)
> 
> We need to add the hasOwnProperty check back. I forgot to check for this in
> my earlier review. This was added by Matt recently to fix the case where
> event dispatch to constructors would dispatch the event multiple times as it
> walked the prototype chain.

https://bugs.webkit.org/show_bug.cgi?id=153269

[Nikita Vasilyev]

Comment on attachment 269207 [details]
Patch

This was fixed elsewhere.