Add AllocationOption::Grow

This is meant to reduce the number of allocations on growing containers.
It serves the same purpose as the existing qAllocMore which is currently
used by container classes.

While only a container knows when it is growing, it doesn't need to care
how that information is used. qAllocMore is currently treated as a
black-box and its result is (basically) forwarded blindly to an allocate
function. In that respect, container code using qAllocMore acts as an
intermediary.

By merging that functionality in the allocate function itself we offer
the same benefits without the intermediaries, allowing for simpler code
and centralized decisions on memory allocation.

Once all users of qAllocMore get ported to QArrayData and
QArrayData::allocate, qAllocMore can be moved or more closely integrated
into qarraydata.cpp and qtools_p.h can be dropped.

Change-Id: I4c09bf7df274b45c399082fc7113a18e4641c5f0
Reviewed-by: Bradley T. Hughes <bradley.hughes@nokia.com>

4 files changed, 49 insertions, 9 deletions

diff --git a/src/corelib/tools/qarraydata.cpp b/src/corelib/tools/qarraydata.cpp
index 5ed3ce015f..8498d0e4d5 100644
--- a/src/corelib/tools/qarraydata.cpp
+++ b/src/corelib/tools/qarraydata.cpp
@@ -40,6 +40,7 @@
 ****************************************************************************/
 
 #include <QtCore/qarraydata.h>
+#include <QtCore/private/qtools_p.h>
 
 #include <stdlib.h>
 
@@ -63,14 +64,20 @@ QArrayData *QArrayData::allocate(size_t objectSize, size_t alignment,
             ? const_cast<QArrayData *>(&qt_array_empty)
             : const_cast<QArrayData *>(&qt_array_unsharable_empty);
 
-    size_t allocSize = sizeof(QArrayData) + objectSize * capacity;
+    size_t headerSize = sizeof(QArrayData);
 
     // Allocate extra (alignment - Q_ALIGNOF(QArrayData)) padding bytes so we
     // can properly align the data array. This assumes malloc is able to
     // provide appropriate alignment for the header -- as it should!
     // Padding is skipped when allocating a header for RawData.
     if (!(options & RawData))
-        allocSize += (alignment - Q_ALIGNOF(QArrayData));
+        headerSize += (alignment - Q_ALIGNOF(QArrayData));
+
+    // Allocate additional space if array is growing
+    if (options & Grow)
+        capacity = qAllocMore(objectSize * capacity, headerSize) / objectSize;
+
+    size_t allocSize = headerSize + objectSize * capacity;
 
     QArrayData *header = static_cast<QArrayData *>(::malloc(allocSize));
     if (header) {
diff --git a/src/corelib/tools/qarraydata.h b/src/corelib/tools/qarraydata.h
index da2058dccf..351a75aade 100644
--- a/src/corelib/tools/qarraydata.h
+++ b/src/corelib/tools/qarraydata.h
@@ -81,9 +81,10 @@ struct Q_CORE_EXPORT QArrayData
     }
 
     enum AllocationOption {
-        CapacityReserved = 0x1,
-        Unsharable = 0x2,
-        RawData = 0x4,
+        CapacityReserved    = 0x1,
+        Unsharable          = 0x2,
+        RawData             = 0x4,
+        Grow                = 0x8,
 
         Default = 0
     };
diff --git a/tests/auto/corelib/tools/qarraydata/simplevector.h b/tests/auto/corelib/tools/qarraydata/simplevector.h
index a0a9b5f764..fe8108bff2 100644
--- a/tests/auto/corelib/tools/qarraydata/simplevector.h
+++ b/tests/auto/corelib/tools/qarraydata/simplevector.h
@@ -178,7 +178,7 @@ public:
                 || capacity() - size() < size_t(last - first)) {
             SimpleVector detached(Data::allocate(
                         qMax(capacity(), size() + (last - first)),
-                        d->detachFlags()));
+                        d->detachFlags() | Data::Grow));
 
             detached.d->copyAppend(first, last);
             detached.d->copyAppend(begin, begin + d->size);
@@ -199,7 +199,7 @@ public:
                 || capacity() - size() < size_t(last - first)) {
             SimpleVector detached(Data::allocate(
                         qMax(capacity(), size() + (last - first)),
-                        d->detachFlags()));
+                        d->detachFlags() | Data::Grow));
 
             if (d->size) {
                 const T *const begin = constBegin();
@@ -239,7 +239,7 @@ public:
                 || capacity() - size() < size_t(last - first)) {
             SimpleVector detached(Data::allocate(
                         qMax(capacity(), size() + (last - first)),
-                        d->detachFlags()));
+                        d->detachFlags() | Data::Grow));
 
             if (position)
                 detached.d->copyAppend(begin, where);
diff --git a/tests/auto/corelib/tools/qarraydata/tst_qarraydata.cpp b/tests/auto/corelib/tools/qarraydata/tst_qarraydata.cpp
index 36bf7516a9..f3f1daba0f 100644
--- a/tests/auto/corelib/tools/qarraydata/tst_qarraydata.cpp
+++ b/tests/auto/corelib/tools/qarraydata/tst_qarraydata.cpp
@@ -87,6 +87,7 @@ private slots:
     void literals();
     void variadicLiterals();
     void rValueReferences();
+    void grow();
 };
 
 template <class T> const T &const_(const T &t) { return t; }
@@ -651,6 +652,7 @@ void tst_QArrayData::allocate_data()
             QArrayData::CapacityReserved | QArrayData::Unsharable, true, false,
             unsharable_empty },
         { "Unsharable", QArrayData::Unsharable, false, false, unsharable_empty },
+        { "Grow", QArrayData::Grow, false, true, shared_empty }
     };
 
     for (size_t i = 0; i < sizeof(types)/sizeof(types[0]); ++i)
@@ -690,7 +692,10 @@ void tst_QArrayData::allocate()
         keeper.headers.append(data);
 
         QCOMPARE(data->size, 0);
-        QVERIFY(data->alloc >= uint(capacity));
+        if (allocateOptions & QArrayData::Grow)
+            QVERIFY(data->alloc > uint(capacity));
+        else
+            QCOMPARE(data->alloc, uint(capacity));
         QCOMPARE(data->capacityReserved, uint(isCapacityReserved));
         QCOMPARE(data->ref.isSharable(), isSharable);
 
@@ -1385,5 +1390,32 @@ void tst_QArrayData::rValueReferences()
 #endif
 }
 
+void tst_QArrayData::grow()
+{
+    SimpleVector<int> vector;
+
+    QCOMPARE(vector.size(), size_t(0));
+
+    size_t previousCapacity = vector.capacity();
+    size_t allocations = 0;
+    for (size_t i = 1; i <=  (1 << 20); ++i) {
+        int source[1] = { i };
+        vector.append(source, source + 1);
+        QCOMPARE(vector.size(), i);
+        if (vector.capacity() != previousCapacity) {
+            previousCapacity = vector.capacity();
+            ++allocations;
+        }
+    }
+    QCOMPARE(vector.size(), size_t(1 << 20));
+
+    // QArrayData::Grow prevents excessive allocations on a growing container
+    QVERIFY(allocations > 20 / 2);
+    QVERIFY(allocations < 20 * 2);
+
+    for (size_t i = 0; i < (1 << 20); ++i)
+        QCOMPARE(const_(vector).at(i), int(i + 1));
+}
+
 QTEST_APPLESS_MAIN(tst_QArrayData)
 #include "tst_qarraydata.moc"