1376695 - nsHTMLDocument::MatchNameAttribute() shows up in profiles due to the search on the name attribute

Status: RESOLVED FIXED

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

Description

[(no longer active)]

See this Speedometer profile for example: http://bit.ly/2s0sgFB

The GetAttr() call (inlined) comes from MatchNameAttribute() here: <https://searchfox.org/mozilla-central/rev/fdb811340ac4e6b93703d72ee99217f3b1d250ac/dom/html/nsHTMLDocument.cpp#2059>

It would be nice to cache the index of the attribute using IndexOfAttr() and avoid repeatedly searching for the attribute.  This is an O(n) search per content appended/removed/etc notification.

I also looked into where this comes from.  This is quite sad, see for example this code in https://trac.webkit.org/export/216735/webkit/trunk/PerformanceTests/Speedometer/resources/todomvc/architecture-examples/emberjs/assets/vendor.js:

    // Support: IE<10
    // Check if getElementById returns elements by name
    // The broken getElementById methods don't pick up programatically-set names,
    // so use a roundabout getElementsByName test
    support.getById = assert(function( div ) {
        docElem.appendChild( div ).id = expando;
        return !document.getElementsByName || !document.getElementsByName( expando ).length;
    });

IINM this gets called when this This basically means any app including ember currently takes this perf hit in Gecko.

There is also similar code in jquery that causes a similar issue there as well.

Comment 1

[(no longer active)]

This code comes from the jquery sizzle library.  I filed an issue in the upstream library about this <https://github.com/jquery/sizzle/issues/402>, hopefully the entire getElementsByName() call can be removed (at least for non-IE browsers) at the library level.

Comment 2

[Hsin-Yi Tsai (she/her) [:hsinyi]]

Jessica, mind taking a look at this?

Comment 3

[Jessica Jong [:jessica] (inactive)]

(In reply to (Away 7/10-7/17) from comment #0)
> See this Speedometer profile for example: http://bit.ly/2s0sgFB
> 
> The GetAttr() call (inlined) comes from MatchNameAttribute() here:
> <https://searchfox.org/mozilla-central/rev/
> fdb811340ac4e6b93703d72ee99217f3b1d250ac/dom/html/nsHTMLDocument.cpp#2059>
> 
> It would be nice to cache the index of the attribute using IndexOfAttr() and
> avoid repeatedly searching for the attribute.  This is an O(n) search per
> content appended/removed/etc notification.

Do you mean to cache the 'name' attribute index? so that next time MatchNameAttribute() is called, we can get the 'name' attribute value directly using the cached index, right?
We may also need to reset the cached index when 'name' attribute is unset. It looks like we don't need to update the cached index when 'name' attribute value is changed.
Is there any other case where index of an attribute may change?

Comment 4

[(no longer active)]

I've thought more about this after comment 0 but forgot to put the thoughts here before going on vacation, sorry about that!

The idea of caching the index of the name attribute may actually not be the best idea, that was the first thing that came to my mind.

The overall problem with the MatchNameAttribute callback IMO is that its callers can have some useful information that the callback can use but they don't have any way to pass this information down to the callback due to its generic nature.  For example:

  * The nsContentList::AttributeChanged() function receives the name of the changed attribute as an argument, so we tThe can immediately know whether a name attribute changed or not, and if not, we won't need to do any more work.  But right now this function just calls down into MatchNameAttribute and that function does the expensive search for the name attribute.

  * The rest of the nsContentList callbacks (ContentInserted, ContentAppended and ContentRemoved) could in theory quickly tell whether they need to look at a node or not if for example we could store a bit on the node indicating whether the node has a name attr on it.  This way we could avoid calling MatchNameAttribute() and doing the expensive search to find the name attr if we know in advance that the name attribute doesn't exist (which is the common case.)

This would mean that we can't use NS_GetFuncStringNodeList() to implement GetElementsByName() any more and we would need to implement a custom nsContentList class, but I think that should be relatively easy.

I think if we did the above, then we could avoid having to cache the index of the name attr, since the case where the node does have an attr should be quite rare and in the majority of the cases we can immediately tell inside the mutation observer callback that we don't have any work to do without having to scan the list of attributes.

Comment 5

[Jessica Jong [:jessica] (inactive)]

Yeah, looking closer at the source of the problem, nsContentList implementation is kind of expensive if the matching function is sensitive to all attribute changes. Maybe nsContentList users should be able to pass in a list of attributes to listen to... but that's a bigger topic.

It looks like NS_GetFuncStringNodeList() and nsCacheableFuncStringNodeList (which inhertis from nsContentList) is only used by GetElementsByName(), can we change nsCacheableFuncStringNodeList directly into a custom nsContentList where we only act on changes on 'name' attribute and elements that have 'name' attribute, or should we do it in a new class inheriting nsCacheableFuncStringNodeList? Using a new class that inherits from nsCacheableFuncStringNodeList sounds more reasonable, right?

Comment 6

[(no longer active)]

(In reply to Jessica Jong [:jessica] from comment #5)
> Yeah, looking closer at the source of the problem, nsContentList
> implementation is kind of expensive if the matching function is sensitive to
> all attribute changes. Maybe nsContentList users should be able to pass in a
> list of attributes to listen to... but that's a bigger topic.

I haven't checked how many other consumers would need such a functionality.  If there are other consumers and they are performance sensitive perhaps designing something more generic is helpful but if we just manage to make getElementsByName() faster here without improving anything else I'd still be quite happy!  :-)

> It looks like NS_GetFuncStringNodeList() and nsCacheableFuncStringNodeList
> (which inhertis from nsContentList) is only used by GetElementsByName(), can
> we change nsCacheableFuncStringNodeList directly into a custom nsContentList
> where we only act on changes on 'name' attribute and elements that have
> 'name' attribute, or should we do it in a new class inheriting
> nsCacheableFuncStringNodeList? Using a new class that inherits from
> nsCacheableFuncStringNodeList sounds more reasonable, right?

Since after these changes nsCacheableFuncStringNodeList will no longer have a reason to exist, I'd say you can morph nsCacheableFuncStringNodeList into this new class (and please give it a better name, like nsElementsByNameContentList), and remove NS_GetFuncStringNodeList().  Or if you think it's cleaner, just create a new nsElementsByNameContentList class from scratch and remove both NS_GetFuncStringNodeList() and nsCacheableFuncStringNodeList.  nsCacheableFuncStringNodeList as it is currently doesn't really have any functionality that will be useful to you as far as I can tell so both approaches will probably result in the same outcome, it's up to you which one you prefer.  :-)

