Bug 863966 - Improve perf of querySelector by caching selector list. r=bz
authorMina Almasry <almasry.mina@gmail.com>
Wed, 09 Oct 2013 09:20:45 -0400
changeset 150197 965b4f247f4b5dd67da46877855b59c524bff7e0
parent 150196 bfbd9429912734609cfccbd36af388749920f505
child 150198 6512d20b7d6f59f701a8e170d7630c40c3e6155e
push id34776
push userryanvm@gmail.com
push dateWed, 09 Oct 2013 13:21:57 +0000
treeherdermozilla-inbound@994c850a583a [default view] [failures only]
perfherder[talos] [build metrics] [platform microbench] (compared to previous push)
reviewersbz
bugs863966
milestone27.0a1
first release with
nightly linux32
nightly linux64
nightly mac
nightly win32
nightly win64
last release without
nightly linux32
nightly linux64
nightly mac
nightly win32
nightly win64
Bug 863966 - Improve perf of querySelector by caching selector list. r=bz
content/base/public/nsIDocument.h
content/base/src/nsDocument.cpp
content/base/src/nsINode.cpp
xpcom/ds/nsExpirationTracker.h
--- a/content/base/public/nsIDocument.h
+++ b/content/base/public/nsIDocument.h
@@ -22,16 +22,18 @@
 #include "nsINode.h"                     // for base class
 #include "nsIScriptGlobalObject.h"       // for member (in nsCOMPtr)
 #include "nsIStructuredCloneContainer.h" // for member (in nsCOMPtr)
 #include "nsPIDOMWindow.h"               // for use in inline functions
 #include "nsPropertyTable.h"             // for member
 #include "nsTHashtable.h"                // for member
 #include "mozilla/dom/DocumentBinding.h"
 #include "Units.h"
+#include "nsExpirationTracker.h"
+#include "nsClassHashtable.h"
 
 class imgIRequest;
 class nsAString;
 class nsBindingManager;
 class nsCSSStyleSheet;
 class nsDOMNavigationTiming;
 class nsDOMTouchList;
 class nsEventStates;
@@ -75,16 +77,17 @@ class nsSMILAnimationController;
 class nsStyleSet;
 class nsTextNode;
 class nsWindowSizes;
 class nsSmallVoidArray;
 class nsDOMCaretPosition;
 class nsViewportInfo;
 class nsDOMEvent;
 class nsIGlobalObject;
