Bug 89783 – REGRESSION(r120979): getElementsByTagName is 12% slower

• Component: DOM
• Status: RESOLVED FIXED

[Ryosuke Niwa]

Bindings/get-elements-by-tag-name:
http://webkit-perf.appspot.com/graph.html#tests=[[3030063,2001,3001]]&sel=1340301988349.4067,1340400396485&displayrange=7&datatype=running

Dromaeo/dom-query:
http://webkit-perf.appspot.com/graph.html#tests=[[33030,2001,3001]]&sel=1340301988349.4067,1340400396485&displayrange=7&datatype=running

[Ryosuke Niwa]

r120978:

rniwa-macpro:webkit3 rniwa$ Tools/Scripts/run-perf-tests PerformanceTests/Bindings/get-elements-by-tag-name.html
Running 1 tests
Running Bindings/get-elements-by-tag-name.html (1 of 1)
DESCRIPTION: This benchmark covers 'getElementsByTagName (not in document)', 'getElementsByTagName', 'getElementsByName (not in document)' and 'getElementsByName' in Dromaeo/dom-query.html, and other DOM methods that return a NodeList.
RESULT Bindings: get-elements-by-tag-name= 202.852774047 runs/s
median= 202.78833967 runs/s, stdev= 0.179787510207 runs/s, min= 202.53164557 runs/s, max= 203.303684879 runs/s

rniwa-macpro:webkit3 rniwa$ Tools/Scripts/run-perf-tests PerformanceTests/Bindings/get-elements-by-tag-name.html
Running 1 tests
Running Bindings/get-elements-by-tag-name.html (1 of 1)
DESCRIPTION: This benchmark covers 'getElementsByTagName (not in document)', 'getElementsByTagName', 'getElementsByName (not in document)' and 'getElementsByName' in Dromaeo/dom-query.html, and other DOM methods that return a NodeList.
RESULT Bindings: get-elements-by-tag-name= 211.241877558 runs/s
median= 211.64021164 runs/s, stdev= 1.18863533758 runs/s, min= 206.451612903 runs/s, max= 212.201591512 runs/s

rniwa-macpro:webkit3 rniwa$ Tools/Scripts/run-perf-tests PerformanceTests/Bindings/get-elements-by-tag-name.html
Running 1 tests
Running Bindings/get-elements-by-tag-name.html (1 of 1)
DESCRIPTION: This benchmark covers 'getElementsByTagName (not in document)', 'getElementsByTagName', 'getElementsByName (not in document)' and 'getElementsByName' in Dromaeo/dom-query.html, and other DOM methods that return a NodeList.
RESULT Bindings: get-elements-by-tag-name= 209.901121292 runs/s
median= 211.081794195 runs/s, stdev= 3.60176160791 runs/s, min= 196.319018405 runs/s, max= 212.201591512 runs/s



r120979 with my patch I'm about to post

rniwa-macpro:webkit rniwa$ Tools/Scripts/run-perf-tests PerformanceTests/Bindings/get-elements-by-tag-name.html
Running 1 tests
Running Bindings/get-elements-by-tag-name.html (1 of 1)
DESCRIPTION: This benchmark covers 'getElementsByTagName (not in document)', 'getElementsByTagName', 'getElementsByName (not in document)' and 'getElementsByName' in Dromaeo/dom-query.html, and other DOM methods that return a NodeList.
RESULT Bindings: get-elements-by-tag-name= 211.632166697 runs/s
median= 211.360634082 runs/s, stdev= 0.777945237496 runs/s, min= 210.803689065 runs/s, max= 213.77672209 runs/s
 
rniwa-macpro:webkit rniwa$ Tools/Scripts/run-perf-tests PerformanceTests/Bindings/get-elements-by-tag-name.html
Running 1 tests
Running Bindings/get-elements-by-tag-name.html (1 of 1)
DESCRIPTION: This benchmark covers 'getElementsByTagName (not in document)', 'getElementsByTagName', 'getElementsByName (not in document)' and 'getElementsByName' in Dromaeo/dom-query.html, and other DOM methods that return a NodeList.
RESULT Bindings: get-elements-by-tag-name= 214.982647722 runs/s
median= 215.462156943 runs/s, stdev= 3.92329100174 runs/s, min= 209.973753281 runs/s, max= 220.048899756 runs/s

