97345 - Insertion of Options in Select elements very slow

Status: VERIFIED FIXED

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

Description

[Fabian Guisset]

From Bugzilla Helper:
User-Agent: Mozilla/5.0 (X11; U; Linux i686; en-US; rv:0.9.3+) Gecko/20010515
BuildID:    20010828

Insertion of new options in select elements is very slow, whatever way you use
to do it: nsIDOMHTMLSelectElement::Add() or through select.options[].
I will attach a testcase that demonstrates it.
Randell volunteered to jprof it. Please don't dup this bug, we will use it as a
tracking bug for this particular performance issue.

Reproducible: Always
Steps to Reproduce:
1.Open the testcase


Actual Results:  Takes too long

Expected Results:  Should take much less time.

Optimization of insertion would be very helpful for the bugzilla team. Let's get
some traction going.

Comment 1

[Fabian Guisset]

Attachment: Testcase for bug 97345

Comment 2

[Christian Reis]

Yes, Fabian speaks the truth :) We would like to see Select controls updating
much faster, because it significantly hampers performance on query.cgi, as per
bug 96534. If somebody needs proof of this, visit
http://bugzilla.redhat.com/query2.cgi?jscript=1 (might be query.cgi by then).

Adding David so he can watch this.

Comment 3

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

I'll have a jprof of this shortly

Comment 4

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

61% of the time is spent in nsHTMLOptionElement::QueryInterface which is called
from:

82% in GetOptionsRecurse() which is called from:

91% in nsHTMLOptionCollection::IndexOf() which is called from:

98% in nsGenericElement::doInsertBefore()

Comment 5

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

Attachment: jprof of ~5min of trying to add 10000 options using Add()

Comment 6

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

Attachment: Initial shot at a patch for this. Tested, but not extensively. Works quite well

Comment 7

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

All time remaining is in nsLineBox::IndexOf() and friends it appears.

Note: I haven't tested extensively and have to go home.  Have fun.

Taking bug.

Comment 8

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

Attachment: jprof with patch, 10000 options Add(), completed (unlike previous where I gave up)

Comment 9

[Fabian Guisset]

Wow, excellent work!!
Insertion of 5000 items using my testcase dropped from 45 seconds to 10 seconds
for both buttons when using the above patch on an athlon 1Ghz with 256MB RAM on
linux.
However I crash consinstently when reloading the page after hitting one of the
two buttons. This did not happen before applying the patch. Any idea Randell?

Comment 10

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

