Issue #2148 - Shrink Vector from (usually) four pointers in size to three

when no inline storage is used.

See Bug 1338374

2 files changed, 168 insertions, 82 deletions

diff --git a/mfbt/Vector.h b/mfbt/Vector.h
index b8fc4617bc..1fcd77242b 100644
--- a/mfbt/Vector.h
+++ b/mfbt/Vector.h
@@ -146,7 +146,7 @@ struct VectorImpl
     aV.free_(aV.mBegin);
     aV.mBegin = newbuf;
     /* aV.mLength is unchanged. */
-    aV.mCapacity = aNewCap;
+    aV.mTail.mCapacity = aNewCap;
     return true;
   }
 };
@@ -225,28 +225,30 @@ struct VectorImpl<T, N, AP, true>
   {
     MOZ_ASSERT(!aV.usingInlineStorage());
     MOZ_ASSERT(!CapacityHasExcessSpace<T>(aNewCap));
-    T* newbuf = aV.template pod_realloc<T>(aV.mBegin, aV.mCapacity, aNewCap);
+    T* newbuf =
+      aV.template pod_realloc<T>(aV.mBegin, aV.mTail.mCapacity, aNewCap);
     if (MOZ_UNLIKELY(!newbuf)) {
       return false;
     }
     aV.mBegin = newbuf;
     /* aV.mLength is unchanged. */
-    aV.mCapacity = aNewCap;
+    aV.mTail.mCapacity = aNewCap;
     return true;
   }
 
   static inline void
   podResizeToFit(Vector<T, N, AP>& aV)
   {
-    if (aV.usingInlineStorage() || aV.mLength == aV.mCapacity) {
+    if (aV.usingInlineStorage() || aV.mLength == aV.mTail.mCapacity) {
       return;
     }
-    T* newbuf = aV.template pod_realloc<T>(aV.mBegin, aV.mCapacity, aV.mLength);
+    T* newbuf =
+      aV.template pod_realloc<T>(aV.mBegin, aV.mTail.mCapacity, aV.mLength);
     if (MOZ_UNLIKELY(!newbuf)) {
       return;
     }
     aV.mBegin = newbuf;
-    aV.mCapacity = aV.mLength;
+    aV.mTail.mCapacity = aV.mLength;
   }
 };
 
@@ -341,42 +343,84 @@ class MOZ_NON_PARAM Vector final : private AllocPolicy
   /* Number of elements in the vector. */
   size_t mLength;
 
-  /* Max number of elements storable in the vector without resizing. */
-  size_t mCapacity;
-
-#ifdef DEBUG
-  /* Max elements of reserved or used space in this vector. */
-  size_t mReserved;
-#endif
-
   /*
-   * Memory used for inline storage.  We want basically this:
+   * Memory used to store capacity, reserved element count (debug builds only),
+   * and inline storage.  The simple "answer" is:
+   *
+   *   size_t mCapacity;
+   *   #ifdef DEBUG
+   *   size_t mReserved;
+   *   #endif
+   *   alignas(T) unsigned char mBytes[kInlineCapacity * sizeof(T)];
    *
-   *   alignas(T) unsigned char storage[kInlineCapacity * sizeof(T)];
+   * but there are complications.  First, C++ forbids zero-sized arrays that
+   * might result.  Second, we don't want zero capacity to affect Vector's size
+   * (even empty classes take up a byte, unless they're base classes).
    *
-   * but C++ forbids zero-sized arrays that might result if we did this.  We fix
-   * this by (again) using partial specialization, defining an array only if
-   * contains at least one element.
+   * Yet again, we eliminate the zero-sized array using partial specialization.
+   * And we eliminate potential size hit by putting capacity/reserved in one
+   * struct, then putting the array (if any) in a derived struct.  If no array
+   * is needed, the derived struct won't consume extra space.
    */
