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