rniwa-macpro:webkit rniwa$ Tools/Scripts/run-perf-tests PerformanceTests/Bindings/get-elements-by-tag-name.html
Running 1 tests
Running Bindings/get-elements-by-tag-name.html (1 of 1)
DESCRIPTION: This benchmark covers 'getElementsByTagName (not in document)', 'getElementsByTagName', 'getElementsByName (not in document)' and 'getElementsByName' in Dromaeo/dom-query.html, and other DOM methods that return a NodeList.
RESULT Bindings: get-elements-by-tag-name= 214.561723123 runs/s
median= 213.191300488 runs/s, stdev= 3.90098642596 runs/s, min= 210.526315789 runs/s, max= 221.13022113 runs/s

[Ryosuke Niwa]

Created attachment 149106 [details]
Regain the performance by creating a custom hash function

[Ryosuke Niwa]

Comment on attachment 149106 [details]
Regain the performance by creating a custom hash function

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

> Source/WebCore/dom/NodeRareData.h:66
> +        return WTF::DefaultHash<StringType>::Hash::hash(entry.name) + entry.type;

We can call IntHash on entry.type if we wanted since type is known at compilation time.

[Erik Arvidsson]

Comment on attachment 149106 [details]
Regain the performance by creating a custom hash function

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

> Source/WebCore/dom/NodeRareData.h:48
> +    NodeListMapEntry(DynamicNodeList::NodeListType type, const AtomicString& name)

Shouldn't this be StringType& instead of AtomicString& ?

> Source/WebCore/dom/NodeRareData.h:55
> +        return name == other.name && type == other.type;

Reorder?

[Ryosuke Niwa]