+  struct CapacityAndReserved
+  {
+    explicit CapacityAndReserved(size_t aCapacity, size_t aReserved)
+      : mCapacity(aCapacity)
+#ifdef DEBUG
+      , mReserved(aReserved)
+#endif
+    {}
+    CapacityAndReserved() = default;
+
+    /* Max number of elements storable in the vector without resizing. */
+    size_t mCapacity;
+
+#ifdef DEBUG
+    /* Max elements of reserved or used space in this vector. */
+    size_t mReserved;
+#endif
+  };
+
+// Silence warnings about this struct possibly being padded dued to the
+// alignas() in it -- there's nothing we can do to avoid it.
+#ifdef _MSC_VER
+#  pragma warning(push)
+#  pragma warning(disable:4324)
+#endif // _MSC_VER
+
   template<size_t Capacity, size_t Dummy>
-  struct InlineStorage
+  struct CRAndStorage : CapacityAndReserved
   {
+    explicit CRAndStorage(size_t aCapacity, size_t aReserved)
+      : CapacityAndReserved(aCapacity, aReserved)
+    {}
+    CRAndStorage() = default;
+
     alignas(T) unsigned char mBytes[Capacity * sizeof(T)];
 
     // GCC fails due to -Werror=strict-aliasing if |mBytes| is directly cast to
     // T*.  Indirecting through this function addresses the problem.
     void* data() { return mBytes; }
 
-    T* addr() { return static_cast<T*>(data()); }
+    T* storage() { return static_cast<T*>(data()); }
   };
 
   template<size_t Dummy>
-  struct InlineStorage<0, Dummy>
+  struct CRAndStorage<0, Dummy> : CapacityAndReserved
   {
-    T* addr() { return nullptr; }
+    explicit CRAndStorage(size_t aCapacity, size_t aReserved)
+      : CapacityAndReserved(aCapacity, aReserved)
+    {}
+    CRAndStorage() = default;
+
+    T* storage() { return nullptr; }
   };
 
-  InlineStorage<kInlineCapacity, 0> mStorage;
+  CRAndStorage<kInlineCapacity, 0> mTail;
+
+#ifdef _MSC_VER
+#  pragma warning(pop)
+#endif // _MSC_VER
 
 #ifdef DEBUG
   friend class ReentrancyGuard;
@@ -392,7 +436,7 @@ class MOZ_NON_PARAM Vector final : private AllocPolicy
 
   T* inlineStorage()
   {
-    return mStorage.addr();
+    return mTail.storage();
   }
 
   T* beginNoCheck() const
@@ -420,9 +464,9 @@ class MOZ_NON_PARAM Vector final : private AllocPolicy
    */
   size_t reserved() const
   {
-    MOZ_ASSERT(mLength <= mReserved);
-    MOZ_ASSERT(mReserved <= mCapacity);
-    return mReserved;
+    MOZ_ASSERT(mLength <= mTail.mReserved);
+    MOZ_ASSERT(mTail.mReserved <= mTail.mCapacity);
+    return mTail.mReserved;
   }
 #endif
 
@@ -455,7 +499,7 @@ public:
 
   bool empty() const { return mLength == 0; }
 
