Bug 1477627 - Convert CCGraph::mPtrToNodeMap to a mozilla::HashSet. r=mccr8
authorNicholas Nethercote <nnethercote@mozilla.com>
Tue, 14 Aug 2018 09:25:51 +1000
changeset 829001 6b1f74eb6d3dc0f127c1390b0e42d0ff6faec271
parent 829000 e76d40d9a7d87f57edefdf6790101d3c84fb22e0
child 829002 e4f165c26370def0a21c0d7bf36a41bcf055ff53
push id118741
push userbmo:kshvmdn@gmail.com
push dateTue, 14 Aug 2018 18:31:47 +0000
reviewersmccr8
bugs1477627
milestone63.0a1
Bug 1477627 - Convert CCGraph::mPtrToNodeMap to a mozilla::HashSet. r=mccr8 Because mozilla::HashSet is much faster than PLDHashTable, and mPtrToNodeMap is hot.
xpcom/base/nsCycleCollector.cpp
--- a/xpcom/base/nsCycleCollector.cpp
+++ b/xpcom/base/nsCycleCollector.cpp
@@ -152,16 +152,17 @@
 
 #include "base/process_util.h"
 
 #include "mozilla/ArrayUtils.h"
 #include "mozilla/AutoRestore.h"
 #include "mozilla/CycleCollectedJSContext.h"
 #include "mozilla/CycleCollectedJSRuntime.h"
 #include "mozilla/DebugOnly.h"
+#include "mozilla/HashTable.h"
 #include "mozilla/HoldDropJSObjects.h"
 /* This must occur *after* base/process_util.h to avoid typedefs conflicts. */
 #include "mozilla/LinkedList.h"
 #include "mozilla/MemoryReporting.h"
 #include "mozilla/Move.h"
 #include "mozilla/SegmentedVector.h"
 
 #include "nsCycleCollectionParticipant.h"
@@ -844,38 +845,30 @@ public:
     return n;
   }
 
 private:
   NodeBlock* mBlocks;
   PtrInfo* mLast;
 };
 