However, I think inheriting a new class from nsCacheableFuncStringNodeList is a slightly worse apporach since nsCacheableFuncStringNodeList really has nothing useful in it!

Comment 7

[Jessica Jong [:jessica] (inactive)]

(In reply to :Ehsan Akhgari (needinfo please, extremely long backlog) from comment #6)
> Since after these changes nsCacheableFuncStringNodeList will no longer have
> a reason to exist, I'd say you can morph nsCacheableFuncStringNodeList into
> this new class (and please give it a better name, like
> nsElementsByNameContentList), and remove NS_GetFuncStringNodeList().  Or if
> you think it's cleaner, just create a new nsElementsByNameContentList class
> from scratch and remove both NS_GetFuncStringNodeList() and
> nsCacheableFuncStringNodeList.  nsCacheableFuncStringNodeList as it is
> currently doesn't really have any functionality that will be useful to you
> as far as I can tell so both approaches will probably result in the same
> outcome, it's up to you which one you prefer.  :-)
> 
> However, I think inheriting a new class from nsCacheableFuncStringNodeList
> is a slightly worse apporach since nsCacheableFuncStringNodeList really has
> nothing useful in it!

I see, I just though there'd be users in the future that need a more generic class like nsCacheableFuncStringNodeList, but we can remove it for now.
However, the new class, nsElementsByNameContentList still needs to inherit from nsCacheableFuncStringContentList,  right? since we still need to cache the list for a specific name.

I'll upload a patch soon, it will be easier to discuss if we have something first :)

Comment 8

[Jessica Jong [:jessica] (inactive)]

Attachment: patch, v1.

This is just a draft.

In this patch, I've changed 'nsCacheableFuncStringNodeList' into 'nsCachableElementsByNameNodeList' and it still inheris from nsCacheableFuncStringContentList. I didn't remove NS_GetFuncStringNodeList yet, since I'm not sure whether we should remove it or just rename it.

Ehsan, could you take a look if I'm in the right direction? Thanks!

Comment 9

[(no longer active)]

Comment on attachment 8888226 [details] [diff] [review]
patch, v1.

Review of attachment 8888226 [details] [diff] [review]:
-----------------------------------------------------------------

Thanks, yes, this looks like it's on the right track!

Note the subtree traversals can still be expensive.  It'd be nice to profile after these changes to see what the before and after picture looks like.  Thanks!

::: dom/base/nsContentList.cpp
@@ +340,3 @@
>  
>  already_AddRefed<nsContentList>
>  NS_GetFuncStringNodeList(nsINode* aRootNode,

I'd consider removing this helper also and just moving the call directly to https://searchfox.org/mozilla-central/rev/3a3af33f513071ea829debdfbc628caebcdf6996/dom/html/nsHTMLDocument.h#192.

@@ +1095,5 @@
> +  if (aAttribute != nsGkAtoms::name) {
> +    return;
> +  }
> +
> +  nsContentList::AttributeChanged(aDocument, aElement, aNameSpaceID, aAttribute,

Technically here and below your base class is nsCacheableFuncStringContentList not nsContentList, so you should use that class instead.

@@ +1106,5 @@
> +                                                  nsIContent* aFirstNewContent,
> +                                                  int32_t aNewIndexInContainer)
> +{
> +  bool anyContentHasName = false;
> +  for (nsIContent* cur = aFirstNewContent; cur; cur = cur->GetNextSibling()) {

I think you need to look into the entire subtree, not just the siblings, to also pick up the case where something gets appended with a kid somewhere which has a name attribute.  If this doesn't break any tests, please make sure to add a test that fails with your current patch!

@@ +1129,5 @@
> +                                                  int32_t aIndexInContainer)
> +{
> +  if (!aChild->HasName()) {
> +    return;
> +  }

I think here you should also look inside the entire subtree.

@@ +1144,5 @@
> +                                                 nsIContent* aPreviousSibling)
> +{
> +  if (!aChild->HasName()) {
> +    return;
> +  }

Ditto.

Comment 10

[Jessica Jong [:jessica] (inactive)]

Attachment: patch, v2.

In this patch, I addressed some of the feedback in comment 9:
- Removed NS_GetFuncStringHTMLCollection/NodeList and use GetFuncStringContentList directly
- Call base class function using nsCacheableFuncStringContentList instead of nsContentList
- For ContentAppended/Inserted/Removed, if we look into the entire subtree to see if any element has a name attribute, the worst case is that we end up searching the tree twice (the first time to look if there is any element with name attribute and the second time in nsContentUtils::MatchSelf to see if the name attribute matches the name passed). After thinking it again, I'd prefer to modify MatchNameAttribute to return early if the element doesn't have a name attribute. I think we can avoid possible performance regression this way.
- If we are going to use HasName() to check if an element has a name attribute, we need to set the flag for all elements, now we only set for elements that CanHaveName(), so fixed this part too.

TODO:
- add tests that pick up the case where something gets appended with a kid somewhere which has a name attribute
- see if we can notice any performance improvement by profiling

Comment 11

[Jessica Jong [:jessica] (inactive)]

Attachment: patch, v3.

- Added tests that pick up the case where something gets appended with a kid somewhere which has a name attribute
- Other details are in comment 10 and also in the commit message
- Profile running before (https://perfht.ml/2usUyvS) and after (https://perfht.ml/2usQko5) the patch. We can see that MatchNameAttribute is still called in ContentRemoved, but it does not do nsAttrAndChildArray::GetAttr() anymore, most likely because the matching element does not have a name attribute

Comment 12

[(no longer active)]

(In reply to Jessica Jong [:jessica] from comment #11)
> - Profile running before (https://perfht.ml/2usUyvS) and after
> (https://perfht.ml/2usQko5) the patch. We can see that MatchNameAttribute is
> still called in ContentRemoved, but it does not do
> nsAttrAndChildArray::GetAttr() anymore, most likely because the matching
> element does not have a name attribute

This looks great!  It's a bit surprising to me how much MatchNameAttribute is showing up in the after profile still, but given that nsAttrAndChildArray::GetAttr() isn't showing up at all any more, it seems to me that every time that MatchNameAttribute() shows up, we're running a mutation observer and what you have showing up in the after profile is the pure overhead of running the mutation observer, and it's hard to see how to improve on that...

Comment 13

[(no longer active)]

Comment on attachment 8889879 [details] [diff] [review]
patch, v3.

Review of attachment 8889879 [details] [diff] [review]:
-----------------------------------------------------------------

::: dom/base/nsContentList.cpp
@@ +1080,5 @@
> +                                                   int32_t aModType,
> +                                                   const nsAttrValue* aOldValue)
> +{
> +  if (aAttribute != nsGkAtoms::name) {
> +    return;

Can you please add a comment explaining why returning early here is OK?

::: dom/html/nsGenericHTMLElement.cpp
@@ +486,5 @@
>    NS_ENSURE_SUCCESS(rv, rv);
>  
>    if (aDocument) {
>      RegAccessKey();
> +    if (CanHaveName(NodeInfo()->NameAtom()) && HasName()) {

It may be a good idea to break off the nsGenericHTMLElement.cpp part of this patch into a separate part because this part is allowing you to use the ElementHasName flag on all nodes, even those that CanHaveName() returns false for.  It took me a couple of minutes to understand how this is related to the patch, so I think having this as a separate part would make this a bit easier to understand.

Comment 14

[Jessica Jong [:jessica] (inactive)]

Thanks Ehsan for the review.

(In reply to :Ehsan Akhgari (needinfo please, extremely long backlog) from comment #13)
> Comment on attachment 8889879 [details] [diff] [review]
> patch, v3.
> 
> Review of attachment 8889879 [details] [diff] [review]:
> -----------------------------------------------------------------
> 
> ::: dom/base/nsContentList.cpp
> @@ +1080,5 @@
> > +                                                   int32_t aModType,
> > +                                                   const nsAttrValue* aOldValue)
> > +{
> > +  if (aAttribute != nsGkAtoms::name) {
> > +    return;
> 
> Can you please add a comment explaining why returning early here is OK?

Sure, will add some comments here.

> 
> ::: dom/html/nsGenericHTMLElement.cpp
> @@ +486,5 @@
> >    NS_ENSURE_SUCCESS(rv, rv);
> >  
> >    if (aDocument) {
> >      RegAccessKey();
> > +    if (CanHaveName(NodeInfo()->NameAtom()) && HasName()) {
> 
> It may be a good idea to break off the nsGenericHTMLElement.cpp part of this
> patch into a separate part because this part is allowing you to use the
> ElementHasName flag on all nodes, even those that CanHaveName() returns
> false for.  It took me a couple of minutes to understand how this is related
> to the patch, so I think having this as a separate part would make this a
> bit easier to understand.

Ok, I'll separate this patch into two parts.

Comment 15

[Jessica Jong [:jessica] (inactive)]

Attachment: Part 1: Apply ElementHasName flag to all nodes.

Splitting attachment 8889879 [details] [diff] [review] into two patches, carrying r+.

Comment 16

[Jessica Jong [:jessica] (inactive)]

Attachment: Part 2: Avoid rebuilding getElementsByName list when not needed.

Splitting attachment 8889879 [details] [diff] [review] into two patches, carrying r+.

Comment 17

[Jessica Jong [:jessica] (inactive)]

https://treeherder.mozilla.org/#/jobs?repo=try&revision=4f01a94e095e0ad59e89ce565b613a38f00cad17&group_state=expanded

Comment 18

[Pulsebot]

Pushed by [e-mail]:
https://hg.mozilla.org/integration/mozilla-inbound/rev/7eb9728ad2a1
Part 1: Let ElementHasName flag be applied to all nodes. r=ehsan
https://hg.mozilla.org/integration/mozilla-inbound/rev/753fd9590841
Part 2: Avoid rebuilding the list returned by getElementsByName when not needed. r=ehsan

Comment 19

[Carsten Book [:Tomcat]]

https://hg.mozilla.org/mozilla-central/rev/7eb9728ad2a1
https://hg.mozilla.org/mozilla-central/rev/753fd9590841

Comment 20

[Boris Zbarsky [:bzbarsky]]

In BindToTree, is there a reason we check CanHaveName() before HasName()?

HasName() should be cheaper and would typically be false, I'd think.

Comment 21

[Jessica Jong [:jessica] (inactive)]

(In reply to Boris Zbarsky [:bz] from comment #20)
> In BindToTree, is there a reason we check CanHaveName() before HasName()?
> 
> HasName() should be cheaper and would typically be false, I'd think.

No special reason. I think we can do HasName() first, the same in RemoveFromNameTable(). I'll do it in a followup patch.

Comment 22

[Jessica Jong [:jessica] (inactive)]

Attachment: (followup) Check HasName() before CanHaveName().

Followup as suggested by bz.

Comment 23

[(no longer active)]

Comment on attachment 8891260 [details] [diff] [review]
(followup) Check HasName() before CanHaveName().

Review of attachment 8891260 [details] [diff] [review]:
-----------------------------------------------------------------

(Please file follow-ups in the future, it's usually considered a bad idea to attach more patches to already fixed bugs since it makes the tracking of which parts landed when etc difficult.  In this case it doesn't matter much!)

Thanks!

Comment 24

[Jessica Jong [:jessica] (inactive)]

(In reply to :Ehsan Akhgari (needinfo please, extremely long backlog) from comment #23)
> Comment on attachment 8891260 [details] [diff] [review]
> (followup) Check HasName() before CanHaveName().
> 
> Review of attachment 8891260 [details] [diff] [review]:
> -----------------------------------------------------------------
> 
> (Please file follow-ups in the future, it's usually considered a bad idea to
> attach more patches to already fixed bugs since it makes the tracking of
> which parts landed when etc difficult.  In this case it doesn't matter much!)
> 
> Thanks!

Noted, will file a separate bug in the future. Thanks.

Comment 25

[Jessica Jong [:jessica] (inactive)]

checkin-needed for followup patch in attachment 8891260 [details] [diff] [review].

Comment 26

[Pulsebot]

Pushed by [e-mail]:
https://hg.mozilla.org/integration/mozilla-inbound/rev/dd3e2939065e
Check HasName() before CanHaveName(). r=ehsan

Comment 27

[Ryan VanderMeulen [:RyanVM]]

https://hg.mozilla.org/mozilla-central/rev/dd3e2939065e