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 --- src/corelib/text/qstringlist.cpp | 10 +-- src/corelib/tools/qduplicatetracker_p.h | 94 ++++++++++++++++++++++ src/corelib/tools/tools.pri | 1 + .../fontconfig/qfontconfigdatabase.cpp | 9 ++- src/widgets/itemviews/qtreewidget.cpp | 7 +- src/xml/dom/qdom.cpp | 8 +- tests/benchmarks/corelib/text/qstringlist/main.cpp | 39 +++++++++ .../corelib/text/qstringlist/qstringlist.pro | 1 + 8 files changed, 153 insertions(+), 16 deletions(-) create mode 100644 src/corelib/tools/qduplicatetracker_p.h diff --git a/src/corelib/text/qstringlist.cpp b/src/corelib/text/qstringlist.cpp index 4bbe424ed2..4b9dcee169 100644 --- a/src/corelib/text/qstringlist.cpp +++ b/src/corelib/text/qstringlist.cpp @@ -43,9 +43,9 @@ #if QT_CONFIG(regularexpression) # include #endif +#include #include - QT_BEGIN_NAMESPACE /*! \typedef QStringListIterator @@ -885,15 +885,13 @@ int QtPrivate::QStringList_removeDuplicates(QStringList *that) { int n = that->size(); int j = 0; - QSet seen; + + QDuplicateTracker seen; seen.reserve(n); - int setSize = 0; for (int i = 0; i < n; ++i) { const QString &s = that->at(i); - seen.insert(s); - if (setSize == seen.size()) // unchanged size => was already seen + if (seen.hasSeen(s)) continue; - ++setSize; if (j != i) that->swapItemsAt(i, j); ++j; diff --git a/src/corelib/tools/qduplicatetracker_p.h b/src/corelib/tools/qduplicatetracker_p.h new file mode 100644 index 0000000000..99068c01a3 --- /dev/null +++ b/src/corelib/tools/qduplicatetracker_p.h @@ -0,0 +1,94 @@ +/**************************************************************************** +** +** Copyright (C) 2020 Klarälvdalens Datakonsult AB, a KDAB Group company, info@kdab.com, author Marc Mutz +** Contact: http://www.qt.io/licensing/ +** +** This file is part of the QtCore module of the Qt Toolkit. +** +** $QT_BEGIN_LICENSE:LGPL$ +** 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 Lesser General Public License Usage +** Alternatively, this file may be used under the terms of the GNU Lesser +** General Public License version 3 as published by the Free Software +** Foundation and appearing in the file LICENSE.LGPL3 included in the +** packaging of this file. Please review the following information to +** ensure the GNU Lesser General Public License version 3 requirements +** will be met: https://www.gnu.org/licenses/lgpl-3.0.html. +** +** GNU General Public License Usage +** Alternatively, this file may be used under the terms of the GNU +** General Public License version 2.0 or (at your option) the GNU General +** Public license version 3 or any later version approved by the KDE Free +** Qt Foundation. The licenses are as published by the Free Software +** Foundation and appearing in the file LICENSE.GPL2 and LICENSE.GPL3 +** 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-2.0.html and +** https://www.gnu.org/licenses/gpl-3.0.html. +** +** $QT_END_LICENSE$ +** +****************************************************************************/ +#ifndef QDUPLICATETRACKER_P_H +#define QDUPLICATETRACKER_P_H + +// +// W A R N I N G +// ------------- +// +// This file is not part of the Qt API. It exists purely as an +// implementation detail. This header file may change from version to +// version without notice, or even be removed. +// +// We mean it. +// + +#include + +#if QT_HAS_INCLUDE() && __cplusplus > 201402L +# include +# include +#else +# include +#endif + +QT_BEGIN_NAMESPACE + +template +class QDuplicateTracker { +#ifdef __cpp_lib_memory_resource + char buffer[Prealloc * sizeof(T)]; + std::pmr::monotonic_buffer_resource res{buffer, sizeof buffer}; + std::pmr::unordered_set set{&res}; +#else + QSet set; + int setSize = 0; +#endif + Q_DISABLE_COPY_MOVE(QDuplicateTracker); +public: + QDuplicateTracker() = default; + void reserve(int n) { set.reserve(n); } + Q_REQUIRED_RESULT bool hasSeen(const T &s) + { + bool inserted; +#ifdef __cpp_lib_memory_resource + inserted = set.insert(s).second; +#else + set.insert(s); + const int n = set.size(); + inserted = qExchange(setSize, n) != n; +#endif + return !inserted; + } +}; + +QT_END_NAMESPACE + +#endif /* QDUPLICATETRACKER_P_H */ diff --git a/src/corelib/tools/tools.pri b/src/corelib/tools/tools.pri index 40c84157cd..e078ab4409 100644 --- a/src/corelib/tools/tools.pri +++ b/src/corelib/tools/tools.pri @@ -12,6 +12,7 @@ HEADERS += \ tools/qcontainerfwd.h \ tools/qcontainertools_impl.h \ tools/qcryptographichash.h \ + tools/qduplicatetracker_p.h \ tools/qfreelist_p.h \ tools/qhash.h \ tools/qhashfunctions.h \ diff --git a/src/platformsupport/fontdatabases/fontconfig/qfontconfigdatabase.cpp b/src/platformsupport/fontdatabases/fontconfig/qfontconfigdatabase.cpp index 7af5490963..af49ad6407 100644 --- a/src/platformsupport/fontdatabases/fontconfig/qfontconfigdatabase.cpp +++ b/src/platformsupport/fontdatabases/fontconfig/qfontconfigdatabase.cpp @@ -56,6 +56,8 @@ #include +#include + #include #if FC_VERSION >= 20402 #include @@ -778,9 +780,9 @@ QStringList QFontconfigDatabase::fallbacksForFamily(const QString &family, QFont FcPatternDestroy(pattern); if (fontSet) { - QSet duplicates; + QDuplicateTracker duplicates; duplicates.reserve(fontSet->nfont + 1); - duplicates.insert(family.toCaseFolded()); + (void)duplicates.hasSeen(family.toCaseFolded()); for (int i = 0; i < fontSet->nfont; i++) { FcChar8 *value = nullptr; if (FcPatternGetString(fontSet->fonts[i], FC_FAMILY, 0, &value) != FcResultMatch) @@ -788,9 +790,8 @@ QStringList QFontconfigDatabase::fallbacksForFamily(const QString &family, QFont // capitalize(value); const QString familyName = QString::fromUtf8((const char *)value); const QString familyNameCF = familyName.toCaseFolded(); - if (!duplicates.contains(familyNameCF)) { + if (!duplicates.hasSeen(familyNameCF)) { fallbackFamilies << familyName; - duplicates.insert(familyNameCF); } } FcFontSetDestroy(fontSet); diff --git a/src/widgets/itemviews/qtreewidget.cpp b/src/widgets/itemviews/qtreewidget.cpp index ddb31523fd..0d4c391e1c 100644 --- a/src/widgets/itemviews/qtreewidget.cpp +++ b/src/widgets/itemviews/qtreewidget.cpp @@ -48,6 +48,8 @@ #include #include +#include + #include QT_BEGIN_NAMESPACE @@ -3175,13 +3177,12 @@ QList QTreeWidget::selectedItems() const const QModelIndexList indexes = selectionModel()->selectedIndexes(); QList items; items.reserve(indexes.count()); - QSet seen; + QDuplicateTracker seen; seen.reserve(indexes.count()); for (const auto &index : indexes) { QTreeWidgetItem *item = d->item(index); - if (item->isHidden() || seen.contains(item)) + if (item->isHidden() || seen.hasSeen(item)) continue; - seen.insert(item); items.append(item); } return items; diff --git a/src/xml/dom/qdom.cpp b/src/xml/dom/qdom.cpp index bbc877eead..26c1a2122b 100644 --- a/src/xml/dom/qdom.cpp +++ b/src/xml/dom/qdom.cpp @@ -60,6 +60,9 @@ #include #include #include +#include + + #include QT_BEGIN_NAMESPACE @@ -4081,10 +4084,10 @@ void QDomElementPrivate::save(QTextStream& s, int depth, int indent) const } s << '<' << qName << nsDecl; - QSet outputtedPrefixes; /* Write out attributes. */ if (!m_attr->map.isEmpty()) { + QDuplicateTracker outputtedPrefixes; QHash::const_iterator it = m_attr->map.constBegin(); for (; it != m_attr->map.constEnd(); ++it) { s << ' '; @@ -4105,9 +4108,8 @@ void QDomElementPrivate::save(QTextStream& s, int depth, int indent) const * arrive in those situations. */ if((!it.value()->ownerNode || it.value()->ownerNode->prefix != it.value()->prefix) && - !outputtedPrefixes.contains(it.value()->prefix)) { + !outputtedPrefixes.hasSeen(it.value()->prefix)) { s << " xmlns:" << it.value()->prefix << "=\"" << encodeText(it.value()->namespaceURI, s, true, true) << '\"'; - outputtedPrefixes.insert(it.value()->prefix); } } } 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