558516 - Fast-path attribute access for the case of no prefixes, and maybe correct cases

Status: RESOLVED FIXED

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

Description

[Boris Zbarsky [:bzbarsky]]

Right now getAttribute and setAttribute are very general in terms of dealing with casing, prefixed attrs, etc.  But prefixes on attrs are rare and often enough people use the right case (in the upper/lower) anyway.  So it might make sense to fast-path at least the no-prefix case, and maybe the correct-case case too.

Comment 1

[Johnny Stenback (:jst)]

Agreed, and I think we should do both the no colon case and lowercase fast paths. I think Jonas has a plan here...

Comment 2

[Jonas Sicking (:sicking) No longer reading bugmail consistently]

Attachment: patch, doesn't improve perf

I thought I had attached this, but I guess not.

This was my attempt at fixing this bug, but I couldn't see any improved performance in dromaeo.

The problem is that most of the work that GetExistingAttrNameForQName does is stuff that we need to do. The only extra work that we're currently doing is the second iteration over the attribute list in the GetAttr call. However that iteration seems very fast.

Another strategy to try would be to always call GetAttr directly, without any case inspections and conversions. However afterwards we still almost always have to at least check for uppercase characters in the string.

If we found an attribute, we still have to check if there are uppercase characters in the string, thus meaning we should not have found an attribute.

If we haven't found an attribute, we need to check if there are uppercase characters and potentially lowercase the string and search again.

So possibly we could avoid the data copy that now always happen if the string was already lowercased. But I wouldn't expect the data copy to be expensive if you're iterating the string and checking for uppercase characters anyway.

Then there is the issue of ':' characters. However that's mostly free in the current implementation since we only look for it if there are namespaced attributes.

Comment 3

[Boris Zbarsky [:bzbarsky]]

Hmm.  With that patch, getAttribute on an HTML div from script seems to call nsGenericElement::GetAttribute, not nsGenericHTMLElement::GetAttribute.

Comment 4

[Boris Zbarsky [:bzbarsky]]

In particular, because nsGenericElement::GetAttribute is non-virtual and the quickstub now unwraps to nsGenericElement.

> But I wouldn't expect the data copy to be expensive

Allocating the buffer to copy into is expensive.

Comment 5

[Boris Zbarsky [:bzbarsky]]

So what webkit does is to first loop over in the given case and see whether any attrs match.  Then if there were not matches and there were any attributes with a prefix or if the attr get is case-insensitive (this is all implemented in their attribute container class, so the caller needs to pass in whether to do the get case-insensitively), the loop over the attributes again, this time doing case-insensitive compares (using a function that compares two strings case-insensitively, not creating a new string object).

Comment 6

[Boris Zbarsky [:bzbarsky]]

Attachment: Patch that gives a speedup; applies on top of Jonas' patch and fixes the correctness bug in it

For example, this patch applied on top of yours gives me somewhere around a 15% speedup for getAttribute, as measured using the testcase in bug 582228.  That's a 15% speedup after some other optimizations have already been done, though.

Without this patch, in my tree, the testcase averages about 5.5ms (I bumped up the iteration count in the loop by a factor of 10 to get numbers I can work with).  With this patch it averages 4.7.  If I change the testcase to use getAttribute("styleE") it goes back to 5.5, so we're no worse off there than before.

The completely case-sensitive version which happened with the patch Jonas attached gave me about 4.5ms.

I'd be really interested in what the numbers look like with an approach like webkit's, though.

Comment 7

[Jonas Sicking (:sicking) No longer reading bugmail consistently]

> > But I wouldn't expect the data copy to be expensive
> 
> Allocating the buffer to copy into is expensive.

We very rarely should be allocating a buffer though, right? Most of the time we should just be using the nsAutoString buffer

Comment 8

[Peter Van der Beken [:peterv]]

Attachment: Alternative patch for avoiding buffer copy for lowercase strings.

Here's what I tried.

Comment 9

[Peter Van der Beken [:peterv]]

Attachment: Alternative patch for looking for attributes once

And this is what I tried for avoiding GetAttr. (attachment 462353 [details] [diff] [review] goes on top of this one).

Comment 10

[Peter Van der Beken [:peterv]]

