Replace nsRuleList with a next sibling pointer on the rule node itself (saving one word in the normal linked list case, and wasting one in the hash table case). (Bug 439184.) r+sr=bzbarsky
authorL. David Baron <dbaron@dbaron.org>
Sun, 13 Jul 2008 13:57:38 -0700
changeset 15903 5b6fa5bcaccd17c95bafe39667f1b0e90817e9d4
parent 15902 a00c120d4a6e06d98392980a30a4754435b1b1bf
child 15904 571dbbcf60bf079667fc6f99c382850d1ab45014
push id592
push userdbaron@mozilla.com
push dateSun, 13 Jul 2008 20:58:08 +0000
treeherdermozilla-central@6a513bc88338 [default view] [failures only]
perfherder[talos] [build metrics] [platform microbench] (compared to previous push)
bugs439184
milestone1.9.1a1pre
Replace nsRuleList with a next sibling pointer on the rule node itself (saving one word in the normal linked list case, and wasting one in the hash table case). (Bug 439184.) r+sr=bzbarsky
layout/style/nsRuleNode.cpp
layout/style/nsRuleNode.h
--- a/layout/style/nsRuleNode.cpp
+++ b/layout/style/nsRuleNode.cpp
@@ -64,57 +64,16 @@
 #include "nsSize.h"
 #include "imgIRequest.h"
 #include "nsRuleData.h"
 #include "nsILanguageAtomService.h"
 #include "nsIStyleRule.h"
 #include "nsBidiUtils.h"
 
 /*
- * For storage of an |nsRuleNode|'s children in a linked list.
- */
-struct nsRuleList {
-  nsRuleNode* mRuleNode;
-  nsRuleList* mNext;
-  
-public:
-  nsRuleList(nsRuleNode* aNode, nsRuleList* aNext= nsnull) {
-    MOZ_COUNT_CTOR(nsRuleList);
-    mRuleNode = aNode;
-    mNext = aNext;
-  }
- 
-  ~nsRuleList() {
-    MOZ_COUNT_DTOR(nsRuleList);
-    mRuleNode->Destroy();
-    if (mNext)
-      mNext->Destroy(mNext->mRuleNode->mPresContext);
-  }
-
-  void* operator new(size_t sz, nsPresContext* aContext) CPP_THROW_NEW {
-    return aContext->AllocateFromShell(sz);
-  }
-  void operator delete(void* aPtr) {} // Does nothing. The arena will free us up when the rule tree
-                                      // dies.
-
-  void Destroy(nsPresContext* aContext) {
-    this->~nsRuleList();
-    aContext->FreeToShell(sizeof(nsRuleList), this);
-  }
-
-  // Destroy this node, but not its rule node or the rest of the list.
-  nsRuleList* DestroySelf(nsPresContext* aContext) {
-    nsRuleList *next = mNext;
-    MOZ_COUNT_DTOR(nsRuleList); // hack
-    aContext->FreeToShell(sizeof(nsRuleList), this);
-    return next;
-  }
-};
-
-/*
  * For storage of an |nsRuleNode|'s children in a PLDHashTable.
  */
 
 struct ChildrenHashEntry : public PLDHashEntryHdr {
   // key is |mRuleNode->GetKey()|
   nsRuleNode *mRuleNode;
 };
 
