diff options
Diffstat (limited to 'tests/benchmarks/corelib/tools/qlist')
| -rw-r--r-- | tests/benchmarks/corelib/tools/qlist/CMakeLists.txt | 7 | ||||
| -rw-r--r-- | tests/benchmarks/corelib/tools/qlist/main.cpp | 560 | ||||
| -rw-r--r-- | tests/benchmarks/corelib/tools/qlist/tst_bench_qlist.cpp | 410 |
3 files changed, 414 insertions, 563 deletions
diff --git a/tests/benchmarks/corelib/tools/qlist/CMakeLists.txt b/tests/benchmarks/corelib/tools/qlist/CMakeLists.txt index 46ca1c8514..dabfe08122 100644 --- a/tests/benchmarks/corelib/tools/qlist/CMakeLists.txt +++ b/tests/benchmarks/corelib/tools/qlist/CMakeLists.txt @@ -1,4 +1,5 @@ -# Generated from qlist.pro. +# Copyright (C) 2022 The Qt Company Ltd. +# SPDX-License-Identifier: BSD-3-Clause ##################################################################### ## tst_bench_qlist Binary: @@ -6,7 +7,7 @@ qt_internal_add_benchmark(tst_bench_qlist SOURCES - main.cpp - PUBLIC_LIBRARIES + tst_bench_qlist.cpp + LIBRARIES Qt::Test ) diff --git a/tests/benchmarks/corelib/tools/qlist/main.cpp b/tests/benchmarks/corelib/tools/qlist/main.cpp deleted file mode 100644 index 3426336cb7..0000000000 --- a/tests/benchmarks/corelib/tools/qlist/main.cpp +++ /dev/null @@ -1,560 +0,0 @@ -/**************************************************************************** -** -** Copyright (C) 2020 The Qt Company Ltd. -** Contact: https://www.qt.io/licensing/ -** -** This file is part of the QtCore module of the Qt Toolkit. -** -** $QT_BEGIN_LICENSE:GPL-EXCEPT$ -** Commercial License Usage -** Licensees holding valid commercial Qt licenses may use this file in -** accordance with the commercial license agreement provided with the -** Software or, alternatively, in accordance with the terms contained in -** a written agreement between you and The Qt Company. For licensing terms -** and conditions see https://www.qt.io/terms-conditions. For further -** information use the contact form at https://www.qt.io/contact-us. -** -** GNU General Public License Usage -** Alternatively, this file may be used under the terms of the GNU -** General Public License version 3 as published by the Free Software -** Foundation with exceptions as appearing in the file LICENSE.GPL3-EXCEPT -** included in the packaging of this file. Please review the following -** information to ensure the GNU General Public License requirements will -** be met: https://www.gnu.org/licenses/gpl-3.0.html. -** -** $QT_END_LICENSE$ -** -****************************************************************************/ - -#include <QList> -#include <QTest> - -#include <utility> - -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_RELOCATABLE_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(); - - // append 1 element: - void appendOne_int_data() const { commonBenchmark_data<int>(); } - void appendOne_primitive_data() const { commonBenchmark_data<MyPrimitive>(); } - void appendOne_movable_data() const { commonBenchmark_data<MyMovable>(); } - void appendOne_complex_data() const { commonBenchmark_data<MyComplex>(); } - void appendOne_QString_data() const { commonBenchmark_data<QString>(); } - - void appendOne_int() const { appendOne_impl<QList, int>(); } // QTBUG-87330 - void appendOne_primitive() const { appendOne_impl<QList, MyPrimitive>(); } - void appendOne_movable() const { appendOne_impl<QList, MyMovable>(); } - void appendOne_complex() const { appendOne_impl<QList, MyComplex>(); } - void appendOne_QString() const { appendOne_impl<QList, QString>(); } - - // prepend 1 element: - void prependOne_int_data() const { commonBenchmark_data<int>(); } - void prependOne_primitive_data() const { commonBenchmark_data<MyPrimitive>(); } - void prependOne_movable_data() const { commonBenchmark_data<MyMovable>(); } - void prependOne_complex_data() const { commonBenchmark_data<MyComplex>(); } - void prependOne_QString_data() const { commonBenchmark_data<QString>(); } - - void prependOne_int() const { prependOne_impl<QList, int>(); } - void prependOne_primitive() const { prependOne_impl<QList, MyPrimitive>(); } - void prependOne_movable() const { prependOne_impl<QList, MyMovable>(); } - void prependOne_complex() const { prependOne_impl<QList, MyComplex>(); } - void prependOne_QString() const { prependOne_impl<QList, QString>(); } - - // insert in middle 1 element: - void midInsertOne_int_data() const { commonBenchmark_data<int>(); } - void midInsertOne_primitive_data() const { commonBenchmark_data<MyPrimitive>(); } - void midInsertOne_movable_data() const { commonBenchmark_data<MyMovable>(); } - void midInsertOne_complex_data() const { commonBenchmark_data<MyComplex>(); } - void midInsertOne_QString_data() const { commonBenchmark_data<QString>(); } - - void midInsertOne_int() const { midInsertOne_impl<QList, int>(); } - void midInsertOne_primitive() const { midInsertOne_impl<QList, MyPrimitive>(); } - void midInsertOne_movable() const { midInsertOne_impl<QList, MyMovable>(); } - void midInsertOne_complex() const { midInsertOne_impl<QList, MyComplex>(); } - void midInsertOne_QString() const { midInsertOne_impl<QList, QString>(); } - - // append/prepend 1 element - hard times for branch predictor: - void appendPrependOne_int_data() const { commonBenchmark_data<int>(); } - void appendPrependOne_primitive_data() const { commonBenchmark_data<MyPrimitive>(); } - void appendPrependOne_movable_data() const { commonBenchmark_data<MyMovable>(); } - void appendPrependOne_complex_data() const { commonBenchmark_data<MyComplex>(); } - void appendPrependOne_QString_data() const { commonBenchmark_data<QString>(); } - - void appendPrependOne_int() const { appendPrependOne_impl<QList, int>(); } - void appendPrependOne_primitive() const { appendPrependOne_impl<QList, MyPrimitive>(); } - void appendPrependOne_movable() const { appendPrependOne_impl<QList, MyMovable>(); } - void appendPrependOne_complex() const { appendPrependOne_impl<QList, MyComplex>(); } - void appendPrependOne_QString() const { appendPrependOne_impl<QList, QString>(); } - - // prepend half elements, then appen another half: - void prependAppendHalvesOne_int_data() const { commonBenchmark_data<int>(); } - void prependAppendHalvesOne_primitive_data() const { commonBenchmark_data<MyPrimitive>(); } - void prependAppendHalvesOne_movable_data() const { commonBenchmark_data<MyMovable>(); } - void prependAppendHalvesOne_complex_data() const { commonBenchmark_data<MyComplex>(); } - void prependAppendHalvesOne_QString_data() const { commonBenchmark_data<QString>(); } - - void prependAppendHalvesOne_int() const { prependAppendHalvesOne_impl<QList, int>(); } - void prependAppendHalvesOne_primitive() const - { - prependAppendHalvesOne_impl<QList, MyPrimitive>(); - } - void prependAppendHalvesOne_movable() const { prependAppendHalvesOne_impl<QList, MyMovable>(); } - void prependAppendHalvesOne_complex() const { prependAppendHalvesOne_impl<QList, MyComplex>(); } - void prependAppendHalvesOne_QString() const { prependAppendHalvesOne_impl<QList, QString>(); } - - // emplace in middle 1 element: - void midEmplaceOne_int_data() const { commonBenchmark_data<int>(); } - void midEmplaceOne_primitive_data() const { commonBenchmark_data<MyPrimitive>(); } - void midEmplaceOne_movable_data() const { commonBenchmark_data<MyMovable>(); } - void midEmplaceOne_complex_data() const { commonBenchmark_data<MyComplex>(); } - void midEmplaceOne_QString_data() const { commonBenchmark_data<QString>(); } - - void midEmplaceOne_int() const { midEmplaceOne_impl<QList, int>(); } - void midEmplaceOne_primitive() const { midEmplaceOne_impl<QList, MyPrimitive>(); } - void midEmplaceOne_movable() const { midEmplaceOne_impl<QList, MyMovable>(); } - void midEmplaceOne_complex() const { midEmplaceOne_impl<QList, MyComplex>(); } - void midEmplaceOne_QString() const { midEmplaceOne_impl<QList, QString>(); } - -// For 5.15 we also want to compare against QVector -#if QT_VERSION < QT_VERSION_CHECK(6, 0, 0) - // append 1 element: - void qvector_appendOne_int_data() const { commonBenchmark_data<int>(); } - void qvector_appendOne_primitive_data() const { commonBenchmark_data<MyPrimitive>(); } - void qvector_appendOne_movable_data() const { commonBenchmark_data<MyMovable>(); } - void qvector_appendOne_complex_data() const { commonBenchmark_data<MyComplex>(); } - void qvector_appendOne_QString_data() const { commonBenchmark_data<QString>(); } - - void qvector_appendOne_int() const { appendOne_impl<QVector, int>(); } // QTBUG-87330 - void qvector_appendOne_primitive() const { appendOne_impl<QVector, MyPrimitive>(); } - void qvector_appendOne_movable() const { appendOne_impl<QVector, MyMovable>(); } - void qvector_appendOne_complex() const { appendOne_impl<QVector, MyComplex>(); } - void qvector_appendOne_QString() const { appendOne_impl<QVector, QString>(); } - - // prepend 1 element: - void qvector_prependOne_int_data() const { commonBenchmark_data<int>(); } - void qvector_prependOne_primitive_data() const { commonBenchmark_data<MyPrimitive>(); } - void qvector_prependOne_movable_data() const { commonBenchmark_data<MyMovable>(); } - void qvector_prependOne_complex_data() const { commonBenchmark_data<MyComplex>(); } - void qvector_prependOne_QString_data() const { commonBenchmark_data<QString>(); } - - void qvector_prependOne_int() const { prependOne_impl<QVector, int>(); } - void qvector_prependOne_primitive() const { prependOne_impl<QVector, MyPrimitive>(); } - void qvector_prependOne_movable() const { prependOne_impl<QVector, MyMovable>(); } - void qvector_prependOne_complex() const { prependOne_impl<QVector, MyComplex>(); } - void qvector_prependOne_QString() const { prependOne_impl<QVector, QString>(); } - - // insert in middle 1 element: - void qvector_midInsertOne_int_data() const { commonBenchmark_data<int>(); } - void qvector_midInsertOne_primitive_data() const { commonBenchmark_data<MyPrimitive>(); } - void qvector_midInsertOne_movable_data() const { commonBenchmark_data<MyMovable>(); } - void qvector_midInsertOne_complex_data() const { commonBenchmark_data<MyComplex>(); } - void qvector_midInsertOne_QString_data() const { commonBenchmark_data<QString>(); } - - void qvector_midInsertOne_int() const { midInsertOne_impl<QVector, int>(); } - void qvector_midInsertOne_primitive() const { midInsertOne_impl<QVector, MyPrimitive>(); } - void qvector_midInsertOne_movable() const { midInsertOne_impl<QVector, MyMovable>(); } - void qvector_midInsertOne_complex() const { midInsertOne_impl<QVector, MyComplex>(); } - void qvector_midInsertOne_QString() const { midInsertOne_impl<QVector, QString>(); } - - // append/prepend 1 element - hard times for branch predictor: - void qvector_appendPrependOne_int_data() const { commonBenchmark_data<int>(); } - void qvector_appendPrependOne_primitive_data() const { commonBenchmark_data<MyPrimitive>(); } - void qvector_appendPrependOne_movable_data() const { commonBenchmark_data<MyMovable>(); } - void qvector_appendPrependOne_complex_data() const { commonBenchmark_data<MyComplex>(); } - void qvector_appendPrependOne_QString_data() const { commonBenchmark_data<QString>(); } - - void qvector_appendPrependOne_int() const { appendPrependOne_impl<QVector, int>(); } - void qvector_appendPrependOne_primitive() const - { - appendPrependOne_impl<QVector, MyPrimitive>(); - } - void qvector_appendPrependOne_movable() const { appendPrependOne_impl<QVector, MyMovable>(); } - void qvector_appendPrependOne_complex() const { appendPrependOne_impl<QVector, MyComplex>(); } - void qvector_appendPrependOne_QString() const { appendPrependOne_impl<QVector, QString>(); } - - // prepend half elements, then appen another half: - void qvector_prependAppendHalvesOne_int_data() const { commonBenchmark_data<int>(); } - void qvector_prependAppendHalvesOne_primitive_data() const - { - commonBenchmark_data<MyPrimitive>(); - } - void qvector_prependAppendHalvesOne_movable_data() const { commonBenchmark_data<MyMovable>(); } - void qvector_prependAppendHalvesOne_complex_data() const { commonBenchmark_data<MyComplex>(); } - void qvector_prependAppendHalvesOne_QString_data() const { commonBenchmark_data<QString>(); } - - void qvector_prependAppendHalvesOne_int() const { prependAppendHalvesOne_impl<QVector, int>(); } - void qvector_prependAppendHalvesOne_primitive() const - { - prependAppendHalvesOne_impl<QVector, MyPrimitive>(); - } - void qvector_prependAppendHalvesOne_movable() const - { - prependAppendHalvesOne_impl<QVector, MyMovable>(); - } - void qvector_prependAppendHalvesOne_complex() const - { - prependAppendHalvesOne_impl<QVector, MyComplex>(); - } - void qvector_prependAppendHalvesOne_QString() const - { - prependAppendHalvesOne_impl<QVector, QString>(); - } - - // emplace in middle 1 element: - void qvector_midEmplaceOne_int_data() const { commonBenchmark_data<int>(); } - void qvector_midEmplaceOne_primitive_data() const { commonBenchmark_data<MyPrimitive>(); } - void qvector_midEmplaceOne_movable_data() const { commonBenchmark_data<MyMovable>(); } - void qvector_midEmplaceOne_complex_data() const { commonBenchmark_data<MyComplex>(); } - void qvector_midEmplaceOne_QString_data() const { commonBenchmark_data<QString>(); } - - void qvector_midEmplaceOne_int() const { midEmplaceOne_impl<QVector, int>(); } - void qvector_midEmplaceOne_primitive() const { midEmplaceOne_impl<QVector, MyPrimitive>(); } - void qvector_midEmplaceOne_movable() const { midEmplaceOne_impl<QVector, MyMovable>(); } - void qvector_midEmplaceOne_complex() const { midEmplaceOne_impl<QVector, MyComplex>(); } - void qvector_midEmplaceOne_QString() const { midEmplaceOne_impl<QVector, QString>(); } -#endif - -private: - template<typename> - void commonBenchmark_data() const; - - template<template<typename> typename, typename> - void appendOne_impl() const; - - template<template<typename> typename, typename> - void prependOne_impl() const; - - template<template<typename> typename, typename> - void midInsertOne_impl() const; - - template<template<typename> typename, typename> - void appendPrependOne_impl() const; - - template<template<typename> typename, typename> - void prependAppendHalvesOne_impl() const; - - template<template<typename> typename, typename> - void midEmplaceOne_impl() const; -}; - -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); -} - - -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); -} - -template<typename T> -void tst_QList::commonBenchmark_data() const -{ - QTest::addColumn<int>("elemCount"); - - const auto addRow = [](int count, const char *text) { QTest::newRow(text) << count; }; - - const auto p = [](int i, const char *text) { return std::make_pair(i, text); }; - - // cap at 20m elements to allow 5.15/6.0 coverage to be the same - for (auto pair : { p(100, "100"), p(1000, "1k"), p(10000, "10k"), p(100000, "100k"), - p(1000000, "1m"), p(10000000, "10m"), p(20000000, "20m") }) { - addRow(pair.first, pair.second); - } -} - -template<template<typename> typename Container, typename T> -void tst_QList::appendOne_impl() const -{ - QFETCH(int, elemCount); - constexpr auto getValue = []() { return T {}; }; - - QBENCHMARK { - Container<T> container; - auto lvalue = getValue(); - - for (int i = 0; i < elemCount; ++i) { - container.append(lvalue); - } - } -} - -template<template<typename> typename Container, typename T> -void tst_QList::prependOne_impl() const -{ - QFETCH(int, elemCount); - constexpr auto getValue = []() { return T {}; }; - - QBENCHMARK { - Container<T> container; - auto lvalue = getValue(); - - for (int i = 0; i < elemCount; ++i) { - container.prepend(lvalue); - } - } -} - -template<template<typename> typename Container, typename T> -void tst_QList::midInsertOne_impl() const -{ - QFETCH(int, elemCount); - constexpr auto getValue = []() { return T {}; }; - - QBENCHMARK { - Container<T> container; - auto lvalue = getValue(); - - for (int i = 0; i < elemCount; ++i) { - container.insert(container.size() / 2, lvalue); - } - } -} - -template<template<typename> typename Container, typename T> -void tst_QList::appendPrependOne_impl() const -{ - QFETCH(int, elemCount); - constexpr auto getValue = []() { return T {}; }; - - QBENCHMARK { - Container<T> container; - auto lvalue = getValue(); - - for (int i = 0; i < elemCount; ++i) { - if (i % 2 == 0) { - container.append(lvalue); - } else { - container.prepend(lvalue); - } - } - } -} - -template<template<typename> typename Container, typename T> -void tst_QList::prependAppendHalvesOne_impl() const -{ - QFETCH(int, elemCount); - constexpr auto getValue = []() { return T {}; }; - - QBENCHMARK { - Container<T> container; - auto lvalue = getValue(); - - for (int i = 0; i < elemCount / 2; ++i) { - container.prepend(lvalue); - } - - for (int i = elemCount / 2; i < elemCount; ++i) { - container.append(lvalue); - } - } -} - -template<template<typename> typename Container, typename T> -void tst_QList::midEmplaceOne_impl() const -{ - QFETCH(int, elemCount); - constexpr auto getValue = []() { return T {}; }; - - QBENCHMARK { - Container<T> container; - auto lvalue = getValue(); - - for (int i = 0; i < elemCount; ++i) { - container.emplace(container.size() / 2, lvalue); - } - } -} - -QTEST_APPLESS_MAIN(tst_QList) - -#include "main.moc" diff --git a/tests/benchmarks/corelib/tools/qlist/tst_bench_qlist.cpp b/tests/benchmarks/corelib/tools/qlist/tst_bench_qlist.cpp new file mode 100644 index 0000000000..24691d1f71 --- /dev/null +++ b/tests/benchmarks/corelib/tools/qlist/tst_bench_qlist.cpp @@ -0,0 +1,410 @@ +// Copyright (C) 2021 The Qt Company Ltd. +// SPDX-License-Identifier: LicenseRef-Qt-Commercial OR GPL-3.0-only + +#include <QList> +#include <QTest> + +#include <utility> + +static const int N = 1000; + +struct MyBase +{ + MyBase(int i_) : i(i_) { } + + MyBase(const MyBase &other) : i(other.i) { } + + MyBase &operator=(const MyBase &other) + { + i = other.i; + return *this; + } + + bool operator==(const MyBase &other) const + { return i == other.i; } + +protected: + int i; +}; + +struct MyPrimitive : public MyBase +{ + MyPrimitive(int i_ = -1) : MyBase(i_) { } + MyPrimitive(const MyPrimitive &other) : MyBase(other) { } + MyPrimitive &operator=(const MyPrimitive &other) + { + MyBase::operator=(other); + return *this; + } +}; + +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_RELOCATABLE_TYPE); +Q_DECLARE_TYPEINFO(MyComplex, Q_COMPLEX_TYPE); + +QT_END_NAMESPACE + + +class tst_QList: public QObject +{ + Q_OBJECT + + const int million = 1000000; +private Q_SLOTS: + void removeAll_primitive_data(); + void removeAll_primitive() { removeAll_impl<MyPrimitive>(); } + void removeAll_movable_data() { removeAll_primitive_data(); } + void removeAll_movable() { removeAll_impl<MyMovable>(); } + void removeAll_complex_data() { removeAll_primitive_data(); } + void removeAll_complex() { removeAll_impl<MyComplex>(); } + + // append 1 element: + void appendOne_int_data() const { commonBenchmark_data<int>(); } + void appendOne_primitive_data() const { commonBenchmark_data<MyPrimitive>(); } + void appendOne_movable_data() const { commonBenchmark_data<MyMovable>(); } + void appendOne_complex_data() const { commonBenchmark_data<MyComplex>(); } + void appendOne_QString_data() const { commonBenchmark_data<QString>(); } + + void appendOne_int() const { appendOne_impl<QList, int>(); } // QTBUG-87330 + void appendOne_primitive() const { appendOne_impl<QList, MyPrimitive>(); } + void appendOne_movable() const { appendOne_impl<QList, MyMovable>(); } + void appendOne_complex() const { appendOne_impl<QList, MyComplex>(); } + void appendOne_QString() const { appendOne_impl<QList, QString>(); } + + // prepend 1 element: + void prependOne_int_data() const { commonBenchmark_data<int>(); } + void prependOne_primitive_data() const { commonBenchmark_data<MyPrimitive>(); } + void prependOne_movable_data() const { commonBenchmark_data<MyMovable>(); } + void prependOne_complex_data() const { commonBenchmark_data<MyComplex>(); } + void prependOne_QString_data() const { commonBenchmark_data<QString>(); } + + void prependOne_int() const { prependOne_impl<QList, int>(); } + void prependOne_primitive() const { prependOne_impl<QList, MyPrimitive>(); } + void prependOne_movable() const { prependOne_impl<QList, MyMovable>(); } + void prependOne_complex() const { prependOne_impl<QList, MyComplex>(); } + void prependOne_QString() const { prependOne_impl<QList, QString>(); } + + // insert in middle 1 element (quadratic, slow): + void midInsertOne_int_data() const { commonBenchmark_data<int>(million); } + void midInsertOne_primitive_data() const { commonBenchmark_data<MyPrimitive>(million); } + void midInsertOne_movable_data() const { commonBenchmark_data<MyMovable>(million); } + void midInsertOne_complex_data() const { commonBenchmark_data<MyComplex>(million / 10); } + void midInsertOne_QString_data() const { commonBenchmark_data<QString>(million / 10); } + + void midInsertOne_int() const { midInsertOne_impl<QList, int>(); } + void midInsertOne_primitive() const { midInsertOne_impl<QList, MyPrimitive>(); } + void midInsertOne_movable() const { midInsertOne_impl<QList, MyMovable>(); } + void midInsertOne_complex() const { midInsertOne_impl<QList, MyComplex>(); } + void midInsertOne_QString() const { midInsertOne_impl<QList, QString>(); } + + // append/prepend 1 element - hard times for branch predictor: + void appendPrependOne_int_data() const { commonBenchmark_data<int>(); } + void appendPrependOne_primitive_data() const { commonBenchmark_data<MyPrimitive>(); } + void appendPrependOne_movable_data() const { commonBenchmark_data<MyMovable>(); } + void appendPrependOne_complex_data() const { commonBenchmark_data<MyComplex>(); } + void appendPrependOne_QString_data() const { commonBenchmark_data<QString>(); } + + void appendPrependOne_int() const { appendPrependOne_impl<QList, int>(); } + void appendPrependOne_primitive() const { appendPrependOne_impl<QList, MyPrimitive>(); } + void appendPrependOne_movable() const { appendPrependOne_impl<QList, MyMovable>(); } + void appendPrependOne_complex() const { appendPrependOne_impl<QList, MyComplex>(); } + void appendPrependOne_QString() const { appendPrependOne_impl<QList, QString>(); } + + // prepend half elements, then appen another half: + void prependAppendHalvesOne_int_data() const { commonBenchmark_data<int>(); } + void prependAppendHalvesOne_primitive_data() const { commonBenchmark_data<MyPrimitive>(); } + void prependAppendHalvesOne_movable_data() const { commonBenchmark_data<MyMovable>(); } + void prependAppendHalvesOne_complex_data() const { commonBenchmark_data<MyComplex>(); } + void prependAppendHalvesOne_QString_data() const { commonBenchmark_data<QString>(); } + + void prependAppendHalvesOne_int() const { prependAppendHalvesOne_impl<QList, int>(); } + void prependAppendHalvesOne_primitive() const + { + prependAppendHalvesOne_impl<QList, MyPrimitive>(); + } + void prependAppendHalvesOne_movable() const { prependAppendHalvesOne_impl<QList, MyMovable>(); } + void prependAppendHalvesOne_complex() const { prependAppendHalvesOne_impl<QList, MyComplex>(); } + void prependAppendHalvesOne_QString() const { prependAppendHalvesOne_impl<QList, QString>(); } + + // emplace in middle 1 element (quadratic, slow): + void midEmplaceOne_int_data() const { commonBenchmark_data<int>(million); } + void midEmplaceOne_primitive_data() const { commonBenchmark_data<MyPrimitive>(million); } + void midEmplaceOne_movable_data() const { commonBenchmark_data<MyMovable>(million); } + void midEmplaceOne_complex_data() const { commonBenchmark_data<MyComplex>(million / 10); } + void midEmplaceOne_QString_data() const { commonBenchmark_data<QString>(million / 10); } + + void midEmplaceOne_int() const { midEmplaceOne_impl<QList, int>(); } + void midEmplaceOne_primitive() const { midEmplaceOne_impl<QList, MyPrimitive>(); } + void midEmplaceOne_movable() const { midEmplaceOne_impl<QList, MyMovable>(); } + void midEmplaceOne_complex() const { midEmplaceOne_impl<QList, MyComplex>(); } + void midEmplaceOne_QString() const { midEmplaceOne_impl<QList, QString>(); } + + // remove from beginning in a general way + void removeFirstGeneral_int_data() const { commonBenchmark_data<int>(); } + void removeFirstGeneral_primitive_data() const { commonBenchmark_data<MyPrimitive>(); } + void removeFirstGeneral_movable_data() const { commonBenchmark_data<MyMovable>(); } + void removeFirstGeneral_complex_data() const { commonBenchmark_data<MyComplex>(); } + void removeFirstGeneral_QString_data() const { commonBenchmark_data<QString>(); } + + void removeFirstGeneral_int() const { removeFirstGeneral_impl<QList, int>(); } + void removeFirstGeneral_primitive() const { removeFirstGeneral_impl<QList, MyPrimitive>(); } + void removeFirstGeneral_movable() const { removeFirstGeneral_impl<QList, MyMovable>(); } + void removeFirstGeneral_complex() const { removeFirstGeneral_impl<QList, MyComplex>(); } + void removeFirstGeneral_QString() const { removeFirstGeneral_impl<QList, QString>(); } + + // remove from beginning in a special way (using fast part of QList::removeFirst()) + void removeFirstSpecial_int_data() const { commonBenchmark_data<int>(); } + void removeFirstSpecial_primitive_data() const { commonBenchmark_data<MyPrimitive>(); } + void removeFirstSpecial_movable_data() const { commonBenchmark_data<MyMovable>(); } + void removeFirstSpecial_complex_data() const { commonBenchmark_data<MyComplex>(); } + void removeFirstSpecial_QString_data() const { commonBenchmark_data<QString>(); } + + void removeFirstSpecial_int() const { removeFirstSpecial_impl<QList, int>(); } + void removeFirstSpecial_primitive() const { removeFirstSpecial_impl<QList, MyPrimitive>(); } + void removeFirstSpecial_movable() const { removeFirstSpecial_impl<QList, MyMovable>(); } + void removeFirstSpecial_complex() const { removeFirstSpecial_impl<QList, MyComplex>(); } + void removeFirstSpecial_QString() const { removeFirstSpecial_impl<QList, QString>(); } + +private: + template <class T> + void removeAll_impl() const; + + template<typename> + void commonBenchmark_data(int max = 200000000) const; + + template<template<typename> typename, typename> + void appendOne_impl() const; + + template<template<typename> typename, typename> + void prependOne_impl() const; + + template<template<typename> typename, typename> + void midInsertOne_impl() const; + + template<template<typename> typename, typename> + void appendPrependOne_impl() const; + + template<template<typename> typename, typename> + void prependAppendHalvesOne_impl() const; + + template<template<typename> typename, typename> + void midEmplaceOne_impl() const; + + template<template<typename> typename, typename> + void removeFirstGeneral_impl() const; + + template<template<typename> typename, typename> + void removeFirstSpecial_impl() const; +}; + +template <class T> +void tst_QList::removeAll_impl() const +{ + QFETCH(QList<int>, i10); + QFETCH(int, itemsToRemove); + + constexpr int valueToRemove = 5; + + QList<T> list; + for (int i = 0; i < 10 * N; ++i) { + T t(i10.at(i % 10)); + list.append(t); + } + + T t(valueToRemove); + + qsizetype removedCount = 0; // make compiler happy by setting to 0 + QList<T> l; + + QBENCHMARK { + l = list; + removedCount = l.removeAll(t); + } + QCOMPARE(removedCount, itemsToRemove * N); + QCOMPARE(l.size() + removedCount, list.size()); + QVERIFY(!l.contains(valueToRemove)); +} + +void tst_QList::removeAll_primitive_data() +{ + qRegisterMetaType<QList<int> >(); + + QTest::addColumn<QList<int> >("i10"); + QTest::addColumn<int>("itemsToRemove"); + + QTest::newRow("0%") << QList<int>(10, 0) << 0; + QTest::newRow("10%") << (QList<int>() << 0 << 0 << 0 << 0 << 5 << 0 << 0 << 0 << 0 << 0) << 1; + QTest::newRow("90%") << (QList<int>() << 5 << 5 << 5 << 5 << 0 << 5 << 5 << 5 << 5 << 5) << 9; + QTest::newRow("100%") << QList<int>(10, 5) << 10; +} + +template<typename T> +void tst_QList::commonBenchmark_data(int max) const +{ + QTest::addColumn<int>("elemCount"); + + const auto addRow = [](int count, const char *text) { QTest::newRow(text) << count; }; + + const auto p = [](int i, const char *text) { return std::make_pair(i, text); }; + + // cap at 20m elements to allow 5.15/6.0 coverage to be the same + for (auto pair : { p(100, "100"), p(1000, "1k"), p(10000, "10k"), p(100000, "100k"), + p(1000000, "1m"), p(10000000, "10m"), p(20000000, "20m") }) { + if (pair.first <= max) + addRow(pair.first, pair.second); + } +} + +template<template<typename> typename Container, typename T> +void tst_QList::appendOne_impl() const +{ + QFETCH(int, elemCount); + constexpr auto getValue = []() { return T {}; }; + + QBENCHMARK { + Container<T> container; + auto lvalue = getValue(); + + for (int i = 0; i < elemCount; ++i) { + container.append(lvalue); + } + } +} + +template<template<typename> typename Container, typename T> +void tst_QList::prependOne_impl() const +{ + QFETCH(int, elemCount); + constexpr auto getValue = []() { return T {}; }; + + QBENCHMARK { + Container<T> container; + auto lvalue = getValue(); + + for (int i = 0; i < elemCount; ++i) { + container.prepend(lvalue); + } + } +} + +template<template<typename> typename Container, typename T> +void tst_QList::midInsertOne_impl() const +{ + QFETCH(int, elemCount); + constexpr auto getValue = []() { return T {}; }; + + QBENCHMARK { + Container<T> container; + auto lvalue = getValue(); + + for (int i = 0; i < elemCount; ++i) { + const int remainder = i % 2; + // use insert(i, n, t) as insert(i, t) calls emplace (implementation + // detail) + container.insert(container.size() / 2 + remainder, 1, lvalue); + } + } +} + +template<template<typename> typename Container, typename T> +void tst_QList::appendPrependOne_impl() const +{ + QFETCH(int, elemCount); + constexpr auto getValue = []() { return T {}; }; + + QBENCHMARK { + Container<T> container; + auto lvalue = getValue(); + + for (int i = 0; i < elemCount; ++i) { + if (i % 2 == 0) { + container.append(lvalue); + } else { + container.prepend(lvalue); + } + } + } +} + +template<template<typename> typename Container, typename T> +void tst_QList::prependAppendHalvesOne_impl() const +{ + QFETCH(int, elemCount); + constexpr auto getValue = []() { return T {}; }; + + QBENCHMARK { + Container<T> container; + auto lvalue = getValue(); + + for (int i = 0; i < elemCount / 2; ++i) { + container.prepend(lvalue); + } + + for (int i = elemCount / 2; i < elemCount; ++i) { + container.append(lvalue); + } + } +} + +template<template<typename> typename Container, typename T> +void tst_QList::midEmplaceOne_impl() const +{ + QFETCH(int, elemCount); + constexpr auto getValue = []() { return T {}; }; + + QBENCHMARK { + Container<T> container; + auto lvalue = getValue(); + + for (int i = 0; i < elemCount; ++i) { + const int remainder = i % 2; + container.emplace(container.size() / 2 + remainder, lvalue); + } + } +} + +template<template<typename> typename Container, typename T> +void tst_QList::removeFirstGeneral_impl() const +{ + QFETCH(int, elemCount); + constexpr auto getValue = []() { return T {}; }; + + QBENCHMARK { + Container<T> container(elemCount, getValue()); + + for (int i = 0; i < elemCount - 1; ++i) { + container.remove(0, 1); + } + } +} + +template<template<typename> typename Container, typename T> +void tst_QList::removeFirstSpecial_impl() const +{ + QFETCH(int, elemCount); + constexpr auto getValue = []() { return T {}; }; + + QBENCHMARK { + Container<T> container(elemCount, getValue()); + + for (int i = 0; i < elemCount; ++i) { + container.removeFirst(); + } + } +} + +QTEST_APPLESS_MAIN(tst_QList) + +#include "tst_bench_qlist.moc" |