Bug 613595. Speed up the cache-hit case for getElementsByTagName. r=peterv
authorBoris Zbarsky <bzbarsky@mit.edu>
Tue, 23 Nov 2010 14:10:56 -0500
changeset 63637 17d2910e2941f992881812363ff677e91e5ccacf
parent 63636 ba272ca527136d9d02d6ac93055105174a5cdbf1
child 63638 77483e45592e8dc5dd1e45d40d30eb4101b5accf
push id19248
push usereakhgari@mozilla.com
push dateWed, 23 Mar 2011 23:19:35 +0000
treeherdermozilla-central@ab95ab9e389b [default view] [failures only]
perfherder[talos] [build metrics] [platform microbench] (compared to previous push)
reviewerspeterv
bugs613595
milestone2.0b13pre
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 613595. Speed up the cache-hit case for getElementsByTagName. r=peterv
content/base/src/nsContentList.cpp
content/base/src/nsContentList.h
content/base/src/nsDocument.cpp
content/base/src/nsDocument.h
content/base/src/nsGenericElement.cpp
content/html/document/src/nsHTMLDocument.cpp
--- a/content/base/src/nsContentList.cpp
+++ b/content/base/src/nsContentList.cpp
@@ -198,34 +198,30 @@ ContentListHashtableHashKey(PLDHashTable
 
 static PRBool
 ContentListHashtableMatchEntry(PLDHashTable *table,
                                const PLDHashEntryHdr *entry,
                                const void *key)
 {
   const ContentListHashEntry *e =
     static_cast<const ContentListHashEntry *>(entry);
-  const nsContentListKey* list1 = e->mContentList->GetKey();
-  const nsContentListKey* list2 = static_cast<const nsContentListKey *>(key);
+  const nsContentList* list = e->mContentList;
+  const nsContentListKey* ourKey = static_cast<const nsContentListKey *>(key);
 
-  return list1->Equals(*list2);
+  return list->MatchesKey(*ourKey);
 }
 
 already_AddRefed<nsContentList>
 NS_GetContentList(nsINode* aRootNode, 
                   PRInt32  aMatchNameSpaceId,
-                  nsIAtom* aHTMLMatchAtom,
-                  nsIAtom* aXMLMatchAtom)
+                  const nsAString& aTagname)
                   
 {
   NS_ASSERTION(aRootNode, "content list has to have a root");
 
-  if(!aXMLMatchAtom)
-    aXMLMatchAtom = aHTMLMatchAtom;
-
   nsContentList* list = nsnull;
 
   static PLDHashTableOps hash_table_ops =
   {
     PL_DHashAllocTable,
     PL_DHashFreeTable,
     ContentListHashtableHashKey,
     ContentListHashtableMatchEntry,
@@ -244,34 +240,42 @@ NS_GetContentList(nsINode* aRootNode,
     if (!success) {
       gContentListHashTable.ops = nsnull;
     }
   }
   
   ContentListHashEntry *entry = nsnull;
   // First we look in our hashtable.  Then we create a content list if needed
   if (gContentListHashTable.ops) {
-    nsContentListKey hashKey(aRootNode, aHTMLMatchAtom,
-                             aXMLMatchAtom, aMatchNameSpaceId);
+    nsContentListKey hashKey(aRootNode, aMatchNameSpaceId, aTagname);
     
     // A PL_DHASH_ADD is equivalent to a PL_DHASH_LOOKUP for cases
     // when the entry is already in the hashtable.
     entry = static_cast<ContentListHashEntry *>
                        (PL_DHashTableOperate(&gContentListHashTable,
-                                                &hashKey,
-                                                PL_DHASH_ADD));
+                                             &hashKey,
+                                             PL_DHASH_ADD));
     if (entry)
       list = entry->mContentList;
   }
 
   if (!list) {
     // We need to create a ContentList and add it to our new entry, if
     // we have an entry
+    nsCOMPtr<nsIAtom> xmlAtom = do_GetAtom(aTagname);
+    nsCOMPtr<nsIAtom> htmlAtom;
+    if (aMatchNameSpaceId == kNameSpaceID_Unknown) {
+      nsAutoString lowercaseName;
+      nsContentUtils::ASCIIToLower(aTagname, lowercaseName);
+      htmlAtom = do_GetAtom(lowercaseName);
+    } else {
+      htmlAtom = xmlAtom;
+    }
     list = new nsContentList(aRootNode, aMatchNameSpaceId,
-                             aHTMLMatchAtom, aXMLMatchAtom);
+                             htmlAtom, xmlAtom);
     if (entry) {
       entry->mContentList = list;
     }
   }
 
   NS_ADDREF(list);
 
   return list;