-  size_t capacity() const { return mCapacity; }
+  size_t capacity() const { return mTail.mCapacity; }
 
   T* begin()
   {
@@ -782,10 +826,10 @@ private:
 /* This does the re-entrancy check plus several other sanity checks. */
 #define MOZ_REENTRANCY_GUARD_ET_AL \
   ReentrancyGuard g(*this); \
-  MOZ_ASSERT_IF(usingInlineStorage(), mCapacity == kInlineCapacity); \
-  MOZ_ASSERT(reserved() <= mCapacity); \
+  MOZ_ASSERT_IF(usingInlineStorage(), mTail.mCapacity == kInlineCapacity); \
+  MOZ_ASSERT(reserved() <= mTail.mCapacity); \
   MOZ_ASSERT(mLength <= reserved()); \
-  MOZ_ASSERT(mLength <= mCapacity)
+  MOZ_ASSERT(mLength <= mTail.mCapacity)
 
 /* Vector Implementation */
 
@@ -794,9 +838,8 @@ MOZ_ALWAYS_INLINE
 Vector<T, N, AP>::Vector(AP aAP)
   : AP(aAP)
   , mLength(0)
-  , mCapacity(kInlineCapacity)
+  , mTail(kInlineCapacity, 0)
 #ifdef DEBUG
-  , mReserved(0)
   , mEntered(false)
 #endif
 {
@@ -813,9 +856,9 @@ Vector<T, N, AllocPolicy>::Vector(Vector&& aRhs)
 #endif
 {
   mLength = aRhs.mLength;
-  mCapacity = aRhs.mCapacity;
+  mTail.mCapacity = aRhs.mTail.mCapacity;
 #ifdef DEBUG
-  mReserved = aRhs.mReserved;
+  mTail.mReserved = aRhs.mTail.mReserved;
 #endif
 
   if (aRhs.usingInlineStorage()) {
@@ -833,10 +876,10 @@ Vector<T, N, AllocPolicy>::Vector(Vector&& aRhs)
      */
     mBegin = aRhs.mBegin;
     aRhs.mBegin = aRhs.inlineStorage();
-    aRhs.mCapacity = kInlineCapacity;
+    aRhs.mTail.mCapacity = kInlineCapacity;
     aRhs.mLength = 0;
 #ifdef DEBUG
-    aRhs.mReserved = 0;
+    aRhs.mTail.mReserved = 0;
 #endif
   }
 }
@@ -900,7 +943,7 @@ Vector<T, N, AP>::convertToHeapStorage(size_t aNewCap)
   /* Switch in heap buffer. */
   mBegin = newBuf;
   /* mLength is unchanged. */
-  mCapacity = aNewCap;
+  mTail.mCapacity = aNewCap;
   return true;
 }
 
@@ -908,7 +951,7 @@ template<typename T, size_t N, class AP>
 MOZ_NEVER_INLINE bool
 Vector<T, N, AP>::growStorageBy(size_t aIncr)
 {
-  MOZ_ASSERT(mLength + aIncr > mCapacity);
+  MOZ_ASSERT(mLength + aIncr > mTail.mCapacity);
 
   /*
    * When choosing a new capacity, its size should is as close to 2**N bytes
@@ -1000,9 +1043,9 @@ Vector<T, N, AP>::initCapacity(size_t aRequest)
     return false;
   }
   mBegin = newbuf;
-  mCapacity = aRequest;
+  mTail.mCapacity = aRequest;
 #ifdef DEBUG
-  mReserved = aRequest;
+  mTail.mReserved = aRequest;
 #endif
   return true;
 }
@@ -1027,7 +1070,7 @@ Vector<T, N, AP>::maybeCheckSimulatedOOM(size_t aRequestedSize)
   }
 
 #ifdef DEBUG
-  if (aRequestedSize <= mReserved) {
+  if (aRequestedSize <= mTail.mReserved) {
     return true;
   }
 #endif
@@ -1040,7 +1083,7 @@ inline bool
 Vector<T, N, AP>::reserve(size_t aRequest)
 {
   MOZ_REENTRANCY_GUARD_ET_AL;
-  if (aRequest > mCapacity) {
+  if (aRequest > mTail.mCapacity) {
     if (MOZ_UNLIKELY(!growStorageBy(aRequest - mLength))) {
       return false;
     }
@@ -1048,11 +1091,11 @@ Vector<T, N, AP>::reserve(size_t aRequest)
     return false;
   }
 #ifdef DEBUG
-  if (aRequest > mReserved) {
-    mReserved = aRequest;
+  if (aRequest > mTail.mReserved) {
+    mTail.mReserved = aRequest;
   }
-  MOZ_ASSERT(mLength <= mReserved);
-  MOZ_ASSERT(mReserved <= mCapacity);
+  MOZ_ASSERT(mLength <= mTail.mReserved);
+  MOZ_ASSERT(mTail.mReserved <= mTail.mCapacity);
 #endif
   return true;
 }
@@ -1080,20 +1123,20 @@ MOZ_ALWAYS_INLINE bool
 Vector<T, N, AP>::growBy(size_t aIncr)
 {
   MOZ_REENTRANCY_GUARD_ET_AL;
-  if (aIncr > mCapacity - mLength) {
+  if (aIncr > mTail.mCapacity - mLength) {
     if (MOZ_UNLIKELY(!growStorageBy(aIncr))) {
       return false;
     }
   } else if (!maybeCheckSimulatedOOM(mLength + aIncr)) {
     return false;
   }
-  MOZ_ASSERT(mLength + aIncr <= mCapacity);
+  MOZ_ASSERT(mLength + aIncr <= mTail.mCapacity);
   T* newend = endNoCheck() + aIncr;
   Impl::initialize(endNoCheck(), newend);
   mLength += aIncr;
 #ifdef DEBUG
-  if (mLength > mReserved) {
-    mReserved = mLength;
+  if (mLength > mTail.mReserved) {
+    mTail.mReserved = mLength;
   }
 #endif
   return true;
@@ -1104,7 +1147,7 @@ MOZ_ALWAYS_INLINE bool
 Vector<T, N, AP>::growByUninitialized(size_t aIncr)
 {
   MOZ_REENTRANCY_GUARD_ET_AL;
-  if (aIncr > mCapacity - mLength) {
+  if (aIncr > mTail.mCapacity - mLength) {
     if (MOZ_UNLIKELY(!growStorageBy(aIncr))) {
       return false;
     }
@@ -1112,8 +1155,8 @@ Vector<T, N, AP>::growByUninitialized(size_t aIncr)
     return false;
   }
 #ifdef DEBUG
-  if (mLength + aIncr > mReserved) {
-    mReserved = mLength + aIncr;
+  if (mLength + aIncr > mTail.mReserved) {
+    mTail.mReserved = mLength + aIncr;
   }
 #endif
   infallibleGrowByUninitialized(aIncr);
@@ -1172,9 +1215,9 @@ Vector<T, N, AP>::clearAndFree()
   }
   this->free_(beginNoCheck());
   mBegin = inlineStorage();
-  mCapacity = kInlineCapacity;
+  mTail.mCapacity = kInlineCapacity;
 #ifdef DEBUG
-  mReserved = 0;
+  mTail.mReserved = 0;
 #endif
 }
 
@@ -1191,7 +1234,7 @@ template<typename T, size_t N, class AP>
 inline bool
 Vector<T, N, AP>::canAppendWithoutRealloc(size_t aNeeded) const
 {
-  return mLength + aNeeded <= mCapacity;
+  return mLength + aNeeded <= mTail.mCapacity;
 }
 
 template<typename T, size_t N, class AP>
@@ -1207,8 +1250,8 @@ template<typename U>
 MOZ_ALWAYS_INLINE void
 Vector<T, N, AP>::internalAppend(U&& aU)
 {
-  MOZ_ASSERT(mLength + 1 <= mReserved);
-  MOZ_ASSERT(mReserved <= mCapacity);
+  MOZ_ASSERT(mLength + 1 <= mTail.mReserved);
+  MOZ_ASSERT(mTail.mReserved <= mTail.mCapacity);
   Impl::new_(endNoCheck(), Forward<U>(aU));
   ++mLength;
 }
@@ -1218,7 +1261,7 @@ MOZ_ALWAYS_INLINE bool
 Vector<T, N, AP>::appendN(const T& aT, size_t aNeeded)
 {
   MOZ_REENTRANCY_GUARD_ET_AL;
-  if (mLength + aNeeded > mCapacity) {
+  if (mLength + aNeeded > mTail.mCapacity) {
     if (MOZ_UNLIKELY(!growStorageBy(aNeeded))) {
       return false;
     }
@@ -1226,8 +1269,8 @@ Vector<T, N, AP>::appendN(const T& aT, size_t aNeeded)
     return false;
   }
 #ifdef DEBUG
-  if (mLength + aNeeded > mReserved) {
-    mReserved = mLength + aNeeded;
+  if (mLength + aNeeded > mTail.mReserved) {
+    mTail.mReserved = mLength + aNeeded;
   }
 #endif
   internalAppendN(aT, aNeeded);
@@ -1238,8 +1281,8 @@ template<typename T, size_t N, class AP>
 MOZ_ALWAYS_INLINE void
 Vector<T, N, AP>::internalAppendN(const T& aT, size_t aNeeded)
 {
-  MOZ_ASSERT(mLength + aNeeded <= mReserved);
-  MOZ_ASSERT(mReserved <= mCapacity);
+  MOZ_ASSERT(mLength + aNeeded <= mTail.mReserved);
+  MOZ_ASSERT(mTail.mReserved <= mTail.mCapacity);
   Impl::copyConstructN(endNoCheck(), aNeeded, aT);
   mLength += aNeeded;
 }
@@ -1304,7 +1347,7 @@ Vector<T, N, AP>::append(const U* aInsBegin, const U* aInsEnd)
 {
   MOZ_REENTRANCY_GUARD_ET_AL;
   size_t aNeeded = PointerRangeSize(aInsBegin, aInsEnd);
-  if (mLength + aNeeded > mCapacity) {
+  if (mLength + aNeeded > mTail.mCapacity) {
     if (MOZ_UNLIKELY(!growStorageBy(aNeeded))) {
       return false;
     }
@@ -1312,8 +1355,8 @@ Vector<T, N, AP>::append(const U* aInsBegin, const U* aInsEnd)
       return false;
   }
 #ifdef DEBUG
-  if (mLength + aNeeded > mReserved) {
-    mReserved = mLength + aNeeded;
+  if (mLength + aNeeded > mTail.mReserved) {
+    mTail.mReserved = mLength + aNeeded;
   }
 #endif
   internalAppend(aInsBegin, aNeeded);
@@ -1325,8 +1368,8 @@ template<typename U>
 MOZ_ALWAYS_INLINE void
 Vector<T, N, AP>::internalAppend(const U* aInsBegin, size_t aInsLength)
 {
-  MOZ_ASSERT(mLength + aInsLength <= mReserved);
-  MOZ_ASSERT(mReserved <= mCapacity);
+  MOZ_ASSERT(mLength + aInsLength <= mTail.mReserved);
+  MOZ_ASSERT(mTail.mReserved <= mTail.mCapacity);
   Impl::copyConstruct(endNoCheck(), aInsBegin, aInsBegin + aInsLength);
   mLength += aInsLength;
 }
@@ -1337,7 +1380,7 @@ MOZ_ALWAYS_INLINE bool
 Vector<T, N, AP>::append(U&& aU)
 {
   MOZ_REENTRANCY_GUARD_ET_AL;
-  if (mLength == mCapacity) {
+  if (mLength == mTail.mCapacity) {
     if (MOZ_UNLIKELY(!growStorageBy(1))) {
       return false;
     }
@@ -1345,8 +1388,8 @@ Vector<T, N, AP>::append(U&& aU)
       return false;
   }
 #ifdef DEBUG
-  if (mLength + 1 > mReserved) {
-    mReserved = mLength + 1;
+  if (mLength + 1 > mTail.mReserved) {
+    mTail.mReserved = mLength + 1;
   }
 #endif
   internalAppend(Forward<U>(aU));
@@ -1401,9 +1444,9 @@ Vector<T, N, AP>::extractRawBuffer()
   T* ret = mBegin;
   mBegin = inlineStorage();
   mLength = 0;
-  mCapacity = kInlineCapacity;
+  mTail.mCapacity = kInlineCapacity;
 #ifdef DEBUG
-  mReserved = 0;
+  mTail.mReserved = 0;
 #endif
   return ret;
 }
@@ -1427,9 +1470,9 @@ Vector<T, N, AP>::extractOrCopyRawBuffer()
   Impl::destroy(beginNoCheck(), endNoCheck());
   mBegin = inlineStorage();
   mLength = 0;
-  mCapacity = kInlineCapacity;
+  mTail.mCapacity = kInlineCapacity;
 #ifdef DEBUG
-  mReserved = 0;
+  mTail.mReserved = 0;
 #endif
   return copy;
 }
@@ -1455,17 +1498,17 @@ Vector<T, N, AP>::replaceRawBuffer(T* aP, size_t aLength)
      */
     mBegin = inlineStorage();
     mLength = aLength;
-    mCapacity = kInlineCapacity;
+    mTail.mCapacity = kInlineCapacity;
     Impl::moveConstruct(mBegin, aP, aP + aLength);
     Impl::destroy(aP, aP + aLength);
     this->free_(aP);
   } else {
     mBegin = aP;
     mLength = aLength;
-    mCapacity = aLength;
+    mTail.mCapacity = aLength;
   }
 #ifdef DEBUG
-  mReserved = aLength;
+  mTail.mReserved = aLength;
 #endif
 }
 
