Add QSortFilterProxyModel clear-filter benchmark

Use QBENCHMARK_ONCE rather than QBENCHMARK to avoid skewing the results:
when the QBENCHMARK block is repeated multiple times after the setup
code above runs once, only the first setFilterRegularExpression() call
unfilters some rows, while the subsequent calls simply check that there
is nothing to do.

The added benchmark is sensitive to the inefficiency - quadratic rather
than linear time complexity - fixed by
7d92ef63d7c2d9d017d89905a2ee0d1e9226b15c. The following two tables
contain the benchmark results on my GNU/Linux system. The numbers denote
milliseconds per iteration.

1. Qt 5.15.2 without the performance fix:
                    10K 25K 50K     100K    250K    500K
       no match     0    1    2       5       14       28
            all     0    0    0       1        3        7
          first     0    1    2       5       14       28
         1000th     2    6   12      25       68      302
         middle     3   34  132     518     3300    13665
1000th from end     1    4    9      19       50      103
           last     0    1    2       5       14       30
  each 10'000th     0   39  211     937     6326    41050
 each 100'000th     0    1    2       5     4226    34780

Without the fix the benchmark times out and aborts at 1000K and 2000K
data rows.

2. Qt 5.15.2 with the performance fix:
                    10K 25K 50K 100K    250K    500K    1000K   2000K
       no match     0   1   2   4       12      26       56      136
            all     0   0   0   1        3       7       14       28
          first     0   1   2   4       12      26       56      136
         1000th     0   1   2   4       13      28       62      145
         middle     0   1   2   4       13      27       59      142
1000th from end     0   1   2   4       13      28       60      145
           last     0   1   2   4       13      27       59      141
  each 10'000th     0   1   2   6       22      69      290     1413
 each 100'000th     0   1   2   4       13      30       81      261

Change-Id: I419a5521dd0be7676fbb09b34b4069d4a76423b1
Reviewed-by: Qt CI Bot <qt_ci_bot@qt-project.org>
Reviewed-by: Giuseppe D'Angelo <giuseppe.dangelo@kdab.com>

4 files changed, 131 insertions, 0 deletions

diff --git a/tests/benchmarks/corelib/CMakeLists.txt b/tests/benchmarks/corelib/CMakeLists.txt
index a84f317928..ff30862180 100644
--- a/tests/benchmarks/corelib/CMakeLists.txt
+++ b/tests/benchmarks/corelib/CMakeLists.txt
@@ -1,6 +1,7 @@
 # Generated from corelib.pro.
 
 add_subdirectory(io)
+add_subdirectory(itemmodels)
 add_subdirectory(json)
 add_subdirectory(mimetypes)
 add_subdirectory(kernel)
