Bug 1170045 - part 1 - add bulk pop support to SegmentedVector; r=erahm
authorNathan Froyd <froydnj@mozilla.com>
Fri, 04 Mar 2016 12:02:24 -0500
changeset 286850 00d7f8217cc249d9e358661f8a2f67e4b3de5fcf
parent 286849 a9609f981f978909be000e7025e84eff5209d05c
child 286851 dfc843963851c884874a199a723efe5a9f9380a5
push id30056
push userryanvm@gmail.com
push dateSun, 06 Mar 2016 00:19:57 +0000
treeherdermozilla-central@fcd55efa0672 [default view] [failures only]
perfherder[talos] [build metrics] [platform microbench] (compared to previous push)
reviewerserahm
bugs1170045
milestone47.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 1170045 - part 1 - add bulk pop support to SegmentedVector; r=erahm Writing PopLastN in this way is probably a bit of a micro-optimization, but at least it comes with tests and some comments for verifying the goodness of the code.
mfbt/SegmentedVector.h
mfbt/tests/TestSegmentedVector.cpp
--- a/mfbt/SegmentedVector.h
+++ b/mfbt/SegmentedVector.h
@@ -213,16 +213,66 @@ public:
     last->PopLast();
     if (!last->Length()) {
       mSegments.popLast();
       last->~Segment();
       this->free_(last);
     }
   }
 
+  // Equivalent to calling |PopLast| |aNumElements| times, but potentially
+  // more efficient.
+  void PopLastN(uint32_t aNumElements)
+  {
+    MOZ_ASSERT(aNumElements <= Length());
+
+    Segment* last;
+
+    // Pop full segments for as long as we can.  Note that this loop
+    // cleanly handles the case when the initial last segment is not
+    // full and we are popping more elements than said segment contains.
+    do {
+      last = mSegments.getLast();
+
+      // The list is empty.  We're all done.
+      if (!last) {
+        return;
+      }
+
+      // Check to see if the list contains too many elements.  Handle
+      // that in the epilogue.
+      uint32_t segmentLen = last->Length();
+      if (segmentLen > aNumElements) {
+        break;
+      }
+
+      // Destroying the segment destroys all elements contained therein.
+      mSegments.popLast();
+      last->~Segment();
+      this->free_(last);
+
+      MOZ_ASSERT(aNumElements >= segmentLen);
+      aNumElements -= segmentLen;
+      if (aNumElements == 0) {
+        return;
+      }
+    } while (true);
+
+    // Handle the case where the last segment contains more elements
+    // than we want to pop.
+    MOZ_ASSERT(last);
+    MOZ_ASSERT(last == mSegments.getLast());
+    MOZ_ASSERT(aNumElements != 0);
+    MOZ_ASSERT(aNumElements < last->Length());
+    for (uint32_t i = 0; i < aNumElements; ++i) {
+      last->PopLast();
+    }
+    MOZ_ASSERT(last->Length() != 0);
+  }
+
   // Use this class to iterate over a SegmentedVector, like so:
   //
   //  for (auto iter = v.Iter(); !iter.Done(); iter.Next()) {
   //    MyElem& elem = iter.Get();
   //    f(elem);
   //  }
   //
   class IterImpl
--- a/mfbt/tests/TestSegmentedVector.cpp
+++ b/mfbt/tests/TestSegmentedVector.cpp
@@ -94,16 +94,35 @@ void TestBasics()
     v.InfallibleAppend(mozilla::Move(i));
   }
   MOZ_RELEASE_ASSERT(!v.IsEmpty());
   MOZ_RELEASE_ASSERT(v.Length() == 1000);
 
   v.Clear();
   MOZ_RELEASE_ASSERT(v.IsEmpty());
   MOZ_RELEASE_ASSERT(v.Length() == 0);
+
+  // Fill the vector up to verify PopLastN works.
+  for (i = 0; i < 1000; ++i) {
+    v.InfallibleAppend(mozilla::Move(i));
+  }
+  MOZ_RELEASE_ASSERT(!v.IsEmpty());
+  MOZ_RELEASE_ASSERT(v.Length() == 1000);
+
+  // Verify we pop the right amount of elements.
+  v.PopLastN(300);
+  MOZ_RELEASE_ASSERT(v.Length() == 700);
+
+  // Verify the contents are what we expect.
+  n = 0;
+  for (auto iter = v.Iter(); !iter.Done(); iter.Next()) {
+    MOZ_RELEASE_ASSERT(iter.Get() == n);
+    n++;
+  }
+  MOZ_RELEASE_ASSERT(n == 700);
 }
 
 static size_t gNumDefaultCtors;
 static size_t gNumExplicitCtors;
 static size_t gNumCopyCtors;
 static size_t gNumMoveCtors;
 static size_t gNumDtors;
 
