From 9f865df5d1bd98b8fd43e72c1d0c21f42ae3afec Mon Sep 17 00:00:00 2001 From: Ritt Konstantin Date: Wed, 13 Jul 2011 18:14:38 +0200 Subject: 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 (cherry picked from commit b209fe3b1a51f64541067917e96de99f14ad65f3) Change-Id: Ia26036ed741cefcf4b5868b7b2fc5eae8130d3dc Reviewed-on: http://codereview.qt-project.org/4577 Reviewed-by: Qt Sanity Bot Reviewed-by: Oswald Buddenhagen --- src/corelib/tools/qlist.h | 30 +-- tests/benchmarks/corelib/tools/qlist/main.cpp | 250 +++++++++++++++++++++++++ tests/benchmarks/corelib/tools/qlist/qlist.pro | 5 + tests/benchmarks/corelib/tools/tools.pro | 1 + 4 files changed, 275 insertions(+), 11 deletions(-) create mode 100644 tests/benchmarks/corelib/tools/qlist/main.cpp create mode 100644 tests/benchmarks/corelib/tools/qlist/qlist.pro 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::clear() template Q_OUTOFLINE_TEMPLATE int QList::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(p.at(i)))->t() == t) { - node_destruct(n); - p.remove(i); - ++removedCount; - } else { - ++i; - } + detach(); + + Node *i = reinterpret_cast(p.at(index)); + Node *e = reinterpret_cast(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 +#include + +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 +void removeAll_test(const QList &i10, ushort valueToRemove, int itemsToRemove) +{ + bool isComplex = QTypeInfo::isComplex; + + MyBase::errorCount = 0; + MyBase::liveCount = 0; + MyBase::copyCount = 0; + { + QList 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 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); + +void tst_QList::removeAll_primitive_data() +{ + qRegisterMetaType >(); + + QTest::addColumn >("i10"); + QTest::addColumn("valueToRemove"); + QTest::addColumn("itemsToRemove"); + + QTest::newRow("0%") << (QList() << 0 << 0 << 0 << 0 << 0 << 0 << 0 << 0 << 0 << 0) << 5 << 0; + QTest::newRow("10%") << (QList() << 0 << 0 << 0 << 0 << 5 << 0 << 0 << 0 << 0 << 0) << 5 << 1; + QTest::newRow("90%") << (QList() << 5 << 5 << 5 << 5 << 0 << 5 << 5 << 5 << 5 << 5) << 5 << 9; + QTest::newRow("100%") << (QList() << 5 << 5 << 5 << 5 << 5 << 5 << 5 << 5 << 5 << 5) << 5 << 10; +} + +void tst_QList::removeAll_primitive() +{ + QFETCH(QList, i10); + QFETCH(int, valueToRemove); + QFETCH(int, itemsToRemove); + + removeAll_test(i10, valueToRemove, itemsToRemove); +} + +void tst_QList::removeAll_movable_data() +{ + removeAll_primitive_data(); +} + +void tst_QList::removeAll_movable() +{ + QFETCH(QList, i10); + QFETCH(int, valueToRemove); + QFETCH(int, itemsToRemove); + + removeAll_test(i10, valueToRemove, itemsToRemove); +} + +void tst_QList::removeAll_complex_data() +{ + removeAll_primitive_data(); +} + +void tst_QList::removeAll_complex() +{ + QFETCH(QList, i10); + QFETCH(int, valueToRemove); + QFETCH(int, itemsToRemove); + + removeAll_test(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 \ -- cgit v1.2.3