I think there still are a few issues with this patch.  As I said, I threw it
together right before going home.  In addition to the crash (which should be
easy to track down), I worry my patch doesn't work correctly when the list has
sub-items (i.e. the tree isn't flat).   I have a solution to that as well that
uses 4 bytes (roughly) per option.  Also, I can merge some of the added
functions I threw in.

The principle is correct, however, and the performance improvement should hold
up as I polish the patch.  The jprof above (post-patch)  took 51 sec to totally
complete 10000 elements; before the patch I waited 5 min and then gave up. 
Also, while it's locked adding elements, the UI is locked too.

This will not be 0.9.4, but should be no problem for 0.9.5

Comment 11

[Fabian Guisset]

I'll run some more with the patch to track any new crash. Thanks for taking the
time to look at this. btw, I hear rods is back. Adding him back to CC since this
is HTML Form Controls, maybe he has more ideas to speed it up.

Comment 12

[Fabian Guisset]

I finally got jprof working and I logged the addition of 15000 options with the
Add() button. I took ~30 seconds with the patch on the configuration mentioned
above. With the patch, 46% of the time is spent in
nsLineBox::FindLineContaining() which calls nsLineBox::IndexOf(), like Randell
mentioned. 20% of the time is spent in nsFrame::GetNextSibling(), which is
called by nsLineBox::IndexOf(). All those
are called at the begining by nsDocument::ContentInserted, called by
nsHTMLSelectElement::InsertChildAt(). Johnny suggested special-casing the case
when an option is appended instead of inserted, and to call
nsDocument::ContentAppended() instead of nsDocument::ContentInserted() in that
case. An option is appended when the second argument to Add() is null. I'm
afraid my coding skills are still a bit narrow to try this suggestion, but we
should investigate.

Comment 13

[rods (gone)]

My comments from Bug 62568:

------- Additional Comments From [e-mail] 2001-08-20 13:12 -------

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 14

[rods (gone)]

Ignore my lastest message above, that describes a different problem

Comment 15

[rods (gone)]

I want to say the patch looks execellent, but when I run the testcase and exit 
viewer (on WinNT) I get the following crash and below is the stack trace.

I have looked at the patch a couple of time and nothing at all jumps out at me. 
I went back to the current tip and it worked (slower) but did not crash. If you 
can find what is probably an extra release somewhere I will give it an r= for 
0.9.5

Thanks a lot for the help

nsGenericHTMLContainerElement::~nsGenericHTMLContainerElement() line 3546 + 11 
bytes
nsGenericHTMLContainerFormElement::~nsGenericHTMLContainerFormElement() line 
3866 + 8 bytes
nsHTMLSelectElement::~nsHTMLSelectElement() line 229 + 8 bytes
nsHTMLSelectElement::`scalar deleting destructor'(unsigned int 1) + 15 bytes
nsGenericElement::Release(nsGenericElement * const 0x02ec2fb0) line 2597 + 157 
bytes
nsHTMLSelectElement::Release(nsHTMLSelectElement * const 0x02ec2fb0) line 235 + 
12 bytes
nsGenericHTMLContainerElement::~nsGenericHTMLContainerElement() line 3547 + 12 
bytes
nsBodySuper::~nsBodySuper() line 153 + 8 bytes
nsHTMLBodyElement::~nsHTMLBodyElement() line 756 + 8 bytes
nsHTMLBodyElement::`scalar deleting destructor'(unsigned int 1) + 15 bytes
nsGenericElement::Release(nsGenericElement * const 0x0282e030) line 2597 + 157 
bytes
nsHTMLBodyElement::Release(nsHTMLBodyElement * const 0x0282e030) line 230 + 12 
bytes
nsGenericHTMLContainerElement::~nsGenericHTMLContainerElement() line 3547 + 12 
bytes
nsHTMLHtmlElement::~nsHTMLHtmlElement() line 93 + 8 bytes
nsHTMLHtmlElement::`scalar deleting destructor'(unsigned int 1) + 15 bytes
nsGenericElement::Release(nsGenericElement * const 0x02e98040) line 2597 + 157 
bytes
nsHTMLHtmlElement::Release(nsHTMLHtmlElement * const 0x02e98040) line 97 + 12 
bytes
nsSupportsArray::Clear(nsSupportsArray * const 0x02e9c740) line 585 + 54 bytes
nsDocument::~nsDocument() line 495
nsMarkupDocument::~nsMarkupDocument() line 39 + 8 bytes
nsHTMLDocument::~nsHTMLDocument() line 286 + 67 bytes
nsHTMLDocument::`scalar deleting destructor'() + 15 bytes
nsDocument::Release(nsDocument * const 0x02e9d4e0) line 556 + 158 bytes
nsHTMLDocument::Release(nsHTMLDocument * const 0x02e9d4e0) line 289 + 12 bytes
XPCJSRuntime::GCCallback(JSContext * 0x01493320, JSGCStatus JSGC_END) line 529 + 
18 bytes
DOMGCCallback(JSContext * 0x01493320, JSGCStatus JSGC_END) line 1496 + 23 bytes
js_GC(JSContext * 0x01493320, unsigned int 0) line 1306 + 12 bytes
js_ForceGC(JSContext * 0x01493320) line 945 + 11 bytes
JS_GC(JSContext * 0x01493320) line 1619 + 9 bytes
nsDOMSOFactory::Observe(nsDOMSOFactory * const 0x0147cfe4, nsISupports * 
0x00bb5f40, const unsigned short * 0x0012febc, const unsigned short * 
0x00000000) line 162 + 13 bytes
nsObserverService::Notify(nsObserverService * const 0x00caddf0, nsISupports * 
0x00bb5f40, const unsigned short * 0x0012febc, const unsigned short * 
0x00000000) line 238
NS_ShutdownXPCOM(nsIServiceManager * 0x00000000) line 465
main(int 1, char * * 0x00bb4640) line 160 + 8 bytes
mainCRTStartup() line 338 + 17 bytes

Comment 16

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

rods: do I need to worry about whether the index applies when I do the insert? 
I haven't looked that closely at the code, but it appears to recurse into
sub-entries, which implies the index in the parent used for inserting the
content node isn't the same as the index in the options array.  (I have a
solution to this that uses a second array, I think.)

As for the remaining cycles, that's a known issue with how content is added and
the linked list is walked, already being tracked/discussed in bug 93620.

I'll track down the crash shortly and post a new patch.