@@ -386,17 +390,20 @@ NS_GetFuncStringContentList(nsINode* aRo
 // nsContentList implementation
 
 nsContentList::nsContentList(nsINode* aRootNode,
                              PRInt32 aMatchNameSpaceId,
                              nsIAtom* aHTMLMatchAtom,
                              nsIAtom* aXMLMatchAtom,
                              PRBool aDeep)
   : nsBaseContentList(),
-    nsContentListKey(aRootNode, aHTMLMatchAtom, aXMLMatchAtom, aMatchNameSpaceId),
+    mRootNode(aRootNode),
+    mMatchNameSpaceId(aMatchNameSpaceId),
+    mHTMLMatchAtom(aHTMLMatchAtom),
+    mXMLMatchAtom(aXMLMatchAtom),
     mFunc(nsnull),
     mDestroyFunc(nsnull),
     mData(nsnull),
     mState(LIST_DIRTY),
     mDeep(aDeep),
     mFuncMayDependOnAttr(PR_FALSE)
 {
   NS_ASSERTION(mRootNode, "Must have root");
@@ -414,22 +421,25 @@ nsContentList::nsContentList(nsINode* aR
                              nsContentListMatchFunc aFunc,
                              nsContentListDestroyFunc aDestroyFunc,
                              void* aData,
                              PRBool aDeep,
                              nsIAtom* aMatchAtom,
                              PRInt32 aMatchNameSpaceId,
                              PRBool aFuncMayDependOnAttr)
   : nsBaseContentList(),
-    nsContentListKey(aRootNode, aMatchAtom, aMatchAtom, aMatchNameSpaceId),
+    mRootNode(aRootNode),
+    mMatchNameSpaceId(aMatchNameSpaceId),
+    mHTMLMatchAtom(aMatchAtom),
+    mXMLMatchAtom(aMatchAtom),
     mFunc(aFunc),
     mDestroyFunc(aDestroyFunc),
     mData(aData),
+    mState(LIST_DIRTY),
     mMatchAll(PR_FALSE),
-    mState(LIST_DIRTY),
     mDeep(aDeep),
     mFuncMayDependOnAttr(aFuncMayDependOnAttr)
 {
   NS_ASSERTION(mRootNode, "Must have root");
   mRootNode->AddMutationObserver(this);
 }
 
 nsContentList::~nsContentList()
@@ -902,18 +912,20 @@ nsContentList::RemoveFromHashtable()
   if (mFunc) {
     // This can't be in the table anyway
     return;
   }
   
   if (!gContentListHashTable.ops)
     return;
 
+  nsDependentAtomString str(mXMLMatchAtom);
+  nsContentListKey key(mRootNode, mMatchNameSpaceId, str);
   PL_DHashTableOperate(&gContentListHashTable,
-                       GetKey(),
+                       &key,
                        PL_DHASH_REMOVE);
 
   if (gContentListHashTable.entryCount == 0) {
     PL_DHashTableFinish(&gContentListHashTable);
     gContentListHashTable.ops = nsnull;
   }
 }
 
--- a/content/base/src/nsContentList.h
+++ b/content/base/src/nsContentList.h
@@ -135,63 +135,45 @@ public:
   nsFormContentList(nsIDOMHTMLFormElement *aForm,
                     nsBaseContentList& aContentList);
 };
 
 /**
  * Class that's used as the key to hash nsContentList implementations
  * for fast retrieval
  */