@@ -122,20 +141,22 @@ void TestConstructorsAndDestructors()
 {
   size_t defaultCtorCalls = 0;
   size_t explicitCtorCalls = 0;
   size_t copyCtorCalls = 0;
   size_t moveCtorCalls = 0;
   size_t dtorCalls = 0;
 
   {
+    static const size_t segmentSize = 64;
+
     // A SegmentedVector with a non-POD element type.
     NonPOD x(1);                          // explicit constructor called
     explicitCtorCalls++;
-    SegmentedVector<NonPOD, 64, InfallibleAllocPolicy> v;
+    SegmentedVector<NonPOD, segmentSize, InfallibleAllocPolicy> v;
                                           // default constructor called 0 times
     MOZ_RELEASE_ASSERT(v.IsEmpty());
     gDummy = v.Append(x);                 // copy constructor called
     copyCtorCalls++;
     NonPOD y(1);                          // explicit constructor called
     explicitCtorCalls++;
     gDummy = v.Append(mozilla::Move(y));  // move constructor called
     moveCtorCalls++;
@@ -144,16 +165,80 @@ void TestConstructorsAndDestructors()
     v.InfallibleAppend(mozilla::Move(z)); // move constructor called
     moveCtorCalls++;
     v.PopLast();                          // destructor called 1 time
     dtorCalls++;
     MOZ_RELEASE_ASSERT(gNumDtors == dtorCalls);
     v.Clear();                            // destructor called 2 times
     dtorCalls += 2;
 
+    // Test that PopLastN() correctly calls the destructors of all the
+    // elements in the segments it destroys.
+    //
+    // We depend on the size of NonPOD when determining how many things
+    // to push onto the vector.  It would be nicer to get this information
+    // from SegmentedVector itself...
+    static_assert(sizeof(NonPOD) == 1, "Fix length calculations!");
+
+    size_t nonFullLastSegmentSize = segmentSize - 1;
+    for (size_t i = 0; i < nonFullLastSegmentSize; ++i) {
+      gDummy = v.Append(x);     // copy constructor called
+      copyCtorCalls++;
+    }
+    MOZ_RELEASE_ASSERT(gNumCopyCtors == copyCtorCalls);
+
+    // Pop some of the elements.
+    {
+      size_t partialPopAmount = 5;
+      MOZ_RELEASE_ASSERT(nonFullLastSegmentSize > partialPopAmount);
+      v.PopLastN(partialPopAmount); // destructor called partialPopAmount times
+      dtorCalls += partialPopAmount;
+      MOZ_RELEASE_ASSERT(v.Length() == nonFullLastSegmentSize - partialPopAmount);
+      MOZ_RELEASE_ASSERT(!v.IsEmpty());
+      MOZ_RELEASE_ASSERT(gNumDtors == dtorCalls);
+    }
+
+    // Pop a full segment.
+    {
+      size_t length = v.Length();
+      v.PopLastN(length);
+      dtorCalls += length;
+      // These two tests *are* semantically different given the underlying
+      // implementation; Length sums up the sizes of the internal segments,
+      // while IsEmpty looks at the sequence of internal segments.
+      MOZ_RELEASE_ASSERT(v.Length() == 0);
+      MOZ_RELEASE_ASSERT(v.IsEmpty());
+      MOZ_RELEASE_ASSERT(gNumDtors == dtorCalls);
+    }
+
+    size_t multipleSegmentsSize = (segmentSize * 3) / 2;
+    for (size_t i = 0; i < multipleSegmentsSize; ++i) {
+      gDummy = v.Append(x);     // copy constructor called
+      copyCtorCalls++;
+    }
+    MOZ_RELEASE_ASSERT(gNumCopyCtors == copyCtorCalls);
+
+    // Pop across segment boundaries.
+    {
+      v.PopLastN(segmentSize);
+      dtorCalls += segmentSize;
+      MOZ_RELEASE_ASSERT(v.Length() == (multipleSegmentsSize - segmentSize));
+      MOZ_RELEASE_ASSERT(!v.IsEmpty());
+      MOZ_RELEASE_ASSERT(gNumDtors == dtorCalls);
+    }
+
+    // Clear everything here to make calculations easier.
+    {
+      size_t length = v.Length();
+      v.Clear();
+      dtorCalls += length;
+      MOZ_RELEASE_ASSERT(v.IsEmpty());
+      MOZ_RELEASE_ASSERT(gNumDtors == dtorCalls);
+    }
+
     MOZ_RELEASE_ASSERT(gNumDefaultCtors  == defaultCtorCalls);
     MOZ_RELEASE_ASSERT(gNumExplicitCtors == explicitCtorCalls);
     MOZ_RELEASE_ASSERT(gNumCopyCtors     == copyCtorCalls);
     MOZ_RELEASE_ASSERT(gNumMoveCtors     == moveCtorCalls);
     MOZ_RELEASE_ASSERT(gNumDtors         == dtorCalls);
   }                                       // destructor called for x, y, z
   dtorCalls += 3;
   MOZ_RELEASE_ASSERT(gNumDtors == dtorCalls);