Bug 1048044 - Use exponential growth when growing an nsTArray. r=froydnj.
authorNicholas Nethercote <nnethercote@mozilla.com>
Wed, 29 Oct 2014 20:34:33 -0700
changeset 213059 ac0d7bf37abced5397e34e1f1a5ccc3413c0a115
parent 213058 b56b9aa70d22803fd0d9f8a68e043dc863c2efe3
child 213060 7c2f1416473fc4c03f96299a68ba869de9467b48
push id27738
push usercbook@mozilla.com
push dateThu, 30 Oct 2014 13:46:07 +0000
treeherdermozilla-central@1aa1b23d799e [default view] [failures only]
perfherder[talos] [build metrics] [platform microbench] (compared to previous push)
reviewersfroydnj
bugs1048044
milestone36.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 1048044 - Use exponential growth when growing an nsTArray. r=froydnj.
xpcom/glue/nsTArray-inl.h
xpcom/glue/nsTArray.h
--- a/xpcom/glue/nsTArray-inl.h
+++ b/xpcom/glue/nsTArray-inl.h
@@ -123,55 +123,50 @@ nsTArray_base<Alloc, Copy>::EnsureCapaci
   // Additionally, if it exceeds uint32_t(-1) then we couldn't fit in the
   // Header::mCapacity member. Just bail out in cases like that.  We don't want
   // to be allocating 2 GB+ arrays anyway.
   if (!IsTwiceTheRequiredBytesRepresentableAsUint32(aCapacity, aElemSize)) {
     Alloc::SizeTooBig((size_t)aCapacity * aElemSize);
     return Alloc::FailureResult();
   }
 
+  size_t reqSize = sizeof(Header) + aCapacity * aElemSize;
+
   if (mHdr == EmptyHdr()) {
     // Malloc() new data
-    Header* header =
-      static_cast<Header*>(Alloc::Malloc(sizeof(Header) + aCapacity * aElemSize));
+    Header* header = static_cast<Header*>(Alloc::Malloc(reqSize));
     if (!header) {
       return Alloc::FailureResult();
     }
     header->mLength = 0;
     header->mCapacity = aCapacity;
     header->mIsAutoArray = 0;
     mHdr = header;
 
     return Alloc::SuccessResult();
   }
 
-  // We increase our capacity so |aCapacity * aElemSize + 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 size_t pageSizeBytes = 12;
-  const size_t pageSize = 1 << pageSizeBytes;
+  // We increase our capacity so that the allocated buffer grows exponentially,
+  // which gives us amortized O(1) appending. Below the threshold, we use
+  // powers-of-two. Above the threshold, we grow by at least 1.125, rounding up
+  // to the nearest MiB.
+  const size_t slowGrowthThreshold = 8 * 1024 * 1024;
 
-  size_t minBytes = aCapacity * aElemSize + sizeof(Header);
   size_t bytesToAlloc;
-  if (minBytes >= pageSize) {
-    // Round up to the next multiple of pageSize.
-    bytesToAlloc = pageSize * ((minBytes + pageSize - 1) / pageSize);
+  if (reqSize >= slowGrowthThreshold) {
+    size_t currSize = sizeof(Header) + Capacity() * aElemSize;
+    size_t minNewSize = currSize + (currSize >> 3); // multiply by 1.125
+    bytesToAlloc = reqSize > minNewSize ? reqSize : minNewSize;
+
+    // Round up to the next multiple of MiB.
+    const size_t MiB = 1 << 20;
+    bytesToAlloc = MiB * ((bytesToAlloc + MiB - 1) / MiB);
   } 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++;
-
-    MOZ_ASSERT((bytesToAlloc & (bytesToAlloc - 1)) == 0,
-               "nsTArray's allocation size should be a power of two!");
+    // Round up to the next power of two.
+    bytesToAlloc = mozilla::RoundUpPow2(reqSize);
   }
 
   Header* header;
   if (UsesAutoArrayBuffer() || !Copy::allowRealloc) {
     // Malloc() and copy
     header = static_cast<Header*>(Alloc::Malloc(bytesToAlloc));
     if (!header) {
       return Alloc::FailureResult();
--- a/xpcom/glue/nsTArray.h
+++ b/xpcom/glue/nsTArray.h
@@ -6,16 +6,17 @@
 
 #ifndef nsTArray_h__
 #define nsTArray_h__
 
 #include "nsTArrayForwardDeclare.h"
 #include "mozilla/Alignment.h"
 #include "mozilla/Assertions.h"
 #include "mozilla/BinarySearch.h"
+#include "mozilla/MathAlgorithms.h"
 #include "mozilla/MemoryReporting.h"
 #include "mozilla/Move.h"
 #include "mozilla/TypeTraits.h"
 
 #include <string.h>
 
 #include "nsCycleCollectionNoteChild.h"
 #include "nsAlgorithm.h"