-
-// Declarations for mPtrToNodeMap.
-
-struct PtrToNodeEntry : public PLDHashEntryHdr
+struct PtrToNodeHashPolicy
 {
-  // The key is mNode->mPointer
-  PtrInfo* mNode;
-};
-
-static bool
-PtrToNodeMatchEntry(const PLDHashEntryHdr* aEntry, const void* aKey)
-{
-  const PtrToNodeEntry* n = static_cast<const PtrToNodeEntry*>(aEntry);
-  return n->mNode->mPointer == aKey;
-}
-
-static PLDHashTableOps PtrNodeOps = {
-  PLDHashTable::HashVoidPtrKeyStub,
-  PtrToNodeMatchEntry,
-  PLDHashTable::MoveEntryStub,
-  PLDHashTable::ClearEntryStub,
-  nullptr
+  using Key = PtrInfo*;
+  using Lookup = void*;
+
+  static js::HashNumber hash(const Lookup& aLookup)
+  {
+    return mozilla::HashGeneric(aLookup);
+  }
+
+  static bool match(const Key& aKey, const Lookup& aLookup)
+  {
+    return aKey->mPointer == aLookup;
+  }
 };
 
 
 struct WeakMapping
 {
   // map and key will be null if the corresponding objects are GC marked
   PtrInfo* mMap;
   PtrInfo* mKey;
@@ -888,120 +881,99 @@ class CCGraphBuilder;
 struct CCGraph
 {
   NodePool mNodes;
   EdgePool mEdges;
   nsTArray<WeakMapping> mWeakMaps;
   uint32_t mRootCount;
 
 private:
-  PLDHashTable mPtrToNodeMap;
+  friend CCGraphBuilder;
+
+  mozilla::HashSet<PtrInfo*, PtrToNodeHashPolicy> mPtrInfoMap;
+
   bool mOutOfMemory;
 
   static const uint32_t kInitialMapLength = 16384;
 
 public:
   CCGraph()
     : mRootCount(0)
-    , mPtrToNodeMap(&PtrNodeOps, sizeof(PtrToNodeEntry), kInitialMapLength)
+    , mPtrInfoMap(kInitialMapLength)
     , mOutOfMemory(false)
-  {}
+  {
+  }
 
   ~CCGraph() {}
 
   void Init()
   {
     MOZ_ASSERT(IsEmpty(), "Failed to call CCGraph::Clear");
   }
 
   void Clear()
   {
     mNodes.Clear();
     mEdges.Clear();
     mWeakMaps.Clear();
     mRootCount = 0;
-    mPtrToNodeMap.ClearAndPrepareForLength(kInitialMapLength);
+    mPtrInfoMap.clearAndCompact();
     mOutOfMemory = false;
   }
 
 #ifdef DEBUG
   bool IsEmpty()
   {
     return mNodes.IsEmpty() && mEdges.IsEmpty() &&
            mWeakMaps.IsEmpty() && mRootCount == 0 &&
-           mPtrToNodeMap.EntryCount() == 0;
+           mPtrInfoMap.empty();
   }
 #endif
 
   PtrInfo* FindNode(void* aPtr);
-  PtrToNodeEntry* AddNodeToMap(void* aPtr);
   void RemoveObjectFromMap(void* aObject);
 
   uint32_t MapCount() const
   {
-    return mPtrToNodeMap.EntryCount();
+    return mPtrInfoMap.count();
   }
 
   size_t SizeOfExcludingThis(MallocSizeOf aMallocSizeOf) const
   {
     size_t n = 0;
 
     n += mNodes.SizeOfExcludingThis(aMallocSizeOf);
     n += mEdges.SizeOfExcludingThis(aMallocSizeOf);
 
     // We don't measure what the WeakMappings point to, because the
     // pointers are non-owning.
     n += mWeakMaps.ShallowSizeOfExcludingThis(aMallocSizeOf);
 
-    n += mPtrToNodeMap.ShallowSizeOfExcludingThis(aMallocSizeOf);
+    n += mPtrInfoMap.shallowSizeOfExcludingThis(aMallocSizeOf);
 
     return n;
   }
-
-private:
-  PtrToNodeEntry* FindNodeEntry(void* aPtr) const
-  {
-    return static_cast<PtrToNodeEntry*>(mPtrToNodeMap.Search(aPtr));
-  }
 };
 
 PtrInfo*
 CCGraph::FindNode(void* aPtr)
 {
-  PtrToNodeEntry* e = FindNodeEntry(aPtr);
-  return e ? e->mNode : nullptr;
-}
-
-PtrToNodeEntry*
-CCGraph::AddNodeToMap(void* aPtr)
-{
-  JS::AutoSuppressGCAnalysis suppress;
-  if (mOutOfMemory) {
-    return nullptr;
-  }
-
-  auto e = static_cast<PtrToNodeEntry*>(mPtrToNodeMap.Add(aPtr, fallible));
-  if (!e) {
-    mOutOfMemory = true;
-    MOZ_ASSERT(false, "Ran out of memory while building cycle collector graph");
-    return nullptr;
-  }
-  return e;
+  auto p = mPtrInfoMap.lookup(aPtr);
+  return p ? *p : nullptr;
 }
 
 void
 CCGraph::RemoveObjectFromMap(void* aObj)
 {
-  PtrToNodeEntry* e = FindNodeEntry(aObj);
-  PtrInfo* pinfo = e ? e->mNode : nullptr;
-  if (pinfo) {
-    mPtrToNodeMap.RemoveEntry(e);
-
+  auto p = mPtrInfoMap.lookup(aObj);
+  if (p) {
+    PtrInfo* pinfo = *p;
     pinfo->mPointer = nullptr;
     pinfo->mParticipant = nullptr;
+    mPtrInfoMap.remove(p);
   }
 }
 
 
 static nsISupports*
 CanonicalizeXPCOMParticipant(nsISupports* aIn)
 {
   nsISupports* out = nullptr;
@@ -2266,36 +2238,43 @@ CCGraphBuilder::CCGraphBuilder(CCGraph& 
 
 CCGraphBuilder::~CCGraphBuilder()
 {
 }
 
 PtrInfo*
 CCGraphBuilder::AddNode(void* aPtr, nsCycleCollectionParticipant* aParticipant)
 {
-  PtrToNodeEntry* e = mGraph.AddNodeToMap(aPtr);
-  if (!e) {
+  if (mGraph.mOutOfMemory) {
     return nullptr;
   }
 
   PtrInfo* result;
-  if (!e->mNode) {
-    // New entry.
+  auto p = mGraph.mPtrInfoMap.lookupForAdd(aPtr);
+  if (!p) {
+    // New entry
     result = mNodeBuilder.Add(aPtr, aParticipant);
     if (!result) {
       return nullptr;
     }
 
-    e->mNode = result;
-    NS_ASSERTION(result, "mNodeBuilder.Add returned null");
+    if (!mGraph.mPtrInfoMap.add(p, result)) {
+      // `result` leaks here, but we can't free it because it's
+      // pool-allocated within NodePool.
+      mGraph.mOutOfMemory = true;
+      MOZ_ASSERT(false, "OOM while building cycle collector graph");
+      return nullptr;
+    }
+
   } else {
-    result = e->mNode;
+    result = *p;
     MOZ_ASSERT(result->mParticipant == aParticipant,
                "nsCycleCollectionParticipant shouldn't change!");
   }
+
   return result;
 }
 
 bool
 CCGraphBuilder::AddPurpleRoot(void* aRoot, nsCycleCollectionParticipant* aParti)
 {
   ToParticipant(aRoot, &aParti);