- Revision
- 119330
- Author
- [email protected]
- Date
- 2012-06-02 12:23:25 -0700 (Sat, 02 Jun 2012)
Log Message
[Performance] Optimize querySelector() by caching SelectorQuery objects
https://bugs.webkit.org/show_bug.cgi?id=87942
Reviewed by Antti Koivisto.
This patch improves performance of Node::querySelector() by 7.1x in Safari/Mac
and by 8.5x in Chromium/Linux.
Performance test: Parser/query-selector-first.html, Parser/query-selector-last.html
[query-selector-first.html]
Safari/Mac 264.97 runs/s => 1872.78 runs/s (7.06x speed-up)
Chromium/Linux 244.84 runs/s => 2071.60 runs/s (8.46x speed-up)
[query-selector-last.html]
Safari/Mac 393.73 runs/s => 466.05 runs/s (1.18x speed-up)
Chromium/Linux 401.15 runs/s => 484.45 runs/s (1.20x speed-up)
Previously Node::querySelector() and Node::querySelectorAll() had been
parsing CSS queries every time. This patch optimizes the performance by caching
parsed results onto a Document.
The cache is invalidated when any of CSS related variables is updated.
As per the current implementation of CSSParserContext::operator==(), the CSS related
variables are as follows:
- baseURI
- charset
- mode
- isHTMLDocument
- isCSSCustomFilterEnabled
- isCSSRegionsEnabled
- needsSiteSpecificQuirks
- enforcesCSSMIMETypeInNoQuirksMode
Actually, we do not need to watch all of these variables:
- The current implementation does not watch the change of charset.
charset is always set to a null String by CSSParserContext::CSSParserContext().
- isHTMLDocument never changes.
- isCSSCustomFilterEnabled, isCSSRegionsEnabled, needsSiteSpecificQuirks and
enforcesCSSMIMETypeInNoQuirksMode are not flipped in a user scenario.
If someone changes them, it would be reasonable to expect them
to take the effect only on subsequent document loads.
Thus we do not need to invalidate the cache when these variables are updated.
Consequently, the condition under which we have to invalidate the cache is
that any of the following variables is updated:
- baseURI
- mode
Tests: fast/dom/SelectorAPI/*. No change in test results.
* dom/SelectorQuery.h: SelectorQueryCache is a cache from CSS selectors to parsed results.
SelectorQueryCache::Entry is an entry of the cache.
SelectorQueryCache::Entry holds a SelectorQuery object and a CSSSelectorList object.
The reason why SelectorQueryCache::Entry needs to hold the CSSSelectorList object
is that the CSSSelectorList object keeps the lifetime of CSSSelector objects
in the SelectorQuery object. Since the SelectorQuery object just holds pointers
to CSSSelector objects, the CSSSelectorList object must not be destructed
before the SelectorQuery object is destructed.
(WebCore):
(SelectorDataList):
(WebCore::SelectorQuery::SelectorQuery):
(SelectorQuery):
(SelectorQueryCache):
(WebCore::SelectorQueryCache::SelectorQueryCache):
(Entry):
(WebCore::SelectorQueryCache::Entry::selectorQuery):
* dom/SelectorQuery.cpp:
(WebCore::SelectorQuery::initialize):
(WebCore::SelectorQueryCache::Entry::Entry):
(WebCore::SelectorQueryCache::add): Returns a cached SelectorQuery object if any.
Otherwise, parses a given CSS selector, creates a SelectorQuery object,
adds the SelectorQuery object to a new entry in the cache, returns the SelectorQuery
object.
(WebCore::SelectorQueryCache::invalidate): Clears the cache.
* dom/Document.h:
(WebCore):
(Document):
* dom/Document.cpp:
(WebCore::Document::selectorQueryCache):
(WebCore):
(WebCore::Document::setCompatibilityMode): Invalidates the cache
when m_compatibilityMode is updated.
(WebCore::Document::updateBaseURL): Invalidates the cache
when m_baseURL is updated.
* dom/Node.h: Changed String to AtomicString, since the key of the cache
should be AtomicString.
(Node):
* dom/Node.cpp: Optimized the code by using the cache.
(WebCore::Node::querySelector):
(WebCore::Node::querySelectorAll):
Modified Paths
Diff
Modified: trunk/Source/WebCore/ChangeLog (119329 => 119330)
--- trunk/Source/WebCore/ChangeLog 2012-06-02 19:05:37 UTC (rev 119329)
+++ trunk/Source/WebCore/ChangeLog 2012-06-02 19:23:25 UTC (rev 119330)
@@ -1,3 +1,104 @@
+2012-06-02 Kentaro Hara <[email protected]>
+
+ [Performance] Optimize querySelector() by caching SelectorQuery objects
+ https://bugs.webkit.org/show_bug.cgi?id=87942
+
+ Reviewed by Antti Koivisto.
+
+ This patch improves performance of Node::querySelector() by 7.1x in Safari/Mac
+ and by 8.5x in Chromium/Linux.
+
+ Performance test: Parser/query-selector-first.html, Parser/query-selector-last.html
+
+ [query-selector-first.html]
+ Safari/Mac 264.97 runs/s => 1872.78 runs/s (7.06x speed-up)
+ Chromium/Linux 244.84 runs/s => 2071.60 runs/s (8.46x speed-up)
+
+ [query-selector-last.html]
+ Safari/Mac 393.73 runs/s => 466.05 runs/s (1.18x speed-up)
+ Chromium/Linux 401.15 runs/s => 484.45 runs/s (1.20x speed-up)
+
+ Previously Node::querySelector() and Node::querySelectorAll() had been
+ parsing CSS queries every time. This patch optimizes the performance by caching
+ parsed results onto a Document.
+
+ The cache is invalidated when any of CSS related variables is updated.
+ As per the current implementation of CSSParserContext::operator==(), the CSS related
+ variables are as follows:
+
+ - baseURI
+ - charset
+ - mode
+ - isHTMLDocument
+ - isCSSCustomFilterEnabled
+ - isCSSRegionsEnabled
+ - needsSiteSpecificQuirks
+ - enforcesCSSMIMETypeInNoQuirksMode
+
+ Actually, we do not need to watch all of these variables:
+
+ - The current implementation does not watch the change of charset.
+ charset is always set to a null String by CSSParserContext::CSSParserContext().
+
+ - isHTMLDocument never changes.
+
+ - isCSSCustomFilterEnabled, isCSSRegionsEnabled, needsSiteSpecificQuirks and
+ enforcesCSSMIMETypeInNoQuirksMode are not flipped in a user scenario.
+ If someone changes them, it would be reasonable to expect them
+ to take the effect only on subsequent document loads.
+ Thus we do not need to invalidate the cache when these variables are updated.
+
+ Consequently, the condition under which we have to invalidate the cache is
+ that any of the following variables is updated:
+
+ - baseURI
+ - mode
+
+ Tests: fast/dom/SelectorAPI/*. No change in test results.
+
+ * dom/SelectorQuery.h: SelectorQueryCache is a cache from CSS selectors to parsed results.
+ SelectorQueryCache::Entry is an entry of the cache.
+ SelectorQueryCache::Entry holds a SelectorQuery object and a CSSSelectorList object.
+ The reason why SelectorQueryCache::Entry needs to hold the CSSSelectorList object
+ is that the CSSSelectorList object keeps the lifetime of CSSSelector objects
+ in the SelectorQuery object. Since the SelectorQuery object just holds pointers
+ to CSSSelector objects, the CSSSelectorList object must not be destructed
+ before the SelectorQuery object is destructed.
+ (WebCore):
+ (SelectorDataList):
+ (WebCore::SelectorQuery::SelectorQuery):
+ (SelectorQuery):
+ (SelectorQueryCache):
+ (WebCore::SelectorQueryCache::SelectorQueryCache):
+ (Entry):
+ (WebCore::SelectorQueryCache::Entry::selectorQuery):
+ * dom/SelectorQuery.cpp:
+ (WebCore::SelectorQuery::initialize):
+ (WebCore::SelectorQueryCache::Entry::Entry):
+ (WebCore::SelectorQueryCache::add): Returns a cached SelectorQuery object if any.
+ Otherwise, parses a given CSS selector, creates a SelectorQuery object,
+ adds the SelectorQuery object to a new entry in the cache, returns the SelectorQuery
+ object.
+ (WebCore::SelectorQueryCache::invalidate): Clears the cache.
+
+ * dom/Document.h:
+ (WebCore):
+ (Document):
+ * dom/Document.cpp:
+ (WebCore::Document::selectorQueryCache):
+ (WebCore):
+ (WebCore::Document::setCompatibilityMode): Invalidates the cache
+ when m_compatibilityMode is updated.
+ (WebCore::Document::updateBaseURL): Invalidates the cache
+ when m_baseURL is updated.
+
+ * dom/Node.h: Changed String to AtomicString, since the key of the cache
+ should be AtomicString.
+ (Node):
+ * dom/Node.cpp: Optimized the code by using the cache.
+ (WebCore::Node::querySelector):
+ (WebCore::Node::querySelectorAll):
+
2012-06-02 Dan Bernstein <[email protected]>
Reverted the last change.
Modified: trunk/Source/WebCore/dom/Document.cpp (119329 => 119330)
--- trunk/Source/WebCore/dom/Document.cpp 2012-06-02 19:05:37 UTC (rev 119329)
+++ trunk/Source/WebCore/dom/Document.cpp 2012-06-02 19:23:25 UTC (rev 119330)
@@ -140,6 +140,7 @@
#include "SecurityOrigin.h"
#include "SecurityPolicy.h"
#include "SegmentedString.h"
+#include "SelectorQuery.h"
#include "Settings.h"
#include "ShadowRoot.h"
#include "StaticHashSetNodeList.h"
@@ -731,6 +732,13 @@
m_elementsByAccessKey.clear();
}
+SelectorQueryCache* Document::selectorQueryCache()
+{
+ if (!m_selectorQueryCache)
+ m_selectorQueryCache = adoptPtr(new SelectorQueryCache());
+ return m_selectorQueryCache.get();
+}
+
MediaQueryMatcher* Document::mediaQueryMatcher()
{
if (!m_mediaQueryMatcher)
@@ -745,6 +753,7 @@
ASSERT(!m_styleSheets->length());
bool wasInQuirksMode = inQuirksMode();
m_compatibilityMode = mode;
+ selectorQueryCache()->invalidate();
if (inQuirksMode() != wasInQuirksMode) {
// All user stylesheets have to reparse using the different mode.
clearPageUserSheet();
@@ -2653,6 +2662,7 @@
// so we use a null base URL.
m_baseURL = KURL(KURL(), documentURI());
}
+ selectorQueryCache()->invalidate();
if (!m_baseURL.isValid())
m_baseURL = KURL();
Modified: trunk/Source/WebCore/dom/Document.h (119329 => 119330)
--- trunk/Source/WebCore/dom/Document.h 2012-06-02 19:05:37 UTC (rev 119329)
+++ trunk/Source/WebCore/dom/Document.h 2012-06-02 19:23:25 UTC (rev 119330)
@@ -123,6 +123,7 @@
class ScriptElementData;
class ScriptRunner;
class SecurityOrigin;
+class SelectorQueryCache;
class SerializedScriptValue;
class SegmentedString;
class Settings;
@@ -269,6 +270,8 @@
Element* getElementByAccessKey(const String& key);
void invalidateAccessKeyMap();
+ SelectorQueryCache* selectorQueryCache();
+
// DOM methods & attributes for Document
DEFINE_ATTRIBUTE_EVENT_LISTENER(abort);
@@ -1451,6 +1454,8 @@
HashMap<StringImpl*, Element*, CaseFoldingHash> m_elementsByAccessKey;
bool m_accessKeyMapValid;
+ OwnPtr<SelectorQueryCache> m_selectorQueryCache;
+
bool m_useSecureKeyboardEntryWhenActive;
bool m_isXHTML;
Modified: trunk/Source/WebCore/dom/Node.cpp (119329 => 119330)
--- trunk/Source/WebCore/dom/Node.cpp 2012-06-02 19:05:37 UTC (rev 119329)
+++ trunk/Source/WebCore/dom/Node.cpp 2012-06-02 19:23:25 UTC (rev 119330)
@@ -1672,54 +1672,30 @@
return list.release();
}
-PassRefPtr<Element> Node::querySelector(const String& selectors, ExceptionCode& ec)
+PassRefPtr<Element> Node::querySelector(const AtomicString& selectors, ExceptionCode& ec)
{
if (selectors.isEmpty()) {
ec = SYNTAX_ERR;
return 0;
}
- CSSParser parser(document());
- CSSSelectorList querySelectorList;
- parser.parseSelector(selectors, querySelectorList);
- if (!querySelectorList.first() || querySelectorList.hasUnknownPseudoElements()) {
- ec = SYNTAX_ERR;
+ SelectorQuery* selectorQuery = document()->selectorQueryCache()->add(selectors, document(), ec);
+ if (!selectorQuery)
return 0;
- }
-
- // throw a NAMESPACE_ERR if the selector includes any namespace prefixes.
- if (querySelectorList.selectorsNeedNamespaceResolution()) {
- ec = NAMESPACE_ERR;
- return 0;
- }
-
- SelectorQuery selectorQuery(querySelectorList);
- return selectorQuery.queryFirst(this);
+ return selectorQuery->queryFirst(this);
}
-PassRefPtr<NodeList> Node::querySelectorAll(const String& selectors, ExceptionCode& ec)
+PassRefPtr<NodeList> Node::querySelectorAll(const AtomicString& selectors, ExceptionCode& ec)
{
if (selectors.isEmpty()) {
ec = SYNTAX_ERR;
return 0;
}
- CSSParser p(document());
- CSSSelectorList querySelectorList;
- p.parseSelector(selectors, querySelectorList);
- if (!querySelectorList.first() || querySelectorList.hasUnknownPseudoElements()) {
- ec = SYNTAX_ERR;
+ SelectorQuery* selectorQuery = document()->selectorQueryCache()->add(selectors, document(), ec);
+ if (!selectorQuery)
return 0;
- }
-
- // Throw a NAMESPACE_ERR if the selector includes any namespace prefixes.
- if (querySelectorList.selectorsNeedNamespaceResolution()) {
- ec = NAMESPACE_ERR;
- return 0;
- }
-
- SelectorQuery selectorQuery(querySelectorList);
- return selectorQuery.queryAll(this);
+ return selectorQuery->queryAll(this);
}
Document *Node::ownerDocument() const
Modified: trunk/Source/WebCore/dom/Node.h (119329 => 119330)
--- trunk/Source/WebCore/dom/Node.h 2012-06-02 19:05:37 UTC (rev 119329)
+++ trunk/Source/WebCore/dom/Node.h 2012-06-02 19:23:25 UTC (rev 119330)
@@ -577,8 +577,8 @@
PassRefPtr<NodeList> getElementsByName(const String& elementName);
PassRefPtr<NodeList> getElementsByClassName(const String& classNames);
- PassRefPtr<Element> querySelector(const String& selectors, ExceptionCode&);
- PassRefPtr<NodeList> querySelectorAll(const String& selectors, ExceptionCode&);
+ PassRefPtr<Element> querySelector(const AtomicString& selectors, ExceptionCode&);
+ PassRefPtr<NodeList> querySelectorAll(const AtomicString& selectors, ExceptionCode&);
unsigned short compareDocumentPosition(Node*);
Modified: trunk/Source/WebCore/dom/SelectorQuery.cpp (119329 => 119330)
--- trunk/Source/WebCore/dom/SelectorQuery.cpp 2012-06-02 19:05:37 UTC (rev 119329)
+++ trunk/Source/WebCore/dom/SelectorQuery.cpp 2012-06-02 19:23:25 UTC (rev 119330)
@@ -26,10 +26,12 @@
#include "config.h"
#include "SelectorQuery.h"
+#include "CSSParser.h"
#include "CSSSelectorList.h"
#include "Document.h"
#include "StaticNodeList.h"
#include "StyledElement.h"
+#include <wtf/HashMap.h>
namespace WebCore {
@@ -37,11 +39,6 @@
{
}
-SelectorDataList::SelectorDataList(const CSSSelectorList& selectorList)
-{
- initialize(selectorList);
-}
-
void SelectorDataList::initialize(const CSSSelectorList& selectorList)
{
ASSERT(m_selectors.isEmpty());
@@ -146,12 +143,11 @@
}
}
-SelectorQuery::SelectorQuery(const CSSSelectorList& selectorList)
- : m_selectors(selectorList)
+void SelectorQuery::initialize(const CSSSelectorList& selectorList)
{
+ m_selectors.initialize(selectorList);
}
-
PassRefPtr<NodeList> SelectorQuery::queryAll(Node* rootNode) const
{
SelectorChecker selectorChecker(rootNode->document(), !rootNode->document()->inQuirksMode());
@@ -166,4 +162,41 @@
return m_selectors.queryFirst(selectorChecker, rootNode);
}
+SelectorQueryCache::Entry::Entry(CSSSelectorList& querySelectorList) : m_querySelectorList(querySelectorList)
+{
+ m_selectorQuery.initialize(m_querySelectorList);
}
+
+SelectorQuery* SelectorQueryCache::add(const AtomicString& selectors, Document* document, ExceptionCode& ec)
+{
+ HashMap<AtomicString, OwnPtr<SelectorQueryCache::Entry> >::iterator it = m_entries.find(selectors);
+ if (it != m_entries.end())
+ return it->second->selectorQuery();
+
+ CSSParser parser(document);
+ CSSSelectorList querySelectorList;
+ parser.parseSelector(selectors, querySelectorList);
+
+ if (!querySelectorList.first() || querySelectorList.hasUnknownPseudoElements()) {
+ ec = SYNTAX_ERR;
+ return 0;
+ }
+
+ // throw a NAMESPACE_ERR if the selector includes any namespace prefixes.
+ if (querySelectorList.selectorsNeedNamespaceResolution()) {
+ ec = NAMESPACE_ERR;
+ return 0;
+ }
+
+ OwnPtr<SelectorQueryCache::Entry> entry = adoptPtr(new SelectorQueryCache::Entry(querySelectorList));
+ SelectorQuery* selectorQuery = entry->selectorQuery();
+ m_entries.add(selectors, entry.release());
+ return selectorQuery;
+}
+
+void SelectorQueryCache::invalidate()
+{
+ m_entries.clear();
+}
+
+}
Modified: trunk/Source/WebCore/dom/SelectorQuery.h (119329 => 119330)
--- trunk/Source/WebCore/dom/SelectorQuery.h 2012-06-02 19:05:37 UTC (rev 119329)
+++ trunk/Source/WebCore/dom/SelectorQuery.h 2012-06-02 19:23:25 UTC (rev 119330)
@@ -26,21 +26,22 @@
#ifndef SelectorQuery_h
#define SelectorQuery_h
+#include "CSSSelectorList.h"
#include "SelectorChecker.h"
#include <wtf/Vector.h>
namespace WebCore {
+
+typedef int ExceptionCode;
+class CSSSelector;
+class Element;
class Node;
class NodeList;
-class Element;
-class CSSSelector;
-class CSSSelectorList;
class SelectorDataList {
public:
SelectorDataList();
- explicit SelectorDataList(const CSSSelectorList&);
void initialize(const CSSSelectorList&);
@@ -67,14 +68,43 @@
class SelectorQuery {
WTF_MAKE_NONCOPYABLE(SelectorQuery);
public:
- SelectorQuery(const CSSSelectorList&);
-
+ SelectorQuery() { };
+ void initialize(const CSSSelectorList&);
PassRefPtr<NodeList> queryAll(Node* rootNode) const;
PassRefPtr<Element> queryFirst(Node* rootNode) const;
private:
SelectorDataList m_selectors;
};
+class SelectorQueryCache {
+ WTF_MAKE_NONCOPYABLE(SelectorQueryCache);
+ WTF_MAKE_FAST_ALLOCATED;
+public:
+ SelectorQueryCache() { };
+
+ SelectorQuery* add(const AtomicString&, Document*, ExceptionCode&);
+ void invalidate();
+
+private:
+
+ class Entry {
+ WTF_MAKE_NONCOPYABLE(Entry);
+ WTF_MAKE_FAST_ALLOCATED;
+ public:
+ explicit Entry(CSSSelectorList&);
+ SelectorQuery* selectorQuery() { return &m_selectorQuery; };
+
+ private:
+ // m_querySelectorList keeps the lifetime of CSSSelectors in m_selectorQuery.
+ // Since m_selectorQuery just holds pointers to CSSSelector objects,
+ // m_querySelectorList must not be destructed before m_selectorQuery is destructed.
+ CSSSelectorList m_querySelectorList;
+ SelectorQuery m_selectorQuery;
+ };
+
+ HashMap<AtomicString, OwnPtr<SelectorQueryCache::Entry> > m_entries;
+};
+
}
#endif
