src/tests/kfileitemmodelbenchmark.cpp

   1 /***************************************************************************
   2  *   Copyright (C) 2011 by Peter Penz <peter.penz19@gmail.com>             *
   3  *   Copyright (C) 2013 by Frank Reininghaus <frank78ac@googlemail.com>    *
   4  *                                                                         *
   5  *   This program is free software; you can redistribute it and/or modify  *
   6  *   it under the terms of the GNU General Public License as published by  *
   7  *   the Free Software Foundation; either version 2 of the License, or     *
   8  *   (at your option) any later version.                                   *
   9  *                                                                         *
  10  *   This program is distributed in the hope that it will be useful,       *
  11  *   but WITHOUT ANY WARRANTY; without even the implied warranty of        *
  12  *   MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the         *
  13  *   GNU General Public License for more details.                          *
  14  *                                                                         *
  15  *   You should have received a copy of the GNU General Public License     *
  16  *   along with this program; if not, write to the                         *
  17  *   Free Software Foundation, Inc.,                                       *
  18  *   51 Franklin Street, Fifth Floor, Boston, MA 02110-1301 USA            *
  19  ***************************************************************************/
  20
  21 #include <QTest>
  22 #include <QSignalSpy>
  23
  24 #include <algorithm>
  25 #include <random>
  26
  27 #include "kitemviews/kfileitemmodel.h"
  28 #include "kitemviews/private/kfileitemmodelsortalgorithm.h"
  29
  30 #include "testdir.h"
  31
  32 void myMessageOutput(QtMsgType type, const char* msg)
  33 {
  34     switch (type) {
  35     case QtDebugMsg:
  36         break;
  37     case QtWarningMsg:
  38         break;
  39     case QtCriticalMsg:
  40         fprintf(stderr, "Critical: %s\n", msg);
  41         break;
  42     case QtFatalMsg:
  43         fprintf(stderr, "Fatal: %s\n", msg);
  44         abort();
  45     default:
  46        break;
  47     }
  48 }
  49
  50 Q_DECLARE_METATYPE(KFileItemList)
  51 Q_DECLARE_METATYPE(KItemRangeList)
  52
  53 class KFileItemModelBenchmark : public QObject
  54 {
  55     Q_OBJECT
  56
  57 public:
  58     KFileItemModelBenchmark();
  59
  60 private slots:
  61     void insertAndRemoveManyItems_data();
  62     void insertAndRemoveManyItems();
  63     void insertManyChildItems();
  64
  65 private:
  66     static KFileItemList createFileItemList(const QStringList& fileNames, const QString& urlPrefix = QLatin1String("file:///"));
  67 };
  68
  69 KFileItemModelBenchmark::KFileItemModelBenchmark()
  70 {
  71 }
  72
  73 void KFileItemModelBenchmark::insertAndRemoveManyItems_data()
  74 {
  75     QTest::addColumn<KFileItemList>("initialItems");
  76     QTest::addColumn<KFileItemList>("newItems");
  77     QTest::addColumn<KFileItemList>("removedItems");
  78     QTest::addColumn<KFileItemList>("expectedFinalItems");
  79     QTest::addColumn<KItemRangeList>("expectedItemsInserted");
  80     QTest::addColumn<KItemRangeList>("expectedItemsRemoved");
  81
  82     QList<int> sizes;
  83     sizes << 1000 << 4000 << 16000 << 64000 << 256000;
  84     //sizes << 50000 << 100000 << 150000 << 200000 << 250000;
  85
  86     foreach (int n, sizes) {
  87         QStringList allStrings;
  88         for (int i = 0; i < n; ++i) {
  89             allStrings << QString::number(i);
  90         }
  91
  92         // We want to keep the sorting overhead in the benchmark low.
  93         // Therefore, we do not use natural sorting. However, this
  94         // means that our list is currently not sorted.
  95         allStrings.sort();
  96
  97         KFileItemList all = createFileItemList(allStrings);
  98
  99         KFileItemList firstHalf, secondHalf, even, odd;
 100         for (int i = 0; i < n; ++i) {
 101             if (i < n / 2) {
 102                 firstHalf << all.at(i);
 103             } else {
 104                 secondHalf << all.at(i);
 105             }
 106
 107             if (i % 2 == 0) {
 108                 even << all.at(i);
 109             } else {
 110                 odd << all.at(i);
 111             }
 112         }
 113
 114         KItemRangeList itemRangeListFirstHalf;
 115         itemRangeListFirstHalf << KItemRange(0, firstHalf.count());
 116
 117         KItemRangeList itemRangeListSecondHalf;
 118         itemRangeListSecondHalf << KItemRange(firstHalf.count(), secondHalf.count());
 119
 120         KItemRangeList itemRangeListOddInserted, itemRangeListOddRemoved;
 121         for (int i = 0; i < odd.count(); ++i) {
 122             // Note that the index in the KItemRange is the index of
 123             // the model *before* the items have been inserted.
 124             itemRangeListOddInserted << KItemRange(i + 1, 1);
 125             itemRangeListOddRemoved << KItemRange(2 * i + 1, 1);
 126         }
 127
 128         const int bufferSize = 128;
 129         char buffer[bufferSize];
 130
 131         snprintf(buffer, bufferSize, "all--n=%i", n);
 132         QTest::newRow(buffer) << all << KFileItemList() << KFileItemList() << all << KItemRangeList() << KItemRangeList();
 133
 134         snprintf(buffer, bufferSize, "1st half + 2nd half--n=%i", n);
 135         QTest::newRow(buffer) << firstHalf << secondHalf << KFileItemList() << all << itemRangeListSecondHalf << KItemRangeList();
 136
 137         snprintf(buffer, bufferSize, "2nd half + 1st half--n=%i", n);
 138         QTest::newRow(buffer) << secondHalf << firstHalf << KFileItemList() << all << itemRangeListFirstHalf << KItemRangeList();
 139
 140         snprintf(buffer, bufferSize, "even + odd--n=%i", n);
 141         QTest::newRow(buffer) << even << odd << KFileItemList() << all << itemRangeListOddInserted << KItemRangeList();
 142
 143         snprintf(buffer, bufferSize, "all - 2nd half--n=%i", n);
 144         QTest::newRow(buffer) << all << KFileItemList() << secondHalf << firstHalf << KItemRangeList() << itemRangeListSecondHalf;
 145
 146         snprintf(buffer, bufferSize, "all - 1st half--n=%i", n);
 147         QTest::newRow(buffer) << all << KFileItemList() << firstHalf << secondHalf << KItemRangeList() << itemRangeListFirstHalf;
 148
 149         snprintf(buffer, bufferSize, "all - odd--n=%i", n);
 150         QTest::newRow(buffer) << all << KFileItemList() << odd << even << KItemRangeList() << itemRangeListOddRemoved;
 151     }
 152 }
 153
 154 void KFileItemModelBenchmark::insertAndRemoveManyItems()
 155 {
 156     QFETCH(KFileItemList, initialItems);
 157     QFETCH(KFileItemList, newItems);
 158     QFETCH(KFileItemList, removedItems);
 159     QFETCH(KFileItemList, expectedFinalItems);
 160     QFETCH(KItemRangeList, expectedItemsInserted);
 161     QFETCH(KItemRangeList, expectedItemsRemoved);
 162
 163     KFileItemModel model;
 164
 165     // Avoid overhead caused by natural sorting
 166     // and determining the isDir/isLink roles.
 167     model.m_naturalSorting = false;
 168     model.setRoles({"text"});
 169
 170     QSignalSpy spyItemsInserted(&model, SIGNAL(itemsInserted(KItemRangeList)));
 171     QSignalSpy spyItemsRemoved(&model, SIGNAL(itemsRemoved(KItemRangeList)));
 172
 173     QBENCHMARK {
 174         model.slotClear();
 175         model.slotItemsAdded(model.directory(), initialItems);
 176         model.slotCompleted();
 177         QCOMPARE(model.count(), initialItems.count());
 178
 179         if (!newItems.isEmpty()) {
 180             model.slotItemsAdded(model.directory(), newItems);
 181             model.slotCompleted();
 182         }
 183         QCOMPARE(model.count(), initialItems.count() + newItems.count());
 184
 185         if (!removedItems.isEmpty()) {
 186             model.slotItemsDeleted(removedItems);
 187         }
 188         QCOMPARE(model.count(), initialItems.count() + newItems.count() - removedItems.count());
 189     }
 190
 191     QVERIFY(model.isConsistent());
 192
 193     for (int i = 0; i < model.count(); ++i) {
 194         QCOMPARE(model.fileItem(i), expectedFinalItems.at(i));
 195     }
 196
 197     if (!expectedItemsInserted.empty()) {
 198         QVERIFY(!spyItemsInserted.empty());
 199         const KItemRangeList actualItemsInserted = spyItemsInserted.last().first().value<KItemRangeList>();
 200         QCOMPARE(actualItemsInserted, expectedItemsInserted);
 201     }
 202
 203     if (!expectedItemsRemoved.empty()) {
 204         QVERIFY(!spyItemsRemoved.empty());
 205         const KItemRangeList actualItemsRemoved = spyItemsRemoved.last().first().value<KItemRangeList>();
 206         QCOMPARE(actualItemsRemoved, expectedItemsRemoved);
 207     }
 208 }
 209
 210 void KFileItemModelBenchmark::insertManyChildItems()
 211 {
 212     // TODO: this function needs to be adjusted to the changes in KFileItemModel
 213     // (replacement of slotNewItems(KFileItemList) by slotItemsAdded(KUrl,KFileItemList))
 214     // Currently, this function tries to insert child items of multiple
 215     // directories by invoking the slot only once.
 216 #if 0
 217     qInstallMsgHandler(myMessageOutput);
 218
 219     KFileItemModel model;
 220
 221     // Avoid overhead caused by natural sorting.
 222     model.m_naturalSorting = false;
 223
 224     QSet<QByteArray> modelRoles = model.roles();
 225     modelRoles << "isExpanded" << "isExpandable" << "expandedParentsCount";
 226     model.setRoles(modelRoles);
 227     model.setSortDirectoriesFirst(false);
 228
 229     // Create a test folder with a 3-level tree structure of folders.
 230     TestDir testFolder;
 231     int numberOfFolders = 0;
 232
 233     QStringList subFolderNames;
 234     subFolderNames << "a/" << "b/" << "c/" << "d/";
 235
 236     foreach (const QString& s1, subFolderNames) {
 237         ++numberOfFolders;
 238         foreach (const QString& s2, subFolderNames) {
 239             ++numberOfFolders;
 240             foreach (const QString& s3, subFolderNames) {
 241                 testFolder.createDir("level-1-" + s1 + "level-2-" + s2 + "level-3-" + s3);
 242                 ++numberOfFolders;
 243             }
 244         }
 245     }
 246
 247     // Open the folder in the model and expand all subfolders.
 248     model.loadDirectory(testFolder.url());
 249     QVERIFY(QTest::kWaitForSignal(&model, SIGNAL(itemsInserted(KItemRangeList)), DefaultTimeout));
 250
 251     int index = 0;
 252     while (index < model.count()) {
 253         if (model.isExpandable(index)) {
 254             model.setExpanded(index, true);
 255
 256             if (!model.data(index).value("text").toString().startsWith("level-3")) {
 257                 // New subfolders will appear unless we are on the final level already.
 258                 QVERIFY(QTest::kWaitForSignal(&model, SIGNAL(itemsInserted(KItemRangeList)), DefaultTimeout));
 259             }
 260
 261             QVERIFY(model.isExpanded(index));
 262         }
 263         ++index;
 264     }
 265
 266     QCOMPARE(model.count(), numberOfFolders);
 267
 268     // Create a list of many file items, which will be added to each of the
 269     // "level 1", "level 2", and "level 3" folders.
 270     const int filesPerDirectory = 500;
 271     QStringList allStrings;
 272     for (int i = 0; i < filesPerDirectory; ++i) {
 273         allStrings << QString::number(i);
 274     }
 275     allStrings.sort();
 276
 277     KFileItemList newItems;
 278
 279     // Also keep track of all expected items, including the existing
 280     // folders, to verify the final state of the model.
 281     KFileItemList allExpectedItems;
 282
 283     for (int i = 0; i < model.count(); ++i) {
 284         const KFileItem folderItem = model.fileItem(i);
 285         allExpectedItems << folderItem;
 286
 287         const KUrl folderUrl = folderItem.url();
 288         KFileItemList itemsInFolder = createFileItemList(allStrings, folderUrl.url(KUrl::AddTrailingSlash));
 289
 290         newItems.append(itemsInFolder);
 291         allExpectedItems.append(itemsInFolder);
 292     }
 293
 294     // Bring the items into random order.
 295     std::random_device rd;
 296     std::mt19937 g(rd());
 297     std::shuffle(newItems.begin(), newItems.end(), g);
 298
 299     // Measure how long it takes to insert and then remove all files.
 300     QBENCHMARK {
 301         model.slotNewItems(newItems);
 302         model.slotCompleted();
 303
 304         QCOMPARE(model.count(), allExpectedItems.count());
 305         QVERIFY(model.isConsistent());
 306         for (int i = 0; i < model.count(); ++i) {
 307             QCOMPARE(model.fileItem(i), allExpectedItems.at(i));
 308         }
 309
 310         model.slotItemsDeleted(newItems);
 311         QCOMPARE(model.count(), numberOfFolders);
 312         QVERIFY(model.isConsistent());
 313     }
 314 #endif
 315 }
 316
 317 KFileItemList KFileItemModelBenchmark::createFileItemList(const QStringList& fileNames, const QString& prefix)
 318 {
 319     // Suppress 'file does not exist anymore' messages from KFileItemPrivate::init().
 320     qInstallMsgHandler(myMessageOutput);
 321
 322     KFileItemList result;
 323     foreach (const QString& name, fileNames) {
 324         const KFileItem item(QUrl::fromLocalFile(prefix + name), QString(), KFileItem::Unknown);
 325         result << item;
 326     }
 327     return result;
 328 }
 329
 330 QTEST_MAIN(KFileItemModelBenchmark)
 331
 332 #include "kfileitemmodelbenchmark.moc"