RESOLVED FIXED 152422
Web Inspector: WebInspector.Object.addEventListener is O(n), make it O(1)
https://bugs.webkit.org/show_bug.cgi?id=152422
Summary Web Inspector: WebInspector.Object.addEventListener is O(n), make it O(1)
Nikita Vasilyev
Reported 2015-12-18 01:13:59 PST
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.
Attachments
WIP (2.58 KB, patch)
2015-12-18 02:17 PST, Nikita Vasilyev
joepeck: review-
nvasilyev: commit-queue-
Archive of layout-test-results from ews116 for mac-yosemite (775.63 KB, application/zip)
2015-12-18 03:10 PST, Build Bot
no flags
WIP (15.10 KB, patch)
2016-01-11 04:52 PST, Nikita Vasilyev
nvasilyev: review-
nvasilyev: commit-queue-
Patch (16.06 KB, patch)
2016-01-14 00:14 PST, Nikita Vasilyev
bburg: review-
bburg: commit-queue-
Patch (142.54 KB, patch)
2016-01-17 16:38 PST, Nikita Vasilyev
no flags
Patch (142.50 KB, patch)
2016-01-17 16:49 PST, Nikita Vasilyev
nvasilyev: review-
nvasilyev: commit-queue-
Nikita Vasilyev
Comment 1 2015-12-18 01:23:23 PST
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
Comment 2 2015-12-18 01:33:33 PST
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
Comment 3 2015-12-18 02:17:48 PST
Nikita Vasilyev
Comment 4 2015-12-18 02:28:05 PST
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
Comment 5 2015-12-18 02:44:56 PST
(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 6 2015-12-18 03:10:28 PST
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
Comment 7 2015-12-18 03:10:30 PST
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 8 2015-12-18 03:34:28 PST
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 9 2015-12-18 07:48:11 PST
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
Comment 10 2015-12-18 08:32:37 PST
(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 11 2015-12-18 11:10:22 PST
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
Comment 12 2015-12-18 11:16:34 PST
(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
Comment 13 2015-12-18 11:28:00 PST
> 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
Comment 14 2015-12-18 18:01:49 PST
(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
Comment 15 2015-12-18 18:16:03 PST
(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
Comment 16 2015-12-18 18:41:05 PST
(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
Comment 17 2015-12-18 20:11:07 PST
> 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
Comment 18 2015-12-18 20:16:08 PST
> [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
Comment 19 2015-12-19 11:19:04 PST
(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
Comment 20 2015-12-19 11:24:35 PST
(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
Comment 21 2015-12-19 11:27:01 PST
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
Comment 22 2015-12-19 11:29:33 PST
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
Comment 23 2015-12-19 11:31:23 PST
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
Comment 24 2015-12-19 14:49:33 PST
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
Comment 25 2015-12-19 14:54:19 PST
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
Comment 26 2015-12-19 19:56:46 PST
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
Comment 27 2015-12-19 20:45:29 PST
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
Comment 28 2015-12-19 21:00:34 PST
(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
Comment 29 2015-12-21 06:11:25 PST
(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
Comment 30 2015-12-21 06:16:20 PST
(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
Comment 31 2015-12-21 16:53:11 PST
(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
Comment 32 2015-12-21 16:54:30 PST
And yes, add/has/remove operations of Set/Map are a win.
Nikita Vasilyev
Comment 33 2016-01-04 02:08:49 PST
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
Comment 34 2016-01-04 02:09:06 PST
Blaze Burg
Comment 35 2016-01-04 08:29:19 PST
(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
Comment 36 2016-01-11 04:52:20 PST
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 37 2016-01-11 11:39:10 PST
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 38 2016-01-12 12:44:51 PST
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 39 2016-01-12 12:49:11 PST
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
Comment 40 2016-01-12 14:10:31 PST
(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
Comment 41 2016-01-12 15:10:27 PST
(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 42 2016-01-12 15:50:15 PST
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 43 2016-01-12 15:56:25 PST
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
Comment 44 2016-01-13 21:45:30 PST
(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
Comment 45 2016-01-14 00:14:17 PST
Nikita Vasilyev
Comment 46 2016-01-14 00:20:17 PST
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 47 2016-01-14 10:12:15 PST
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 48 2016-01-14 17:10:55 PST
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 49 2016-01-14 21:14:01 PST
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 50 2016-01-14 21:43:18 PST
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
Comment 51 2016-01-14 22:36:30 PST
(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
Comment 52 2016-01-17 16:38:35 PST
Nikita Vasilyev
Comment 53 2016-01-17 16:49:30 PST
WebKit Commit Bot
Comment 54 2016-01-19 12:21:05 PST
Comment on attachment 269207 [details] Patch Clearing flags on attachment: 269207 Committed r195305: <http://trac.webkit.org/changeset/195305>
WebKit Commit Bot
Comment 55 2016-01-19 12:21:12 PST
All reviewed patches have been landed. Closing bug.
Joseph Pecoraro
Comment 56 2016-01-19 12:26:17 PST
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
Comment 57 2016-01-19 15:06:52 PST
inspector/model/remote-object.html is failing on Mac. Guess we missed a rebaseline of the platform specific expectation?
Nikita Vasilyev
Comment 58 2016-01-19 16:15:53 PST
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
Comment 59 2016-01-19 16:28:30 PST
(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
Comment 60 2016-01-19 20:46:45 PST
(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 61 2016-01-19 21:24:43 PST
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
Comment 62 2016-01-19 21:53:51 PST
(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 63 2016-08-02 16:47:07 PDT
Comment on attachment 269207 [details] Patch This was fixed elsewhere.
Note You need to log in before you can comment on or make changes to this bug.