Closed Bug 352980 Opened 13 years ago Closed 12 years ago

[FIXr]Track extra submit element index to speed up parsing in some forms

Categories

(Core :: DOM: Core & HTML, defect, P2)

defect

Tracking

()

RESOLVED FIXED
mozilla1.9beta1

People

(Reporter: jlurz24, Assigned: bzbarsky)

References

Details

Attachments

(2 files, 1 obsolete file)

Quoting bz in bug 347165:

"That said, maybe we should actually keep track of the first submits in both
mInElements and mNotInElements?  With the current setup I worry that a single
submit followed by a bunch of image inputs will make life unhappy.  For
example, we could store the indices in both, rather than the element pointers. 
We'd need to maintain the indices a little on insertion and removal, and change
GetDefaultSubmitElement to compare the two indices and return the right
thing... but then in this code we could simply do an index compare and be done
with it."

To summarize, instead of tracking the default submit element, we would track the index of the first submit element in the in-elements list, and the first submit element in the not-in-elements list. The default submit element could be quickly determined from these. This would speed up parsing certain forms.

I'll come up with a testcase for this.
Attached file Speed test
Reports the average over 20 runs of parsing a large number of form elements, with and without an image element first.
Sample results:

Average elapsed time over 20 trials
With image?	Number of submit elements	Time
No	100	4.5
Yes	100	6.05
No	1000	24.5
Yes	1000	26.05
No	10000	208.3
Yes	10000	350

Image submit element overhead
100 submit elements: 	34.44%
1000 submit elements: 	6.33%
10000 submit elements: 	68.03%
I'm a little bit concerned about the perf impact of calling CompareFormControlPosition from within GetDefaultSubmit because GetDefaultSubmit is called from the intrinsic state calculation in nsGenericHTMLFormElement and CompareFormControlPosition boils down to two calls to IndexOf, so this should be n^2.
We could keep track of all three -- default submit element and the index of the first submit in each array.  Would that help?
Attached patch Fix per my proposal (obsolete) — Splinter Review
This fixes things based on this speed test.  I already checked in reftests to make sure this doesn't regress basic correctness.
Assignee: jlurz24 → bzbarsky
Status: NEW → ASSIGNED
Attachment #273860 - Flags: superreview?(jst)
Attachment #273860 - Flags: review?(jst)
Priority: -- → P2
Summary: Track extra submit element index to speed up parsing in some forms → [FIX]Track extra submit element index to speed up parsing in some forms
Target Milestone: --- → mozilla1.9beta2
Attached patch Updated to tipSplinter Review
Attachment #273860 - Attachment is obsolete: true
Attachment #273922 - Flags: superreview?(jst)
Attachment #273922 - Flags: review?(jst)
Attachment #273860 - Flags: superreview?(jst)
Attachment #273860 - Flags: review?(jst)
Attachment #273922 - Flags: superreview?(jst)
Attachment #273922 - Flags: superreview+
Attachment #273922 - Flags: review?(jst)
Attachment #273922 - Flags: review+
Summary: [FIX]Track extra submit element index to speed up parsing in some forms → [FIXr]Track extra submit element index to speed up parsing in some forms
Comment on attachment 273922 [details] [diff] [review]
Updated to tip

This is a slight optimization that should help with parsing for forms that have image inputs somewhere near the beginning of the form and then a bunch of submit elements (prevents this situation from being O(N^2) in number of submits).  Risk is pretty low.
Attachment #273922 - Flags: approval1.9?
Comment on attachment 273922 [details] [diff] [review]
Updated to tip

Approving, but please do keep an eye out for form submission related bugs that could be regressions from this. It's not like this is in code where we haven't seen odd regressions before :)
Attachment #273922 - Flags: approval1.9? → approval1.9+
Checked in.

It would be nice to have some basic tests of this stuff... :(
Status: ASSIGNED → RESOLVED
Closed: 12 years ago
Flags: in-testsuite?
Resolution: --- → FIXED
Er... Except I checked in tests, per comment 5!
Flags: in-testsuite? → in-testsuite+
Component: DOM: HTML → DOM: Core & HTML
QA Contact: ian → general
You need to log in before you can comment on or make changes to this bug.