-class nsContentListKey
+struct nsContentListKey
 {
-public:
   nsContentListKey(nsINode* aRootNode,
-                   nsIAtom* aHTMLMatchAtom,
-                   nsIAtom* aXMLMatchAtom,
-                   PRInt32 aMatchNameSpaceId)
-    : mHTMLMatchAtom(aHTMLMatchAtom),
-      mXMLMatchAtom(aXMLMatchAtom),
+                   PRInt32 aMatchNameSpaceId,
+                   const nsAString& aTagname)
+    : mRootNode(aRootNode),
       mMatchNameSpaceId(aMatchNameSpaceId),
-      mRootNode(aRootNode)
-  {
-    NS_ASSERTION(!aXMLMatchAtom == !aHTMLMatchAtom, "Either neither or both atoms should be null");
-  }
-  
-  nsContentListKey(const nsContentListKey& aContentListKey)
-    : mHTMLMatchAtom(aContentListKey.mHTMLMatchAtom),
-      mXMLMatchAtom(aContentListKey.mXMLMatchAtom),
-      mMatchNameSpaceId(aContentListKey.mMatchNameSpaceId),
-      mRootNode(aContentListKey.mRootNode)
+      mTagname(aTagname)
   {
   }
 
-  PRBool Equals(const nsContentListKey& aContentListKey) const
+  nsContentListKey(const nsContentListKey& aContentListKey)
+    : mRootNode(aContentListKey.mRootNode),
+      mMatchNameSpaceId(aContentListKey.mMatchNameSpaceId),
+      mTagname(aContentListKey.mTagname)
   {
-    NS_ASSERTION(mHTMLMatchAtom == aContentListKey.mHTMLMatchAtom 
-                 || mXMLMatchAtom != aContentListKey.mXMLMatchAtom, "HTML atoms should match if XML atoms match");
-
-    return
-      mXMLMatchAtom == aContentListKey.mXMLMatchAtom &&
-      mMatchNameSpaceId == aContentListKey.mMatchNameSpaceId &&
-      mRootNode == aContentListKey.mRootNode;
   }
 
   inline PRUint32 GetHash(void) const
   {
     return
-      NS_PTR_TO_INT32(mXMLMatchAtom.get()) ^
+      HashString(mTagname) ^
       (NS_PTR_TO_INT32(mRootNode) << 12) ^
       (mMatchNameSpaceId << 24);
   }
   
-protected:
-  nsCOMPtr<nsIAtom> mHTMLMatchAtom;
-  nsCOMPtr<nsIAtom> mXMLMatchAtom;
-  PRInt32 mMatchNameSpaceId;
-  nsINode* mRootNode; // Weak ref
+  nsINode* const mRootNode; // Weak ref
+  const PRInt32 mMatchNameSpaceId;
+  const nsAString& mTagname;
 };
 
 /**
  * LIST_UP_TO_DATE means that the list is up to date and need not do
  * any walking to be able to answer any questions anyone may have.
  */
 #define LIST_UP_TO_DATE 0
 /**
@@ -209,17 +191,16 @@ protected:
  */
 #define LIST_LAZY 2
 
 /**
  * Class that implements a live NodeList that matches Elements in the
  * tree based on some criterion.
  */
 class nsContentList : public nsBaseContentList,
