Bug 1102525 (part 3) - Replace SegmentedArray with mozilla::SegmentedVector in the cycle collector. r=smaug.
authorNicholas Nethercote <nnethercote@mozilla.com>
Mon, 08 Dec 2014 14:45:13 -0800
changeset 218812 a251917f5bfcc7cfe1c7690f1920be89e076b8ad
parent 218811 96c0e71d648d4735a8d3e9da2fc9038f334906e5
child 218813 a0a2ada426523514d6e43298c4c60c28fd4ceef4
push id27944
push usercbook@mozilla.com
push dateTue, 09 Dec 2014 11:54:28 +0000
treeherdermozilla-central@acf5660d2048 [default view] [failures only]
perfherder[talos] [build metrics] [platform microbench] (compared to previous push)
reviewerssmaug
bugs1102525
milestone37.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 1102525 (part 3) - Replace SegmentedArray with mozilla::SegmentedVector in the cycle collector. r=smaug.
xpcom/base/nsCycleCollector.cpp
--- a/xpcom/base/nsCycleCollector.cpp
+++ b/xpcom/base/nsCycleCollector.cpp
@@ -152,18 +152,19 @@
 
 #include "base/process_util.h"
 
 #include "mozilla/ArrayUtils.h"
 #include "mozilla/AutoRestore.h"
 #include "mozilla/CycleCollectedJSRuntime.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/LinkedList.h"
+#include "mozilla/SegmentedVector.h"
 
 #include "nsCycleCollectionParticipant.h"
 #include "nsCycleCollectionNoteRootCallback.h"
 #include "nsDeque.h"
 #include "nsCycleCollector.h"
 #include "nsThreadUtils.h"
 #include "nsXULAppAPI.h"
 #include "prenv.h"
@@ -2461,103 +2462,34 @@ ChildFinder::NoteJSChild(void* aChild)
 static bool
 MayHaveChild(void* aObj, nsCycleCollectionParticipant* aCp)
 {
   ChildFinder cf;
   aCp->Traverse(aObj, cf);
   return cf.MayHaveChild();
 }
 
