File indexing completed on 2024-06-23 10:37:19

0001 /*
0002     This file is part of the KDE project
0003     SPDX-FileCopyrightText: 2018 Jaime Torres <jtamate@gmail.com>
0004 
0005     SPDX-License-Identifier: LGPL-2.0-or-later
0006 */
0007 
0008 #include <QTest>
0009 
0010 #include <kfileitem.h>
0011 
0012 #include <QHash>
0013 #include <QList>
0014 #include <QMap>
0015 
0016 #include <algorithm>
0017 #include <random>
0018 
0019 // BEGIN Global variables
0020 const QString fileNameArg = QLatin1String("/home/user/Folder1/SubFolder2/a%1.txt");
0021 // to check with 10, 100, 1000, ... KFileItem
0022 const int maxPowerOfTen = 3;
0023 // To use the same random list of names and url for all the tests
0024 QVector<int> randInt[maxPowerOfTen];
0025 // The same list of random integers for all the tests
0026 std::default_random_engine generator;
0027 
0028 // END Global variables
0029 
0030 /*
0031    This is to compare the old list API vs QMap API vs QHash API vs sorted list API
0032    in terms of performance for KcoreDirLister list of items.
0033    This benchmark assumes that KFileItem has the < operators.
0034 */
0035 class kcoreDirListerEntryBenchmark : public QObject
0036 {
0037     Q_OBJECT
0038 public:
0039     kcoreDirListerEntryBenchmark()
0040     {
0041         // Fill randInt[i] with random numbers from 0 to (10^(i+1))-1
0042         for (int i = 0; i < maxPowerOfTen; ++i) {
0043             std::uniform_int_distribution<int> distribution(0, pow(10, i + 1) - 1);
0044 
0045             // Fill the vector with consecutive numbers
0046             randInt[i].reserve(pow(10, i + 1));
0047             for (int j = 0; j < pow(10, i + 1); ++j) {
0048                 randInt[i].append(j);
0049             }
0050             // And now scramble them a little bit
0051             for (int j = 0; j < pow(10, i + 1); ++j) {
0052                 int rd1 = distribution(generator);
0053                 int rd2 = distribution(generator);
0054                 int swap = randInt[i].at(rd1);
0055                 randInt[i].replace(rd1, randInt[i].at(rd2));
0056                 randInt[i].replace(rd2, swap);
0057             }
0058             // qDebug() << randInt[i];
0059         }
0060     }
0061 private Q_SLOTS:
0062     void testCreateFiles_List_data();
0063     void testCreateFiles_List();
0064     void testFindByNameFiles_List_data();
0065     void testFindByNameFiles_List();
0066     void testFindByUrlFiles_List_data();
0067     void testFindByUrlFiles_List();
0068     void testFindByUrlAllFiles_List_data();
0069     void testFindByUrlAllFiles_List();
0070 
0071     void testCreateFiles_Map_data();
0072     void testCreateFiles_Map();
0073     void testFindByNameFiles_Map_data();
0074     void testFindByNameFiles_Map();
0075     void testFindByUrlFiles_Map_data();
0076     void testFindByUrlFiles_Map();
0077     void testFindByUrlAllFiles_Map_data();
0078     void testFindByUrlAllFiles_Map();
0079 
0080     void testCreateFiles_Hash_data();
0081     void testCreateFiles_Hash();
0082     void testFindByNameFiles_Hash_data();
0083     void testFindByNameFiles_Hash();
0084     void testFindByUrlFiles_Hash_data();
0085     void testFindByUrlFiles_Hash();
0086     void testFindByUrlAllFiles_Hash_data();
0087     void testFindByUrlAllFiles_Hash();
0088 
0089     void testCreateFiles_Binary_data();
0090     void testCreateFiles_Binary();
0091     void testFindByNameFiles_Binary_data();
0092     void testFindByNameFiles_Binary();
0093     void testFindByUrlFiles_Binary_data();
0094     void testFindByUrlFiles_Binary();
0095     void testFindByUrlAllFiles_Binary_data();
0096     void testFindByUrlAllFiles_Binary();
0097 };
0098 
0099 // BEGIN Implementations
0100 
0101 // BEGIN List
0102 // List Implementation (without binary search)
0103 class ListImplementation
0104 {
0105 public:
0106     QList<KFileItem> lstItems;
0107 
0108 public:
0109     void reserve(int size)
0110     {
0111         lstItems.reserve(size);
0112     }
0113 
0114     // This search must be fast also
0115     KFileItem findByName(const QString &fileName) const
0116     {
0117         const auto end = lstItems.cend();
0118         for (auto it = lstItems.cbegin(); it != end; ++it) {
0119             if ((*it).name() == fileName) {
0120                 return *it;
0121             }
0122         }
0123         return KFileItem();
0124     }
0125 
0126     // simulation of the search by Url in an existing lister (the slowest path)
0127     KFileItem findByUrl(const QUrl &_u) const
0128     {
0129         QUrl url(_u);
0130         url = url.adjusted(QUrl::StripTrailingSlash);
0131         const auto end = lstItems.cend();
0132         for (auto it = lstItems.cbegin(); it != end; ++it) {
0133             if ((*it).url() == url) {
0134                 return *it;
0135             }
0136         }
0137         return KFileItem();
0138     }
0139 
0140     void clear()
0141     {
0142         lstItems.clear();
0143     }
0144 
0145     void insert(int powerOfTen)
0146     {
0147         for (int x = 0; x < pow(10, powerOfTen + 1); ++x) {
0148             QUrl u = QUrl::fromLocalFile(fileNameArg.arg(randInt[powerOfTen].at(x))).adjusted(QUrl::StripTrailingSlash);
0149 
0150             KFileItem kfi(u, QStringLiteral("text/text"));
0151             lstItems.append(kfi);
0152         }
0153     }
0154 };
0155 // END List
0156 // BEGIN QMap
0157 // Proposed Implementation using QMap
0158 class QMapImplementation
0159 {
0160 public:
0161     void reserve(int size)
0162     {
0163         Q_UNUSED(size);
0164     }
0165 
0166     KFileItem findByName(const QString &fileName) const
0167     {
0168         const auto itend = lstItems.cend();
0169         for (auto it = lstItems.cbegin(); it != itend; ++it) {
0170             if ((*it).name() == fileName) {
0171                 return *it;
0172             }
0173         }
0174         return KFileItem();
0175     }
0176 
0177     // simulation of the search by Url in an existing lister (the slowest path)
0178     KFileItem findByUrl(const QUrl &_u) const
0179     {
0180         QUrl url(_u);
0181         url = url.adjusted(QUrl::StripTrailingSlash);
0182 
0183         auto it = lstItems.find(url);
0184         if (it != lstItems.end()) {
0185             return *it;
0186         }
0187         return KFileItem();
0188     }
0189 
0190     void clear()
0191     {
0192         lstItems.clear();
0193     }
0194 
0195     void insert(int powerOfTen)
0196     {
0197         for (int x = 0; x < pow(10, powerOfTen + 1); ++x) {
0198             QUrl u = QUrl::fromLocalFile(fileNameArg.arg(randInt[powerOfTen].at(x))).adjusted(QUrl::StripTrailingSlash);
0199 
0200             KFileItem kfi(u, QStringLiteral("text/text"));
0201 
0202             lstItems.insert(u, kfi);
0203         }
0204     }
0205 
0206 public:
0207     QMap<QUrl, KFileItem> lstItems;
0208 };
0209 // END QMap
0210 // BEGIN QHash
0211 // Proposed Implementation using QHash
0212 class QHashImplementation
0213 {
0214 public:
0215     void reserve(int size)
0216     {
0217         lstItems.reserve(size);
0218     }
0219     KFileItem findByName(const QString &fileName) const
0220     {
0221         const auto itend = lstItems.cend();
0222         for (auto it = lstItems.cbegin(); it != itend; ++it) {
0223             if ((*it).name() == fileName) {
0224                 return *it;
0225             }
0226         }
0227         return KFileItem();
0228     }
0229 
0230     // simulation of the search by Url in an existing lister (the slowest path)
0231     KFileItem findByUrl(const QUrl &_u) const
0232     {
0233         QUrl url(_u);
0234         url = url.adjusted(QUrl::StripTrailingSlash);
0235 
0236         auto it = lstItems.find(url);
0237         if (it != lstItems.end()) {
0238             return *it;
0239         }
0240         return KFileItem();
0241     }
0242 
0243     void clear()
0244     {
0245         lstItems.clear();
0246     }
0247 
0248     void insert(int powerOfTen)
0249     {
0250         for (int x = 0; x < pow(10, powerOfTen + 1); ++x) {
0251             QUrl u = QUrl::fromLocalFile(fileNameArg.arg(randInt[powerOfTen].at(x))).adjusted(QUrl::StripTrailingSlash);
0252 
0253             KFileItem kfi(u, QStringLiteral("text/text"));
0254 
0255             lstItems.insert(u, kfi);
0256         }
0257     }
0258 
0259 public:
0260     QHash<QUrl, KFileItem> lstItems;
0261 };
0262 // END QHash
0263 // BEGIN BinaryList
0264 // Proposed Implementation using QList with ordered insert and binary search
0265 class BinaryListImplementation
0266 {
0267 public:
0268     QList<KFileItem> lstItems;
0269 
0270 public:
0271     void reserve(int size)
0272     {
0273         lstItems.reserve(size);
0274     }
0275     KFileItem findByName(const QString &fileName) const
0276     {
0277         const auto itend = lstItems.cend();
0278         for (auto it = lstItems.cbegin(); it != itend; ++it) {
0279             if ((*it).name() == fileName) {
0280                 return *it;
0281             }
0282         }
0283         return KFileItem();
0284     }
0285 
0286     // simulation of the search by Url in an existing lister (the slowest path)
0287     KFileItem findByUrl(const QUrl &_u) const
0288     {
0289         QUrl url(_u);
0290         url = url.adjusted(QUrl::StripTrailingSlash);
0291 
0292         auto it = std::lower_bound(lstItems.cbegin(), lstItems.cend(), url);
0293         if (it != lstItems.cend() && (*it).url() == url) {
0294             return *it;
0295         }
0296         return KFileItem();
0297     }
0298 
0299     void clear()
0300     {
0301         lstItems.clear();
0302     }
0303 
0304     // Add files in random order from the randInt vector
0305     void insert(int powerOfTen)
0306     {
0307         for (int x = 0; x < pow(10, powerOfTen + 1); ++x) {
0308             QUrl u = QUrl::fromLocalFile(fileNameArg.arg(randInt[powerOfTen].at(x))).adjusted(QUrl::StripTrailingSlash);
0309 
0310             KFileItem kfi(u, QStringLiteral("text/text"));
0311             auto it = std::lower_bound(lstItems.begin(), lstItems.end(), u);
0312             lstItems.insert(it, kfi);
0313         }
0314     }
0315 };
0316 // END BinaryList
0317 // END Implementations
0318 
0319 // BEGIN templates
0320 
0321 template<class T>
0322 void fillNumberOfFiles()
0323 {
0324     QTest::addColumn<int>("numberOfFiles");
0325     for (int i = 0; i < maxPowerOfTen; ++i) {
0326         // it shows numberOfFiles: 10, 100 or 1000 but the data is the power of ten
0327         QTest::newRow(QStringLiteral("%1").arg(pow(10, i + 1)).toLatin1()) << i;
0328     }
0329 }
0330 
0331 template<class T>
0332 void createFiles(int powerOfTen)
0333 {
0334     T data;
0335     const int numberOfFiles = pow(10, powerOfTen + 1);
0336     data.reserve(numberOfFiles);
0337     QBENCHMARK {
0338         data.clear();
0339         data.insert(powerOfTen);
0340     }
0341     QCOMPARE(data.lstItems.size(), numberOfFiles);
0342 }
0343 
0344 template<class T>
0345 void findByName(int powerOfTen)
0346 {
0347     T data;
0348     data.clear();
0349     data.reserve(pow(10, powerOfTen + 1));
0350     data.insert(powerOfTen);
0351 
0352     QBENCHMARK {
0353         for (int i = 0; i < powerOfTen; i++) {
0354             QString randName = QStringLiteral("a%1.txt").arg(pow(10, i));
0355             KFileItem item = data.findByName(randName);
0356             // QCOMPARE(item.name(), randName);
0357         }
0358     }
0359     QVERIFY(data.findByName(QLatin1String("b1.txt")).isNull());
0360 }
0361 
0362 template<class T>
0363 void findByUrl(int powerOfTen)
0364 {
0365     T data;
0366     data.clear();
0367     data.reserve(pow(10, powerOfTen + 1));
0368     data.insert(powerOfTen);
0369     QBENCHMARK {
0370         for (int i = 0; i < powerOfTen; i++) {
0371             QUrl randUrl = QUrl::fromLocalFile(fileNameArg.arg(pow(10, i)));
0372             KFileItem item = data.findByUrl(randUrl);
0373             // QCOMPARE(item.url(), randUrl);
0374         }
0375     }
0376     QVERIFY(data.findByUrl(QUrl::fromLocalFile(QLatin1String("/home/user/Folder1/SubFolder1/b1.txt"))).isNull());
0377 }
0378 
0379 template<class T>
0380 void findByUrlAll(int powerOfTen)
0381 {
0382     T data;
0383     data.clear();
0384     data.reserve(pow(10, powerOfTen + 1));
0385     data.insert(powerOfTen);
0386     QBENCHMARK {
0387         for (int i = 0; i < pow(10, powerOfTen + 1); i++) {
0388             QUrl u = QUrl::fromLocalFile(fileNameArg.arg(i)).adjusted(QUrl::StripTrailingSlash);
0389             data.findByUrl(u);
0390         }
0391     }
0392 }
0393 
0394 // END templates
0395 
0396 // BEGIN tests
0397 void kcoreDirListerEntryBenchmark::testCreateFiles_List_data()
0398 {
0399     fillNumberOfFiles<ListImplementation>();
0400 }
0401 void kcoreDirListerEntryBenchmark::testCreateFiles_List()
0402 {
0403     QFETCH(int, numberOfFiles);
0404     createFiles<ListImplementation>(numberOfFiles);
0405 }
0406 void kcoreDirListerEntryBenchmark::testFindByNameFiles_List_data()
0407 {
0408     fillNumberOfFiles<ListImplementation>();
0409 }
0410 void kcoreDirListerEntryBenchmark::testFindByNameFiles_List()
0411 {
0412     QFETCH(int, numberOfFiles);
0413     findByName<ListImplementation>(numberOfFiles);
0414 }
0415 void kcoreDirListerEntryBenchmark::testFindByUrlFiles_List_data()
0416 {
0417     fillNumberOfFiles<ListImplementation>();
0418 }
0419 void kcoreDirListerEntryBenchmark::testFindByUrlFiles_List()
0420 {
0421     QFETCH(int, numberOfFiles);
0422     findByUrl<ListImplementation>(numberOfFiles);
0423 }
0424 void kcoreDirListerEntryBenchmark::testFindByUrlAllFiles_List_data()
0425 {
0426     fillNumberOfFiles<ListImplementation>();
0427 }
0428 void kcoreDirListerEntryBenchmark::testFindByUrlAllFiles_List()
0429 {
0430     QFETCH(int, numberOfFiles);
0431     findByUrlAll<ListImplementation>(numberOfFiles);
0432 }
0433 
0434 void kcoreDirListerEntryBenchmark::testCreateFiles_Map_data()
0435 {
0436     fillNumberOfFiles<ListImplementation>();
0437 }
0438 void kcoreDirListerEntryBenchmark::testCreateFiles_Map()
0439 {
0440     QFETCH(int, numberOfFiles);
0441     createFiles<QMapImplementation>(numberOfFiles);
0442 }
0443 void kcoreDirListerEntryBenchmark::testFindByNameFiles_Map_data()
0444 {
0445     fillNumberOfFiles<ListImplementation>();
0446 }
0447 void kcoreDirListerEntryBenchmark::testFindByNameFiles_Map()
0448 {
0449     QFETCH(int, numberOfFiles);
0450     findByName<QMapImplementation>(numberOfFiles);
0451 }
0452 void kcoreDirListerEntryBenchmark::testFindByUrlFiles_Map_data()
0453 {
0454     fillNumberOfFiles<ListImplementation>();
0455 }
0456 void kcoreDirListerEntryBenchmark::testFindByUrlFiles_Map()
0457 {
0458     QFETCH(int, numberOfFiles);
0459     findByUrl<QMapImplementation>(numberOfFiles);
0460 }
0461 void kcoreDirListerEntryBenchmark::testFindByUrlAllFiles_Map_data()
0462 {
0463     fillNumberOfFiles<ListImplementation>();
0464 }
0465 void kcoreDirListerEntryBenchmark::testFindByUrlAllFiles_Map()
0466 {
0467     QFETCH(int, numberOfFiles);
0468     findByUrlAll<QMapImplementation>(numberOfFiles);
0469 }
0470 
0471 void kcoreDirListerEntryBenchmark::testCreateFiles_Hash_data()
0472 {
0473     fillNumberOfFiles<ListImplementation>();
0474 }
0475 void kcoreDirListerEntryBenchmark::testCreateFiles_Hash()
0476 {
0477     QFETCH(int, numberOfFiles);
0478     createFiles<QHashImplementation>(numberOfFiles);
0479 }
0480 void kcoreDirListerEntryBenchmark::testFindByNameFiles_Hash_data()
0481 {
0482     fillNumberOfFiles<ListImplementation>();
0483 }
0484 void kcoreDirListerEntryBenchmark::testFindByNameFiles_Hash()
0485 {
0486     QFETCH(int, numberOfFiles);
0487     findByName<QHashImplementation>(numberOfFiles);
0488 }
0489 void kcoreDirListerEntryBenchmark::testFindByUrlFiles_Hash_data()
0490 {
0491     fillNumberOfFiles<ListImplementation>();
0492 }
0493 void kcoreDirListerEntryBenchmark::testFindByUrlFiles_Hash()
0494 {
0495     QFETCH(int, numberOfFiles);
0496     findByUrl<QHashImplementation>(numberOfFiles);
0497 }
0498 void kcoreDirListerEntryBenchmark::testFindByUrlAllFiles_Hash_data()
0499 {
0500     fillNumberOfFiles<ListImplementation>();
0501 }
0502 void kcoreDirListerEntryBenchmark::testFindByUrlAllFiles_Hash()
0503 {
0504     QFETCH(int, numberOfFiles);
0505     findByUrlAll<QHashImplementation>(numberOfFiles);
0506 }
0507 
0508 void kcoreDirListerEntryBenchmark::testCreateFiles_Binary_data()
0509 {
0510     fillNumberOfFiles<ListImplementation>();
0511 }
0512 void kcoreDirListerEntryBenchmark::testCreateFiles_Binary()
0513 {
0514     QFETCH(int, numberOfFiles);
0515     createFiles<BinaryListImplementation>(numberOfFiles);
0516 }
0517 void kcoreDirListerEntryBenchmark::testFindByNameFiles_Binary_data()
0518 {
0519     fillNumberOfFiles<ListImplementation>();
0520 }
0521 void kcoreDirListerEntryBenchmark::testFindByNameFiles_Binary()
0522 {
0523     QFETCH(int, numberOfFiles);
0524     findByName<BinaryListImplementation>(numberOfFiles);
0525 }
0526 void kcoreDirListerEntryBenchmark::testFindByUrlFiles_Binary_data()
0527 {
0528     fillNumberOfFiles<ListImplementation>();
0529 }
0530 void kcoreDirListerEntryBenchmark::testFindByUrlFiles_Binary()
0531 {
0532     QFETCH(int, numberOfFiles);
0533     findByUrl<BinaryListImplementation>(numberOfFiles);
0534 }
0535 void kcoreDirListerEntryBenchmark::testFindByUrlAllFiles_Binary_data()
0536 {
0537     fillNumberOfFiles<ListImplementation>();
0538 }
0539 void kcoreDirListerEntryBenchmark::testFindByUrlAllFiles_Binary()
0540 {
0541     QFETCH(int, numberOfFiles);
0542     findByUrlAll<BinaryListImplementation>(numberOfFiles);
0543 }
0544 
0545 // END tests
0546 
0547 QTEST_MAIN(kcoreDirListerEntryBenchmark)
0548 
0549 #include "kcoredirlister_benchmark.moc"