-                      protected nsContentListKey,
                       public nsIHTMLCollection,
                       public nsStubMutationObserver,
                       public nsWrapperCache
 {
 public:
   NS_DECL_ISUPPORTS_INHERITED
 
   /**
@@ -285,21 +266,16 @@ public:
                                     nsresult* aResult);
 
   // nsContentList public methods
   NS_HIDDEN_(nsINode*) GetParentObject() { return mRootNode; }
   NS_HIDDEN_(PRUint32) Length(PRBool aDoFlush);
   NS_HIDDEN_(nsIContent*) Item(PRUint32 aIndex, PRBool aDoFlush);
   NS_HIDDEN_(nsIContent*) NamedItem(const nsAString& aName, PRBool aDoFlush);
 
-  nsContentListKey* GetKey() {
-    return static_cast<nsContentListKey*>(this);
-  }
-  
-
   // nsIMutationObserver
   NS_DECL_NSIMUTATIONOBSERVER_ATTRIBUTECHANGED
   NS_DECL_NSIMUTATIONOBSERVER_CONTENTAPPENDED
   NS_DECL_NSIMUTATIONOBSERVER_CONTENTINSERTED
   NS_DECL_NSIMUTATIONOBSERVER_CONTENTREMOVED
   NS_DECL_NSIMUTATIONOBSERVER_NODEWILLBEDESTROYED
   
   static nsContentList* FromSupports(nsISupports* aSupports)
@@ -313,16 +289,29 @@ public:
       // question doesn't use the nsINodeList pointer as the nsISupports
       // pointer. That must be fixed, or we'll crash...
       NS_ASSERTION(list_qi == list, "Uh, fix QI!");
     }
 #endif
     return static_cast<nsContentList*>(list);
   }
 
+  PRBool MatchesKey(const nsContentListKey& aKey) const
+  {
+    // The root node is most commonly the same: the document.  And the
+    // most common namespace id is kNameSpaceID_Unknown.  So check the
+    // string first.
+    NS_PRECONDITION(mXMLMatchAtom,
+                    "How did we get here with a null match atom on our list?");
+    return
+      mXMLMatchAtom->Equals(aKey.mTagname) &&
+      mRootNode == aKey.mRootNode &&
+      mMatchNameSpaceId == aKey.mMatchNameSpaceId;
+  }
+
 protected:
   /**
    * Returns whether the element matches our criterion
    *
    * @param  aElement the element to attempt to match
    * @return whether we match
    */
   PRBool Match(mozilla::dom::Element *aElement);
@@ -383,16 +372,21 @@ protected:
    * To be called from non-destructor locations that want to remove from caches.
    * Needed because if subclasses want to have cache behavior they can't just
    * override RemoveFromHashtable(), since we call that in our destructor.
    */
   virtual void RemoveFromCaches() {
     RemoveFromHashtable();
   }
 
+  nsINode* mRootNode; // Weak ref
+  PRInt32 mMatchNameSpaceId;
+  nsCOMPtr<nsIAtom> mHTMLMatchAtom;
+  nsCOMPtr<nsIAtom> mXMLMatchAtom;
+
   /**
    * Function to use to determine whether a piece of content matches
    * our criterion
    */
   nsContentListMatchFunc mFunc;
   /**
    * Cleanup closure data with this.
    */
@@ -489,21 +483,25 @@ protected:
   virtual void RemoveFromCaches() {
     RemoveFromFuncStringHashtable();
   }
   void RemoveFromFuncStringHashtable();
 
   nsString mString;
 };
 
+// If aMatchNameSpaceId is kNameSpaceID_Unknown, this will return a
+// content list which matches ASCIIToLower(aTagname) against HTML
+// elements in HTML documents and aTagname against everything else.
+// For any other value of aMatchNameSpaceId, the list will match
+// aTagname against all elements.
 already_AddRefed<nsContentList>
 NS_GetContentList(nsINode* aRootNode,
                   PRInt32 aMatchNameSpaceId,
-                  nsIAtom* aHTMLMatchAtom,
-                  nsIAtom* aXMLMatchAtom = nsnull);
+                  const nsAString& aTagname);
 
 already_AddRefed<nsContentList>
 NS_GetFuncStringContentList(nsINode* aRootNode,
                             nsContentListMatchFunc aFunc,
                             nsContentListDestroyFunc aDestroyFunc,
                             nsFuncStringContentListDataAllocator aDataAllocator,
                             const nsAString& aString);
 #endif // nsContentList_h___
--- a/content/base/src/nsDocument.cpp
+++ b/content/base/src/nsDocument.cpp
@@ -4574,27 +4574,16 @@ nsDocument::CreateEntityReference(const 
                                   nsIDOMEntityReference** aReturn)
 {
   NS_ENSURE_ARG_POINTER(aReturn);
 
   *aReturn = nsnull;
   return NS_OK;
 }
 
