From 250b69ace47923b51aaeaaea39e0ffc638fa4b4a Mon Sep 17 00:00:00 2001
From: Andrei Golubev <andrei.golubev@qt.io>
Date: Wed, 4 Nov 2020 17:58:12 +0100
Subject: Fix QArrayDataOps generic and relocatable emplace()
MIME-Version: 1.0
Content-Type: text/plain; charset=UTF-8
Content-Transfer-Encoding: 8bit

Emplace() implemented with std::rotate is just awful on my system
(Ubuntu 18.04 GCC 7.5.0). Custom code is much faster, so go for
it. Cannot really use insert() code, which is also fast, because
it doesn't forward-reference values but copies them always

Changes in performance (approximately) for emplacing 100k elements
into the middle:
Complex 7600ms -> 1700ms
Movable 7600ms -> 200ms

Task-number: QTBUG-86583
Change-Id: If883c9b8498a89e757f3806aea11f8fd3aa3c709
Reviewed-by: Mårten Nordheim <marten.nordheim@qt.io>
Reviewed-by: Lars Knoll <lars.knoll@qt.io>
Reviewed-by: Thiago Macieira <thiago.macieira@intel.com>
---
 src/corelib/tools/qarraydataops.h | 107 +++++++++++++++++++++++++++++++++++---
 1 file changed, 100 insertions(+), 7 deletions(-)

(limited to 'src/corelib/tools/qarraydataops.h')

diff --git a/src/corelib/tools/qarraydataops.h b/src/corelib/tools/qarraydataops.h
index 957fa9e218f..1fd7e99c42e 100644
--- a/src/corelib/tools/qarraydataops.h
+++ b/src/corelib/tools/qarraydataops.h
@@ -772,10 +772,31 @@ public:
         Q_ASSERT(where >= this->begin() && where <= this->end());
         Q_ASSERT(this->freeSpaceAtEnd() >= 1);
 
-        createInPlace(this->end(), std::forward<Args>(args)...);
-        ++this->size;
+        if (where == this->end()) {
+            createInPlace(this->end(), std::forward<Args>(args)...);
+            ++this->size;
+        } else {
+            T tmp(std::forward<Args>(args)...);
+
+            T *const end = this->end();
+            T *readIter = end - 1;
+            T *writeIter = end;
+
+            // Create new element at the end
+            new (writeIter) T(std::move(*readIter));
+            ++this->size;
+
+            // Move assign over existing elements
+            while (readIter != where) {
+                --readIter;
+                --writeIter;
+                *writeIter = std::move(*readIter);
+            }
 
-        std::rotate(where, this->end() - 1, this->end());
+            // Assign new element
+            --writeIter;
+            *writeIter = std::move(tmp);
+        }
     }
 
     template <typename iterator, typename ...Args>
@@ -785,11 +806,35 @@ public:
         Q_ASSERT(where >= this->begin() && where <= this->end());
         Q_ASSERT(this->freeSpaceAtBegin() >= 1);
 
-        createInPlace(this->begin() - 1, std::forward<Args>(args)...);
-        --this->ptr;
-        ++this->size;
+        if (where == this->begin()) {
+            createInPlace(this->begin() - 1, std::forward<Args>(args)...);
+            --this->ptr;
+            ++this->size;
+        } else {
+            T tmp(std::forward<Args>(args)...);
+
+            T *const begin = this->begin();
+            T *readIter = begin;
+            T *writeIter = begin - 1;
+
+            // Create new element at the beginning
+            new (writeIter) T(std::move(*readIter));
+            --this->ptr;
+            ++this->size;
+
+            ++readIter;
+            ++writeIter;
+
+            // Move assign over existing elements
+            while (readIter != where) {
+                *writeIter = std::move(*readIter);
+                ++readIter;
+                ++writeIter;
+            }
 
-        std::rotate(this->begin(), this->begin() + 1, where);
+            // Assign new element
+            *writeIter = std::move(tmp);
+        }
     }
 
     void erase(T *b, T *e)
@@ -998,6 +1043,54 @@ public:
     // use moving insert
     using QGenericArrayOps<T>::insert;
 
+    template<typename iterator, typename... Args>
+    void emplace(iterator where, Args &&... args)
+    {
+        emplace(GrowsForwardTag {}, where, std::forward<Args>(args)...);
+    }
+
+    template<typename iterator, typename... Args>
+    void emplace(GrowsForwardTag, iterator where, Args &&... args)
+    {
+        Q_ASSERT(!this->isShared());
+        Q_ASSERT(where >= this->begin() && where <= this->end());
+        Q_ASSERT(this->freeSpaceAtEnd() >= 1);
+
+        if (where == this->end()) {
+            this->createInPlace(where, std::forward<Args>(args)...);
+        } else {
+            T tmp(std::forward<Args>(args)...);
+            typedef typename QArrayExceptionSafetyPrimitives<T>::Displacer ReversibleDisplace;
+            ReversibleDisplace displace(where, this->end(), 1);
+            this->createInPlace(where, std::move(tmp));
+            displace.commit();
+        }
+        ++this->size;
+    }
+
+    template<typename iterator, typename... Args>
+    void emplace(GrowsBackwardsTag, iterator where, Args &&... args)
+    {
+        Q_ASSERT(!this->isShared());
+        Q_ASSERT(where >= this->begin() && where <= this->end());
+        Q_ASSERT(this->freeSpaceAtBegin() >= 1);
+
+        if (where == this->begin()) {
+            this->createInPlace(where - 1, std::forward<Args>(args)...);
+        } else {
+            T tmp(std::forward<Args>(args)...);
+            typedef typename QArrayExceptionSafetyPrimitives<T>::Displacer ReversibleDisplace;
+            ReversibleDisplace displace(this->begin(), where, -1);
+            this->createInPlace(where - 1, std::move(tmp));
+            displace.commit();
+        }
+        --this->ptr;
+        ++this->size;
+    }
+
+    // use moving emplace
+    using QGenericArrayOps<T>::emplace;
+
     void erase(T *b, T *e)
     { erase(GrowsForwardTag{}, b, e); }
 
-- 
cgit v1.2.3