Bug 99394 - Optimize QualifiedName-as-hash-key scenario.
Summary: Optimize QualifiedName-as-hash-key scenario.
Status: RESOLVED FIXED
Alias: None
Product: WebKit
Classification: Unclassified
Component: DOM (show other bugs)
Version: 528+ (Nightly build)
Hardware: Unspecified Unspecified
: P2 Normal
Assignee: Andreas Kling
URL:
Keywords:
Depends on:
Blocks: 98798
  Show dependency treegraph
 
Reported: 2012-10-15 17:24 PDT by Andreas Kling
Modified: 2012-10-22 14:29 PDT (History)
7 users (show)

See Also:


Attachments
Proposed patch (5.36 KB, patch)
2012-10-15 17:28 PDT, Andreas Kling
andersca: review+
Details | Formatted Diff | Diff

Note You need to log in before you can comment on or make changes to this bug.
Description Andreas Kling 2012-10-15 17:24:45 PDT
Using QualifiedName as the key type in WTF hash tables is currently a lot less efficient than it could be.
Comment 1 Andreas Kling 2012-10-15 17:26:01 PDT
In the RoboHornet svgresize.html benchmark, I'm seeing ~200ms below QualifiedName instantiation and hash lookups on my MBP. I have a patch to cut this in half.
Comment 2 Andreas Kling 2012-10-15 17:28:14 PDT
Created attachment 168815 [details]
Proposed patch
Comment 3 Eric Seidel (no email) 2012-10-15 18:27:47 PDT
There is some debate as to if we should even be using QualifiedNames here.  anyQName() is this odd hack that we seem to use to be the "null" QualifiedName, and it's basically only used for SVG code:
http://code.google.com/p/chromium/source/search?q=anyQName&origq=anyQName&btnG=Search+Trunk

I think this patch is totally reasonable, and I can see it being a huge speed win.  I'm just not sure if the concept of a null QualifieName (or using QualfiedName in a hash) even makes sense as we currently do it.
Comment 4 Eric Seidel (no email) 2012-10-15 18:28:41 PDT
This patch makes me wonder if we shouldn't just ditch anyQName in prefernce for this nullQName anyway. :)
Comment 5 Philip Rogers 2012-10-15 18:43:52 PDT
Love this patch. Nice work!
Comment 6 Darin Adler 2012-10-15 19:58:29 PDT
Comment on attachment 168815 [details]
Proposed patch

View in context: https://bugs.webkit.org/attachment.cgi?id=168815&action=review

> Source/WebCore/dom/QualifiedName.h:134
> +            QualifiedNameComponents c = { name->m_prefix.impl(), name->m_localName.impl(), name->m_namespace.impl() };
> +            name->m_existingHash = hashComponents(c);

I think it’d be nice to have this part be out of line to keep the inlined code tighter. Worth testing to see if it makes things faster or slower. If it’s not slower, we should do it.

Also, I’d name the local variable something other than c.

> Source/WebCore/svg/SVGElement.h:164
> +            QualifiedNameComponents c = { nullAtom.impl(), key.localName().impl(), key.namespaceURI().impl() };
> +            return hashComponents(c);

It’s be nice to name this something other than c.

I think we could cache this no-prefix form of the qualified name too; just add another field to QualifiedName for that.
Comment 7 Darin Adler 2012-10-15 20:02:41 PDT
Comment on attachment 168815 [details]
Proposed patch

View in context: https://bugs.webkit.org/attachment.cgi?id=168815&action=review

> Source/WebCore/ChangeLog:3
> +        Clean up QualifiedName-as-hash-key scenario.

I would call this “optimize” not “clean up”.
Comment 8 Maciej Stachowiak 2012-10-15 21:12:13 PDT
anyQName is super mysterious to me. From the name and the "*" strings in it, I would expect it to have some sort of wildcard semantic, but it doesn't really. I wonder if Hyatt remembers what it's for?
Comment 9 Eric Seidel (no email) 2012-10-16 00:37:30 PDT
Oddly enough anyQName was added by hyatt!  http://trac.webkit.org/changeset/9824  Just hijacked by SVG for null purposes. :(
Comment 10 Maciej Stachowiak 2012-10-16 01:07:17 PDT
(In reply to comment #9)
> Oddly enough anyQName was added by hyatt!  http://trac.webkit.org/changeset/9824  Just hijacked by SVG for null purposes. :(

Indeed, I remembered that he added it because I reviewed that patch. But I do not remember the original purpose.
Comment 11 Andreas Kling 2012-10-20 16:12:43 PDT
Committed <http://trac.webkit.org/changeset/131993>
(Darn, forgot to change the bug title in the ChangeLog.)
Comment 12 Philip Rogers 2012-10-22 14:29:38 PDT
(In reply to comment #11)
> Committed <http://trac.webkit.org/changeset/131993>
> (Darn, forgot to change the bug title in the ChangeLog.)

This progression is visible in various webkit-perf graphs (bigger is better):
http://webkit-perf.appspot.com/graph.html#tests=[[8195914,2001,173262]]&sel=1350758073445.8484,1350797740907.5178,0.9000000000000004,6&displayrange=7&datatype=running

Nice work!