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>

2 files changed, 10 insertions, 2 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);