Fix performance issue with QList::insert() for complex T

When storing complex types in the list and inserting in the middle,
we ended up in some cases moving the items in the list onto itself,
to make space for 0 new items.

Obviously that's not a very good idea. It was not a huge deal for
POD or relocatable types as we'd use memmove in that case which would
return quickly. But for complex types, we actually did copy around
half of the items stored in the list onto themselves.

Change-Id: I54467dccf2e17ba4a604bded755242197dd96b06
Reviewed-by: Mårten Nordheim <marten.nordheim@qt.io>
Reviewed-by: Thiago Macieira <thiago.macieira@intel.com>
Reviewed-by: Andrei Golubev <andrei.golubev@qt.io>

1 files changed, 28 insertions, 16 deletions

diff --git a/src/corelib/tools/qarraydataops.h b/src/corelib/tools/qarraydataops.h
index d4fd08d54c..d8508b22a8 100644
--- a/src/corelib/tools/qarraydataops.h
+++ b/src/corelib/tools/qarraydataops.h
@@ -288,7 +288,7 @@ public:
         Q_ASSERT(this->isMutable() || (b == e && where == this->end()));
         Q_ASSERT(!this->isShared() || (b == e && where == this->end()));
         Q_ASSERT(where >= this->begin() && where <= this->end());
-        Q_ASSERT(b <= e);
+        Q_ASSERT(b < e);
         Q_ASSERT(e <= where || b > this->end() || where == this->end()); // No overlap or append
         Q_ASSERT((e - b) <= this->freeSpaceAtEnd());
 
@@ -303,7 +303,7 @@ public:
         Q_ASSERT(this->isMutable() || (b == e && where == this->end()));
         Q_ASSERT(!this->isShared() || (b == e && where == this->end()));
         Q_ASSERT(where >= this->begin() && where <= this->end());
-        Q_ASSERT(b <= e);
+        Q_ASSERT(b < e);
         Q_ASSERT(e <= where || b > this->end() || where == this->end()); // No overlap or append
         Q_ASSERT((e - b) <= this->freeSpaceAtBegin());
 