+class nsCSSSelectorList;
 
 namespace mozilla {
 class ErrorResult;
 
 namespace css {
 class Loader;
 class ImageLoader;
 } // namespace css
@@ -655,17 +658,71 @@ public:
 
   bool DidDocumentOpen() {
     return mDidDocumentOpen;
   }
 
 protected:
   virtual Element *GetRootElementInternal() const = 0;
 
+private:
+  class SelectorCacheKey
+  {
+    public:
+      SelectorCacheKey(const nsAString& aString) : mKey(aString)
+      {
+        MOZ_COUNT_CTOR(SelectorCacheKey);
+      }
+
+      nsString mKey;
+      nsExpirationState mState;
+
+      nsExpirationState* GetExpirationState() { return &mState; }
+
+      ~SelectorCacheKey()
+      {
+        MOZ_COUNT_DTOR(SelectorCacheKey);
+      }
+  };
+
+  class SelectorCacheKeyDeleter;
+
 public:
+  class SelectorCache MOZ_FINAL
+    : public nsExpirationTracker<SelectorCacheKey, 4>
+  {
+    public:
+      SelectorCache();
+
+      // CacheList takes ownership of aSelectorList.
+      void CacheList(const nsAString& aSelector, nsCSSSelectorList* aSelectorList);
+
+      virtual void NotifyExpired(SelectorCacheKey* aSelector) MOZ_OVERRIDE;
+
+      // We do not call MarkUsed because it would just slow down lookups and
+      // because we're OK expiring things after a few seconds even if they're
+      // being used.
+      nsCSSSelectorList* GetList(const nsAString& aSelector)
+      {
+        return mTable.Get(aSelector);
+      }
+
+      ~SelectorCache()
+      {
+        AgeAllGenerations();
+      }
+
+    private:
+      nsClassHashtable<nsStringHashKey, nsCSSSelectorList> mTable;
+  };
+
+  SelectorCache& GetSelectorCache()
+  {
+    return mSelectorCache;
+  }
   // Get the root <html> element, or return null if there isn't one (e.g.
   // if the root isn't <html>)
   Element* GetHtmlElement() const;
   // Returns the first child of GetHtmlContent which has the given tag,
   // or nullptr if that doesn't exist.
   Element* GetHtmlChildElement(nsIAtom* aTag);
   // Get the canonical <body> element, or return null if there isn't one (e.g.
   // if the root isn't <html> or if the <body> isn't there)
@@ -2128,16 +2185,17 @@ public:
 
   virtual nsHTMLDocument* AsHTMLDocument() { return nullptr; }
 
   virtual JSObject* WrapObject(JSContext *aCx,
                                JS::Handle<JSObject*> aScope) MOZ_OVERRIDE;
 
 private:
   uint64_t mWarnedAbout;
+  SelectorCache mSelectorCache;
 
 protected:
   ~nsIDocument();
   nsPropertyTable* GetExtraPropertyTable(uint16_t aCategory);
 
   // Never ever call this. Only call GetWindow!
   virtual nsPIDOMWindow *GetWindowInternal() const = 0;
 
--- a/content/base/src/nsDocument.cpp
+++ b/content/base/src/nsDocument.cpp
@@ -1310,16 +1310,59 @@ nsDOMStyleSheetSetList::GetSets(nsTArray
       return NS_ERROR_OUT_OF_MEMORY;
     }
   }
 
   return NS_OK;
 }
 
 // ==================================================================
