Properly implement emplaceBack/Front() in QArrayDataOps

This improves the performance of QList<QString>::append/prepend()
and we now beat QVector in Qt 5. QList from Qt 5 is still a bit
better for QString, but this might be related to the fact that
QString in Qt 6 is larger than in Qt 5.

Appending 20M integers to the list gives:

Qt 6:             35ms
Qt 5.15/QVector:  99ms
Qt 5.15/QList:    78ms

Appending 20M QStrings to the list gives:

Qt 6:            172ms
Qt 5.15/QVector: 194ms
Qt 5.15/QList:   136ms

Appending 20M structs of three pointers gives (100M will
crash in Qt5 as 100M*24bytes overflows):

Qt 6:            109ms
Qt 5.15/QVector: 272ms
Qt 5.15/QList:   469ms

Prepending 20M integers to the list gives:

Qt 6:             58ms
Qt 5.15/QList:    90ms

Prepending 20M QStrings to the list gives:

Qt 6:            448ms
Qt 5.15/QList:   147ms

Prepending 20M structs of three pointers gives (100M will
crash in Qt5 as 100M*24bytes overflows):

Qt 6:            267ms
Qt 5.15/QList:   435ms

No numbers for prepending to a QVector in 5.15 as the operation
was O(n) there. The difference in time between append and prepend
comes from the fact that our growth policy favors appending to
some extent.

Change-Id: Ice4598df5ca408413bfb00f5fe05e0b8d512623d
Reviewed-by: Thiago Macieira <thiago.macieira@intel.com>
Reviewed-by: Andrei Golubev <andrei.golubev@qt.io>

2 files changed, 17 insertions, 5 deletions

diff --git a/src/corelib/tools/qarraydataops.h b/src/corelib/tools/qarraydataops.h
index a864ac4c2b..d4fd08d54c 100644
--- a/src/corelib/tools/qarraydataops.h
+++ b/src/corelib/tools/qarraydataops.h
@@ -1255,7 +1255,20 @@ public:
     template <typename ...Args>
     void emplaceBack(Args&&... args)
     {
-        this->emplace(this->end(), std::forward<Args>(args)...);
+        Q_ASSERT(!this->isShared());
+        Q_ASSERT(this->freeSpaceAtEnd() >= 1);
+        new (this->end()) T(std::forward<Args>(args)...);
+        ++this->size;
+    }
+
+    template <typename ...Args>
+    void emplaceFront(Args&&... args)
+    {
+        Q_ASSERT(!this->isShared());
+        Q_ASSERT(this->freeSpaceAtBegin() >= 1);
+        new (this->ptr - 1) T(std::forward<Args>(args)...);
+        --this->ptr;
+        ++this->size;
     }
 
     void erase(T *b, T *e)
diff --git a/src/corelib/tools/qlist.h b/src/corelib/tools/qlist.h
index 3ea932c0fe..0d29c459df 100644
--- a/src/corelib/tools/qlist.h
+++ b/src/corelib/tools/qlist.h
@@ -711,15 +711,14 @@ inline typename QList<T>::reference QList<T>::emplaceFront(Args &&... args)
     if (d->needsDetach() || !d.freeSpaceAtBegin()) {
         DataPointer detached(DataPointer::allocateGrow(d, 1, QArrayData::AllocateAtBeginning));
 
-        detached->emplace(detached.begin(), std::forward<Args>(args)...);
+        detached->emplaceBack(std::forward<Args>(args)...);
         if (!d.needsDetach())
             detached->moveAppend(d.begin(), d.end());
         else
             detached->copyAppend(constBegin(), constEnd());
         d.swap(detached);
     } else {
-        // ### replace with emplaceFront
-        d->emplace(d.begin(), std::forward<Args>(args)...);
+        d->emplaceFront(std::forward<Args>(args)...);
     }
     return *d.begin();
 }
@@ -787,7 +786,7 @@ inline typename QList<T>::reference QList<T>::emplaceBack(Args &&... args)
             d->emplace(d.end(), std::move(tmp));
         }
     } else {
-        d->emplace(d.end(), std::forward<Args>(args)...);
+        d->emplaceBack(std::forward<Args>(args)...);
     }
     return *(d.end() - 1);
 }