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>

1 files changed, 15 insertions, 7 deletions

diff --git a/tests/auto/corelib/tools/qarraydata/tst_qarraydata.cpp b/tests/auto/corelib/tools/qarraydata/tst_qarraydata.cpp
index 4c520d0eaa..b7d07f836e 100644
--- a/tests/auto/corelib/tools/qarraydata/tst_qarraydata.cpp
+++ b/tests/auto/corelib/tools/qarraydata/tst_qarraydata.cpp
@@ -2094,6 +2094,7 @@ void tst_QArrayData::dataPointerAllocate()
         using DataPointer = QArrayDataPointer<Type>;
 
         auto oldDataPointer = createDataPointer(capacity, initValue);
+        oldDataPointer->insert(oldDataPointer.begin(), 1, initValue);
         oldDataPointer->insert(oldDataPointer.begin(), 1, initValue);  // trigger prepend
         QVERIFY(!oldDataPointer.needsDetach());
 
@@ -2105,11 +2106,14 @@ void tst_QArrayData::dataPointerAllocate()
 
         QVERIFY(newAlloc > oldDataPointer.constAllocatedCapacity());
         QCOMPARE(freeAtBegin + freeAtEnd, newAlloc);
-        // when not detached, the behavior is the same as of ::realloc
-        if (allocationOptions & (QArrayData::GrowsForward | QArrayData::GrowsBackwards))
+        if (allocationOptions & QArrayData::GrowsBackwards) {
+            // bad check, but will suffice for now, hopefully
+            QCOMPARE(freeAtBegin, (newAlloc - newSize) / 2);
+        } else if (allocationOptions & QArrayData::GrowsForward) {
             QCOMPARE(freeAtBegin, oldDataPointer.freeSpaceAtBegin());
-        else
+        } else {
             QCOMPARE(freeAtBegin, 0);
+        }
     };
 
     for (size_t n : {10, 512, 1000}) {
@@ -2186,14 +2190,18 @@ void tst_QArrayData::dataPointerAllocateAlignedWithReallocate()
         QVERIFY(a.freeSpaceAtBegin() == 0);
     }
     QCOMPARE(a.freeSpaceAtBegin(), b.freeSpaceAtBegin());
+    const auto oldSpaceAtBeginA = a.freeSpaceAtBegin();
 
     a->reallocate(100, newFlags);
     b = QArrayDataPointer<int>::allocateGrow(b, 100, b.size, newFlags);
 
-    // It is enough to test that the behavior of reallocate is the same as the
-    // behavior of allocate w.r.t. pointer adjustment in case of
-    // GrowsBackwards. Actual values are not that interesting
-    QCOMPARE(a.freeSpaceAtBegin(), b.freeSpaceAtBegin());
+    // NB: when growing backwards, the behavior is not aligned
+    if (!(newFlags & QArrayData::GrowsBackwards)) {
+        QCOMPARE(a.freeSpaceAtBegin(), b.freeSpaceAtBegin());
+    } else {
+        QCOMPARE(a.freeSpaceAtBegin(), oldSpaceAtBeginA);
+        QCOMPARE(b.freeSpaceAtBegin(), b.constAllocatedCapacity() / 2);
+    }
 }
 
 #ifndef QT_NO_EXCEPTIONS