diff --git a/tests/benchmarks/corelib/itemmodels/CMakeLists.txt b/tests/benchmarks/corelib/itemmodels/CMakeLists.txt
new file mode 100644
index 0000000000..c74f36709c
--- /dev/null
+++ b/tests/benchmarks/corelib/itemmodels/CMakeLists.txt
@@ -0,0 +1 @@
+add_subdirectory(qsortfilterproxymodel)
diff --git a/tests/benchmarks/corelib/itemmodels/qsortfilterproxymodel/CMakeLists.txt b/tests/benchmarks/corelib/itemmodels/qsortfilterproxymodel/CMakeLists.txt
new file mode 100644
index 0000000000..a18678159b
--- /dev/null
+++ b/tests/benchmarks/corelib/itemmodels/qsortfilterproxymodel/CMakeLists.txt
@@ -0,0 +1,6 @@
+qt_internal_add_benchmark(tst_bench_qsortfilterproxymodel
+    SOURCES
+        tst_qsortfilterproxymodel.cpp
+    PUBLIC_LIBRARIES
+        Qt::Test
+)
diff --git a/tests/benchmarks/corelib/itemmodels/qsortfilterproxymodel/tst_qsortfilterproxymodel.cpp b/tests/benchmarks/corelib/itemmodels/qsortfilterproxymodel/tst_qsortfilterproxymodel.cpp
new file mode 100644
index 0000000000..f7fc0963bc
--- /dev/null
+++ b/tests/benchmarks/corelib/itemmodels/qsortfilterproxymodel/tst_qsortfilterproxymodel.cpp
@@ -0,0 +1,123 @@
+/****************************************************************************
+**
+** Copyright (C) 2021 Igor Kushnir <igorkuo@gmail.com>
+** Contact: https://www.qt.io/licensing/
+**
+** This file is part of the test suite 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 <QSortFilterProxyModel>
+#include <QString>
+#include <QStringList>
+#include <QStringListModel>
+#include <QTest>
+
+static void resizeNumberList(QStringList &numberList, int size)
+{
+    if (!numberList.empty())
+        QCOMPARE(numberList.constLast(), QString::number(numberList.size()));
+
+    if (numberList.size() < size) {
+        numberList.reserve(size);
+        for (int i = numberList.size() + 1; i <= size; ++i)
+            numberList.push_back(QString::number(i));
+    } else if (numberList.size() > size) {
+        numberList.erase(numberList.begin() + size, numberList.end());
+    }
+
+    QCOMPARE(numberList.size(), size);
+    if (!numberList.empty())
+        QCOMPARE(numberList.constLast(), QString::number(numberList.size()));
+}
+
+class tst_QSortFilterProxyModel : public QObject
+{
+    Q_OBJECT
+private slots:
+    void clearFilter_data();
+    void clearFilter();
+
+private:
+    QStringList m_numberList; ///< Cache the strings for efficiency.
+};
+
+void tst_QSortFilterProxyModel::clearFilter_data()
+{
+    QTest::addColumn<int>("itemCount");
+    QTest::addColumn<QString>("pattern");
+    QTest::addColumn<int>("filteredRowCount");
+
+    const auto matchSingleItem = [](int item) { return QStringLiteral("^%1$").arg(item); };
+
+    for (int thousandItemCount : { 10, 25, 50, 100, 250, 500, 1000, 2000 }) {
+        const auto itemCount = thousandItemCount * 1000;
+
+        QTest::addRow("no match in %dK", thousandItemCount) << itemCount << "-" << 0;
+        QTest::addRow("match all in %dK", thousandItemCount) << itemCount << "\\d+" << itemCount;
+
+        QTest::addRow("match first in %dK", thousandItemCount)
+                << itemCount << matchSingleItem(1) << 1;
+        QTest::addRow("match 1000th in %dK", thousandItemCount)
+                << itemCount << matchSingleItem(1000) << 1;
+        QTest::addRow("match middle in %dK", thousandItemCount)
+                << itemCount << matchSingleItem(itemCount / 2) << 1;
+        QTest::addRow("match 1000th from end in %dK", thousandItemCount)
+                << itemCount << matchSingleItem(itemCount - 999) << 1;
+        QTest::addRow("match last in %dK", thousandItemCount)
+                << itemCount << matchSingleItem(itemCount) << 1;
+
+        QTest::addRow("match each 10'000th in %dK", thousandItemCount)
+                << itemCount << "0000$" << thousandItemCount / 10;
+        QTest::addRow("match each 100'000th in %dK", thousandItemCount)
+                << itemCount << "00000$" << thousandItemCount / 100;
+    }
+}
+
+void tst_QSortFilterProxyModel::clearFilter()
+{
+    QFETCH(const int, itemCount);
+    resizeNumberList(m_numberList, itemCount);
+    QStringListModel model(qAsConst(m_numberList));
+    QCOMPARE(model.rowCount(), itemCount);
+
+    QSortFilterProxyModel proxy;
+    proxy.setSourceModel(&model);
+    QCOMPARE(model.rowCount(), itemCount);
+    QCOMPARE(proxy.rowCount(), itemCount);
+
+    QFETCH(const QString, pattern);
+    QFETCH(const int, filteredRowCount);
+    proxy.setFilterRegularExpression(pattern);
+    QCOMPARE(model.rowCount(), itemCount);
+    QCOMPARE(proxy.rowCount(), filteredRowCount);
+
+    QBENCHMARK_ONCE {
+        proxy.setFilterRegularExpression(QString());
+    }
+    QCOMPARE(model.rowCount(), itemCount);
+    QCOMPARE(proxy.rowCount(), itemCount);
+}
+
+QTEST_MAIN(tst_QSortFilterProxyModel)
+
+#include "tst_qsortfilterproxymodel.moc"