[webkit-reviews] review denied: [Bug 74909] Performance improvement of HTMLInputElement::updateCheckedRadioButtons() : [Attachment 119996] Patch 2

[bugzilla-daemon at webkit.org]

Darin Adler <darin at apple.com> has denied Kent Tamura <tkent at chromium.org>'s
request for review:
Bug 74909: Performance improvement of
HTMLInputElement::updateCheckedRadioButtons()
https://bugs.webkit.org/show_bug.cgi?id=74909

Attachment 119996: Patch 2
https://bugs.webkit.org/attachment.cgi?id=119996&action=review

------- Additional Comments from Darin Adler <darin at apple.com>
View in context: https://bugs.webkit.org/attachment.cgi?id=119996&action=review


It should be straightforward to put a test in LayoutTests/perf that shows that
this was O(n^2) and is no longer O(n^2).

> Source/WebCore/ChangeLog:12
> +	   We can skip this iteration in a case that validity status is not
changed.

This is not a sufficient explanation.

> Source/WebCore/html/HTMLInputElement.cpp:188
> +    CheckedRadioButtons& radioButtons = checkedRadioButtons();
> +    bool radioGroupHadChecked = radioButtons.checkedButtonForGroup(name());
>      if (attached() && checked())
> -	   checkedRadioButtons().addButton(this);
> +	   radioButtons.addButton(this);
> +    bool radioGroupHasChecked = radioButtons.checkedButtonForGroup(name());
> +    if (radioGroupHadChecked == radioGroupHasChecked)
> +	   return;

To understand the concept of this patch, one needs to look at
RadioInputType::valueMissing. That’s where the rule about validity that is
affected by radio button checking comes from. The division of code between
HTMLInputElement and RadioInputType hides that, and it took me a long time to
figure it out. There wasn’t even a comment that pointed specifically to
“missing value” as the validity criterion that can change here. That’s a
problem.

This patch doesn’t optimize all the cases it seems to attempt. By the time this
function is called by HTMLInputElement::setChecked, the button has already been
removed from checkedRadioButtons(). So it seems to me that setChecked(true) on
a radio button that is already checked won’t get the optimization because
radioGroupHadChecked will be false even though it should have been true. This
case ought to be covered by a performance test.

Even for cases where the validity is in fact changing, I’d like to see us get
rid of this massive performance cost for the very common case that the page is
not using validity features at all. We shouldn’t walk the entire list of
controls searching for other buttons in the group if nothing in the entire
document is even looking at validity.

We should probably consider a design where we keep a complete set of all the
radio buttons in a group for each group. We avoided that before and kept track
of only the checked radio button, which was an elegant thing to do without
validity. But now that we have added a feature where the checkedness of a radio
button can affect all the other buttons, even unchecked ones, it’s no longer a
good trick, at least for pages where validity is being used. It seems we should
reconsider the data structure. We cannot get acceptable performance by walking
the whole document the way we do in this function. The algorithm is
proportional to the size of the entire document for radio buttons outside
forms, not just the number of radio buttons, and that is unacceptable.

Even aside from the comments above I also think there are many things we should
do to make the code readable and better. Not sure what order to do these in and
what importance there is:

- Change the updateCheckedRadioButtons function’s name. The function does not
“update” checked radio buttons. What it does is record the fact that this
button is checked if it is, and uncheck the old checked button. It does only
half the job, and HTMLInputElement::setChecked does the other half. Perhaps the
reason it only does half the job is so it can be called by
RadioInputType::attach and doesn’t waste time removing the button if it’s not
already there, but if so that’s not a great reason. Maybe we need to refactor
the function as well.

- Review HTMLInputElement::updateType and the code in
HTMLInputElement::parseMappedAttribute for the name attribute, and figure out
why it’s OK that these functions call CheckedRadioButtons::addButton directly
without doing anything to update validity of other buttons in the group. My
guess is that we could construct test cases showing there are bugs in those
cases.

- Review HTMLInputElement::willMoveToNewOwnerDocument and
HTMLInputElement::~HTMLInputElement and figure out why it’s OK that these
functions call CheckedRadioButtons::removeButton without doing anything to
update validity of other buttons in the group. Again, I suspect at least one of
these is a bug. It’s also strange that ~HTMLInputElement removes the radio
button from the document’s CheckedRadioButtons only, no the one from the form.

- Other functions that also manipulate the CheckedRadioButtons directly and
probably handle the validation impact of this wrong include:
HTMLFormControlElement::parseMappedAttribute for the form attribute,
HTMLFormControlElement::insertedIntoTree, and
HTMLFormElement::registerFormElement.

- In the code that does update validity, currently part of the
updateCheckedRadioButtons function, we need to add a comment to make it clear
how checking a radio button relates to validity. Specifically, if a group gets
into the state where there is no checked button this affects the valueMissing
state of all the radio buttons in that group.

- Since the validity updating in updateCheckedRadioButtons is specific to
RadioInputType, that function should move into RadioInputType and out of
HTMLInputElement. As should all manipulation of the checkedRadioButtons().

- Since CheckedRadioButtons already takes care of checking checked(), we should
remove the redundant call to that function from
HTMLInputElement::updateCheckedRadioButtons, unless it’s a helpful performance
optimization. We should also investigate why
HTMLInputElement::updateCheckedRadioButtons has to check attached(). Presumably
CheckedRadioButtons::addButton should add that check too. Callers that are
calling addButton without checking attached are probably doing it wrong. Maybe
all the code in HTMLInputElement::updateCheckedRadioButtons should move into
CheckedRadioButtons?

- If we still have them, the loops in updateCheckedRadioButtons should use
isRadioButton instead of checking type() == type() to see if something is a
radio button.

- For the the loops in updateCheckedRadioButtons we use an efficient way to
check name equality. Calling name() ends up calling the virtual
formControlName() function, all just to get at a field of HTMLInputElement. I
don’t think we should go through a virtual function each time. I think we
probably could compare m_name directly as long as we figure out what to do
about null vs. empty values. In general it’s not good to have functions in
HTMLInputElement going through a virtual function just to get at the m_name
field with a bit of null value handling. We should override the name function
in HTMLInputElement so that you can get the name instantly without a function
call if you already have an HTMLInputElement*. We should put the special
handling for null into HTMLInputElement::parseMappedAttribute rather than in
HTMLInputElement::formControlName.

- Document::m_formElementsWithState should change to hold
HTMLFormControlElement* instead of Element*, and all the functions should
likewise change. I think the looser type is a remnant of WML support.

- The function HTMLInputElement::setDefaultName is strange and only used by
HTMLIsIndexElement, so I suggest making it protected and giving it a different
name.