diff --git a/autotests/kcoredirlister_benchmark.cpp b/autotests/kcoredirlister_benchmark.cpp index 77cc7e9e..71fdea1b 100644 --- a/autotests/kcoredirlister_benchmark.cpp +++ b/autotests/kcoredirlister_benchmark.cpp @@ -1,550 +1,552 @@ /* This file is part of the KDE project Copyright (C) 2018 Jaime Torres This library is free software; you can redistribute it and/or modify it under the terms of the GNU Library General Public License as published by the Free Software Foundation; either version 2 of the License, or (at your option) any later version. This library is distributed in the hope that it will be useful, but WITHOUT ANY WARRANTY; without even the implied warranty of MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the GNU Library General Public License for more details. You should have received a copy of the GNU Library General Public License along with this library; see the file COPYING.LIB. If not, write to the Free Software Foundation, Inc., 51 Franklin Street, Fifth Floor, Boston, MA 02110-1301, USA. */ #include #include #include #include #include #include #include #include // BEGIN Global variables const QString fileNameArg = QLatin1String("/home/user/Folder1/SubFolder2/a%1.txt"); // to check with 10, 100, 1000, ... KFileItem const int maxPowerOfTen=4; // To use the same random list of names and url for all the tests QVector randInt[maxPowerOfTen]; // The same list of random integers for all the tests std::default_random_engine generator; // END Global variables /* This is to compare the old list API vs QMap API vs QHash API vs sorted list API in terms of performance for KcoreDirLister list of items. This benchmark assumes that KFileItem has the < operators. */ class kcoreDirListerEntryBenchmark : public QObject { Q_OBJECT public: kcoreDirListerEntryBenchmark() { // Fill randInt[i] with random numbers from 0 to (10^(i+1))-1 for (int i=0; i < maxPowerOfTen; ++i) { std::uniform_int_distribution distribution(0,pow(10,i+1)-1); // Fill the vector with consecutive numbers randInt[i].reserve(pow(10,i+1)); for (int j=0; j < pow(10,i+1); ++j) { randInt[i].append(j); } // And now scramble them a little bit for (int j=0; j < pow(10,i+1); ++j) { int rd1 = distribution(generator); int rd2 = distribution(generator); int swap = randInt[i].at(rd1); randInt[i].replace(rd1, randInt[i].at(rd2)); randInt[i].replace(rd2, swap); } // qDebug() << randInt[i]; } } private Q_SLOTS: void testCreateFiles_List_data(); void testCreateFiles_List(); void testFindByNameFiles_List_data(); void testFindByNameFiles_List(); void testFindByUrlFiles_List_data(); void testFindByUrlFiles_List(); void testFindByUrlAllFiles_List_data(); void testFindByUrlAllFiles_List(); void testCreateFiles_Map_data(); void testCreateFiles_Map(); void testFindByNameFiles_Map_data(); void testFindByNameFiles_Map(); void testFindByUrlFiles_Map_data(); void testFindByUrlFiles_Map(); void testFindByUrlAllFiles_Map_data(); void testFindByUrlAllFiles_Map(); void testCreateFiles_Hash_data(); void testCreateFiles_Hash(); void testFindByNameFiles_Hash_data(); void testFindByNameFiles_Hash(); void testFindByUrlFiles_Hash_data(); void testFindByUrlFiles_Hash(); void testFindByUrlAllFiles_Hash_data(); void testFindByUrlAllFiles_Hash(); void testCreateFiles_Binary_data(); void testCreateFiles_Binary(); void testFindByNameFiles_Binary_data(); void testFindByNameFiles_Binary(); void testFindByUrlFiles_Binary_data(); void testFindByUrlFiles_Binary(); void testFindByUrlAllFiles_Binary_data(); void testFindByUrlAllFiles_Binary(); }; //BEGIN Implementations //BEGIN List // List Implementation (without binary search) class ListImplementation { public: QList lstItems; public: void reserve(int size) { lstItems.reserve(size); } // This search must be fast also KFileItem findByName(const QString &fileName) const { const auto end = lstItems.cend(); for (auto it = lstItems.cbegin() ; it != end; ++it) { if ((*it).name() == fileName) { return *it; } } return KFileItem(); } // simulation of the search by Url in an existing lister (the slowest path) KFileItem findByUrl(const QUrl &_u) const { QUrl url(_u); url = url.adjusted(QUrl::StripTrailingSlash); const auto end = lstItems.cend(); for (auto it = lstItems.cbegin(); it != end; ++it) { if ((*it).url() == url) { return *it; } } return KFileItem(); } void clear() { lstItems.clear(); } void insert(int powerOfTen) { for (int x = 0; x < pow(10, powerOfTen+1); ++x) { QUrl u = QUrl::fromLocalFile(fileNameArg.arg(randInt[powerOfTen].at(x) )).adjusted(QUrl::StripTrailingSlash); KFileItem kfi (u, QStringLiteral("text/text")); lstItems.append(kfi); } } }; //END List //BEGIN QMap // Proposed Implementation using QMap class QMapImplementation { public: void reserve(int size) { + Q_UNUSED(size); } + KFileItem findByName(const QString &fileName) const { const auto itend = lstItems.cend(); for (auto it = lstItems.cbegin(); it != itend; ++it) { if ((*it).name() == fileName) { return *it; } } return KFileItem(); } // simulation of the search by Url in an existing lister (the slowest path) KFileItem findByUrl(const QUrl &_u) const { QUrl url(_u); url = url.adjusted(QUrl::StripTrailingSlash); auto it = lstItems.find(url); if (it != lstItems.end()) { return *it; } return KFileItem(); } void clear() { lstItems.clear(); } void insert(int powerOfTen) { for (int x = 0; x < pow(10, powerOfTen+1); ++x) { QUrl u = QUrl::fromLocalFile(fileNameArg.arg(randInt[powerOfTen].at(x) )).adjusted(QUrl::StripTrailingSlash); KFileItem kfi(u, QStringLiteral("text/text")); lstItems.insert(u, kfi); } } public: QMap lstItems; }; //END QMap //BEGIN QHash // Proposed Implementation using QHash class QHashImplementation { public: void reserve(int size) { lstItems.reserve(size); } KFileItem findByName(const QString &fileName) const { const auto itend = lstItems.cend(); for (auto it = lstItems.cbegin(); it != itend; ++it) { if ((*it).name() == fileName) { return *it; } } return KFileItem(); } // simulation of the search by Url in an existing lister (the slowest path) KFileItem findByUrl(const QUrl &_u) const { QUrl url(_u); url = url.adjusted(QUrl::StripTrailingSlash); auto it = lstItems.find(url); if (it != lstItems.end()) { return *it; } return KFileItem(); } void clear() { lstItems.clear(); } void insert(int powerOfTen) { for (int x = 0; x < pow(10, powerOfTen+1); ++x) { QUrl u = QUrl::fromLocalFile(fileNameArg.arg(randInt[powerOfTen].at(x) )).adjusted(QUrl::StripTrailingSlash); KFileItem kfi(u, QStringLiteral("text/text")); lstItems.insert(u, kfi); } } public: QHash lstItems; }; //END QHash //BEGIN BinaryList // Proposed Implementation using QList with ordered insert and binary search class BinaryListImplementation { public: QList lstItems; public: void reserve(int size) { lstItems.reserve(size); } KFileItem findByName(const QString &fileName) const { const auto itend = lstItems.cend(); for (auto it = lstItems.cbegin(); it != itend; ++it) { if ((*it).name() == fileName) { return *it; } } return KFileItem(); } // simulation of the search by Url in an existing lister (the slowest path) KFileItem findByUrl(const QUrl &_u) const { QUrl url(_u); url = url.adjusted(QUrl::StripTrailingSlash); auto it = std::lower_bound(lstItems.cbegin(), lstItems.cend(), url); if (it != lstItems.cend() && (*it).url() == url) { return *it; } return KFileItem(); } void clear() { lstItems.clear(); } // Add files in random order from the randInt vector void insert(int powerOfTen) { for (int x = 0; x < pow(10, powerOfTen+1); ++x) { QUrl u = QUrl::fromLocalFile(fileNameArg.arg(randInt[powerOfTen].at(x) )).adjusted(QUrl::StripTrailingSlash); KFileItem kfi(u, QStringLiteral("text/text")); auto it = std::lower_bound(lstItems.begin(), lstItems.end(), u); lstItems.insert(it, kfi); } } }; //END BinaryList //END Implementations //BEGIN templates template void fillNumberOfFiles() { QTest::addColumn("numberOfFiles"); for (int i=0; i < maxPowerOfTen; ++i) { // it shows numberOfFiles: 10, 100 or 1000 but the data is the power of ten QTest::newRow( QString("%1").arg(pow(10, i+1)).toLatin1() ) << i; } } template void createFiles(int powerOfTen) { T data; const int numberOfFiles = pow(10, powerOfTen+1); data.reserve(numberOfFiles); QBENCHMARK { data.clear(); data.insert(powerOfTen); } QCOMPARE(data.lstItems.size(), numberOfFiles); } template void findByName(int powerOfTen) { T data; data.clear(); data.reserve(pow(10, powerOfTen+1)); data.insert(powerOfTen); QBENCHMARK { for (int i=0; i void findByUrl(int powerOfTen) { T data; data.clear(); data.reserve(pow(10, powerOfTen+1)); data.insert(powerOfTen); QBENCHMARK { for (int i=0; i void findByUrlAll(int powerOfTen) { T data; data.clear(); data.reserve(pow(10, powerOfTen+1)); data.insert(powerOfTen); QBENCHMARK { for (int i=0; i(); } void kcoreDirListerEntryBenchmark::testCreateFiles_List() { QFETCH(int, numberOfFiles); createFiles(numberOfFiles); } void kcoreDirListerEntryBenchmark::testFindByNameFiles_List_data() { fillNumberOfFiles(); } void kcoreDirListerEntryBenchmark::testFindByNameFiles_List() { QFETCH(int, numberOfFiles); findByName(numberOfFiles); } void kcoreDirListerEntryBenchmark::testFindByUrlFiles_List_data() { fillNumberOfFiles(); } void kcoreDirListerEntryBenchmark::testFindByUrlFiles_List() { QFETCH(int, numberOfFiles); findByUrl(numberOfFiles); } void kcoreDirListerEntryBenchmark::testFindByUrlAllFiles_List_data() { fillNumberOfFiles(); } void kcoreDirListerEntryBenchmark::testFindByUrlAllFiles_List() { QFETCH(int, numberOfFiles); findByUrlAll(numberOfFiles); } void kcoreDirListerEntryBenchmark::testCreateFiles_Map_data() { fillNumberOfFiles(); } void kcoreDirListerEntryBenchmark::testCreateFiles_Map() { QFETCH(int, numberOfFiles); createFiles(numberOfFiles); } void kcoreDirListerEntryBenchmark::testFindByNameFiles_Map_data() { fillNumberOfFiles(); } void kcoreDirListerEntryBenchmark::testFindByNameFiles_Map() { QFETCH(int, numberOfFiles); findByName(numberOfFiles); } void kcoreDirListerEntryBenchmark::testFindByUrlFiles_Map_data() { fillNumberOfFiles(); } void kcoreDirListerEntryBenchmark::testFindByUrlFiles_Map() { QFETCH(int, numberOfFiles); findByUrl(numberOfFiles); } void kcoreDirListerEntryBenchmark::testFindByUrlAllFiles_Map_data() { fillNumberOfFiles(); } void kcoreDirListerEntryBenchmark::testFindByUrlAllFiles_Map() { QFETCH(int, numberOfFiles); findByUrlAll(numberOfFiles); } void kcoreDirListerEntryBenchmark::testCreateFiles_Hash_data() { fillNumberOfFiles(); } void kcoreDirListerEntryBenchmark::testCreateFiles_Hash() { QFETCH(int, numberOfFiles); createFiles(numberOfFiles); } void kcoreDirListerEntryBenchmark::testFindByNameFiles_Hash_data() { fillNumberOfFiles(); } void kcoreDirListerEntryBenchmark::testFindByNameFiles_Hash() { QFETCH(int, numberOfFiles); findByName(numberOfFiles); } void kcoreDirListerEntryBenchmark::testFindByUrlFiles_Hash_data() { fillNumberOfFiles(); } void kcoreDirListerEntryBenchmark::testFindByUrlFiles_Hash() { QFETCH(int, numberOfFiles); findByUrl(numberOfFiles); } void kcoreDirListerEntryBenchmark::testFindByUrlAllFiles_Hash_data() { fillNumberOfFiles(); } void kcoreDirListerEntryBenchmark::testFindByUrlAllFiles_Hash() { QFETCH(int, numberOfFiles); findByUrlAll(numberOfFiles); } void kcoreDirListerEntryBenchmark::testCreateFiles_Binary_data() { fillNumberOfFiles(); } void kcoreDirListerEntryBenchmark::testCreateFiles_Binary() { QFETCH(int, numberOfFiles); createFiles(numberOfFiles); } void kcoreDirListerEntryBenchmark::testFindByNameFiles_Binary_data() { fillNumberOfFiles(); } void kcoreDirListerEntryBenchmark::testFindByNameFiles_Binary() { QFETCH(int, numberOfFiles); findByName(numberOfFiles); } void kcoreDirListerEntryBenchmark::testFindByUrlFiles_Binary_data() { fillNumberOfFiles(); } void kcoreDirListerEntryBenchmark::testFindByUrlFiles_Binary() { QFETCH(int, numberOfFiles); findByUrl(numberOfFiles); } void kcoreDirListerEntryBenchmark::testFindByUrlAllFiles_Binary_data() { fillNumberOfFiles(); } void kcoreDirListerEntryBenchmark::testFindByUrlAllFiles_Binary() { QFETCH(int, numberOfFiles); findByUrlAll(numberOfFiles); } //END tests QTEST_MAIN(kcoreDirListerEntryBenchmark) #include "kcoredirlister_benchmark.moc"