Comment 17

[Johnny Stenback (:jst)]

Fabian, from looking at the code we already do call AppendChild and not
InsertChild when an option is appended, but I did find something interesting
that could speed this up when browsing some code, does this help performance
here (totally untested)?

Index: content/base/src/nsGenericElement.cpp
===================================================================
RCS file: /cvsroot/mozilla/content/base/src/nsGenericElement.cpp,v
retrieving revision 3.177
diff -u -r3.177 nsGenericElement.cpp
--- nsGenericElement.cpp        2001/08/17 08:12:44     3.177
+++ nsGenericElement.cpp        2001/08/29 18:49:43
@@ -2298,7 +2298,11 @@
     nsContentUtils::ReparentContentWrapper(newContent, this, mDocument,
                                            old_doc);

-    res = InsertChildAt(newContent, refPos, PR_TRUE, PR_TRUE);
+    if (aRefChild) {
+      res = InsertChildAt(newContent, refPos, PR_TRUE, PR_TRUE);
+    } else {
+      res = AppendChildTo(newContent, PR_TRUE, PR_TRUE);
+    }

     if (NS_FAILED(res)) {
       return res;

Comment 18

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

Attachment: Updated patch - no crash, removed redundant code

Comment 19

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

jst: there will be little or no change from that.  All append really is
internally is InsertElementAt(element,Count()) (more or less).  So working to
use Append instead of InsertElementAt doesn't help you.  It would help you if it
were a linked list with an end-pointer, but it's not.

In fact, I just ripped out the Append stuff from my patch and use Insert's (to
save codespace and reduce duplication).

Comment 20

[Fabian Guisset]

jst: yes that's what I had figured after looking some more at the code. I tried
to bypass the call to nsGenericElement::DoInsertBefore by directly calling
nsHTMLSelectElement::InsertChildAt but it didn't do any good perf-wise. Thanks
for looking at it though :-)

Comment 21

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

After reviewing the code, I don't think there are any issues with sub-elements
of the nsHTMLSelectElement node messing up the index values; there should be a
straight correlation of index relative to the parent to index relative to the
option array (nsHTMLOptionCollection.mElements).

If I'm wrong on this, and there can be children of the nsHTMLSelectElement
_other_ than the options, tell me now and I can make it search the array for the
correct insertion point (by using a second array probably, or by passing the
"aBefore" entry and doing IndexOf - this would be better).  This _would_ be a
performance impact, though not as severe as we started with.

Comment 22

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

Attachment: Updated patch, final cleanup. Also updates nsISelectElement.h

Comment 23

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

Ok, I think we're ready for r=/sr= on this.  Takers?

Comment 24

[Fabian Guisset]

Last posted patch is still as speedy as the previous ones, and fixes the crash I
reported. 5000 insertions in 10 seconds and 15000 in 50 seconds.

Comment 25

[David Baron :dbaron: (⌚️UTC-4, no longer working on Mozilla)]

Does this handle OPTGROUP correctly?

Comment 26

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

dbaron: I don't know if it handles OPTGROUP; I've never heard of it. 
Reference?  I was worried that the content tree under an SelectElement might not
be flat, though there seem to be other assumptions that it is.  If someone can
say definitively that it is or is not flat I can recode (if not flat) to handle
this.

Comment 27

[Chris Waterson]

<optgroup> is described here:

  http://www.w3.org/TR/html401/interact/forms.html#h-17.6

Comment 28

[Johnny Stenback (:jst)]

rjesup: Even if the difference between Append and InsertBefore are next to
nothing today I'd say it's worth checking in my change since at some point
appending might be a *lot* faster than insrting, maybe not now, but some day...
Wanna include that change in your patch?

Comment 29

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

Hmmm.  Thanks; I was worried there was something like that given how
GetOptionsRecurse was coded.  I'll revise the patch to deal with this.  The two
main options are to flag whether the option list is flat or not and only use the
speedup for flat lists (i.e. 99.99%), and use an alternate method to find he
right insertion point.  Note that the two options are not exclusive, and for
speed I may do both.

jst: I suppose.  It doesn't cost us more than a handful of object code bytes.

Comment 30

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

Attachment: Patch that should handle <optgroup> and still be fast in almost all cases

Comment 31

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

Attachment: Oops, sorry, last one was the source file, not the patch. This is the one.

Comment 32

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

Attachment: One more optimization

Comment 33

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