@@ -1504,9 +1547,9 @@ Vector<T, N, AP>::swap(Vector& aOther)
   }
 
   Swap(mLength, aOther.mLength);
-  Swap(mCapacity, aOther.mCapacity);
+  Swap(mTail.mCapacity, aOther.mTail.mCapacity);
 #ifdef DEBUG
-  Swap(mReserved, aOther.mReserved);
+  Swap(mTail.mReserved, aOther.mTail.mReserved);
 #endif
 }
 
diff --git a/mfbt/tests/TestVector.cpp b/mfbt/tests/TestVector.cpp
index 24baf8eae7..9aed9e617c 100644
--- a/mfbt/tests/TestVector.cpp
+++ b/mfbt/tests/TestVector.cpp
@@ -396,6 +396,49 @@ mozilla::detail::VectorTesting::testInsert()
   MOZ_RELEASE_ASSERT(S::destructCount == 1);
 }
 
+// Declare but leave (permanently) incomplete.
+struct Incomplete;
+
+// We could even *construct* a Vector<Incomplete, 0> if we wanted.  But we can't
+// destruct it, so it's not worth the trouble.
+static_assert(sizeof(Vector<Incomplete, 0>) > 0,
+              "Vector of an incomplete type will compile");
+
+// Vector with no inline storage should occupy the absolute minimum space in
+// non-debug builds.  (Debug adds a laundry list of other constraints, none
+// directly relevant to shipping builds, that aren't worth precisely modeling.)
+#ifndef DEBUG
+
+template<typename T>
+struct NoInlineStorageLayout
+{
+  T* mBegin;
+  size_t mLength;
+  struct CRAndStorage {
+    size_t mCapacity;
+  } mTail;
+};
+
+// Only one of these should be necessary, but test a few of them for good
+// measure.
+static_assert(sizeof(Vector<int, 0>) == sizeof(NoInlineStorageLayout<int>),
+              "Vector of int without inline storage shouldn't occupy dead "
+              "space for that absence of storage");
+
+static_assert(sizeof(Vector<bool, 0>) == sizeof(NoInlineStorageLayout<bool>),
+              "Vector of bool without inline storage shouldn't occupy dead "
+              "space for that absence of storage");
+
+static_assert(sizeof(Vector<S, 0>) == sizeof(NoInlineStorageLayout<S>),
+              "Vector of S without inline storage shouldn't occupy dead "
+              "space for that absence of storage");
+
+static_assert(sizeof(Vector<Incomplete, 0>) == sizeof(NoInlineStorageLayout<Incomplete>),
+              "Vector of an incomplete class without inline storage shouldn't "
+              "occupy dead space for that absence of storage");
+
+#endif // DEBUG
+
 int
 main()
 {