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>

1 files changed, 19 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;
 }