(In reply to comment #7)
> We very rarely should be allocating a buffer though, right? Most of the time we
> should just be using the nsAutoString buffer

I was seeing the nsAutoString constructor and SetLength showing up in the profile. I tried bz's approach, but the nsAutoString constructor was still around. So I ended up just looking for the first uppercase char and only if there is one use a nsAutoString and copy.

Comment 11

[Olli Pettay [:smaug][[e-mail]]]

Yeah, all the string ctors and dtors show up pretty badly in the profiles (when the testcase is using strings alot).

Comment 12

[Peter Van der Beken [:peterv]]

Right, ideally we'd fix it everywhere by making the string stuff (constructor and SetLength) cheap.

Comment 13

[Boris Zbarsky [:bzbarsky]]

> We very rarely should be allocating a buffer though, right?

Hmm.  We take a bunch of time in MutatePrep anyway, though.  I hate strings.  Any ideas on making SetLength() cheap are welcome.  The issue is that "cheap" in this context needs to be a handful of instructions...  and if you read the impl, it's _complicated_.

> but the nsAutoString constructor was still around

Note that in my local build the string constructors are inlined, which might be mitigating the issue a bit for me.

Peter, I'll give you patches a shot this afternoon and measure.

Comment 14

[Boris Zbarsky [:bzbarsky]]

Peter's patch measures about the same performance wise as sicking's patch with my change on the testcase in bug 582228.  Breakdown of remaining time is about like so:

23% under nsGenericElement::GetExistingAttrValFromQName (9% in the function
    itself)
16% nsAttrValue::ToString (about half self and half the stringbuffer addref)
30% Converting the nsAString to a jsstring in quickstub code (about 1/3 in
    xpc_qsStringToJsstring and the other 2/3 under ReadableToJSVal).
17% in (not under) GetAttribute_tn.

and some minor stuff.

Comment 15

[Jonas Sicking (:sicking) No longer reading bugmail consistently]

Over to bz who at this point has a better idea of what's going on here in the various patches.

Comment 16

[Boris Zbarsky [:bzbarsky]]

Attachment: Up-to-date attempt using ascii-insensitive compares.

Comment 17

[Boris Zbarsky [:bzbarsky]]

Attachment: This is what I think we should do

This is slightly faster (5-10ns or so, which is a lot if we want to drive this down to 50ns total) than the other option for existing lowercased attributes, and just about as fast for non-existing lowercase attributes.  It's noticeably slower (by 30-40ns) if the attr name is not lowercase, but not slower than what we have _now_, and that's a rare case anyway.

Comment 18

[Olli Pettay [:smaug][[e-mail]]]

Comment on attachment 642058 [details] [diff] [review]
This is what I think we should do


>+StringContainsASCIIUpper(const nsAString& aStr)
>+{
>+  const PRUnichar* iter = aStr.BeginReading();
>+  const PRUnichar* end = aStr.EndReading();
>+  while (iter != end) {
>+    PRUnichar c = *iter;
>+    if (c >= 'A' && c <= 'Z') {
>+      return true;
>+    }
>+    ++iter;
>+  }
>+
>+  return false;
>+}
This could go to contentutils


>   const nsAttrValue* GetAttr(nsIAtom* aLocalName, PRInt32 aNamespaceID = kNameSpaceID_None) const;
>+  // Get an nsAttrValue by qualified name.  Can optionally do
>+  // ASCII-case-insensitive name matching.
>+  const nsAttrValue* GetAttr(const nsAString& aName, bool aCaseInsensitive) const;
We do have nsCaseTreatment. Perhaps use that for the latter parameter.


>+const nsAttrValue*
>+nsXULElement::GetAttribute(const nsAString& aName)
>+{
Should use 4 space indentation in this file :(



>+++ b/content/xul/content/src/nsXULElement.h
>@@ -483,16 +483,20 @@ public:
>     // This function should ONLY be used by BindToTree implementations.
>     // The function exists solely because XUL elements store the binding
>     // parent as a member instead of in the slots, as nsGenericElement does.
>     void SetXULBindingParent(nsIContent* aBindingParent)
>     {
>       mBindingParent = aBindingParent;
>     }
> 
>+    // Override GetAttribute, because we need to do extra stuff
>+    // nsGenericElement doesn't do.
>+    const nsAttrValue* GetAttribute(const nsAString& aName);
Could you call this something else than GetAttribute, since GetAttribute is a public DOM method
which takes in and out param and returns nsresult.
Maybe GetAttributeValue or GetAttrValue

Comment 19

[Boris Zbarsky [:bzbarsky]]

> This could go to contentutils
> We do have nsCaseTreatment. Perhaps use that for the latter parameter.
> Should use 4 space indentation in this file :(

Done.

> Maybe GetAttributeValue or GetAttrValue

GetAttrValue it is.

Comment 20

[Boris Zbarsky [:bzbarsky]]

https://hg.mozilla.org/integration/mozilla-inbound/rev/d49beb57db23

Comment 21

[David Baron :dbaron: (⌚️UTC-4, no longer working on Mozilla)]

Backed out for causing pretty much all mac builds to crash in nsXULElement::GetAttrValue, e.g.:
https://tbpl.mozilla.org/php/getParsedLog.php?id=13510498&tree=Mozilla-Inbound
and probably also for causing, in mochitest-1:
29431 ERROR TEST-UNEXPECTED-FAIL | /tests/content/base/test/test_bug469304.html | Element shouldn't have case-insensitive attribute anymore. - got "123", expected null

https://hg.mozilla.org/integration/mozilla-inbound/rev/d4e43a290fa7

Comment 22

[Boris Zbarsky [:bzbarsky]]

The XUL thing is due to the silly MOZ_ASSERT that ended up sneaking into nsXULElement::GetAttrValue via copy/paste and can't possibly succeed there, since it's asserting !IsXUL().

The test failure is this code:

  o.setAttribute("myAttrib2", "htmlattr");
  o.setAttributeNS("", "myAttrib2", "123");
  is(o.attributes.length, 4, "Should have four attributes.");
  var an = o.attributes.removeNamedItem("myAttrib2");
  is(o.attributes.length, 3, "An attribute should have been removed.");
  is(an.value, "htmlattr", 
     "The removed attribute should have been the case-insensitive attribute.");
  is(o.getAttribute("myAttrib2"), null, 
    "Element shouldn't have case-insensitive attribute anymore.");

Looking into what's going on there now.

Comment 23

[Boris Zbarsky [:bzbarsky]]

Ah, so the problem there is that the element has an attribute with the name "myAttrib2" (with that casing).  When we call getAttribute("myAttrib2"), the old code lowercased it and hence got nothing, while the new code finds the attribute in question.

domcore says, as of today:

  The getAttribute(name) method must run these steps:

    If the context object is in the HTML namespace and its node document is an HTML
    document, let name be converted to ASCII lowercase.

    Return the value of the first attribute in the context object's attribute list whose
    name is name, or null otherwise. 

Neither Presto nor WebKit actually do that yet, though we apparently do.

Ms2ger, are there tests for this in the W3C test suite?

In any case, I can certainly fix the patch to deal with that...

Comment 24

[Boris Zbarsky [:bzbarsky]]

Event simpler testcase that WebKit fails:

  var o = document.createElement("div");
  o.setAttributeNS("", "myAttrib2", "123");
  is(o.getAttribute("myAttrib2"), null, "Should not match non-lowercase attribute");

Comment 25

[Boris Zbarsky [:bzbarsky]]

So I'm fixing that by moving the check for lowercase up to the top of getAttribute.  It does mean that the call is a tiny bit slower, but I'm not sure how to make that better in this case.

I guess we could do it by storing a boolean on the element on the nsAttrAndChildArray if there were ever any non-lowercase attr names (or more precisely, non-canonical-case ones)....  If anyone thinks that's worth it, feel free!

Comment 26

[Boris Zbarsky [:bzbarsky]]

Oh, and this also means the approach of "Up-to-date attempt using ascii-insensitive compares" was definitely wrong.

Comment 27

[:Ms2ger (he/him; ⌚ UTC+1/+2)]

(In reply to Boris Zbarsky (:bz) from comment #23)
> Ah, so the problem there is that the element has an attribute with the name
> "myAttrib2" (with that casing).  When we call getAttribute("myAttrib2"), the
> old code lowercased it and hence got nothing, while the new code finds the
> attribute in question.
> 
> domcore says, as of today:
> 
>   The getAttribute(name) method must run these steps:
> 
>     If the context object is in the HTML namespace and its node document is
> an HTML
>     document, let name be converted to ASCII lowercase.
> 
>     Return the value of the first attribute in the context object's
> attribute list whose
>     name is name, or null otherwise. 
> 
> Neither Presto nor WebKit actually do that yet, though we apparently do.
> 
> Ms2ger, are there tests for this in the W3C test suite?

Yep, over at <http://w3c-test.org/webapps/DOMCore/tests/submissions/Ms2ger/attributes.html>.

Comment 28

[Olli Pettay [:smaug][[e-mail]]]

(In reply to Boris Zbarsky (:bz) from comment #26)
> Oh, and this also means the approach of "Up-to-date attempt using
> ascii-insensitive compares" was definitely wrong.

Yeah, unfortunately.

But DOM spec makes sense here. It is easy (although perhaps a bit slower for implementation) for everyone to understand.

Comment 29

[Boris Zbarsky [:bzbarsky]]

With the test bits fixed: https://hg.mozilla.org/integration/mozilla-inbound/rev/247fb4c3ad5f

Comment 30

[Olli Pettay [:smaug][[e-mail]]]

This got backed out https://hg.mozilla.org/mozilla-central/rev/d4e43a290fa7 because you forgot
to remove the MOZ_ASSERT from GetAttrValue

Comment 31

[Ryan VanderMeulen [:RyanVM]]

https://hg.mozilla.org/mozilla-central/rev/247fb4c3ad5f

Comment 32

[Olli Pettay [:smaug][[e-mail]]]

This is not fixed.

Comment 33

[Olli Pettay [:smaug][[e-mail]]]

Oops, my mistake. My local tree wasn't up-to-date