(In reply to comment #4)
> (From update of attachment 149106 [details])
> View in context: https://bugs.webkit.org/attachment.cgi?id=149106&action=review
> 
> > Source/WebCore/dom/NodeRareData.h:48
> > +    NodeListMapEntry(DynamicNodeList::NodeListType type, const AtomicString& name)
> 
> Shouldn't this be StringType& instead of AtomicString& ?

Oops, nice catch!

> > Source/WebCore/dom/NodeRareData.h:55
> > +        return name == other.name && type == other.type;
> 
> Reorder?

Done.

[Ryosuke Niwa]

Created attachment 149116 [details]
Fixed per Erik's comment

[Ryosuke Niwa]

Created attachment 149122 [details]
Fix a bad merge

[Darin Adler]

Comment on attachment 149122 [details]
Fix a bad merge

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

Does this other optimizations, or is it really the hash function that’s the issue? It it’s just the hash function, then you can do a much smaller patch.

We can supply a custom hash function for the pairs in those maps without using a custom class instead of pair. The hash function struct is passed as the third argument to the HashMap class template. We can even make a single struct for both types of pairs, using function overloading or even function templates.

I have various review comments on the hash traits if you do want to make a custom class, but I am not sure you need one.

> Source/WebCore/dom/NodeRareData.h:58
> +    unsigned char type;

Do we get higher performance here by using an unsigned char rather than an unsigned?

[Ryosuke Niwa]

(In reply to comment #8)
> Does this other optimizations, or is it really the hash function that’s the issue? It it’s just the hash function, then you can do a much smaller patch.

My understanding is that the hash function is the issue.

> We can supply a custom hash function for the pairs in those maps without using a custom class instead of pair. The hash function struct is passed as the third argument to the HashMap class template. We can even make a single struct for both types of pairs, using function overloading or even function templates.

Ah, that's a good point. I can try that later.

> > Source/WebCore/dom/NodeRareData.h:58
> > +    unsigned char type;
> 
> Do we get higher performance here by using an unsigned char rather than an unsigned?

I don't think so but we wouldn't need unsigned int anyways.

[Ryosuke Niwa]

Created attachment 149167 [details]
Patch

[Darin Adler]

Comment on attachment 149167 [details]
Patch

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

A few things that still look like mistakes.

> Source/WebCore/dom/NodeRareData.h:62
> +    template <typename StringType>
> +    struct NodeListCacheMapEntryHash {
> +        static unsigned hash(const std::pair<StringType, unsigned char>& entry)
> +        {
> +            return WTF::DefaultHash<StringType>::Hash::hash(entry.first) + entry.second;
> +        }
> +
> +        static bool equal(const std::pair<StringType, unsigned char>& a, const std::pair<StringType, unsigned char>& b) { return a == b; }
> +
> +        static const bool safeToCompareToEmptyOrDeleted = WTF::DefaultHash<StringType>::Hash::safeToCompareToEmptyOrDeleted;
> +    };

We could make this smaller by deriving from WTF::PairHash and overriding only the hash function. There is no need to write a custom equal function or to set safeToCompareEmptyOrDeleted if we derive.

There is no need for the WTF:: prefix in WTF::DefaultHash; it can just be DefaultHash.

> Source/WebCore/dom/NodeRareData.h:64
> +    typedef HashMap<std::pair<AtomicString, unsigned char>, DynamicSubtreeNodeList*, NodeListCacheMapEntryHash<AtomicString> > NodeListAtomicNameCacheMap;

Why did we reorder the pair to put the string first? Why did we change from unsigned short to unsigned char. Maybe those are good changes, but nothing here says they were intentional or helpful changes.

> Source/WebCore/dom/NodeRareData.h:169
> -    std::pair<unsigned short, AtomicString> namedNodeListKey(DynamicNodeList::NodeListType listType, const AtomicString& name)
> +    std::pair<AtomicString, unsigned short> namedNodeListKey(DynamicNodeList::NodeListType listType, const AtomicString& name)
>      {
> -        return std::pair<unsigned short, AtomicString>(listType, name);
> +        return std::pair<AtomicString, unsigned short>(name, listType);
>      }

We changed the maps to use unsigned char, but for some reason left it unsigned short here. That will result in conversions. I suggest just leaving this all alone, or making the types consistent if there is a good reason to change that.

[Ryosuke Niwa]

(In reply to comment #11)
> (From update of attachment 149167 [details])
> View in context: https://bugs.webkit.org/attachment.cgi?id=149167&action=review
> 
> A few things that still look like mistakes.
> 
> > Source/WebCore/dom/NodeRareData.h:62
> > +    template <typename StringType>
> > +    struct NodeListCacheMapEntryHash {
> > +        static unsigned hash(const std::pair<StringType, unsigned char>& entry)
> > +        {
> > +            return WTF::DefaultHash<StringType>::Hash::hash(entry.first) + entry.second;
> > +        }
> > +
> > +        static bool equal(const std::pair<StringType, unsigned char>& a, const std::pair<StringType, unsigned char>& b) { return a == b; }
> > +
> > +        static const bool safeToCompareToEmptyOrDeleted = WTF::DefaultHash<StringType>::Hash::safeToCompareToEmptyOrDeleted;
> > +    };
> 
> We could make this smaller by deriving from WTF::PairHash and overriding only the hash function. There is no need to write a custom equal function or to set safeToCompareEmptyOrDeleted if we derive.

Unfortunately not because hash traits isn't defined for unsigned char. It was also the reason I used unsigned short in the original patch.

> There is no need for the WTF:: prefix in WTF::DefaultHash; it can just be DefaultHash.

Fixed.

> > Source/WebCore/dom/NodeRareData.h:64
> > +    typedef HashMap<std::pair<AtomicString, unsigned char>, DynamicSubtreeNodeList*, NodeListCacheMapEntryHash<AtomicString> > NodeListAtomicNameCacheMap;
> 
> Why did we reorder the pair to put the string first? Why did we change from unsigned short to unsigned char. Maybe those are good changes, but nothing here says they were intentional or helpful changes.

Oops, that's a left-over from my old patch. Fixed.

> > Source/WebCore/dom/NodeRareData.h:169
> > -    std::pair<unsigned short, AtomicString> namedNodeListKey(DynamicNodeList::NodeListType listType, const AtomicString& name)
> > +    std::pair<AtomicString, unsigned short> namedNodeListKey(DynamicNodeList::NodeListType listType, const AtomicString& name)
> >      {
> > -        return std::pair<unsigned short, AtomicString>(listType, name);
> > +        return std::pair<AtomicString, unsigned short>(name, listType);
> >      }
> 
> We changed the maps to use unsigned char, but for some reason left it unsigned short here. That will result in conversions. I suggest just leaving this all alone, or making the types consistent if there is a good reason to change that.

Oops, that explains a slight slowdown (1-2%) from my previous patch. Fixed.

[Ryosuke Niwa]

Created attachment 149178 [details]
Patch for landing

[WebKit Review Bot]

Comment on attachment 149178 [details]
Patch for landing

Clearing flags on attachment: 149178

Committed r121103: <http://trac.webkit.org/changeset/121103>

[WebKit Review Bot]

All reviewed patches have been landed.  Closing bug.

[Ryosuke Niwa]

Build fix landed in http://trac.webkit.org/changeset/121105.