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 486470 6b1f74eb6d3dc0f127c1390b0e42d0ff6faec271
parent 486469 e76d40d9a7d87f57edefdf6790101d3c84fb22e0
child 486471 e4f165c26370def0a21c0d7bf36a41bcf055ff53
push id9719
push userffxbld-merge
push dateFri, 24 Aug 2018 17:49:46 +0000
treeherdermozilla-beta@719ec98fba77 [default view] [failures only]
perfherder[talos] [build metrics] [platform microbench] (compared to previous push)
reviewersmccr8
bugs1477627
milestone63.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 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);