optimize QList::removeAll()

a) don't detach until an occurrence found
b) don't memmove every time an occurrence found
c) truncate quickly )

well, numbers are better than words:
before:
RESULT : tst_QList::removeAll_primitive():
     2,617,902 CPU ticks per iteration (total: 261,790,171, iterations: 100)
RESULT : tst_QList::removeAll_movable():
     2,547,540 CPU ticks per iteration (total: 254,753,960, iterations: 100)
RESULT : tst_QList::removeAll_complex():
     16,852,099 CPU ticks per iteration (total: 1,685,209,906, iterations: 100)

after:
RESULT : tst_QList::removeAll_primitive():
     73,520 CPU ticks per iteration (total: 73,520,442, iterations: 1000)
RESULT : tst_QList::removeAll_movable():
     90,422 CPU ticks per iteration (total: 90,422,464, iterations: 1000)
RESULT : tst_QList::removeAll_complex():
     9,667,073 CPU ticks per iteration (total: 9,667,072,670, iterations: 1000)

Merge-request: 1285
Reviewed-by: Oswald Buddenhagen <oswald.buddenhagen@nokia.com>

(cherry picked from commit b209fe3b1a51f64541067917e96de99f14ad65f3)

Change-Id: Ia26036ed741cefcf4b5868b7b2fc5eae8130d3dc
Reviewed-on: http://codereview.qt-project.org/4577
Reviewed-by: Qt Sanity Bot <qt_sanity_bot@ovi.com>
Reviewed-by: Oswald Buddenhagen <oswald.buddenhagen@nokia.com>

4 files changed, 275 insertions, 11 deletions

diff --git a/src/corelib/tools/qlist.h b/src/corelib/tools/qlist.h
index b4c35b8d35..5c9845539a 100644
--- a/src/corelib/tools/qlist.h
+++ b/src/corelib/tools/qlist.h
@@ -750,18 +750,26 @@ Q_OUTOFLINE_TEMPLATE void QList<T>::clear()
 template <typename T>
 Q_OUTOFLINE_TEMPLATE int QList<T>::removeAll(const T &_t)
 {
-    detachShared();
+    int index = indexOf(_t);
+    if (index == -1)
+        return 0;
+
     const T t = _t;
-    int removedCount=0, i=0;
-    Node *n;
-    while (i < p.size())
-        if ((n = reinterpret_cast<Node *>(p.at(i)))->t() == t) {
-            node_destruct(n);
-            p.remove(i);
-            ++removedCount;
-        } else {
-            ++i;
-        }
+    detach();
+
+    Node *i = reinterpret_cast<Node *>(p.at(index));
+    Node *e = reinterpret_cast<Node *>(p.end());
+    Node *n = i;
+    node_destruct(i);
+    while (++i != e) {
+        if (i->t() == t)
+            node_destruct(i);
+        else
+            *n++ = *i;
+    }
+
+    int removedCount = e - n;
+    d->end -= removedCount;
     return removedCount;
 }
 