@@ -493,37 +452,43 @@ nsRuleNode::~nsRuleNode()
 {
   MOZ_COUNT_DTOR(nsRuleNode);
   if (mStyleData.mResetData || mStyleData.mInheritedData)
     mStyleData.Destroy(0, mPresContext);
   if (ChildrenAreHashed()) {
     PLDHashTable *children = ChildrenHash();
     PL_DHashTableEnumerate(children, DeleteRuleNodeChildren, nsnull);
     PL_DHashTableDestroy(children);
-  } else if (HaveChildren())
-    ChildrenList()->Destroy(mPresContext);
+  } else if (HaveChildren()) {
+    nsRuleNode *node = ChildrenList();
+    do {
+      nsRuleNode *next = node->mNextSibling;
+      node->Destroy();
+      node = next;
+    } while (node);
+  }
   NS_IF_RELEASE(mRule);
 }
 
 nsRuleNode*
 nsRuleNode::Transition(nsIStyleRule* aRule, PRUint8 aLevel,
                        PRPackedBool aIsImportantRule)
 {
   nsRuleNode* next = nsnull;
   nsRuleNode::Key key(aRule, aLevel, aIsImportantRule);
 
   if (HaveChildren() && !ChildrenAreHashed()) {
     PRInt32 numKids = 0;
-    nsRuleList* curr = ChildrenList();
-    while (curr && curr->mRuleNode->GetKey() != key) {
-      curr = curr->mNext;
+    nsRuleNode* curr = ChildrenList();
+    while (curr && curr->GetKey() != key) {
+      curr = curr->mNextSibling;
       ++numKids;
     }
     if (curr)
-      next = curr->mRuleNode;
+      next = curr;
     else if (numKids >= kMaxChildrenInList)
       ConvertChildrenToHash();
   }
 
   if (ChildrenAreHashed()) {
     ChildrenHashEntry *entry = static_cast<ChildrenHashEntry*>
                                           (PL_DHashTableOperate(ChildrenHash(), &key, PL_DHASH_ADD));
     if (!entry) {
@@ -541,44 +506,39 @@ nsRuleNode::Transition(nsIStyleRule* aRu
     }
   } else if (!next) {
     // Create the new entry in our list.
     next = new (mPresContext)
       nsRuleNode(mPresContext, this, aRule, aLevel, aIsImportantRule);
     if (!next) {
       return nsnull;
     }
-    nsRuleList* newChildrenList = new (mPresContext) nsRuleList(next, ChildrenList());
-    if (NS_UNLIKELY(!newChildrenList)) {
-      next->Destroy();
-      return nsnull;
-    }
-    SetChildrenList(newChildrenList);
+    next->mNextSibling = ChildrenList();
+    SetChildrenList(next);
   }
   
   return next;
 }
 
 void
 nsRuleNode::ConvertChildrenToHash()
 {
   NS_ASSERTION(!ChildrenAreHashed() && HaveChildren(),
                "must have a non-empty list of children");
   PLDHashTable *hash = PL_NewDHashTable(&ChildrenHashOps, nsnull,
                                         sizeof(ChildrenHashEntry),
                                         kMaxChildrenInList * 4);
   if (!hash)
     return;
-  for (nsRuleList* curr = ChildrenList(); curr;
-       curr = curr->DestroySelf(mPresContext)) {
+  for (nsRuleNode* curr = ChildrenList(); curr; curr = curr->mNextSibling) {
     // This will never fail because of the initial size we gave the table.
-    ChildrenHashEntry *entry = static_cast<ChildrenHashEntry*>
-                                          (PL_DHashTableOperate(hash, curr->mRuleNode->mRule, PL_DHASH_ADD));
+    ChildrenHashEntry *entry = static_cast<ChildrenHashEntry*>(
+      PL_DHashTableOperate(hash, curr->mRule, PL_DHASH_ADD));
     NS_ASSERTION(!entry->mRuleNode, "duplicate entries in list");
-    entry->mRuleNode = curr->mRuleNode;
+    entry->mRuleNode = curr;
   }
   SetChildrenHash(hash);
 }
 
 inline void
 nsRuleNode::PropagateNoneBit(PRUint32 aBit, nsRuleNode* aHighestNode)
 {
   nsRuleNode* curr = this;
@@ -5246,25 +5206,25 @@ nsRuleNode::Sweep()
 
   // Call sweep on the children, since some may not be marked, and
   // remove any deleted children from the child lists.
   if (HaveChildren()) {
     if (ChildrenAreHashed()) {
       PLDHashTable *children = ChildrenHash();
       PL_DHashTableEnumerate(children, SweepRuleNodeChildren, nsnull);
     } else {
-      for (nsRuleList **children = ChildrenListPtr(); *children; ) {
-        if ((*children)->mRuleNode->Sweep()) {
-          // This rule node was destroyed, so remove this entry, and
-          // implicitly advance by making *children point to the next
-          // entry.
-          *children = (*children)->DestroySelf(mPresContext);
+      for (nsRuleNode **children = ChildrenListPtr(); *children; ) {
+        nsRuleNode *next = (*children)->mNextSibling;
+        if ((*children)->Sweep()) {
+          // This rule node was destroyed, so implicitly advance by
+          // making *children point to the next entry.
+          *children = next;
         } else {
           // Advance.
-          children = &(*children)->mNext;
+          children = &(*children)->mNextSibling;
         }
       }
     }
   }
   return PR_FALSE;
 }
 
 /* static */ PRBool
--- a/layout/style/nsRuleNode.h
+++ b/layout/style/nsRuleNode.h
@@ -44,17 +44,16 @@
 
 #ifndef nsRuleNode_h___
 #define nsRuleNode_h___
 
 #include "nsPresContext.h"
 #include "nsStyleStruct.h"
 
 class nsStyleContext;
-struct nsRuleList;
 struct PLDHashTable;
 class nsILanguageAtomService;
 struct nsRuleData;
 class nsIStyleRule;
 struct nsCSSStruct;
 struct nsCSSValueList;
 // Copy of typedef that's in nsCSSStruct.h, for compilation speed.
 typedef nsCSSStruct nsRuleDataStruct;
@@ -329,16 +328,22 @@ private:
 
   nsRuleNode* mParent; // A pointer to the parent node in the tree.
                        // This enables us to walk backwards from the
                        // most specific rule matched to the least
                        // specific rule (which is the optimal order to
                        // use for lookups of style properties.
   nsIStyleRule* mRule; // [STRONG] A pointer to our specific rule.
 
+  nsRuleNode* mNextSibling; // This value should be used only by the
+                            // parent, since the parent may store
+                            // children in a hash, which means this
+                            // pointer is not meaningful.  Order of
+                            // siblings is also not meaningful.
+
   struct Key {
     nsIStyleRule* mRule;
     PRUint8 mLevel;
     PRPackedBool mIsImportantRule;
 
     Key(nsIStyleRule* aRule, PRUint8 aLevel, PRPackedBool aIsImportantRule)
       : mRule(aRule), mLevel(aLevel), mIsImportantRule(aIsImportantRule)
     {}
@@ -389,26 +394,26 @@ private:
   };
 
   PRBool HaveChildren() {
     return mChildrenTaggedPtr != nsnull;
   }
   PRBool ChildrenAreHashed() {
     return (PRWord(mChildrenTaggedPtr) & kTypeMask) == kHashType;
   }
-  nsRuleList* ChildrenList() {
-    return reinterpret_cast<nsRuleList*>(mChildrenTaggedPtr);
+  nsRuleNode* ChildrenList() {
+    return reinterpret_cast<nsRuleNode*>(mChildrenTaggedPtr);
   }
-  nsRuleList** ChildrenListPtr() {
-    return reinterpret_cast<nsRuleList**>(&mChildrenTaggedPtr);
+  nsRuleNode** ChildrenListPtr() {
+    return reinterpret_cast<nsRuleNode**>(&mChildrenTaggedPtr);
   }
   PLDHashTable* ChildrenHash() {
     return (PLDHashTable*) (PRWord(mChildrenTaggedPtr) & ~PRWord(kTypeMask));
   }
-  void SetChildrenList(nsRuleList *aList) {
+  void SetChildrenList(nsRuleNode *aList) {
     NS_ASSERTION(!(PRWord(aList) & kTypeMask),
                  "pointer not 2-byte aligned");
     mChildrenTaggedPtr = aList;
   }
   void SetChildrenHash(PLDHashTable *aHashtable) {
     NS_ASSERTION(!(PRWord(aHashtable) & kTypeMask),
                  "pointer not 2-byte aligned");
     mChildrenTaggedPtr = (void*)(PRWord(aHashtable) | kHashType);
@@ -433,18 +438,16 @@ private:
                       // out of the rule tree early and just inherit
                       // from the parent style context.  The presence of
                       // this bit means we should just get inherited
                       // data from the parent style context, and it is
                       // never used for reset structs since their
                       // Compute*Data functions don't initialize from
                       // inherited data.
 
-friend struct nsRuleList;
-
 public:
   // Overloaded new operator. Initializes the memory to 0 and relies on an arena
   // (which comes from the presShell) to perform the allocation.
   NS_HIDDEN_(void*) operator new(size_t sz, nsPresContext* aContext) CPP_THROW_NEW;
   NS_HIDDEN_(void) Destroy();
   static NS_HIDDEN_(nsILanguageAtomService*) gLangService;
 
 protected: