QVector - removeLast optimize

In case somebody uses QVector as a stack, it is not fair to have
takeLast, removeLast and pop_back to do way too much work.

This is still very slow compared to std::vector::pop_back
(mostly due implicit sharing), however it is more than a
factor faster than before.

Change-Id: I636872675e80c8ca0c8ebc94b04f587a2dcd6d8d
Reviewed-by: Thiago Macieira <thiago.macieira@intel.com>

3 files changed, 64 insertions, 1 deletions

diff --git a/src/corelib/tools/qvector.h b/src/corelib/tools/qvector.h
index e2c28e4060..a06fb7b4eb 100644
--- a/src/corelib/tools/qvector.h
+++ b/src/corelib/tools/qvector.h
@@ -139,7 +139,7 @@ public:
     void remove(int i);
     void remove(int i, int n);
     inline void removeFirst() { Q_ASSERT(!isEmpty()); erase(d->begin()); }
-    inline void removeLast()  { Q_ASSERT(!isEmpty()); erase(d->end() - 1); }
+    inline void removeLast();
     inline T takeFirst() { Q_ASSERT(!isEmpty()); T r = first(); removeFirst(); return r; }
     inline T takeLast()  { Q_ASSERT(!isEmpty()); T r = last(); removeLast(); return r; }
 
@@ -558,6 +558,22 @@ void QVector<T>::append(const T &t)
 }
 
 template <typename T>
+inline void QVector<T>::removeLast()
+{
+    Q_ASSERT(!isEmpty());
+
+    if (d->alloc) {
+        if (d->ref.isShared()) {
+            reallocData(d->size - 1, int(d->alloc));
+            return;
+        }
+        if (QTypeInfo<T>::isComplex)
+            (d->data() + d->size - 1)->~T();
+        --d->size;
+    }
+}
+
+template <typename T>
 typename QVector<T>::iterator QVector<T>::insert(iterator before, size_type n, const T &t)
 {
     int offset = std::distance(d->begin(), before);
@@ -606,6 +622,7 @@ typename QVector<T>::iterator QVector<T>::erase(iterator abegin, iterator aend)
 
     // FIXME we could do a proper realloc, which copy constructs only needed data.
     // FIXME we ara about to delete data maybe it is good time to shrink?
+    // FIXME the shrink is also an issue in removeLast, that is just a copy + reduce of this.
     if (d->alloc) {
         detach();
         abegin = d->begin() + itemsUntouched;
diff --git a/tests/auto/corelib/tools/qvector/tst_qvector.cpp b/tests/auto/corelib/tools/qvector/tst_qvector.cpp
index 99fbb9cf98..53caec4a64 100644
--- a/tests/auto/corelib/tools/qvector/tst_qvector.cpp
+++ b/tests/auto/corelib/tools/qvector/tst_qvector.cpp
@@ -1479,6 +1479,15 @@ void tst_QVector::removeFirstLast() const
     QCOMPARE(v2.at(0), 1);
     QCOMPARE(v3.at(0), 1);
     QCOMPARE(v3.at(1), 2);
+
+    // Remove last with shared
+    QVector<int> z1, z2;
+    z1.append(9);
+    z2 = z1;
+    z1.removeLast();
+    QCOMPARE(z1.size(), 0);
+    QCOMPARE(z2.size(), 1);
+    QCOMPARE(z2.at(0), 9);
 }
 
 
diff --git a/tests/benchmarks/corelib/tools/qvector/main.cpp b/tests/benchmarks/corelib/tools/qvector/main.cpp
index 1795f2dc6f..3c6defb572 100644
--- a/tests/benchmarks/corelib/tools/qvector/main.cpp
+++ b/tests/benchmarks/corelib/tools/qvector/main.cpp
@@ -206,6 +206,7 @@ private slots:
     void qvector_separator() { qWarning() << "QVector results: "; }
     void qvector_const_read_access();
     void qvector_mutable_read_access();
+    void qvector_pop_back();
     #ifdef TEST_RETURN
     void qvector_fill_and_return();
     #endif
@@ -214,6 +215,8 @@ private slots:
     void stdvector() { qWarning() << "std::vector results: "; }
     void stdvector_const_read_access();
     void stdvector_mutable_read_access();
+    void stdvector_pop_back();
+
     #ifdef TEST_RETURN
     void stdvector_fill_and_return();
     #endif
@@ -315,6 +318,24 @@ void tst_QVector::qrawvector_mutable_read_access()
     }
 }
 
+void tst_QVector::qvector_pop_back()
+{
+    const int c1 = 100000;
+    QVERIFY(N % c1 == 0);
+
+    QVector<int> v;
+    v.resize(N);
+
+    QBENCHMARK {
+        for (int i = 0; i < c1; ++i)
+            v.pop_back();
+        if (v.size() == 0)
+            v.resize(N);
+    }
+}
+
+
+
 #ifdef TEST_RETURN
 extern QVector<double> qrawvector_fill_and_return_helper();
 
@@ -356,6 +377,22 @@ void tst_QVector::stdvector_mutable_read_access()
     }
 }
 
+void tst_QVector::stdvector_pop_back()
+{
+    const int c1 = 100000;
+    QVERIFY(N % c1 == 0);
+
+    std::vector<int> v;
+    v.resize(N);
+
+    QBENCHMARK {
+        for (int i = 0; i < c1; ++i)
+            v.pop_back();
+        if (v.size() == 0)
+            v.resize(N);
+    }
+}
+
 #ifdef TEST_RETURN
 extern std::vector<double> stdvector_fill_and_return_helper();