Bug 1102525 (part 2) - Add SegmentedVector to MFBT. r=froydnj.
authorNicholas Nethercote <nnethercote@mozilla.com>
Mon, 08 Dec 2014 14:45:13 -0800
changeset 244637 96c0e71d648d4735a8d3e9da2fc9038f334906e5
parent 244636 c207ff1b40fd558a72b0f03ddf0a6edcf16f0117
child 244638 a251917f5bfcc7cfe1c7690f1920be89e076b8ad
push id4489
push userraliiev@mozilla.com
push dateMon, 23 Feb 2015 15:17:55 +0000
treeherdermozilla-beta@fd7c3dc24146 [default view] [failures only]
perfherder[talos] [build metrics] [platform microbench] (compared to previous push)
reviewersfroydnj
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 2) - Add SegmentedVector to MFBT. r=froydnj. 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,249 @@
+/* -*- 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.
+//
+// This class should be used in preference to mozilla::Vector or nsTArray when
+// you are simply gathering items in order to later iterate over them.
+//
+// - In the case where you don't know the final size in advance, using
+//   SegmentedVector avoids the need to repeatedly allocate increasingly large
+//   buffers and copy the data into them.
+//
+// - In the case where you know the final size in advance and so can set the
+//   capacity appropriately, using SegmentedVector still avoids the need for
+//   large allocations (which can trigger OOMs).
+
+#ifndef mozilla_SegmentedVector_h
+#define mozilla_SegmentedVector_h
+
+#include "mozilla/Alignment.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 : private AllocPolicy
+{
+  template<size_t SegmentCapacity>
+  struct SegmentImpl
+    : public mozilla::LinkedListElement<SegmentImpl<SegmentCapacity>>
+  {
+    SegmentImpl() : mLength(0) {}
+
+    ~SegmentImpl()
+    {
+      for (uint32_t i = 0; i < mLength; i++) {
+        (*this)[i].~T();
+      }
+    }
+
+    uint32_t Length() const { return mLength; }
+
+    T* Elems() { return reinterpret_cast<T*>(&mStorage.mBuf); }
+
+    T& operator[](size_t aIndex)
+    {
+      MOZ_ASSERT(aIndex < mLength);
+      return Elems()[aIndex];
+    }
+
+    const T& operator[](size_t aIndex) const
+    {
+      MOZ_ASSERT(aIndex < mLength);
+      return Elems()[aIndex];
+    }
+
+    template<typename U>
+    void Append(U&& aU)
+    {
+      // GCC 4.4 gives a bogus "invalid use of member" error for this
+      // assertion, so skip it in that case. Once bug 1056337 lands and GCC 4.4
+      // is no longer used we should be able to remove this condition.
+#if !(defined(__GNUC__) && (__GNUC__ == 4) && (__GNUC_MINOR__ == 4))
+      MOZ_ASSERT(mLength < SegmentCapacity);
+#endif
+      // Pre-increment mLength so that the bounds-check in operator[] passes.
+      mLength++;
+      T* elem = &(*this)[mLength - 1];
+      new (elem) T(mozilla::Forward<U>(aU));
+    }
+
+    uint32_t mLength;
+
+    // The union ensures that the elements are appropriately aligned.
+    union Storage
+    {
+      char mBuf[sizeof(T) * SegmentCapacity];
+      mozilla::AlignedElem<MOZ_ALIGNOF(T)> mAlign;
+    } mStorage;
+
+    static_assert(MOZ_ALIGNOF(T) == MOZ_ALIGNOF(Storage),
+                  "SegmentedVector provides incorrect alignment");
+  };
+
+  // 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(); }
+
+  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, use InfallibleAppend() instead.)
+  template<typename U>
+  MOZ_WARN_UNUSED_RESULT 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;
+  }
+
+  // You should probably only use this instead of Append() if you are using an
+  // infallible allocation policy. It will crash if the allocation fails.
+  template<typename U>
+  void InfallibleAppend(U&& aU)
+  {
+    bool ok = Append(mozilla::Forward<U>(aU));
+    MOZ_RELEASE_ASSERT(ok);
+  }
+
+  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()
+    {
+      MOZ_ASSERT(!Done());
+      return (*mSegment)[mIndex];
+    }
+
+    const T& Get() const
+    {
+      MOZ_ASSERT(!Done());
+      return (*mSegment)[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,161 @@
+/* -*- 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/Alignment.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); }
+};
+
+// We want to test Append(), which is fallible and marked with
+// MOZ_WARN_UNUSED_RESULT. But we're using an infallible alloc policy, and so
+// don't really need to check the result. Casting to |void| works with clang
+// but not GCC, so we instead use this dummy variable which works with both
+// compilers.
+static int gDummy;
+
+// 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++) {
+    gDummy = 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++) {
+    v.InfallibleAppend(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()
+{
+  {
+    // A SegmentedVector with a non-POD element type.
+    NonPOD x(1);                          // explicit constructor called
+    SegmentedVector<NonPOD, 64, InfallibleAllocPolicy> v;
+                                          // default constructor called 0 times
+    MOZ_RELEASE_ASSERT(v.IsEmpty());
+    gDummy = v.Append(x);                 // copy constructor called
+    NonPOD y(1);                          // explicit constructor called
+    gDummy = v.Append(mozilla::Move(y));  // move constructor called
+    NonPOD z(1);                          // explicit constructor called
+    v.InfallibleAppend(mozilla::Move(z)); // move constructor called
+    v.Clear();                            // destructor called 3 times
+
+    MOZ_RELEASE_ASSERT(gNumDefaultCtors  == 0);
+    MOZ_RELEASE_ASSERT(gNumExplicitCtors == 3);
+    MOZ_RELEASE_ASSERT(gNumCopyCtors     == 1);
+    MOZ_RELEASE_ASSERT(gNumMoveCtors     == 2);
+    MOZ_RELEASE_ASSERT(gNumDtors         == 3);
+  }                                       // destructor called for x, y, z
+  MOZ_RELEASE_ASSERT(gNumDtors == 6);
+}
+
+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, and that the elements are aligned appropriately.
+void TestSegmentCapacitiesAndAlignments()
+{
+  // 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.
+  //
+  // Also, SegmentedVector has a static assertion that elements are
+  // appropriately aligned.
+  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);
+  SegmentedVector<mozilla::AlignedElem<16>, 100> v7(100);
+}
+
+int main(void)
+{
+  TestBasics();
+  TestConstructorsAndDestructors();
+  TestSegmentCapacitiesAndAlignments();
+
+  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',
     'TestVector',
     'TestWeakPtr',
 ])