62568 - [MF]Use lazy instantiation of combobox dropdowns to improve performance

Status: RESOLVED WONTFIX

(Core :: Layout: Form Controls, defect, P1)

Description

[Kevin McCluskey (gone)]

From Rod Spears:

Did some counting of Reflow with a Combobox and its Dropdown being reflowed and
then with a hack of lazy instantiation. Below is a table of the reflows:

                  Lazy  Current  Diff  %Change
--------------------------------------------------
www.netscape.com  3529   3651     122   0.03
www.weather.com   2136   2283     147   0.06
www.cnn.com       5863   6305     442   0.07
www.cnnsi.com     2778   3512     734   0.21
www.cbsnews.com   4267   5610    1343   0.24
stock portfolio   1934   2487     553   0.22

I also did an experiement with loading pages with a lot of comboboxes The memory
usage is for the document. The CPU Time is from the MOZ_PERF directive.

Lazy
Num Combos   Mem Use     CPU Time
-----------------------------------
   10         5884        1.1
  100         8956        2.1
  200         8954        3.1
  300         8956        4.0
  400         8954        5.2
  500         9980        6.4

Current
Num Combos   Mem Use     CPU Time
-----------------------------------
   10         5884        1.4
  100         9044        4.5
  200        11112       10.65
  300        14208       20.58
  400        15256       36.25
  500        19376       60.00

Summary
Lazy creation of dropdowns will improve performance. It will decrease the number
of reflows on a page somewhere between 3%-25%. The reflows that are reduced the
most are Text Frame, InLine Block Frame, Block Frame. This makes sense because
the dropdown isn't being reflowed anymore. The reflows were mostly initial and
resize reflows.

The test that had roughly a 22% drop in reflows; the TableFrames, Table Row
Frame, and Table Cell Frame saw a 65% reduction in incremental reflows, but only
one less resize reflow.

Lazy creation of the dropdown increase CPU usage linearly, and barely effects
memory. The current method seems to increase the CPU usage grows much more
dramatically and also greatly effects memory. The test had 10 selects with 3
options in each select.

The difference in reflows are when there are a 10 comboboxes as follows:

When doing Lazy:
10 less ScrollFrame Intial Reflows
10 less ScrollFrame Resize Reflows
10 less ListControlFrame Initial Reflows
30 less TextFrame Initial Reflows
40 less BlockFrame Intial Reflows
40 less BlockFrame Resize Reflows

There is nothing in the reflow counts that would indicate that the CPU should
grow so dramatically and in a non-linear fashion. The CPU time doubled for evey
100 selects I added.


Conclusion
Lazy creation of dropdowns will improve performance and reduce the memory
footprint. But amount of the reductions depend solely on the number of selects
on a page. Most pages in the top 100 have 1-3 selects, so the savings will not
be huge. It will greatly improve pathelogical cases. It will also speed up
JavaScript adding and removing options from a combobox that has not yet been
dropped down, because it won't do any frame work.

What is interesting is a page with 10 selects renders approx. 20% faster in CPU
time with Lazy creation than the current way.

Comment 1

[Kevin McCluskey (gone)]

Setting milestone to mozilla0.9

Comment 2

[rods (gone)]

downgrading from Mozilla 0.9 to future. This may not be needed because we pciked 
up some speed with the fix for bug 69869.

Comment 3

[James Green]

I'm guessing here that we need to re-perform the tests that Rod did? We need to
know whether this bug is still significant or not. Also, should it be OS/All?

Comment 4

[selmer (gone)]

If this gets retested, it would be interesting to see the effect this has on
javascript manipulation of comboboxes.  Just looking at bugzilla pages, it's
pretty dramatically bad today (4.x is orders of magnitude faster than 6.x.)

Rod, any chance you could compare your build against the trunk on the bugzilla
query page by just changing the product and seeing how fast the comboboxes next
to it complete their reflows?

If there's a dramatic win for javascript, this would be worth bringing back.

Comment 5

[rods (gone)]

I have been experimenting with timers for when items are added and removed from 
from selects (See Bug 71682) and it makes a huge difference. The test you 
desribe still isn't super fast, but it is much improved and the listboxes don't 
jump all around.

Comment 6

[Simon Fraser [no longer active]]

Note recent comments on bug 40988. A particularly bad example of this is at this 
URL:
http://www.mozilla.org/quality/help/bugzilla-helper.html
when you change the Product and Component entries. It locked up my G3 Mac for 
several seconds, which I think is unacceptable.

Comment 7

[Simon Fraser [no longer active]]

Attachment: Stack sampled while my machine was locked up.

Comment 8

[rods (gone)]

We need to do two things:

1) Have the HTML in the page changed
2) Fix the bug (see below)

Here are the issues:
1) The nsHTMLOptionElement::SetText call GetPrimaryFrame which flushes the 
reflows, plus it calls for each option that has it's text set instead of just 
the currently selected option, so there is an optimization there for selects.

2) The nsHTMLSelectElement::HandleDOMEvent (line 1389) has a call to 
GetPrimaryFrame which flushes all the pending reflows