OS->All
Now keeps mFlat flag, and if not flat tries to figure out if it's start, end,
or if the previous child is in the array (and use it's index plus one).

That should do it.  It should be fast in almost all cases of <optgroup>, and in
all cases of flat option lists.  r/sr please.

(BTW, I'm not certain that the code as originally written handles insertion into
the middle of select lists with <OPTGROUP> properly (how does <optgroup>
interact with the the DOM, and do additions to the <optgroup> cause the
SelectElement's option list to be marked dirty), but that's a separate
pre-existing issue/bug I'm not affecting).

Comment 34

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

BTW, as per jst's request, I plan to make that mod to nsGenericElement.cpp
(patch in the comment), so include that in any review.

Comment 35

[Fabian Guisset]

OK I did some performance measurements running with the latest patch. I did
testcases for optgroups as well. The conclusion is: we perform very well
whatever the test. Here are some more precise results. Tests run on linux athlon
1GHz 256MB
1) Insertion of 5000 raw options in the select: 10 seconds instead of ~40
seconds before the patch.
2) Insertion of 500 optgroups each containing 10 options in the select: 4
seconds (can you say wow).
3) Insertion of 250 optgroups each containing 10 options + 2500 raw options in
the select ( = 5000 options ): 10 seconds.

Note that the W3C issues this warning in its spec:
"Note. Implementors are advised that future versions of HTML may extend the
grouping mechanism to allow for nested groups (i.e., OPTGROUP elements may nest)"
Does the current implementation allow this?
I'll attach the testcase soon.

Comment 36

[rods (gone)]

I don't think the current parser or Content Sink supports more than one level of 
optgroups, so don't waste any time on this. 

I tested the original patch which had a few issues, but overall looked good. I 
take your word on it that it has been test well and with optgroups.

r=rods

Comment 37

[Johnny Stenback (:jst)]

@@ -93,6 +94,7 @@
 private:
   nsVoidArray mElements;
   PRBool mDirty;
+  PRBool mFlat;
   nsHTMLSelectElement* mSelect;
 };

The two PRBool's really should be converted into PRPackedBool. Be careful with
passing PRPackedBools as PRBool references or pointers tho.

- nsHTMLSelectElement::AddOptionIndexed() is a bit over-enthusiastic wrt error
checking:

+  nsIFormControlFrame* fcFrame = nsnull;
+
+  nsresult result = GetPrimaryFrame(this, fcFrame, PR_FALSE);
+
+  if (NS_SUCCEEDED(result) && fcFrame) {

this would be enoug:

+  nsIFormControlFrame* fcFrame = nsnull;
+
+  GetPrimaryFrame(this, fcFrame, PR_FALSE);
+
+  if (fcFrame) {

I also wouldn't care about the return value from QI, check if you got a non-null
pointer back. It's up to you if you wanto change this tho.

- Be consistent with space-after-comma, I see code that leaves out the space:

+  mOptions->AddOptionIndexed(aContent,aIndex);

- Why do we need AddOptionIndexed() in nsISelectElement, I don't see it ever
being called through that interface?

Comment 38

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

One of the PRBools is passed as a PRBool&, so I can't pack them.

The over-paranoia was there already, though the NS_SUCCEED(result) can be
removed.  (The "nsresult result =" needs to be left, however.)

The space-after-comma thing is just ancient ingrained habit; I doubt I'll ever
totally break myself of it.  Corrected.  Patch to be attached.

I added AddOptionIndexed to the interface because it seemed to make sense to
make it possible to insert an option in a specific spot.  Since I had it anyways
for internal use, the cost is minimal.

Comment 39

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

Attachment: Minor nits dealt with, against current trunk.

Comment 40

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

Attachment: Make PRBool's PRPackedBool's, set via return from GetOptionsRecurse (per jst's request)

Comment 41

[Johnny Stenback (:jst)]

Comment on attachment 48478 [details] [diff] [review]
Make PRBool's PRPackedBool's, set via return from GetOptionsRecurse (per jst's request)

sr=jst

Comment 42

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

Fix checked in last night

Comment 43

[Madhur Bhatia]

marking verified based on developers comments.

Comment 44

[Blake Ross]

Why based on developer comments?  Something as precise as the length of time it
takes to execute a specific action can't be tested?

Comment 45

[Christian Reis]

I will also verify this as _very_ fixed on 2001091108; running the testcase for
10,000 options right now takes 45s-1m on my K6-2 450, and it took over 5 minutes
on a previous build. Looks good; and thanks, jesup.