-template<class T, size_t N>
-class SegmentedArrayElement
-  : public LinkedListElement<SegmentedArrayElement<T, N>>
-  , public AutoFallibleTArray<T, N>
-{
-};
-
-// For a given segment size (in bytes), compute the number of T elements
-// that can fit into it.
-template<typename T, size_t IdealSegmentSize>
-class SegmentedArrayCapacity
-{
-  static const size_t kSingleElemSegmentSize =
-    sizeof(SegmentedArrayElement<T, 1>);
-
-public:
-  static const size_t value =
-    (IdealSegmentSize - kSingleElemSegmentSize) / sizeof(T) + 1;
-
-  static const size_t kActualSegmentSize =
-    sizeof(SegmentedArrayElement<T, value>);
-};
-
-template<class T, size_t N>
-class SegmentedArray
-{
-  typedef SegmentedArrayElement<T, N> Segment;
-
-public:
-  ~SegmentedArray()
-  {
-    MOZ_ASSERT(IsEmpty());
-  }
-
-  void AppendElement(T& aElement)
-  {
-    Segment* last = mSegments.getLast();
-    if (!last || last->Length() == last->Capacity()) {
-      last = new Segment();
-      mSegments.insertBack(last);
-    }
-    last->AppendElement(aElement);
-  }
-
-  void Clear()
-  {
-    Segment* first;
-    while ((first = mSegments.popFirst())) {
-      delete first;
-    }
-  }
-
-  Segment* GetFirstSegment()
-  {
-    return mSegments.getFirst();
-  }
-
-  const Segment* GetFirstSegment() const
-  {
-    return mSegments.getFirst();
-  }
-
-  bool IsEmpty() const
-  {
-    return !GetFirstSegment();
-  }
-
-private:
-  mozilla::LinkedList<Segment> mSegments;
-};
-
 // JSPurpleBuffer keeps references to GCThings which might affect the
 // next cycle collection. It is owned only by itself and during unlink its
 // self reference is broken down and the object ends up killing itself.
 // If GC happens before CC, references to GCthings and the self reference are
 // removed.
 class JSPurpleBuffer
 {
   ~JSPurpleBuffer()
   {
     MOZ_ASSERT(mValues.IsEmpty());
     MOZ_ASSERT(mObjects.IsEmpty());
   }
 
 public:
   explicit JSPurpleBuffer(JSPurpleBuffer*& aReferenceToThis)
     : mReferenceToThis(aReferenceToThis)
+    , mValues(kSegmentSize)
+    , mObjects(kSegmentSize)
   {
     mReferenceToThis = this;
     NS_ADDREF_THIS();
     mozilla::HoldJSObjects(this);
   }
 
   void Destroy()
   {
@@ -2572,41 +2504,38 @@ public:
   NS_DECL_CYCLE_COLLECTION_SCRIPT_HOLDER_NATIVE_CLASS(JSPurpleBuffer)
 
   JSPurpleBuffer*& mReferenceToThis;
 
   // These are raw pointers instead of Heap<T> because we only need Heap<T> for
   // pointers which may point into the nursery. The purple buffer never contains
   // pointers to the nursery because nursery gcthings can never be gray and only
   // gray things can be inserted into the purple buffer.
-  SegmentedArray<JS::Value, 60> mValues;
-  SegmentedArray<JSObject*, 60> mObjects;
+  static const size_t kSegmentSize = 512;
+  SegmentedVector<JS::Value, kSegmentSize, InfallibleAllocPolicy> mValues;
+  SegmentedVector<JSObject*, kSegmentSize, InfallibleAllocPolicy> mObjects;
 };
 
 NS_IMPL_CYCLE_COLLECTION_CLASS(JSPurpleBuffer)
 
 NS_IMPL_CYCLE_COLLECTION_UNLINK_BEGIN(JSPurpleBuffer)
   tmp->Destroy();
 NS_IMPL_CYCLE_COLLECTION_UNLINK_END
 
 NS_IMPL_CYCLE_COLLECTION_TRAVERSE_BEGIN(JSPurpleBuffer)
   CycleCollectionNoteChild(cb, tmp, "self");
   NS_IMPL_CYCLE_COLLECTION_TRAVERSE_SCRIPT_OBJECTS
 NS_IMPL_CYCLE_COLLECTION_TRAVERSE_END
 
-#define NS_TRACE_SEGMENTED_ARRAY(_field, _type)                                \
-  {                                                                            \
-    auto segment = tmp->_field.GetFirstSegment();                              \
-    while (segment) {                                                          \
-      for (uint32_t i = segment->Length(); i > 0;) {                           \
-        js::gc::CallTraceCallbackOnNonHeap<_type, TraceCallbacks>(             \
-            &segment->ElementAt(--i), aCallbacks, #_field, aClosure);          \
-      }                                                                        \
-      segment = segment->getNext();                                            \
-    }                                                                          \
+#define NS_TRACE_SEGMENTED_ARRAY(_field, _type)                               \
+  {                                                                           \
+    for (auto iter = tmp->_field.Iter(); !iter.Done(); iter.Next()) {         \
+      js::gc::CallTraceCallbackOnNonHeap<_type, TraceCallbacks>(              \
+          &iter.Get(), aCallbacks, #_field, aClosure);                        \
+    }                                                                         \
   }
 
 NS_IMPL_CYCLE_COLLECTION_TRACE_BEGIN(JSPurpleBuffer)
   NS_TRACE_SEGMENTED_ARRAY(mValues, JS::Value)
   NS_TRACE_SEGMENTED_ARRAY(mObjects, JSObject*)
 NS_IMPL_CYCLE_COLLECTION_TRACE_END
 
 NS_IMPL_CYCLE_COLLECTION_ROOT_NATIVE(JSPurpleBuffer, AddRef)
@@ -2617,56 +2546,51 @@ class SnowWhiteKiller : public TraceCall
   struct SnowWhiteObject
   {
     void* mPointer;
     nsCycleCollectionParticipant* mParticipant;
     nsCycleCollectingAutoRefCnt* mRefCnt;
   };
 
   // Segments are 4 KiB on 32-bit and 8 KiB on 64-bit.
-  static const size_t kSegmentCapacity =
-    SegmentedArrayCapacity<SnowWhiteObject, sizeof(void*) * 1024>::value;
-  typedef SegmentedArray<SnowWhiteObject, kSegmentCapacity> ObjectsArray;
+  static const size_t kSegmentSize = sizeof(void*) * 1024;
+  typedef SegmentedVector<SnowWhiteObject, kSegmentSize, InfallibleAllocPolicy>
+    ObjectsVector;
 
 public:
   SnowWhiteKiller(nsCycleCollector* aCollector, uint32_t aMaxCount)
     : mCollector(aCollector)
-    , mObjects()
+    , mObjects(kSegmentSize)
   {
     MOZ_ASSERT(mCollector, "Calling SnowWhiteKiller after nsCC went away");
   }
 
   ~SnowWhiteKiller()
   {
-    auto segment = mObjects.GetFirstSegment();
-    while (segment) {
-      for (uint32_t i = 0; i < segment->Length(); i++) {
-        SnowWhiteObject& o = segment->ElementAt(i);
-        if (!o.mRefCnt->get() && !o.mRefCnt->IsInPurpleBuffer()) {
-          mCollector->RemoveObjectFromGraph(o.mPointer);
-          o.mRefCnt->stabilizeForDeletion();
-          o.mParticipant->Trace(o.mPointer, *this, nullptr);
-          o.mParticipant->DeleteCycleCollectable(o.mPointer);
-        }
+    for (auto iter = mObjects.Iter(); !iter.Done(); iter.Next()) {
+      SnowWhiteObject& o = iter.Get();
+      if (!o.mRefCnt->get() && !o.mRefCnt->IsInPurpleBuffer()) {
+        mCollector->RemoveObjectFromGraph(o.mPointer);
+        o.mRefCnt->stabilizeForDeletion();
+        o.mParticipant->Trace(o.mPointer, *this, nullptr);
+        o.mParticipant->DeleteCycleCollectable(o.mPointer);
       }
-      segment = segment->getNext();
     }
-    mObjects.Clear();
   }
 
   void
   Visit(nsPurpleBuffer& aBuffer, nsPurpleBufferEntry* aEntry)
   {
     MOZ_ASSERT(aEntry->mObject, "Null object in purple buffer");
     if (!aEntry->mRefCnt->get()) {
       void* o = aEntry->mObject;
       nsCycleCollectionParticipant* cp = aEntry->mParticipant;
       CanonicalizeParticipant(&o, &cp);
       SnowWhiteObject swo = { o, cp, aEntry->mRefCnt };
-      mObjects.AppendElement(swo);
+      mObjects.InfallibleAppend(swo);
       aBuffer.Remove(aEntry);
     }
   }
 
   bool HasSnowWhiteObjects() const
   {
     return !mObjects.IsEmpty();
   }
@@ -2674,31 +2598,31 @@ public:
   virtual void Trace(JS::Heap<JS::Value>* aValue, const char* aName,
                      void* aClosure) const
   {
     JS::Value val = *aValue;
     if (val.isMarkable()) {
       void* thing = val.toGCThing();
       if (thing && xpc_GCThingIsGrayCCThing(thing)) {
         MOZ_ASSERT(!js::gc::IsInsideNursery((js::gc::Cell*)thing));
-        mCollector->GetJSPurpleBuffer()->mValues.AppendElement(val);
+        mCollector->GetJSPurpleBuffer()->mValues.InfallibleAppend(val);
       }
     }
   }
 
   virtual void Trace(JS::Heap<jsid>* aId, const char* aName,
                      void* aClosure) const
   {
   }
 
   void AppendJSObjectToPurpleBuffer(JSObject* obj) const
   {
     if (obj && xpc_GCThingIsGrayCCThing(obj)) {
       MOZ_ASSERT(!js::gc::IsInsideNursery(JS::AsCell(obj)));
-      mCollector->GetJSPurpleBuffer()->mObjects.AppendElement(obj);
+      mCollector->GetJSPurpleBuffer()->mObjects.InfallibleAppend(obj);
     }
   }
 
   virtual void Trace(JS::Heap<JSObject*>* aObject, const char* aName,
                      void* aClosure) const
   {
     AppendJSObjectToPurpleBuffer(*aObject);
   }
@@ -2721,17 +2645,17 @@ public:
 
   virtual void Trace(JS::Heap<JSFunction*>* aFunction, const char* aName,
                      void* aClosure) const
   {
   }
 
 private:
   nsCycleCollector* mCollector;
-  ObjectsArray mObjects;
+  ObjectsVector mObjects;
 };
 
 class RemoveSkippableVisitor : public SnowWhiteKiller
 {
 public:
   RemoveSkippableVisitor(nsCycleCollector* aCollector,
                          uint32_t aMaxCount, bool aRemoveChildlessNodes,
                          bool aAsyncSnowWhiteFreeing,
@@ -3256,19 +3180,19 @@ nsCycleCollector::CollectWhite()
   // operating on are stable for the duration of our operation. So we
   // make 3 sets of calls to language runtimes:
   //
   //   - Root(whites), which should pin the whites in memory.
   //   - Unlink(whites), which drops outgoing links on each white.
   //   - Unroot(whites), which returns the whites to normal GC.
 
   // Segments are 4 KiB on 32-bit and 8 KiB on 64-bit.
-  static const size_t cap =
-    SegmentedArrayCapacity<PtrInfo*, sizeof(void*) * 1024>::value;
-  SegmentedArray<PtrInfo*, cap> whiteNodes;
+  static const size_t kSegmentSize = sizeof(void*) * 1024;
+  SegmentedVector<PtrInfo*, kSegmentSize, InfallibleAllocPolicy>
+    whiteNodes(kSegmentSize);
   TimeLog timeLog;
 
   MOZ_ASSERT(mIncrementalPhase == ScanAndCollectWhitePhase);
 
   uint32_t numWhiteNodes = 0;
   uint32_t numWhiteGCed = 0;
   uint32_t numWhiteJSZones = 0;
 
@@ -3281,17 +3205,17 @@ nsCycleCollector::CollectWhite()
     PtrInfo* pinfo = etor.GetNext();
     if (pinfo->mColor == white && pinfo->mParticipant) {
       if (pinfo->IsGrayJS()) {
         ++numWhiteGCed;
         if (MOZ_UNLIKELY(pinfo->mParticipant == zoneParticipant)) {
           ++numWhiteJSZones;
         }
       } else {
-        whiteNodes.AppendElement(pinfo);
+        whiteNodes.InfallibleAppend(pinfo);
         pinfo->mParticipant->Root(pinfo->mPointer);
         ++numWhiteNodes;
       }
     }
   }
 
   mResults.mFreedRefCounted += numWhiteNodes;
   mResults.mFreedGCed += numWhiteGCed;
@@ -3302,52 +3226,42 @@ nsCycleCollector::CollectWhite()
   if (mBeforeUnlinkCB) {
     mBeforeUnlinkCB();
     timeLog.Checkpoint("CollectWhite::BeforeUnlinkCB");
   }
 
   // Unlink() can trigger a GC, so do not touch any JS or anything
   // else not in whiteNodes after here.
 
-  auto segment = whiteNodes.GetFirstSegment();
-  while (segment) {
-    for (uint32_t i = 0; i < segment->Length(); i++) {
-      PtrInfo* pinfo = segment->ElementAt(i);
-      MOZ_ASSERT(pinfo->mParticipant,
-                 "Unlink shouldn't see objects removed from graph.");
-      pinfo->mParticipant->Unlink(pinfo->mPointer);
+  for (auto iter = whiteNodes.Iter(); !iter.Done(); iter.Next()) {
+    PtrInfo* pinfo = iter.Get();
+    MOZ_ASSERT(pinfo->mParticipant,
+               "Unlink shouldn't see objects removed from graph.");
+    pinfo->mParticipant->Unlink(pinfo->mPointer);
 #ifdef DEBUG
-      if (mJSRuntime) {
-        mJSRuntime->AssertNoObjectsToTrace(pinfo->mPointer);
-      }
+    if (mJSRuntime) {
+      mJSRuntime->AssertNoObjectsToTrace(pinfo->mPointer);
+    }
 #endif
-    }
-    segment = segment->getNext();
   }
   timeLog.Checkpoint("CollectWhite::Unlink");
 
-  segment = whiteNodes.GetFirstSegment();
-  while (segment) {
-    for (uint32_t i = 0; i < segment->Length(); i++) {
-      PtrInfo* pinfo = segment->ElementAt(i);
-      MOZ_ASSERT(pinfo->mParticipant,
-                 "Unroot shouldn't see objects removed from graph.");
-      pinfo->mParticipant->Unroot(pinfo->mPointer);
-    }
-    segment = segment->getNext();
+  for (auto iter = whiteNodes.Iter(); !iter.Done(); iter.Next()) {
+    PtrInfo* pinfo = iter.Get();
+    MOZ_ASSERT(pinfo->mParticipant,
+               "Unroot shouldn't see objects removed from graph.");
+    pinfo->mParticipant->Unroot(pinfo->mPointer);
   }
   timeLog.Checkpoint("CollectWhite::Unroot");
 
   nsCycleCollector_dispatchDeferredDeletion(false);
   timeLog.Checkpoint("CollectWhite::dispatchDeferredDeletion");
 
   mIncrementalPhase = CleanupPhase;
 
-  whiteNodes.Clear();
-
   return numWhiteNodes > 0 || numWhiteGCed > 0 || numWhiteJSZones > 0;
 }
 
 
 ////////////////////////
 // Memory reporting
 ////////////////////////