QStringList: use local storage in removeDuplicates()

If available, use a C++17 std::pmr::unordered_set with a monotonic
buffer resource and a 256-byte stack buffer to avoid the per-element
allocations of QSet.

Results on my machine:

 RESULT : tst_QStringList::removeDuplicates():"empty":
-     0.00014 msecs per iteration (total: 74, iterations: 524288)
+     0.000031 msecs per iteration (total: 66, iterations: 2097152)
 RESULT : tst_QStringList::removeDuplicates():"short-dup-0.00":
-     0.00043 msecs per iteration (total: 57, iterations: 131072)
+     0.00013 msecs per iteration (total: 69, iterations: 524288)
 RESULT : tst_QStringList::removeDuplicates():"short-dup-0.50":
-     0.00049 msecs per iteration (total: 65, iterations: 131072)
+     0.00032 msecs per iteration (total: 85, iterations: 262144)
 RESULT : tst_QStringList::removeDuplicates():"short-dup-0.66":
-     0.00057 msecs per iteration (total: 75, iterations: 131072)
+     0.00039 msecs per iteration (total: 52, iterations: 131072)
 RESULT : tst_QStringList::removeDuplicates():"short-dup-0.75":
-     0.00064 msecs per iteration (total: 85, iterations: 131072)
+     0.00048 msecs per iteration (total: 63, iterations: 131072)
 RESULT : tst_QStringList::removeDuplicates():"long-dup-0.00":
-     0.083 msecs per iteration (total: 85, iterations: 1024)
+     0.039 msecs per iteration (total: 80, iterations: 2048)
 RESULT : tst_QStringList::removeDuplicates():"long-dup-0.50":
-     0.11 msecs per iteration (total: 58, iterations: 512)
+     0.078 msecs per iteration (total: 80, iterations: 1024)
 RESULT : tst_QStringList::removeDuplicates():"long-dup-0.66":
-     0.13 msecs per iteration (total: 70, iterations: 512)
+     0.10 msecs per iteration (total: 53, iterations: 512)
 RESULT : tst_QStringList::removeDuplicates():"long-dup-0.75":
-     0.16 msecs per iteration (total: 86, iterations: 512)
+     0.13 msecs per iteration (total: 69, iterations: 512)

When interpreting the data, take into account that each iteration
contains _also_ a deep copy of the QStringList d/t the detach from
'input'.

The pattern is used elsewhere in Qt, so I've put the class that
implements the seen set into a private header file and used in some
other places I found.

Change-Id: I1f71a82008a16d5a3818f91f290ade21d837805e
Reviewed-by: Giuseppe D'Angelo <giuseppe.dangelo@kdab.com>

2 files changed, 40 insertions, 0 deletions

diff --git a/tests/benchmarks/corelib/text/qstringlist/main.cpp b/tests/benchmarks/corelib/text/qstringlist/main.cpp
index ae355a8b89..9f184d0cf5 100644
--- a/tests/benchmarks/corelib/text/qstringlist/main.cpp
+++ b/tests/benchmarks/corelib/text/qstringlist/main.cpp
@@ -41,6 +41,9 @@ private slots:
     void join() const;
     void join_data() const;
 
+    void removeDuplicates() const;
+    void removeDuplicates_data() const;
+
     void split_qlist_qbytearray() const;
     void split_qlist_qbytearray_data() const { return split_data(); }
 
@@ -116,6 +119,42 @@ void tst_QStringList::join_data() const
         << QString();
 }
 
+void tst_QStringList::removeDuplicates() const
+{
+    QFETCH(const QStringList, input);
+
+    QBENCHMARK {
+        auto copy = input;
+        copy.removeDuplicates();
+    }
+}
+
+void tst_QStringList::removeDuplicates_data() const
+{
+    QTest::addColumn<QStringList>("input");
+
+    const QStringList s = {"one", "two", "three"};
+
+    QTest::addRow("empty") << QStringList();
+    QTest::addRow("short-dup-0.00") << s;
+    QTest::addRow("short-dup-0.50") << (s + s);
+    QTest::addRow("short-dup-0.66") << (s + s + s);
+    QTest::addRow("short-dup-0.75") << (s + s + s + s);
+
+    const QStringList l = []() {
+        QStringList result;
+        const int n = 1000;
+        result.reserve(n);
+        for (int i = 0; i < n; ++i)
+            result.push_back(QString::number(i));
+        return result;
+    }();
+    QTest::addRow("long-dup-0.00") << l;
+    QTest::addRow("long-dup-0.50") << (l + l);
+    QTest::addRow("long-dup-0.66") << (l + l + l);
+    QTest::addRow("long-dup-0.75") << (l + l + l + l);
+}
+
 void tst_QStringList::split_data() const
 {
     QTest::addColumn<QString>("input");
diff --git a/tests/benchmarks/corelib/text/qstringlist/qstringlist.pro b/tests/benchmarks/corelib/text/qstringlist/qstringlist.pro
index 5803e7da0e..2e7ae058f7 100644
--- a/tests/benchmarks/corelib/text/qstringlist/qstringlist.pro
+++ b/tests/benchmarks/corelib/text/qstringlist/qstringlist.pro
@@ -1,5 +1,6 @@
 TARGET = tst_bench_qstringlist
 CONFIG -= debug
 CONFIG += release
+CONFIG += benchmark
 QT = core testlib
 SOURCES += main.cpp