3) The setting of the "value" in script calls nsHTMLInputElement::SetValue which  
calls GetPrimaryFrame which flushes all the pending reflows

4) When the text is set on the content/DOM Node for the option this ends up 
appending a reflow command. So each option that has it's text changed ends up 
appending a reflow command and then at the end all these reflow commands get 
processed. I could see any easy way of preventing this from happening.


So there are a lot of problems with this type of coding. I will attach an 
example and then try to get the helper page fixed.

Comment 9

[rods (gone)]

Attachment: simplier testcase

Comment 10

[Randell Jesup [:jesup] (needinfo me)]

Due to the truely horrendous performance we have with large numbers of
comboboxes (see bug 39573), I'd like to remove this from Future and target for
mozilla 1.0.

This is an O(n^2) issue currently; with lazy instantiation it should be close to
O(n), as the timings show.

Comment 11

[rods (gone)]

I guess I would argue that the first 5 or so combos on a page NOT get lazy 
instantiated. That way for the typical case the dropdowns are already created 
and they pop down very fast. It's only when there is a large number of combos 
that we kick into the lazy inst. and reap the increased performance benefits.

Although I don't have it working, my guess is that there will be a noticable lag 
the first time somebody clicks on a combo and it gets created before popping 
down. (If not, then they all can be LI'ed)

Comment 12

[Randell Jesup [:jesup] (needinfo me)]

That makes sense.  The O(n^2) doesn't hurt us much until we get over 5 or 10 of
them.

Comment 13

[Cathleen]

base on bug 39573 and bug 86952, lets try for 0.9.5, and see how much we can get
done.

Comment 14

[Randell Jesup [:jesup] (needinfo me)]

We probably need to move this back to 0.9.6 since we have no patch yet; can we
get any traction on solving this for that timeframe?  This is P1/major.

Comment 15

[Randell Jesup [:jesup] (needinfo me)]

Note that this P1/Major perf bug got moved from 0.9.6 to future with no comment.

This is an O(n^2) problem with comboboxes, and there are real-world pages that
hit it badly (such as the original case for bug 39573, a firewall rule edit page).

Rod, if there's absolutely no way for you to get this in the 1.0 timeframe,
please at least provide some guidance here for someone else to take a shot at
it.  Do you have any patches that need updating/polishing for this and/or the
voidarray view-list patch for bug 39573?  Bitrotted would be better than nothing.

Adding helpwanted.

Cathleen: this should be put back onto the perf radar.  The proper solution is
known, and for the testcase cuts time by 70+%.

Comment 16

[Kevin McCluskey (gone)]

The reason this bug was marked future is because the plan is to completely
replace the current form element implementation with an XBL binding which would
include support for both XUL and native widgets. bug 58317

The optimization that is necessary for the current frame-based form elements
would not apply to the XBL-XUL implementation, so it would be wasted effort.

Comment 17

[John Keiser (jkeiser)]

At any rate, performance numbers need to be reworked now that bug 34297 has
landed.  Select instantiation changed drastically, more towards the immediate
than the lazy end.  Also the way selected indices are stored has changed a lot,
probably for the better in terms of memory and speed.

Comment 18

[Kevin McCluskey (gone)]

Note most of the O(n^2) fix for viewmanager2 patch in 49175 was incorporated in
nsViewManager so most of the benefit is already in the tree. (ViewManager2 is no
longer used)

One remaining place where it is still O(n^2) doesn't seem to be causing any
performance issues for the 4000 textbox case. 

I did the equivalent of the patch in 49175 using a release build on WINXP and
I saw minor performance improvement (34.93 seconds instead of 35.291 seconds). It
could not be checked in because it may break if a view is destroyed as result
of event processing.

Also note that storing the view's childlist as a voidarray is equivalent to the
work that was done in the patch in 49175. both of them get rid of the O(n^2)
traversal in nsView::GetChild.  The voidarray solution get's rid of it by
getting rid of the traversal using an array access. The patch in 49175 gets rid
of it by avoiding the call to nsView::GetChild and doing the interation over the
child views directly.

Comment 19

[Kevin McCluskey (gone)]

I do see 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 20

[Kevin McCluskey (gone)]

I broke out the O(n^2) issue in nsView into it's own bug 112525. I also attached
a patch to bug 112525 which fixes it.

Comment 21

[Kevin McCluskey (gone)]

Resolving as WONTFIX since the plan is to completely replace the current form 
element implementation with an XBL binding which would include support for 
both XUL and native widgets. bug 58317.

In addition, the major performance issues which made us consider using lazy 
instantiation seem to have solved by the fix for 112525 and bug 69869.

Comment 22

[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 slowdown on pages
with large numbers of comboboxes. (Now that the fix in bug 112525 has been
checked in these events have less of an effect, but should still be suppressed.)

Comment 23

[Simon Fraser [no longer active]]

Since the creation of child dropdowns involves significant amounts of native code 
(making native windows etc), the speed impact could be very different on 
different platforms. I think you need to run the performance measurements 
everywhere.