-already_AddRefed<nsContentList>
-nsDocument::GetElementsByTagName(const nsAString& aTagname)
-{
-  nsAutoString lowercaseName;
-  nsContentUtils::ASCIIToLower(aTagname, lowercaseName);
-  nsCOMPtr<nsIAtom> xmlAtom = do_GetAtom(aTagname);
-  nsCOMPtr<nsIAtom> htmlAtom = do_GetAtom(lowercaseName);
-
-  return NS_GetContentList(this, kNameSpaceID_Unknown, htmlAtom, xmlAtom);
-}
-
 NS_IMETHODIMP
 nsDocument::GetElementsByTagName(const nsAString& aTagname,
                                  nsIDOMNodeList** aReturn)
 {
   nsRefPtr<nsContentList> list = GetElementsByTagName(aTagname);
   NS_ENSURE_TRUE(list, NS_ERROR_OUT_OF_MEMORY);
 
   // transfer ref to aReturn
@@ -4610,19 +4599,19 @@ nsDocument::GetElementsByTagNameNS(const
 
   if (!aNamespaceURI.EqualsLiteral("*")) {
     nsresult rv =
       nsContentUtils::NameSpaceManager()->RegisterNameSpace(aNamespaceURI,
                                                             nameSpaceId);
     NS_ENSURE_SUCCESS(rv, nsnull);
   }
 
-  nsCOMPtr<nsIAtom> nameAtom = do_GetAtom(aLocalName);
-
-  return NS_GetContentList(this, nameSpaceId, nameAtom);
+  NS_ASSERTION(nameSpaceId != kNameSpaceID_Unknown, "Unexpected namespace ID!");
+
+  return NS_GetContentList(this, nameSpaceId, aLocalName);
 }
 
 NS_IMETHODIMP
 nsDocument::GetElementsByTagNameNS(const nsAString& aNamespaceURI,
                                    const nsAString& aLocalName,
                                    nsIDOMNodeList** aReturn)
 {
   nsRefPtr<nsContentList> list = GetElementsByTagNameNS(aNamespaceURI,
@@ -5179,17 +5168,17 @@ nsDocument::GetTitleContent(PRUint32 aNa
   // <title> element has been bound to this document. So if it's false,
   // we know there is nothing to do here. This avoids us having to search
   // the whole DOM if someone calls document.title on a large document
   // without a title.
   if (!mMayHaveTitleElement)
     return nsnull;
 
   nsRefPtr<nsContentList> list =
-    NS_GetContentList(this, aNamespace, nsGkAtoms::title);
+    NS_GetContentList(this, aNamespace, NS_LITERAL_STRING("title"));
 
   return list->Item(0, PR_FALSE);
 }
 
 void
 nsDocument::GetTitleFromElement(PRUint32 aNamespace, nsAString& aTitle)
 {
   nsIContent* title = GetTitleContent(aNamespace);
@@ -7468,17 +7457,17 @@ nsDocument::OnPageShow(PRBool aPersisted
   EnumerateFreezableElements(NotifyActivityChanged, nsnull);
   EnumerateExternalResources(NotifyPageShow, &aPersisted);
 
   Element* root = GetRootElement();
   if (aPersisted && root) {
     // Send out notifications that our <link> elements are attached.
     nsRefPtr<nsContentList> links = NS_GetContentList(root,
                                                       kNameSpaceID_Unknown,
-                                                      nsGkAtoms::link);
+                                                      NS_LITERAL_STRING("link"));
 
     PRUint32 linkCount = links->Length(PR_TRUE);
     for (PRUint32 i = 0; i < linkCount; ++i) {
       nsCOMPtr<nsILink> link = do_QueryInterface(links->Item(i, PR_FALSE));
       if (link) {
         link->LinkAdded();
       }
     }
@@ -7520,17 +7509,17 @@ nsDocument::OnPageHide(PRBool aPersisted
                        nsIDOMEventTarget* aDispatchStartTarget)
 {
   // Send out notifications that our <link> elements are detached,
   // but only if this is not a full unload.
   Element* root = GetRootElement();
   if (aPersisted && root) {
     nsRefPtr<nsContentList> links = NS_GetContentList(root,
                                                       kNameSpaceID_Unknown,
-                                                      nsGkAtoms::link);
+                                                      NS_LITERAL_STRING("link"));
 
     PRUint32 linkCount = links->Length(PR_TRUE);
     for (PRUint32 i = 0; i < linkCount; ++i) {
       nsCOMPtr<nsILink> link = do_QueryInterface(links->Item(i, PR_FALSE));
       if (link) {
         link->LinkRemoved();
       }
     }
--- a/content/base/src/nsDocument.h
+++ b/content/base/src/nsDocument.h
@@ -973,17 +973,19 @@ public:
   void AsyncBlockOnload();
 
   virtual void SetScrollToRef(nsIURI *aDocumentURI);
   virtual void ScrollToRef();
   virtual void ResetScrolledToRefAlready();
   virtual void SetChangeScrollPosWhenScrollingToRef(PRBool aValue);
 
   already_AddRefed<nsContentList>
-    GetElementsByTagName(const nsAString& aTagName);
+  GetElementsByTagName(const nsAString& aTagName) {
+    return NS_GetContentList(this, kNameSpaceID_Unknown, aTagName);
+  }
   already_AddRefed<nsContentList>
     GetElementsByTagNameNS(const nsAString& aNamespaceURI,
                            const nsAString& aLocalName);
 
   virtual Element *GetElementById(const nsAString& aElementId);
 
   virtual Element *LookupImageElement(const nsAString& aElementId);
 
--- a/content/base/src/nsGenericElement.cpp
+++ b/content/base/src/nsGenericElement.cpp
@@ -2553,23 +2553,18 @@ nsGenericElement::RemoveAttributeNode(ns
 
   return rv;
 }
 
 nsresult
 nsGenericElement::GetElementsByTagName(const nsAString& aTagname,
                                        nsIDOMNodeList** aReturn)
 {
-  nsAutoString lowercaseName;
-  nsContentUtils::ASCIIToLower(aTagname, lowercaseName);
-  nsCOMPtr<nsIAtom> XMLAtom = do_GetAtom(aTagname);
-  nsCOMPtr<nsIAtom> HTMLAtom = do_GetAtom(lowercaseName);
-
   nsContentList *list = NS_GetContentList(this, kNameSpaceID_Unknown, 
-                                          HTMLAtom, XMLAtom).get();
+                                          aTagname).get();
 
   // transfer ref to aReturn
   *aReturn = list;
   return NS_OK;
 }
 
 nsresult
 nsGenericElement::GetAttributeNS(const nsAString& aNamespaceURI,
@@ -2685,19 +2680,19 @@ nsGenericElement::GetElementsByTagNameNS
 
   if (!aNamespaceURI.EqualsLiteral("*")) {
     nsresult rv =
       nsContentUtils::NameSpaceManager()->RegisterNameSpace(aNamespaceURI,
                                                             nameSpaceId);
     NS_ENSURE_SUCCESS(rv, rv);
   }
 
-  nsCOMPtr<nsIAtom> nameAtom = do_GetAtom(aLocalName);
-
-  nsContentList *list = NS_GetContentList(this, nameSpaceId, nameAtom).get();
+  NS_ASSERTION(nameSpaceId != kNameSpaceID_Unknown, "Unexpected namespace ID!");
+
+  nsContentList *list = NS_GetContentList(this, nameSpaceId, aLocalName).get();
 
   // transfer ref to aReturn
   *aReturn = list;
   return NS_OK;
 }
 
 nsresult
 nsGenericElement::HasAttribute(const nsAString& aName, PRBool* aReturn)
--- a/content/html/document/src/nsHTMLDocument.cpp
+++ b/content/html/document/src/nsHTMLDocument.cpp
@@ -1532,17 +1532,17 @@ nsHTMLDocument::GetBody(nsresult *aResul
   if (body) {
     // There is a body element, return that as the body.
     return body;
   }
 
   // The document is most likely a frameset document so look for the
   // outer most frameset element
   nsRefPtr<nsContentList> nodeList =
-    NS_GetContentList(this, kNameSpaceID_XHTML, nsGkAtoms::frameset);
+    NS_GetContentList(this, kNameSpaceID_XHTML, NS_LITERAL_STRING("frameset"));
 
   return nodeList->GetNodeAt(0);
 }
 
 NS_IMETHODIMP
 nsHTMLDocument::GetBody(nsIDOMHTMLElement** aBody)
 {
   *aBody = nsnull;