QArrayDataPointer: redesign (and simplify) growth policy

It looks like we can drastically simplify the way QADP grows without
sacrificing much:
1. append-only use cases should have the same performance as before
2. prepend-only use cases should (with the help of other commits) get
   additional performance speedup
3. mid-insertion is harder to reason about, but it is either unchanged
   or benefits a bit as there's some free space at both ends now
4. mixed prepend/append cases are weird and would keep excess free
   space around but this is less critical and overall less used AFAIK

Now, QList would actually start to feel like a double-ended container
instead of "it's QVector but with faster prepend". This commit should
help close the performance gap between 6.0 and 5.15 as well

As a drawback, we will most likely have more space allocated in mixed
and mid-insert cases. This needs to be checked

Task-number: QTBUG-86583
Change-Id: I7c6ede896144920fe01862b9fe789c8fdfc11f80
Reviewed-by: Lars Knoll <lars.knoll@qt.io>
Reviewed-by: Thiago Macieira <thiago.macieira@intel.com>

4 files changed, 27 insertions, 32 deletions

diff --git a/src/corelib/text/qbytearray.cpp b/src/corelib/text/qbytearray.cpp
index c6dbf4c7aa..e550224c4c 100644
--- a/src/corelib/text/qbytearray.cpp
+++ b/src/corelib/text/qbytearray.cpp
@@ -1728,7 +1728,11 @@ void QByteArray::reallocGrowData(qsizetype alloc, Data::ArrayOptions options)
     if (!alloc)  // expected to always allocate
         alloc = 1;
 
-    if (d->needsDetach()) {
+    // when we're requested to grow backwards, it means we're in prepend-like
+    // case. realloc() is good, but we might actually get more free space at the
+    // beginning with a call to allocateGrow, so prefer that instead
+    const bool preferAllocateGrow = options & Data::GrowsBackwards;
+    if (d->needsDetach() || preferAllocateGrow) {
         const auto newSize = qMin(alloc, d.size);
         DataPointer dd(DataPointer::allocateGrow(d, alloc, newSize, options));
         dd->copyAppend(d.data(), d.data() + newSize);
diff --git a/src/corelib/text/qstring.cpp b/src/corelib/text/qstring.cpp
index 26d0a7acc8..d77ade226e 100644
--- a/src/corelib/text/qstring.cpp
+++ b/src/corelib/text/qstring.cpp
@@ -2525,7 +2525,11 @@ void QString::reallocGrowData(qsizetype alloc, Data::ArrayOptions options)
     if (!alloc)  // expected to always allocate
         alloc = 1;
 
-    if (d->needsDetach()) {
+    // when we're requested to grow backwards, it means we're in prepend-like
+    // case. realloc() is good, but we might actually get more free space at the
+    // beginning with a call to allocateGrow, so prefer that instead
+    const bool preferAllocateGrow = options & Data::GrowsBackwards;
+    if (d->needsDetach() || preferAllocateGrow) {
         const auto newSize = qMin(alloc, d.size);
         DataPointer dd(DataPointer::allocateGrow(d, alloc, newSize, options));
         dd->copyAppend(d.data(), d.data() + newSize);
diff --git a/src/corelib/tools/qarraydataops.h b/src/corelib/tools/qarraydataops.h
index 9626f4eeff..3b95d04fa8 100644
--- a/src/corelib/tools/qarraydataops.h
+++ b/src/corelib/tools/qarraydataops.h
@@ -1320,23 +1320,15 @@ public:
 
         const qsizetype freeAtBegin = this->freeSpaceAtBegin();
         const qsizetype freeAtEnd = this->freeSpaceAtEnd();
-        const qsizetype capacity = this->constAllocatedCapacity();
 
-        if (this->size > 0 && where == this->begin()) {  // prepend
-            // Qt5 QList in prepend: not enough space at begin && 33% full
-            // Now (below):
-            return freeAtBegin < n && (this->size >= (capacity / 3));
+        // Idea: always reallocate when not enough space at the corresponding end
+        if (where == this->end()) { // append or size == 0
+            return freeAtEnd < n;
+        } else if (where == this->begin()) { // prepend
+            return freeAtBegin < n;
+        } else { // general insert
+            return (freeAtBegin < n && freeAtEnd < n);
         }
-
-        if (where == this->end()) {  // append
-            // Qt5 QList in append: not enough space at end && less than 66% free space at front
-            // Now (below):
-            return freeAtEnd < n && !((freeAtBegin - n) >= (2 * capacity / 3));
-        }
-
-        // Qt5 QList in insert: no free space
-        // Now: no free space OR not enough space on either of the sides (bad perf. case)
-        return (freeAtBegin + freeAtEnd) < n || (freeAtBegin < n && freeAtEnd < n);
     }
 
     // using Base::truncate;
diff --git a/src/corelib/tools/qarraydatapointer.h b/src/corelib/tools/qarraydatapointer.h
index ad90b1d580..3cabeca649 100644
--- a/src/corelib/tools/qarraydatapointer.h
+++ b/src/corelib/tools/qarraydatapointer.h
@@ -222,21 +222,16 @@ public:
         if (!valid || !grows)
             return QArrayDataPointer(header, dataPtr);
 
-        // when growing, special rules apply to memory layout
-
-        if (from.needsDetach()) {
-            // When detaching: the free space reservation is biased towards
-            // append as in Qt5 QList. If we're growing backwards, put the data
-            // in the middle instead of at the end - assuming that prepend is
-            // uncommon and even initial prepend will eventually be followed by
-            // at least some appends.
-            if (options & Data::GrowsBackwards)
-                dataPtr += (header->alloc - newSize) / 2;
-        } else {
-            // When not detaching: fake ::realloc() policy - preserve existing
-            // free space at beginning.
-            dataPtr += from.freeSpaceAtBegin();
-        }
+        // must always hold true, as valid is the first condition we check and
+        // if-statement short-circuits
+        Q_ASSERT(valid);
+
+        // Idea: * when growing backwards, adjust pointer to prepare free space at the beginning
+        //       * when growing forward, adjust by the previous data pointer offset
+
+        // TODO: what's with CapacityReserved?
+        dataPtr += (options & Data::GrowsBackwards) ? (header->alloc - newSize) / 2
+                                                    : from.freeSpaceAtBegin();
         return QArrayDataPointer(header, dataPtr);
     }