diff --git a/tests/benchmarks/corelib/tools/qlist/main.cpp b/tests/benchmarks/corelib/tools/qlist/main.cpp
new file mode 100644
index 0000000000..22aaf49861
--- /dev/null
+++ b/tests/benchmarks/corelib/tools/qlist/main.cpp
@@ -0,0 +1,250 @@
+/****************************************************************************
+**
+** Copyright (C) 2011 Nokia Corporation and/or its subsidiary(-ies).
+** All rights reserved.
+** Contact: Nokia Corporation (qt-info@nokia.com)
+**
+** This file is part of the QtCore module of the Qt Toolkit.
+**
+** $QT_BEGIN_LICENSE:LGPL$
+** GNU Lesser General Public License Usage
+** This file may be used under the terms of the GNU Lesser General Public
+** License version 2.1 as published by the Free Software Foundation and
+** appearing in the file LICENSE.LGPL included in the packaging of this
+** file. Please review the following information to ensure the GNU Lesser
+** General Public License version 2.1 requirements will be met:
+** http://www.gnu.org/licenses/old-licenses/lgpl-2.1.html.
+**
+** In addition, as a special exception, Nokia gives you certain additional
+** rights. These rights are described in the Nokia Qt LGPL Exception
+** version 1.1, included in the file LGPL_EXCEPTION.txt in this package.
+**
+** GNU General Public License Usage
+** Alternatively, this file may be used under the terms of the GNU General
+** Public License version 3.0 as published by the Free Software Foundation
+** and appearing in the file LICENSE.GPL included in the packaging of this
+** file. Please review the following information to ensure the GNU General
+** Public License version 3.0 requirements will be met:
+** http://www.gnu.org/copyleft/gpl.html.
+**
+** Other Usage
+** Alternatively, this file may be used in accordance with the terms and
+** conditions contained in a signed written agreement between you and Nokia.
+**
+**
+**
+**
+**
+** $QT_END_LICENSE$
+**
+****************************************************************************/
+
+#include <QList>
+#include <QTest>
+
+static const int N = 1000;
+
+struct MyBase
+{
+    MyBase(int i_)
+        : isCopy(false)
+    {
+        ++liveCount;
+
+        i = i_;
+    }
+
+    MyBase(const MyBase &other)
+        : isCopy(true)
+    {
+        if (isCopy)
+            ++copyCount;
+        ++liveCount;
+
+        i = other.i;
+    }
+
+    MyBase &operator=(const MyBase &other)
+    {
+        if (!isCopy) {
+            isCopy = true;
+            ++copyCount;
+        } else {
+            ++errorCount;
+        }
+
+        i = other.i;
+        return *this;
+    }
+
+    ~MyBase()
+    {
+        if (isCopy) {
+            if (!copyCount)
+                ++errorCount;
+            else
+                --copyCount;
+        }
+        if (!liveCount)
+            ++errorCount;
+        else
+            --liveCount;
+    }
+
+    bool operator==(const MyBase &other) const
+    { return i == other.i; }
+
+protected:
+    ushort i;
+    bool isCopy;
+
+public:
+    static int errorCount;
+    static int liveCount;
+    static int copyCount;
+};
+
+int MyBase::errorCount = 0;
+int MyBase::liveCount = 0;
+int MyBase::copyCount = 0;
+
+struct MyPrimitive : public MyBase
+{
+    MyPrimitive(int i = -1) : MyBase(i)
+    { ++errorCount; }
+    MyPrimitive(const MyPrimitive &other) : MyBase(other)
+    { ++errorCount; }
+    ~MyPrimitive()
+    { ++errorCount; }
+};
+
+struct MyMovable : public MyBase
+{
+    MyMovable(int i = -1) : MyBase(i) {}
+};
+
+struct MyComplex : public MyBase
+{
+    MyComplex(int i = -1) : MyBase(i) {}
+};
+
+QT_BEGIN_NAMESPACE
+
+Q_DECLARE_TYPEINFO(MyPrimitive, Q_PRIMITIVE_TYPE);
+Q_DECLARE_TYPEINFO(MyMovable, Q_MOVABLE_TYPE);
+Q_DECLARE_TYPEINFO(MyComplex, Q_COMPLEX_TYPE);
+
+QT_END_NAMESPACE
+
+
+class tst_QList: public QObject
+{
+    Q_OBJECT
+
+private Q_SLOTS:
+    void removeAll_primitive_data();
+    void removeAll_primitive();
+    void removeAll_movable_data();
+    void removeAll_movable();
+    void removeAll_complex_data();
+    void removeAll_complex();
+};
+
+template <class T>
+void removeAll_test(const QList<int> &i10, ushort valueToRemove, int itemsToRemove)
+{
+    bool isComplex = QTypeInfo<T>::isComplex;
+
+    MyBase::errorCount = 0;
+    MyBase::liveCount = 0;
+    MyBase::copyCount = 0;
+    {
+        QList<T> list;
+        QCOMPARE(MyBase::liveCount, 0);
+        QCOMPARE(MyBase::copyCount, 0);
+
+        for (int i = 0; i < 10 * N; ++i) {
+            T t(i10.at(i % 10));
+            list.append(t);
+        }
+        QCOMPARE(MyBase::liveCount, isComplex ? list.size() : 0);
+        QCOMPARE(MyBase::copyCount, isComplex ? list.size() : 0);
+
+        T t(valueToRemove);
+        QCOMPARE(MyBase::liveCount, isComplex ? list.size() + 1 : 1);
+        QCOMPARE(MyBase::copyCount, isComplex ? list.size() : 0);
+
+        int removedCount;
+        QList<T> l;
+
+        QBENCHMARK {
+            l = list;
+            removedCount = l.removeAll(t);
+        }
+        QCOMPARE(removedCount, itemsToRemove * N);
+        QCOMPARE(l.size() + removedCount, list.size());
+        QVERIFY(!l.contains(valueToRemove));
+
+        QCOMPARE(MyBase::liveCount, isComplex ? l.isDetached() ? list.size() + l.size() + 1 : list.size() + 1 : 1);
+        QCOMPARE(MyBase::copyCount, isComplex ? l.isDetached() ? list.size() + l.size() : list.size() : 0);
+    }
+    if (isComplex)
+        QCOMPARE(MyBase::errorCount, 0);
+}
+
+Q_DECLARE_METATYPE(QList<int>);
+
+void tst_QList::removeAll_primitive_data()
+{
+    qRegisterMetaType<QList<int> >();
+
+    QTest::addColumn<QList<int> >("i10");
+    QTest::addColumn<int>("valueToRemove");
+    QTest::addColumn<int>("itemsToRemove");
+
+    QTest::newRow("0%")   << (QList<int>() << 0 << 0 << 0 << 0 << 0 << 0 << 0 << 0 << 0 << 0) << 5 << 0;
+    QTest::newRow("10%")  << (QList<int>() << 0 << 0 << 0 << 0 << 5 << 0 << 0 << 0 << 0 << 0) << 5 << 1;
+    QTest::newRow("90%")  << (QList<int>() << 5 << 5 << 5 << 5 << 0 << 5 << 5 << 5 << 5 << 5) << 5 << 9;
+    QTest::newRow("100%") << (QList<int>() << 5 << 5 << 5 << 5 << 5 << 5 << 5 << 5 << 5 << 5) << 5 << 10;
+}
+
+void tst_QList::removeAll_primitive()
+{
+    QFETCH(QList<int>, i10);
+    QFETCH(int, valueToRemove);
+    QFETCH(int, itemsToRemove);
+
+    removeAll_test<MyPrimitive>(i10, valueToRemove, itemsToRemove);
+}
+
+void tst_QList::removeAll_movable_data()
+{
+    removeAll_primitive_data();
+}
+
+void tst_QList::removeAll_movable()
+{
+    QFETCH(QList<int>, i10);
+    QFETCH(int, valueToRemove);
+    QFETCH(int, itemsToRemove);
+
+    removeAll_test<MyMovable>(i10, valueToRemove, itemsToRemove);
+}
+
+void tst_QList::removeAll_complex_data()
+{
+    removeAll_primitive_data();
+}
+
+void tst_QList::removeAll_complex()
+{
+    QFETCH(QList<int>, i10);
+    QFETCH(int, valueToRemove);
+    QFETCH(int, itemsToRemove);
+
+    removeAll_test<MyComplex>(i10, valueToRemove, itemsToRemove);
+}
+
+QTEST_APPLESS_MAIN(tst_QList)
+
+#include "main.moc"
diff --git a/tests/benchmarks/corelib/tools/qlist/qlist.pro b/tests/benchmarks/corelib/tools/qlist/qlist.pro
new file mode 100644
index 0000000000..902e72eb2e
--- /dev/null
+++ b/tests/benchmarks/corelib/tools/qlist/qlist.pro
@@ -0,0 +1,5 @@
+load(qttest_p4)
+TARGET = tst_qlist
+QT = core
+
+SOURCES += main.cpp
diff --git a/tests/benchmarks/corelib/tools/tools.pro b/tests/benchmarks/corelib/tools/tools.pro
index 681a6c6e74..44e8973522 100644
--- a/tests/benchmarks/corelib/tools/tools.pro
+++ b/tests/benchmarks/corelib/tools/tools.pro
@@ -3,6 +3,7 @@ SUBDIRS = \
         containers-associative \
         containers-sequential \
         qbytearray \
+        qlist \
         qrect \
         qregexp \
         qstring \