Insertion of Options in Select elements very slow

VERIFIED FIXED in mozilla0.9.5

Status

()

Core
Layout: Form Controls
P1
normal
VERIFIED FIXED
17 years ago
15 years ago

People

(Reporter: Fabian Guisset, Assigned: jesup)

Tracking

({perf})

Trunk
mozilla0.9.5
x86
All
Points:
---

Firefox Tracking Flags

(Not tracked)

Details

(Whiteboard: [Needed for Bugzilla])

Attachments

(10 attachments, 1 obsolete attachment)

1022 bytes, text/html
Details
300.81 KB, text/html
Details
5.40 KB, patch
Details | Diff | Splinter Review
295.99 KB, text/html
Details
4.03 KB, patch
Details | Diff | Splinter Review
4.95 KB, patch
Details | Diff | Splinter Review
6.95 KB, patch
Details | Diff | Splinter Review
7.15 KB, patch
Details | Diff | Splinter Review
6.76 KB, patch
Details | Diff | Splinter Review
6.83 KB, patch
jst
: review+
Details | Diff | Splinter Review
(Reporter)

Description

17 years ago
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.
(Reporter)

Comment 1

17 years ago
Created attachment 47349 [details]
Testcase for bug 97345
(Reporter)

Updated

17 years ago
Keywords: perf
Whiteboard: [Needed for Bugzilla]

Comment 2

17 years ago
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.
(Assignee)

Comment 3

17 years ago
I'll have a jprof of this shortly
(Assignee)

Comment 4

17 years ago
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()


(Assignee)

Comment 5

17 years ago
Created attachment 47357 [details]
jprof of ~5min of trying to add 10000 options using Add()
(Assignee)

Updated

17 years ago
Blocks: 71768
(Assignee)

Comment 6

17 years ago
Created attachment 47376 [details] [diff] [review]
Initial shot at a patch for this.  Tested, but not extensively.  Works quite well
(Assignee)

Comment 7

17 years ago
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.
Assignee: rods → rjesup
(Assignee)

Comment 8

17 years ago
Created attachment 47378 [details]
jprof with patch, 10000 options Add(), completed (unlike previous where I gave up)
(Reporter)

Comment 9

17 years ago
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?
(Reporter)

Updated

17 years ago
No longer blocks: 71768
(Assignee)

Comment 10

17 years ago
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
Status: NEW → ASSIGNED
(Reporter)

Comment 11

17 years ago
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.
(Reporter)

Comment 12

17 years ago
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

17 years ago
My comments from Bug 62568:

------- Additional Comments From rods@netscape.com 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.
Priority: -- → P1
Target Milestone: --- → mozilla0.9.6

Updated

17 years ago
Target Milestone: mozilla0.9.6 → mozilla0.9.5

Comment 14

17 years ago
Ignore my lastest message above, that describes a different problem

Comment 15

17 years ago
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
(Assignee)

Comment 16

17 years ago
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.
Depends on: 93620
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;
(Assignee)

Comment 18

17 years ago
Created attachment 47523 [details] [diff] [review]
Updated patch - no crash, removed redundant code
(Assignee)

Comment 19

17 years ago
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).
(Reporter)

Comment 20

17 years ago
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 :-)
(Assignee)

Comment 21

17 years ago
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.
(Assignee)

Comment 22

17 years ago
Created attachment 47542 [details] [diff] [review]
Updated patch, final cleanup.  Also updates nsISelectElement.h
(Assignee)

Comment 23

17 years ago
Ok, I think we're ready for r=/sr= on this.  Takers?
Keywords: approval
(Reporter)

Comment 24

17 years ago
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.
Does this handle OPTGROUP correctly?
(Assignee)

Comment 26

17 years ago
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.
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?
(Assignee)

Comment 29

17 years ago
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.
(Assignee)

Comment 30

17 years ago
Created attachment 47626 [details] [diff] [review]
Patch that should handle <optgroup> and still be fast in almost all cases
(Assignee)

Comment 31

17 years ago
Created attachment 47629 [details] [diff] [review]
Oops, sorry, last one was the source file, not the patch. This is the one.
(Assignee)

Comment 32

17 years ago
Created attachment 47631 [details] [diff] [review]
One more optimization
(Assignee)

Comment 33

17 years ago
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).
OS: Linux → All
(Assignee)

Comment 34

17 years ago
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.
(Reporter)

Comment 35

17 years ago
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.
(Reporter)

Updated

17 years ago
Blocks: 84891
(Assignee)

Updated

17 years ago
Attachment #47626 - Attachment is obsolete: true

Comment 36

17 years ago
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
@@ -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?
(Assignee)

Comment 38

17 years ago
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.

(Assignee)

Comment 39

17 years ago
Created attachment 48420 [details] [diff] [review]
Minor nits dealt with, against current trunk.
(Assignee)

Comment 40

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

sr=jst
Attachment #48478 - Flags: superreview+
Attachment #48478 - Flags: review+
(Assignee)

Comment 42

17 years ago
Fix checked in last night
Status: ASSIGNED → RESOLVED
Last Resolved: 17 years ago
Resolution: --- → FIXED

Comment 43

17 years ago
marking verified based on developers comments.

Status: RESOLVED → VERIFIED

Comment 44

17 years ago
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

17 years ago
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.

Updated

15 years ago
No longer depends on: 93620
You need to log in before you can comment on or make changes to this bug.