The default bug view has changed. See this FAQ.

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

RESOLVED FIXED in mozilla16

Status

()

Core
DOM
P1
normal
RESOLVED FIXED
7 years ago
5 years ago

People

(Reporter: bz, Assigned: bz)

Tracking

(Blocks: 1 bug, {perf})

Trunk
mozilla16
Points:
---
Dependency tree / graph
Bug Flags:
in-testsuite -

Firefox Tracking Flags

(blocking2.0 -)

Details

Attachments

(5 attachments, 1 obsolete attachment)

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.
Agreed, and I think we should do both the no colon case and lowercase fast paths. I think Jonas has a plan here...
Assignee: nobody → jonas
Keywords: perf
OS: Mac OS X → All
Hardware: x86 → All
Created attachment 462285 [details] [diff] [review]
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.
Hmm.  With that patch, getAttribute on an HTML div from script seems to call nsGenericElement::GetAttribute, not nsGenericHTMLElement::GetAttribute.
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.
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).
Created attachment 462320 [details] [diff] [review]
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.
> > 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
Created attachment 462353 [details] [diff] [review]
Alternative patch for avoiding buffer copy for lowercase strings.

Here's what I tried.
Created attachment 462354 [details] [diff] [review]
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).
Attachment #462353 - Attachment description: Alternative patch → Alternative patch for avoiding buffer copy for lowercase strings.
(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.
Yeah, all the string ctors and dtors show up pretty badly in the profiles (when the testcase is using strings alot).
Right, ideally we'd fix it everywhere by making the string stuff (constructor and SetLength) cheap.
> 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.
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.
Group: mozilla-confidential
Group: mozilla-confidential
Over to bz who at this point has a better idea of what's going on here in the various patches.
Assignee: jonas → bzbarsky
Priority: -- → P1
blocking2.0: --- → ?
blocking2.0: ? → -
Blocks: 570602
Blocks: 772466
Created attachment 642044 [details] [diff] [review]
Up-to-date attempt using ascii-insensitive compares.
Created attachment 642058 [details] [diff] [review]
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.
Attachment #642058 - Flags: review?(bugs)
Attachment #642044 - Attachment is obsolete: true
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
Attachment #642058 - Flags: review?(bugs) → review+
> 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.
https://hg.mozilla.org/integration/mozilla-inbound/rev/d49beb57db23
Flags: in-testsuite-
Target Milestone: --- → mozilla16
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
Target Milestone: mozilla16 → ---
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.
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...
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");
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!
Oh, and this also means the approach of "Up-to-date attempt using ascii-insensitive compares" was definitely wrong.
(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>.
(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.
With the test bits fixed: https://hg.mozilla.org/integration/mozilla-inbound/rev/247fb4c3ad5f
This got backed out https://hg.mozilla.org/mozilla-central/rev/d4e43a290fa7 because you forgot
to remove the MOZ_ASSERT from GetAttrValue
https://hg.mozilla.org/mozilla-central/rev/247fb4c3ad5f
Status: NEW → RESOLVED
Last Resolved: 5 years ago
Resolution: --- → FIXED
Target Milestone: --- → mozilla16
This is not fixed.
Status: RESOLVED → REOPENED
Resolution: FIXED → ---
Oops, my mistake. My local tree wasn't up-to-date
Status: REOPENED → RESOLVED
Last Resolved: 5 years ago5 years ago
Resolution: --- → FIXED
You need to log in before you can comment on or make changes to this bug.