+nsIDocument::SelectorCache::SelectorCache()
+  : nsExpirationTracker<SelectorCacheKey, 4>(1000) { }
+
+// CacheList takes ownership of aSelectorList.
+void nsIDocument::SelectorCache::CacheList(const nsAString& aSelector,
+                                           nsCSSSelectorList* aSelectorList)
+{
+  SelectorCacheKey* key = new SelectorCacheKey(aSelector);
+  mTable.Put(key->mKey, aSelectorList);
+  AddObject(key);
+}
+
+class nsIDocument::SelectorCacheKeyDeleter MOZ_FINAL : public nsRunnable
+{
+public:
+  explicit SelectorCacheKeyDeleter(SelectorCacheKey* aToDelete)
+    : mSelector(aToDelete)
+  {
+    MOZ_COUNT_CTOR(SelectorCacheKeyDeleter);
+  }
+
+  ~SelectorCacheKeyDeleter()
+  {
+    MOZ_COUNT_DTOR(SelectorCacheKeyDeleter);
+  }
+
+  NS_IMETHOD Run()
+  {
+    return NS_OK;
+  }
+
+private:
+  nsAutoPtr<SelectorCacheKey> mSelector;
+};
+
+void nsIDocument::SelectorCache::NotifyExpired(SelectorCacheKey* aSelector)
+{
+  RemoveObject(aSelector);
+  mTable.Remove(aSelector->mKey);
+  nsCOMPtr<nsIRunnable> runnable = new SelectorCacheKeyDeleter(aSelector);
+  NS_DispatchToCurrentThread(runnable);
+}
+
 
 struct nsIDocument::FrameRequest
 {
   FrameRequest(const FrameRequestCallbackHolder& aCallback,
                int32_t aHandle) :
     mCallback(aCallback),
     mHandle(aHandle)
   {}
--- a/content/base/src/nsINode.cpp
+++ b/content/base/src/nsINode.cpp
@@ -2332,31 +2332,40 @@ AddScopeElements(TreeMatchContext& aMatc
 
 // Actually find elements matching aSelectorList (which must not be
 // null) and which are descendants of aRoot and put them in aList.  If
 // onlyFirstMatch, then stop once the first one is found.
 template<bool onlyFirstMatch, class T>
 inline static nsresult
 FindMatchingElements(nsINode* aRoot, const nsAString& aSelector, T &aList)
 {
-  nsAutoPtr<nsCSSSelectorList> selectorList;
-  nsresult rv = ParseSelectorList(aRoot, aSelector,
-                                  getter_Transfers(selectorList));
-  if (NS_FAILED(rv)) {
-    // We hit this for syntax errors, which are quite common, so don't
-    // use NS_ENSURE_SUCCESS.  (For example, jQuery has an extended set
-    // of selectors, but it sees if we can parse them first.)
-    return rv;
+
+  nsIDocument* doc = aRoot->OwnerDoc();
+  nsIDocument::SelectorCache& cache = doc->GetSelectorCache();
+  nsCSSSelectorList* selectorList = cache.GetList(aSelector);
+
+  if (!selectorList) {
+    nsresult rv = ParseSelectorList(aRoot, aSelector,
+                                    &selectorList);
+    if (NS_FAILED(rv)) {
+      delete selectorList;
+      // We hit this for syntax errors, which are quite common, so don't
+      // use NS_ENSURE_SUCCESS.  (For example, jQuery has an extended set
+      // of selectors, but it sees if we can parse them first.)
+      return rv;
+    }
+
+    NS_ENSURE_TRUE(selectorList, NS_OK);
+
+    cache.CacheList(aSelector, selectorList);
   }
-  NS_ENSURE_TRUE(selectorList, NS_OK);
 
   NS_ASSERTION(selectorList->mSelectors,
                "How can we not have any selectors?");
 
-  nsIDocument* doc = aRoot->OwnerDoc();
   TreeMatchContext matchingContext(false, nsRuleWalker::eRelevantLinkUnvisited,
                                    doc, TreeMatchContext::eNeverMatchVisited);
   doc->FlushPendingLinkUpdates();
   AddScopeElements(matchingContext, aRoot);
 
   // Fast-path selectors involving IDs.  We can only do this if aRoot
   // is in the document and the document is not in quirks mode, since
   // ID selectors are case-insensitive in quirks mode.  Also, only do
--- a/xpcom/ds/nsExpirationTracker.h
+++ b/xpcom/ds/nsExpirationTracker.h
@@ -291,16 +291,17 @@ template <class T, uint32_t K> class nsE
       void Init(nsExpirationTracker<T,K> *obj) {
         mOwner = obj;
         nsCOMPtr<nsIObserverService> obs = mozilla::services::GetObserverService();
         if (obs) {
           obs->AddObserver(this, "memory-pressure", false);
         }
       }
       void Destroy() {
+        mOwner = nullptr;
         nsCOMPtr<nsIObserverService> obs = mozilla::services::GetObserverService();
         if (obs)
           obs->RemoveObserver(this, "memory-pressure");
       }
       NS_DECL_ISUPPORTS
       NS_DECL_NSIOBSERVER
     private:
       nsExpirationTracker<T,K> *mOwner;
@@ -329,17 +330,17 @@ template <class T, uint32_t K> class nsE
 };
 
 template<class T, uint32_t K>
 NS_IMETHODIMP
 nsExpirationTracker<T, K>::ExpirationTrackerObserver::Observe(nsISupports     *aSubject,
                                                               const char      *aTopic,
                                                               const PRUnichar *aData)
 {
-  if (!strcmp(aTopic, "memory-pressure"))
+  if (!strcmp(aTopic, "memory-pressure") && mOwner)
     mOwner->AgeAllGenerations();
   return NS_OK;
 }
 
 template <class T, uint32_t K>
 NS_IMETHODIMP_(nsrefcnt)
 nsExpirationTracker<T,K>::ExpirationTrackerObserver::AddRef(void)
 {