Bug 685438 - Avoid wasted space in nsTArray_base due to jemalloc rounding up. r=roc
authorJustin Lebar <justin.lebar@gmail.com>
Wed, 21 Sep 2011 00:46:56 -0400
changeset 77249 069e927983a90bf6d6b04e06f23b5aad05b087a4
parent 77234 c18a3ab59221d23f3818b018c7e9a850bdad91da
child 77250 a3d4a447c8fc8512b169b9d5679f6ab198d5fab6
push id3
push userfelipc@gmail.com
push dateFri, 30 Sep 2011 20:09:13 +0000
reviewersroc
bugs685438
milestone9.0a1
Bug 685438 - Avoid wasted space in nsTArray_base due to jemalloc rounding up. r=roc
xpcom/glue/nsTArray-inl.h
--- a/xpcom/glue/nsTArray-inl.h
+++ b/xpcom/glue/nsTArray-inl.h
@@ -80,40 +80,63 @@ nsTArray_base<Alloc>::EnsureCapacity(siz
     header->mLength = 0;
     header->mCapacity = capacity;
     header->mIsAutoArray = 0;
     mHdr = header;
 
     return PR_TRUE;
   }
 
-  // Use doubling algorithm when forced to increase available
-  // capacity.  (Note that mCapacity is only 31 bits wide, so
-  // multiplication promotes its type. We use |2u| instead of |2|
-  // to make sure it's promoted to unsigned.)
-  capacity = NS_MAX<size_type>(capacity, mHdr->mCapacity * 2U);
+  // We increase our capacity so |capacity * elemSize + sizeof(Header)| is the
+  // next power of two, if this value is less than pageSize bytes, or otherwise
+  // so it's the next multiple of pageSize.
+  const PRUint32 pageSizeBytes = 12;
+  const PRUint32 pageSize = 1 << pageSizeBytes;
+
+  PRUint32 minBytes = capacity * elemSize + sizeof(Header);
+  PRUint32 bytesToAlloc;
+  if (minBytes >= pageSize) {
+    // Round up to the next multiple of pageSize.
+    bytesToAlloc = pageSize * ((minBytes + pageSize - 1) / pageSize);
+  }
+  else {
+    // Round up to the next power of two.  See
+    // http://graphics.stanford.edu/~seander/bithacks.html
+    bytesToAlloc = minBytes - 1;
+    bytesToAlloc |= bytesToAlloc >> 1;
+    bytesToAlloc |= bytesToAlloc >> 2;
+    bytesToAlloc |= bytesToAlloc >> 4;
+    bytesToAlloc |= bytesToAlloc >> 8;
+    bytesToAlloc |= bytesToAlloc >> 16;
+    bytesToAlloc++;
+
+    NS_ASSERTION((bytesToAlloc & (bytesToAlloc - 1)) == 0,
+                 "nsTArray's allocation size should be a power of two!");
+  }
 
   Header *header;
   if (UsesAutoArrayBuffer()) {
     // Malloc() and copy
-    header = static_cast<Header*>
-             (Alloc::Malloc(sizeof(Header) + capacity * elemSize));
+    header = static_cast<Header*>(Alloc::Malloc(bytesToAlloc));
     if (!header)
       return PR_FALSE;
 
     memcpy(header, mHdr, sizeof(Header) + Length() * elemSize);
   } else {
     // Realloc() existing data
-    size_type size = sizeof(Header) + capacity * elemSize;
-    header = static_cast<Header*>(Alloc::Realloc(mHdr, size));
+    header = static_cast<Header*>(Alloc::Realloc(mHdr, bytesToAlloc));
     if (!header)
       return PR_FALSE;
   }
 
-  header->mCapacity = capacity;
+  // How many elements can we fit in bytesToAlloc?
+  PRUint32 newCapacity = (bytesToAlloc - sizeof(Header)) / elemSize;
+  NS_ASSERTION(newCapacity >= capacity, "Didn't enlarge the array enough!");
+  header->mCapacity = newCapacity;
+
   mHdr = header;
 
   return PR_TRUE;
 }
 
 template<class Alloc>
 void
 nsTArray_base<Alloc>::ShrinkCapacity(size_type elemSize) {