Attachment #149167 for bug #89783

View Details Raw Unified Return to Bug 89783

| Differences between



2012-06-23  Ryosuke Niwa  <rniwa@webkit.org>

        REGRESSION(r120979): getElementsByTagName is 12% slower
        https://bugs.webkit.org/show_bug.cgi?id=89783

        Reviewed by NOBODY (OOPS!).

        The problem is that hashing std::pair<unsigned short, AtomicString> is very slow compared to just hashing AtomicString,
        which internally holds a hash already. Fixed the regression by replacing the default hash function by the one that
        computes AtomicString's hash + list type. This is okay because we only have 7 node list types at the moment.

        * dom/NodeRareData.h:
        (NodeListsNodeData):
        (WebCore::NodeListsNodeData::NodeListCacheMapEntryHash::hash):
        (NodeListCacheMapEntryHash):
        (WebCore::NodeListsNodeData::NodeListCacheMapEntryHash::equal):
        (WebCore::NodeListsNodeData::namedNodeListKey):

2012-06-22  Benjamin Poulain  <bpoulain@apple.com>

        Text with text-overflow:ellipsis and text-align:right is left aligned



class NodeListsNodeData {
    WTF_MAKE_NONCOPYABLE(NodeListsNodeData); WTF_MAKE_FAST_ALLOCATED;
public:
    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;
    };

    typedef HashMap<std::pair<AtomicString, unsigned char>, DynamicSubtreeNodeList*, NodeListCacheMapEntryHash<AtomicString> > NodeListAtomicNameCacheMap;
    typedef HashMap<std::pair<String, unsigned char>, DynamicSubtreeNodeList*, NodeListCacheMapEntryHash<String> > NodeListNameCacheMap;
    typedef HashMap<QualifiedName, TagNodeList*> TagNodeListCacheNS;

    template<typename T>

private:
    NodeListsNodeData() { }

    std::pair<AtomicString, unsigned short> namedNodeListKey(DynamicNodeList::NodeListType listType, const AtomicString& name)
    {
        return std::pair<AtomicString, unsigned short>(name, listType);
    }

    std::pair<String, unsigned short> namedNodeListKey(DynamicNodeList::NodeListType listType, const String& name)
    {
        return std::pair<String, unsigned short>(name, listType);
    }

    NodeListAtomicNameCacheMap m_atomicNameCaches;

Return to Bug 89783

Lines 49-56 class TreeScope; Source/WebCore/dom/NodeRareData.h_sec1
- Source/WebCore/dom/NodeRareData.h -6 / +18 lines
49	class NodeListsNodeData {	49	class NodeListsNodeData {
50	WTF_MAKE_NONCOPYABLE(NodeListsNodeData); WTF_MAKE_FAST_ALLOCATED;	50	WTF_MAKE_NONCOPYABLE(NodeListsNodeData); WTF_MAKE_FAST_ALLOCATED;
51	public:	51	public:
52	typedef HashMap<std::pair<unsigned short, AtomicString>, DynamicSubtreeNodeList*> NodeListAtomicNameCacheMap;	52	template <typename StringType>
53	typedef HashMap<std::pair<unsigned short, String>, DynamicSubtreeNodeList*> NodeListNameCacheMap;	53	struct NodeListCacheMapEntryHash {
		54	static unsigned hash(const std::pair<StringType, unsigned char>& entry)
		55	{
		56	return WTF::DefaultHash<StringType>::Hash::hash(entry.first) + entry.second;
		57	}
		58
		59	static bool equal(const std::pair<StringType, unsigned char>& a, const std::pair<StringType, unsigned char>& b) { return a == b; }
		60
		61	static const bool safeToCompareToEmptyOrDeleted = WTF::DefaultHash<StringType>::Hash::safeToCompareToEmptyOrDeleted;
		62	};
		63
		64	typedef HashMap<std::pair<AtomicString, unsigned char>, DynamicSubtreeNodeList*, NodeListCacheMapEntryHash<AtomicString> > NodeListAtomicNameCacheMap;
		65	typedef HashMap<std::pair<String, unsigned char>, DynamicSubtreeNodeList*, NodeListCacheMapEntryHash<String> > NodeListNameCacheMap;
54	typedef HashMap<QualifiedName, TagNodeList*> TagNodeListCacheNS;	66	typedef HashMap<QualifiedName, TagNodeList*> TagNodeListCacheNS;
55		67
56	template<typename T>	68	template<typename T>
Lines 151-164 public: Source/WebCore/dom/NodeRareData.h_sec2
151	private:	163	private:
152	NodeListsNodeData() { }	164	NodeListsNodeData() { }
153		165
154	std::pair<unsigned short, AtomicString> namedNodeListKey(DynamicNodeList::NodeListType listType, const AtomicString& name)	166	std::pair<AtomicString, unsigned short> namedNodeListKey(DynamicNodeList::NodeListType listType, const AtomicString& name)
155	{	167	{
156	return std::pair<unsigned short, AtomicString>(listType, name);	168	return std::pair<AtomicString, unsigned short>(name, listType);
157	}	169	}
158		170
159	std::pair<unsigned short, String> namedNodeListKey(DynamicNodeList::NodeListType listType, const String& name)	171	std::pair<String, unsigned short> namedNodeListKey(DynamicNodeList::NodeListType listType, const String& name)
160	{	172	{
161	return std::pair<unsigned short, String>(listType, name);	173	return std::pair<String, unsigned short>(name, listType);
162	}	174	}
163		175
164	NodeListAtomicNameCacheMap m_atomicNameCaches;	176	NodeListAtomicNameCacheMap m_atomicNameCaches;

Lines 1-3 Source/WebCore/ChangeLog_sec1
- Source/WebCore/ChangeLog +18 lines
		1	2012-06-23 Ryosuke Niwa <rniwa@webkit.org>
		2
		3	REGRESSION(r120979): getElementsByTagName is 12% slower
		4	https://bugs.webkit.org/show_bug.cgi?id=89783
		5
		6	Reviewed by NOBODY (OOPS!).
		7
		8	The problem is that hashing std::pair<unsigned short, AtomicString> is very slow compared to just hashing AtomicString,
		9	which internally holds a hash already. Fixed the regression by replacing the default hash function by the one that
		10	computes AtomicString's hash + list type. This is okay because we only have 7 node list types at the moment.
		11
		12	* dom/NodeRareData.h:
		13	(NodeListsNodeData):
		14	(WebCore::NodeListsNodeData::NodeListCacheMapEntryHash::hash):
		15	(NodeListCacheMapEntryHash):
		16	(WebCore::NodeListsNodeData::NodeListCacheMapEntryHash::equal):
		17	(WebCore::NodeListsNodeData::namedNodeListKey):
		18
1	2012-06-22 Benjamin Poulain <bpoulain@apple.com>	19	2012-06-22 Benjamin Poulain <bpoulain@apple.com>
2		20
3	Text with text-overflow:ellipsis and text-align:right is left aligned	21	Text with text-overflow:ellipsis and text-align:right is left aligned