Bug 1102525 (part 2) - Add SegmentedVector to MFBT.
authorNicholas Nethercote <nnethercote@mozilla.com>
Sun, 23 Nov 2014 20:27:51 -0800
changeset 304669 334c5a1c1b711d6e6b94e751ca723a006953b000
parent 304668 b81fdb0b1662482a811f8136453df73c1860a306
child 304670 f37aa4f01fd9dfd7106a3440c42dd75da0e26e72
push id42856
push usernnethercote@mozilla.com
push dateMon, 24 Nov 2014 04:28:05 +0000
treeherdertry@9c6ae2f642e9 [default view] [failures only]
bugs1102525
milestone36.0a1
Bug 1102525 (part 2) - Add SegmentedVector to MFBT. This is based on the SegmentedArray type from nsCycleCollector.cpp.
mfbt/SegmentedVector.h
mfbt/moz.build
mfbt/tests/TestSegmentedVector.cpp
mfbt/tests/moz.build
new file mode 100644
--- /dev/null
+++ b/mfbt/SegmentedVector.h
@@ -0,0 +1,190 @@
+/* -*- Mode: C++; tab-width: 8; indent-tabs-mode: nil; c-basic-offset: 2 -*- */
+/* vim: set ts=8 sts=2 et sw=2 tw=80: */
+/* This Source Code Form is subject to the terms of the Mozilla Public
+ * License, v. 2.0. If a copy of the MPL was not distributed with this
+ * file, You can obtain one at http://mozilla.org/MPL/2.0/. */
+
+// A simple segmented vector class. It should be used in preference to
+// mozilla::Vector or nsTArray when you are simply gathering items in order to
+// later iterate over them, because it avoids those types' need to continually
+// allocate and copy the data into increasingly large buffers.
+
+#ifndef mozilla_SegmentedVector_h
+#define mozilla_SegmentedVector_h
+
+#include "mozilla/AllocPolicy.h"
+#include "mozilla/Array.h"
+#include "mozilla/LinkedList.h"
+#include "mozilla/MemoryReporting.h"
+#include "mozilla/Move.h"
+#include "mozilla/TypeTraits.h"
+
+#include <new>  // for placement new
+
+namespace mozilla {
+
+// IdealSegmentSize is how big each segment will be in bytes (or as close as is
+// possible). It's best to choose a size that's a power-of-two (to avoid slop)
+// and moderately large (not too small so segment allocations are infrequent,
+// and not too large so that not too much space is wasted when the final
+// segment is not full). Something like 4096 or 8192 is probably good.
+template<typename T, size_t IdealSegmentSize,
+         typename AllocPolicy = MallocAllocPolicy>
+class SegmentedVector : AllocPolicy
+{
+  template<size_t SegmentCapacity>
+  struct SegmentImpl
+    : public mozilla::LinkedListElement<SegmentImpl<SegmentCapacity>>
+  {
+    SegmentImpl() : mLength(0) {}
+
+    uint32_t Length() const { return mLength; }
+
+    template<typename U>
+    void Append(U&& aU)
+    {
+      MOZ_ASSERT(mLength < SegmentCapacity);
+      new (&mElems[mLength]) T(mozilla::Forward<U>(aU));
+      mLength++;
+    }
+
+    uint32_t mLength;
+    mozilla::Array<T, SegmentCapacity> mElems;
+  };
+
+  // See how many we elements we can fit in a segment of IdealSegmentSize. If
+  // IdealSegmentSize is too small, it'll be just one. The +1 is because
+  // kSingleElementSegmentSize already accounts for one element.
+  static const size_t kSingleElementSegmentSize = sizeof(SegmentImpl<1>);
+  static const size_t kSegmentCapacity =
+    kSingleElementSegmentSize <= IdealSegmentSize
+    ? (IdealSegmentSize - kSingleElementSegmentSize) / sizeof(T) + 1
+    : 1;
+
+  typedef SegmentImpl<kSegmentCapacity> Segment;
+
+public:
+  // The |aIdealSegmentSize| is only for sanity checking. If it's specified, we
+  // check that the actual segment size is as close as possible to it. This
+  // serves as a sanity check for SegmentedVectorCapacity's capacity
+  // computation.
+  SegmentedVector(size_t aIdealSegmentSize = 0)
+  {
+    // The difference between the actual segment size and the ideal segment
+    // size should be less than the size of a single element... unless the
+    // ideal size was too small, in which case the capacity should be one.
+    MOZ_ASSERT_IF(
+      aIdealSegmentSize != 0,
+      (sizeof(Segment) > aIdealSegmentSize && kSegmentCapacity == 1) ||
+      aIdealSegmentSize - sizeof(Segment) < sizeof(T));
+  }
+
+  ~SegmentedVector() { Clear(); }
+
+  size_t SegmentCapacity() const { return kSegmentCapacity; }
+
+  bool IsEmpty() const { return !mSegments.getFirst(); }
+
+  // Note that this is O(n) rather than O(1), but the constant factor is very
+  // small because it only has to do one addition per segment.
+  size_t Length() const
+  {
+    size_t n = 0;
+    for (auto segment = mSegments.getFirst();
+         segment;
+         segment = segment->getNext()) {
+      n += segment->Length();
+    }
+    return n;
+  }
+
+  // Returns false if the allocation failed. (If you are using an infallible
+  // allocation policy, the return value doesn't need to be checked.)
+  template<typename U>
+  bool Append(U&& aU)
+  {
+    Segment* last = mSegments.getLast();
+    if (!last || last->Length() == kSegmentCapacity) {
+      last = this->template pod_malloc<Segment>(1);
+      if (!last) {
+        return false;
+      }
+      new (last) Segment();
+      mSegments.insertBack(last);
+    }
+    last->Append(mozilla::Forward<U>(aU));
+    return true;
+  }
+
+  void Clear()
+  {
+    Segment* segment;
+    while ((segment = mSegments.popFirst())) {
+      segment->~Segment();
+      this->free_(segment);
+    }
+  }
+
+  // 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
+  {
+    friend class SegmentedVector;
+
+    Segment* mSegment;
+    size_t mIndex;
+
+    IterImpl(SegmentedVector* aVector)
+      : mSegment(aVector->mSegments.getFirst())
+      , mIndex(0)
+    {}
+
+  public:
+    bool Done() const { return !mSegment; }
+
+    T& Get() const
+    {
+      MOZ_ASSERT(!Done());
+      return mSegment->mElems[mIndex];
+    }
+
+    void Next()
+    {
+      MOZ_ASSERT(!Done());
+      mIndex++;
+      if (mIndex == mSegment->Length()) {
+        mSegment = mSegment->getNext();
+        mIndex = 0;
+      }
+    }
+  };
+
+  IterImpl Iter() { return IterImpl(this); }
+
+  // Measure the memory consumption of the vector excluding |this|. Note that
+  // it only measures the vector itself. If the vector elements contain
+  // pointers to other memory blocks, those blocks must be measured separately
+  // during a subsequent iteration over the vector.
+  size_t SizeOfExcludingThis(mozilla::MallocSizeOf aMallocSizeOf) const
+  {
+    return mSegments.sizeOfExcludingThis(aMallocSizeOf);
+  }
+
+  // Like sizeOfExcludingThis(), but measures |this| as well.
+  size_t SizeOfIncludingThis(mozilla::MallocSizeOf aMallocSizeOf) const
+  {
+    return aMallocSizeOf(this) + SizeOfExcludingThis(aMallocSizeOf);
+  }
+
+private:
+  mozilla::LinkedList<Segment> mSegments;
+};
+
+} // namespace mozilla
+
+#endif /* mozilla_SegmentedVector_h */
--- a/mfbt/moz.build
+++ b/mfbt/moz.build
@@ -56,16 +56,17 @@ EXPORTS.mozilla = [
     'Poison.h',
     'Range.h',
     'RangedPtr.h',
     'RefCountType.h',
     'ReentrancyGuard.h',
     'RefPtr.h',
     'RollingMean.h',
     'Scoped.h',
+    'SegmentedVector.h',
     'SHA1.h',
     'SplayTree.h',
     'TaggedAnonymousMemory.h',
     'TemplateLib.h',
     'ThreadLocal.h',
     'ToString.h',
     'TypedEnum.h',
     'TypedEnumBits.h',
new file mode 100644
--- /dev/null
+++ b/mfbt/tests/TestSegmentedVector.cpp
@@ -0,0 +1,151 @@
+/* -*- Mode: C++; tab-width: 9; indent-tabs-mode: nil; c-basic-offset: 2 -*- */
+/* vim: set ts=8 sts=2 et sw=2 tw=80: */
+/* This Source Code Form is subject to the terms of the Mozilla Public
+ * License, v. 2.0. If a copy of the MPL was not distributed with this file,
+ * You can obtain one at http://mozilla.org/MPL/2.0/. */
+
+// This is included first to ensure it doesn't implicitly depend on anything
+// else.
+#include "mozilla/SegmentedVector.h"
+
+#include "mozilla/Assertions.h"
+
+using mozilla::SegmentedVector;
+
+// It would be nice if we could use the InfallibleAllocPolicy from mozalloc,
+// but MFBT cannot use mozalloc.
+class InfallibleAllocPolicy
+{
+public:
+  template <typename T>
+  T* pod_malloc(size_t aNumElems)
+  {
+    if (aNumElems & mozilla::tl::MulOverflowMask<sizeof(T)>::value) {
+      MOZ_CRASH("TestSegmentedVector.cpp: overflow");
+    }
+    T* rv = static_cast<T*>(malloc(aNumElems * sizeof(T)));
+    if (!rv) {
+      MOZ_CRASH("TestSegmentedVector.cpp: out of memory");
+    }
+    return rv;
+  }
+
+  void free_(void* aPtr) { free(aPtr); }
+};
+
+// This tests basic segmented vector construction and iteration.
+void TestBasics()
+{
+  // A SegmentedVector with a POD element type.
+  typedef SegmentedVector<int, 1024, InfallibleAllocPolicy> MyVector;
+  MyVector v;
+  int i, n;
+
+  MOZ_RELEASE_ASSERT(v.IsEmpty());
+
+  // Add 100 elements, then check various things.
+  i = 0;
+  for ( ; i < 100; i++) {
+    (void) v.Append(mozilla::Move(i));
+  }
+  MOZ_RELEASE_ASSERT(!v.IsEmpty());
+  MOZ_RELEASE_ASSERT(v.Length() == 100);
+
+  n = 0;
+  for (auto iter = v.Iter(); !iter.Done(); iter.Next()) {
+    MOZ_RELEASE_ASSERT(iter.Get() == n);
+    n++;
+  }
+  MOZ_RELEASE_ASSERT(n == 100);
+
+  // Add another 900 elements, then re-check.
+  for ( ; i < 1000; i++) {
+    (void) v.Append(mozilla::Move(i));
+  }
+  MOZ_RELEASE_ASSERT(!v.IsEmpty());
+  MOZ_RELEASE_ASSERT(v.Length() == 1000);
+
+  n = 0;
+  for (auto iter = v.Iter(); !iter.Done(); iter.Next()) {
+    MOZ_RELEASE_ASSERT(iter.Get() == n);
+    n++;
+  }
+  MOZ_RELEASE_ASSERT(n == 1000);
+
+  v.Clear();
+  MOZ_RELEASE_ASSERT(v.IsEmpty());
+  MOZ_RELEASE_ASSERT(v.Length() == 0);
+}
+
+static size_t gNumDefaultCtors;
+static size_t gNumExplicitCtors;
+static size_t gNumCopyCtors;
+static size_t gNumMoveCtors;
+static size_t gNumDtors;
+
+struct NonPOD
+{
+  NonPOD()                { gNumDefaultCtors++; }
+  explicit NonPOD(int x)  { gNumExplicitCtors++; }
+  NonPOD(NonPOD&)         { gNumCopyCtors++; }
+  NonPOD(NonPOD&&)        { gNumMoveCtors++; }
+  ~NonPOD()               { gNumDtors++; }
+};
+
+// This tests how segmented vectors with non-POD elements construct and
+// destruct those elements.
+void TestConstructorsAndDestructors()
+{
+  size_t segmentCapacity;
+  {
+    // A SegmentedVector with a non-POD element type.
+    NonPOD x(1);                        // explicit constructor called
+    SegmentedVector<NonPOD, 64, InfallibleAllocPolicy> v;
+                                        // default constructor called N times
+    segmentCapacity = v.SegmentCapacity();
+    MOZ_RELEASE_ASSERT(v.IsEmpty());
+    (void) v.Append(x);                 // copy constructor called
+    NonPOD y(1);                        // explicit constructor called
+    (void) v.Append(mozilla::Move(y));  // move constructor called
+    NonPOD z(1);                        // explicit constructor called
+    (void) v.Append(mozilla::Move(z));  // move constructor called
+    v.Clear();                          // destructor called N times
+
+    MOZ_RELEASE_ASSERT(gNumDefaultCtors  == segmentCapacity);
+    MOZ_RELEASE_ASSERT(gNumExplicitCtors == 3);
+    MOZ_RELEASE_ASSERT(gNumCopyCtors     == 1);
+    MOZ_RELEASE_ASSERT(gNumMoveCtors     == 2);
+    MOZ_RELEASE_ASSERT(gNumDtors         == segmentCapacity);
+  }                                     // destructor called for x, y, z
+  MOZ_RELEASE_ASSERT(gNumDtors == segmentCapacity + 3);
+}
+
+struct A { int mX; int mY; };
+struct B { int mX; char mY; double mZ; };
+struct C { A mA; B mB; };
+struct D { char mBuf[101]; };
+struct E { };
+
+// This tests that we get the right segment capacities for specified segment
+// sizes.
+void TestSegmentSizing()
+{
+  // When SegmentedVector's constructor is passed a size, it asserts that the
+  // vector's segment capacity results in a segment size equal to (or very
+  // close to) the passed size.
+  SegmentedVector<double, 512> v1(512);
+  SegmentedVector<A, 1024> v2(1024);
+  SegmentedVector<B, 999> v3(999);
+  SegmentedVector<C, 10> v4(10);
+  SegmentedVector<D, 1234> v5(1234);
+  SegmentedVector<E, 4096> v6(4096);
+}
+
+int main(void)
+{
+  TestBasics();
+  TestConstructorsAndDestructors();
+  TestSegmentSizing();
+
+  return 0;
+}
--- a/mfbt/tests/moz.build
+++ b/mfbt/tests/moz.build
@@ -20,16 +20,17 @@ CppUnitTests([
     'TestIntegerPrintfMacros',
     'TestJSONWriter',
     'TestMacroArgs',
     'TestMacroForEach',
     'TestMaybe',
     'TestPair',
     'TestRefPtr',
     'TestRollingMean',
+    'TestSegmentedVector',
     'TestSHA1',
     'TestSplayTree',
     'TestTypedEnum',
     'TestTypeTraits',
     'TestUniquePtr',
     'TestWeakPtr',
 ])