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

Status: RESOLVED FIXED

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

Description

[jpl24]

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.

Comment 1

[jpl24]

Attachment: Speed test

Reports the average over 20 runs of parsing a large number of form elements, with and without an image element first.

Comment 2

[jpl24]

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%

Comment 3

[jpl24]

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.

Comment 4

[Boris Zbarsky [:bzbarsky]]

We could keep track of all three -- default submit element and the index of the first submit in each array.  Would that help?

Comment 5

[Boris Zbarsky [:bzbarsky]]

Attachment: Fix per my proposal

This fixes things based on this speed test.  I already checked in reftests to make sure this doesn't regress basic correctness.

Comment 6

[Boris Zbarsky [:bzbarsky]]

Attachment: Updated to tip

Comment 7

[Boris Zbarsky [:bzbarsky]]

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.

Comment 8

[Johnny Stenback (:jst)]

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 :)

Comment 9

[Boris Zbarsky [:bzbarsky]]

Checked in.

It would be nice to have some basic tests of this stuff... :(

Comment 10

[Boris Zbarsky [:bzbarsky]]

Er... Except I checked in tests, per comment 5!