@@ -321,7 +321,8 @@ public:
 
     void insert(GrowsForwardTag, T *where, size_t n, parameter_type t)
     {
-        Q_ASSERT(!this->isShared() || (n == 0 && where == this->end()));
+        Q_ASSERT(!this->isShared());
+        Q_ASSERT(n);
         Q_ASSERT(where >= this->begin() && where <= this->end());
         Q_ASSERT(size_t(this->freeSpaceAtEnd()) >= n);
 
@@ -334,7 +335,8 @@ public:
 
     void insert(GrowsBackwardsTag, T *where, size_t n, parameter_type t)
     {
-        Q_ASSERT(!this->isShared() || (n == 0 && where == this->end()));
+        Q_ASSERT(!this->isShared());
+        Q_ASSERT(n);
         Q_ASSERT(where >= this->begin() && where <= this->end());
         Q_ASSERT(size_t(this->freeSpaceAtBegin()) >= n);
 
@@ -543,7 +545,7 @@ public:
         Q_ASSERT(this->isMutable() || (b == e && where == this->end()));
         Q_ASSERT(!this->isShared() || (b == e && where == this->end()));
         Q_ASSERT(where >= this->begin() && where <= this->end());
-        Q_ASSERT(b <= e);
+        Q_ASSERT(b < e);
         Q_ASSERT(e <= where || b > this->end() || where == this->end()); // No overlap or append
         Q_ASSERT((e - b) <= this->freeSpaceAtEnd());
 
@@ -596,7 +598,7 @@ public:
         Q_ASSERT(this->isMutable() || (b == e && where == this->end()));
         Q_ASSERT(!this->isShared() || (b == e && where == this->end()));
         Q_ASSERT(where >= this->begin() && where <= this->end());
-        Q_ASSERT(b <= e);
+        Q_ASSERT(b < e);
         Q_ASSERT(e <= where || b > this->end() || where == this->end()); // No overlap or append
         Q_ASSERT((e - b) <= this->freeSpaceAtBegin());
 
@@ -646,7 +648,8 @@ public:
 
     void insert(GrowsForwardTag, T *where, size_t n, parameter_type t)
     {
-        Q_ASSERT(!this->isShared() || (n == 0 && where == this->end()));
+        Q_ASSERT(!this->isShared());
+        Q_ASSERT(n);
         Q_ASSERT(where >= this->begin() && where <= this->end());
         Q_ASSERT(size_t(this->freeSpaceAtEnd()) >= n);
 
@@ -695,7 +698,8 @@ public:
 
     void insert(GrowsBackwardsTag, T *where, size_t n, parameter_type t)
     {
-        Q_ASSERT(!this->isShared() || (n == 0 && where == this->end()));
+        Q_ASSERT(!this->isShared());
+        Q_ASSERT(n);
         Q_ASSERT(where >= this->begin() && where <= this->end());
         Q_ASSERT(size_t(this->freeSpaceAtBegin()) >= n);
 
@@ -873,7 +877,7 @@ public:
         Q_ASSERT(this->isMutable() || (b == e && where == this->end()));
         Q_ASSERT(!this->isShared() || (b == e && where == this->end()));
         Q_ASSERT(where >= this->begin() && where <= this->end());
-        Q_ASSERT(b <= e);
+        Q_ASSERT(b < e);
         Q_ASSERT(e <= where || b > this->end() || where == this->end()); // No overlap or append
         Q_ASSERT((e - b) <= this->freeSpaceAtEnd());
 
@@ -895,7 +899,7 @@ public:
         Q_ASSERT(this->isMutable() || (b == e && where == this->end()));
         Q_ASSERT(!this->isShared() || (b == e && where == this->end()));
         Q_ASSERT(where >= this->begin() && where <= this->end());
-        Q_ASSERT(b <= e);
+        Q_ASSERT(b < e);
         Q_ASSERT(e <= where || b > this->end() || where == this->end()); // No overlap or append
         Q_ASSERT((e - b) <= this->freeSpaceAtBegin());
 
@@ -918,7 +922,8 @@ public:
 
     void insert(GrowsForwardTag, T *where, size_t n, parameter_type t)
     {
-        Q_ASSERT(!this->isShared() || (n == 0 && where == this->end()));
+        Q_ASSERT(!this->isShared());
+        Q_ASSERT(n);
         Q_ASSERT(where >= this->begin() && where <= this->end());
         Q_ASSERT(size_t(this->freeSpaceAtEnd()) >= n);
 
@@ -937,7 +942,8 @@ public:
 
     void insert(GrowsBackwardsTag, T *where, size_t n, parameter_type t)
     {
-        Q_ASSERT(!this->isShared() || (n == 0 && where == this->end()));
+        Q_ASSERT(!this->isShared());
+        Q_ASSERT(n);
         Q_ASSERT(where >= this->begin() && where <= this->end());
         Q_ASSERT(size_t(this->freeSpaceAtBegin()) >= n);
 
@@ -1169,6 +1175,8 @@ public:
     {
         Q_ASSERT(!this->isShared() || n == 0);
         Q_ASSERT(size_t(this->allocatedCapacity() - this->size) >= n);
+        if (!n)
+            return;
 
         Base::insert(GrowsForwardTag{}, this->end(), n, t);
     }
@@ -1200,8 +1208,10 @@ public:
                 // free space by reallocating more frequently)
                 T *where = this->begin() + i;
                 const auto beginSize = sizeToInsertAtBegin(where, n);
-                Base::insert(GrowsBackwardsTag{}, where, beginSize, copy);
-                Base::insert(GrowsForwardTag{}, where, qsizetype(n) - beginSize, copy);
+                if (beginSize)
+                    Base::insert(GrowsBackwardsTag{}, where, beginSize, copy);
+                if (n - beginSize)
+                    Base::insert(GrowsForwardTag{}, where, n - beginSize, copy);
             }
         }
     }
@@ -1227,8 +1237,10 @@ public:
             // free space by reallocating more frequently)
             T *where = this->begin() + i;
             const auto k = sizeToInsertAtBegin(where, n);
-            Base::insert(GrowsBackwardsTag{}, where, data, data + k);
-            Base::insert(GrowsForwardTag{}, where, data + k, data + n);
+            if (k)
+                Base::insert(GrowsBackwardsTag{}, where, data, data + k);
+            if (k != n)
+                Base::insert(GrowsForwardTag{}, where, data + k, data + n);
         }
 
     }