112525 - O(n^2) when dispatching events in nsView :: HandleEvent

Status: RESOLVED FIXED

(Core Graveyard :: GFX, defect)

Description

[Kevin McCluskey (gone)]

The nsView::HandleEvent logic is Order(n^2) because it calls nsView::GetChild
which searches a linked list of view's as it is traversing views during event
dispatch.

Getting rid of the call to GetChild produces a substantial speed improvement on
the 300 combo box example in bug 39544

Un-modified (seconds)
---------------------
47.989
50.753
53.176

Avoiding O(n^2) call to GetChild
---------------------------------
17.736
18.327
19.718

Comment 1

[Kevin McCluskey (gone)]

Attachment: Patch which removes the O(n^2) call to GetChild in nsView::HandleEvent

Comment 2

[Kevin McCluskey (gone)]

This bug was split off from bug 62568

Comment 3

[Robert O'Callahan (:roc) (email my personal email if necessary)]

This is the right idea, but all this code is going to have to go away when I fix
event handling for z-index and all that. (HandleEvent is going to call
CreateDisplayList and then traverse the display list, which will require a
different way of handling the "views deleted while handling event" problem. It
will fix the O(n^2) behaviour too.)

So I'd be happy to approve this but I will be taking it out again in a week or
two :-).

Comment 4

[Robert O'Callahan (:roc) (email my personal email if necessary)]

r=roc+moz

Comment 5

[kinmoz]

Comment on attachment 59635 [details] [diff] [review]
Patch which removes the O(n^2) call to GetChild in nsView::HandleEvent

sr=[e-mail]

Comment 6

[Kevin McCluskey (gone)]

Fix checked in

Comment 7

[Kevin McCluskey (gone)]

I filed bug 112861 for the extra events that are generated during the creation
of child windows. These events were the primary cause of the page load slowdown
on pages with large numbers of comboboxes because they were causing the O(n^2)
code in the viewmanager to be executed. 

Now that the fix in this bug has been checked in these events have less of an
impact, but should still be suppressed to further improve performance on pages
with lots of views.