From f21a6d409ea0504c64cd72861fc16b6f3e080086 Mon Sep 17 00:00:00 2001 From: Marc Mutz Date: Wed, 18 Dec 2019 15:43:24 +0100 Subject: 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 --- tests/benchmarks/corelib/text/qstringlist/main.cpp | 39 ++++++++++++++++++++++ .../corelib/text/qstringlist/qstringlist.pro | 1 + 2 files changed, 40 insertions(+) (limited to 'tests') 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("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("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 -- cgit v1.2.3