Web Inspector: WebInspector.Object.addEventListener is O(n), make it O(1)
authornvasilyev@apple.com <nvasilyev@apple.com@268f45cc-cd09-0410-ab3c-d52691b4dbfc>
Tue, 19 Jan 2016 20:20:53 +0000 (20:20 +0000)
committernvasilyev@apple.com <nvasilyev@apple.com@268f45cc-cd09-0410-ab3c-d52691b4dbfc>
Tue, 19 Jan 2016 20:20:53 +0000 (20:20 +0000)
commitffb545f973a4e9226bac36ebfafef7000b16c539
treecc28045b75c2a33f63e13f1a18218263e580211b
parent5d2658844748212b094c63e1d3554b0823b4d804
Web Inspector: WebInspector.Object.addEventListener is O(n), make it O(1)
https://bugs.webkit.org/show_bug.cgi?id=152422
<rdar://problem/24038047>

Reviewed by Timothy Hatcher.

Source/WebInspectorUI:

Slow addEventListener was the main cause of Console sluggishness[1].

This patch changes:
addEventListener from O(n) to O(1)
removeEventListener from O(n) to O(1)

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

removeEventListener(null, null, thisObject), a special case when all events
for thisObject are removed, was improved from O(n^2) to O(n).

* UserInterface/Base/LinkedList.js: Added.
(LinkedList):
(LinkedList.prototype.clear):
(LinkedList.prototype.get last):
(LinkedList.prototype.push):
(LinkedList.prototype.remove):
(LinkedList.prototype.forEach):
(LinkedList.prototype.toArray):
(LinkedList.prototype.toJSON):
(LinkedListNode):
LinkedList ensures O(1) time complexity for push and remove operations.

* UserInterface/Base/ListMultimap.js: Added.
(ListMultimap):
(ListMultimap.prototype.get size):
(ListMultimap.prototype.add):
(ListMultimap.prototype.delete):
(ListMultimap.prototype.deleteAll):
(ListMultimap.prototype.has):
(ListMultimap.prototype.clear):
(ListMultimap.prototype.forEach):
(ListMultimap.prototype.toArray):
(ListMultimap.prototype.toJSON):
ListMultimap unsures O(1) time complexity for add, has and delete operations.
ListMultimap preserves insertion order by using a LinkedList.

* UserInterface/Base/Object.js:
(WebInspector.Object):
(WebInspector.Object.addEventListener):
(WebInspector.Object.removeEventListener):
(WebInspector.Object.hasEventListeners):
(WebInspector.Object.retainedObjectsWithPrototype):
(WebInspector.Object.prototype.dispatchEventToListeners):
Replace this._listeners[eventType] from array of objects to ListMultimap.

* UserInterface/Main.html:
* UserInterface/Test.html:
* UserInterface/TestStub.html:

LayoutTests:

* inspector/console/console-api-expected.txt:
* inspector/console/console-table-expected.txt:
* inspector/model/remote-object-expected.txt:
Rebaseline tests, add "_listeners: null" to all WebInspector.Object instances.

* inspector/unit-tests/linked-list-expected.txt: Added.
* inspector/unit-tests/linked-list.html: Added.
* inspector/unit-tests/list-multimap-expected.txt: Added.
* inspector/unit-tests/list-multimap.html: Added.

git-svn-id: https://svn.webkit.org/repository/webkit/trunk@195305 268f45cc-cd09-0410-ab3c-d52691b4dbfc
15 files changed:
LayoutTests/ChangeLog
LayoutTests/inspector/console/console-api-expected.txt
LayoutTests/inspector/console/console-table-expected.txt
LayoutTests/inspector/model/remote-object-expected.txt
LayoutTests/inspector/unit-tests/linked-list-expected.txt [new file with mode: 0644]
LayoutTests/inspector/unit-tests/linked-list.html [new file with mode: 0644]
LayoutTests/inspector/unit-tests/list-multimap-expected.txt [new file with mode: 0644]
LayoutTests/inspector/unit-tests/list-multimap.html [new file with mode: 0644]
Source/WebInspectorUI/ChangeLog
Source/WebInspectorUI/UserInterface/Base/LinkedList.js [new file with mode: 0644]
Source/WebInspectorUI/UserInterface/Base/ListMultimap.js [new file with mode: 0644]
Source/WebInspectorUI/UserInterface/Base/Object.js
Source/WebInspectorUI/UserInterface/Main.html
Source/WebInspectorUI/UserInterface/Test.html
Source/WebInspectorUI/UserInterface/TestStub.html