Improve the speed of QDir, QFileInfo and QDirIterator.

This patch basically avoid to call too often currentFileInfo in
QDirIterator. It replaces the QHash that was overkill in QFileInfo for
caching filenames. The last part is reordering the matchesFilter
to avoid stat as much as possible by using the power of && and filters
that are set on QDirIterator. And it fixes some random "mistake".

I have added a benchmark in QDir which test some use case with
10000 files in a dir.

Written-with: Benjamin
Reviewed-by: phartman

7 files changed, 165 insertions, 69 deletions

diff --git a/src/corelib/io/qabstractfileengine.cpp b/src/corelib/io/qabstractfileengine.cpp
index bedc121..379c932 100644
--- a/src/corelib/io/qabstractfileengine.cpp
+++ b/src/corelib/io/qabstractfileengine.cpp
@@ -252,6 +252,8 @@ QAbstractFileEngine *QAbstractFileEngine::create(const QString &fileName)
     \value CanonicalPathName Same as CanonicalName, excluding the base name.
     \value BundleName Returns the name of the bundle implies BundleType is set.
 
+    \omitvalue NFileNames
+
     \sa fileName(), setFileName()
 */
 
diff --git a/src/corelib/io/qabstractfileengine.h b/src/corelib/io/qabstractfileengine.h
index d742467..f60a5eb 100644
--- a/src/corelib/io/qabstractfileengine.h
+++ b/src/corelib/io/qabstractfileengine.h
@@ -100,7 +100,8 @@ public:
         LinkName,
         CanonicalName,
         CanonicalPathName,
-        BundleName
+        BundleName,
+        NFileNames = 9
     };
     enum FileOwner {
         OwnerUser,
diff --git a/src/corelib/io/qdiriterator.cpp b/src/corelib/io/qdiriterator.cpp
index 81bfb27..8ac5d14 100644
--- a/src/corelib/io/qdiriterator.cpp
+++ b/src/corelib/io/qdiriterator.cpp
@@ -110,7 +110,7 @@ public:
                           QDir::Filters filters);
     void advance();
     bool shouldFollowDirectory(const QFileInfo &);
-    bool matchesFilters(const QAbstractFileEngineIterator *it) const;
+    bool matchesFilters(const QString &fileName, const QFileInfo &fi) const;
 
     QSet<QString> visitedLinks;
     QAbstractFileEngine *engine;
@@ -135,14 +135,13 @@ public:
 */
 QDirIteratorPrivate::QDirIteratorPrivate(const QString &path, const QStringList &nameFilters,
                                          QDir::Filters filters, QDirIterator::IteratorFlags flags)
-    : engine(0), path(path), iteratorFlags(flags), followNextDir(false), first(true), done(false)
+    : engine(0), path(path), nextFileInfo(path), iteratorFlags(flags), followNextDir(false), first(true), done(false)
 {
     if (filters == QDir::NoFilter)
         filters = QDir::AllEntries;
     this->filters = filters;
     this->nameFilters = nameFilters;
 
-    nextFileInfo.setFile(path);
     pushSubDirectory(nextFileInfo.isSymLink() ? nextFileInfo.canonicalFilePath() : path,
                      nameFilters, filters);
 }
@@ -214,18 +213,18 @@ void QDirIteratorPrivate::advance()
         bool foundDirectory = false;
         while (it->hasNext()) {
             it->next();
-            if (matchesFilters(it)) {
+            const QFileInfo info = it->currentFileInfo();
+            if (matchesFilters(it->currentFileName(), info)) {
                 currentFileInfo = nextFileInfo;
-                nextFileInfo = it->currentFileInfo();
+                nextFileInfo = info;
                 // Signal that we want to follow this entry.
                 followNextDir = shouldFollowDirectory(nextFileInfo);
                 //We found a matching entry.
                 return;
 
             } else if (iteratorFlags & QDirIterator::Subdirectories) {
-                QFileInfo fileInfo = it->currentFileInfo();
 
-                if (!shouldFollowDirectory(fileInfo))
+                if (!shouldFollowDirectory(info))
                     continue;
                 QString subDir = it->currentFilePath();
 #ifdef Q_OS_WIN
@@ -288,48 +287,32 @@ bool QDirIteratorPrivate::shouldFollowDirectory(const QFileInfo &fileInfo)
     current entry will be returned as part of the directory iteration);
     otherwise, false is returned.
 */
-bool QDirIteratorPrivate::matchesFilters(const QAbstractFileEngineIterator *it) const
+bool QDirIteratorPrivate::matchesFilters(const QString &fileName, const QFileInfo &fi) const
 {
-    const bool filterPermissions = ((filters & QDir::PermissionMask)
-                                    && (filters & QDir::PermissionMask) != QDir::PermissionMask);
-    const bool skipDirs     = !(filters & (QDir::Dirs | QDir::AllDirs));
-    const bool skipFiles    = !(filters & QDir::Files);
-    const bool skipSymlinks = (filters & QDir::NoSymLinks);
-    const bool doReadable   = !filterPermissions || (filters & QDir::Readable);
-    const bool doWritable   = !filterPermissions || (filters & QDir::Writable);
-    const bool doExecutable = !filterPermissions || (filters & QDir::Executable);
-    const bool includeHidden = (filters & QDir::Hidden);
-    const bool includeSystem = (filters & QDir::System);
-
-#ifndef QT_NO_REGEXP
-    // Prepare name filters
-    QList<QRegExp> regexps;
-    bool hasNameFilters = !nameFilters.isEmpty() && !(nameFilters.contains(QLatin1String("*")));
-    if (hasNameFilters) {
-        for (int i = 0; i < nameFilters.size(); ++i) {
-            regexps << QRegExp(nameFilters.at(i),
-                               (filters & QDir::CaseSensitive) ? Qt::CaseSensitive : Qt::CaseInsensitive,
-                               QRegExp::Wildcard);
-        }
-    }
-#endif
-
-    QString fileName = it->currentFileName();
     if (fileName.isEmpty()) {
         // invalid entry
         return false;
     }
 
-    QFileInfo fi = it->currentFileInfo();
-    QString filePath = it->currentFilePath();
+    // filter . and ..?
+    const int fileNameSize = fileName.size();
+    const bool dotOrDotDot = fileName[0] == QLatin1Char('.')
+                             && ((fileNameSize == 1)
+                                 ||(fileNameSize == 2 && fileName[1] == QLatin1Char('.')));
+    if ((filters & QDir::NoDotAndDotDot) && dotOrDotDot)
+        return false;
 
-#ifndef QT_NO_REGEXP
+    // name filter
+#ifndef QT_NO_REGEXP 
+    const bool hasNameFilters = !nameFilters.isEmpty() && !(nameFilters.contains(QLatin1String("*")));
     // Pass all entries through name filters, except dirs if the AllDirs
-    // filter is passed.
     if (hasNameFilters && !((filters & QDir::AllDirs) && fi.isDir())) {
         bool matched = false;
-        for (int i = 0; i < regexps.size(); ++i) {
-            if (regexps.at(i).exactMatch(fileName)) {
+        for (int i = 0; i < nameFilters.size(); ++i) {
+            QRegExp regexp(nameFilters.at(i),
+                            (filters & QDir::CaseSensitive) ? Qt::CaseSensitive : Qt::CaseInsensitive,
+                            QRegExp::Wildcard);
+            if (regexp.exactMatch(fileName)) {
                 matched = true;
                 break;
             }
@@ -338,47 +321,53 @@ bool QDirIteratorPrivate::matchesFilters(const QAbstractFileEngineIterator *it)
             return false;
     }
 #endif
-    
-    bool dotOrDotDot = (fileName == QLatin1String(".") || fileName == QLatin1String(".."));
-    if ((filters & QDir::NoDotAndDotDot) && dotOrDotDot)
-        return false;
 
-    bool isHidden = !dotOrDotDot && fi.isHidden();
-    if (!includeHidden && isHidden)
+    // filter hidden
+    const bool includeHidden = (filters & QDir::Hidden);
+    if (!includeHidden && !dotOrDotDot && fi.isHidden())
         return false;
 
-    bool isSystem = (!fi.isFile() && !fi.isDir() && !fi.isSymLink())
-                    || (!fi.exists() && fi.isSymLink());
-    if (!includeSystem && isSystem)
+    // filter system files
+    const bool includeSystem = (filters & QDir::System);
+    if (!includeSystem && ((!fi.isFile() && !fi.isDir() && !fi.isSymLink())
+                    || (!fi.exists() && fi.isSymLink())))
         return false;
 
-    bool alwaysShow = (filters & QDir::TypeMask) == 0
-        && ((isHidden && includeHidden)
-            || (includeSystem && isSystem));
 
-    // Skip files and directories
-    if ((filters & QDir::AllDirs) == 0 && skipDirs && fi.isDir()) {
-        if (!alwaysShow)
+    if (!includeSystem && !dotOrDotDot && ((fi.exists() && !fi.isFile() && !fi.isDir() && !fi.isSymLink())
+                                           || (!fi.exists() && fi.isSymLink()))) {
+        return false;
+    }
+
+    // skip directories
+    const bool skipDirs = !(filters & (QDir::Dirs | QDir::AllDirs));
+    if (skipDirs && fi.isDir()) {
+        if (!(includeHidden && !dotOrDotDot && fi.isHidden())
+              || (includeSystem && !fi.exists() && fi.isSymLink()))
             return false;
     }
 
-    if ((skipFiles && (fi.isFile() || !fi.exists()))
-        || (skipSymlinks && fi.isSymLink())) {
-        if (!alwaysShow)
+    // skip files
+    const bool skipFiles    = !(filters & QDir::Files);
+    const bool skipSymlinks = (filters & QDir::NoSymLinks);
+    if ((skipFiles && (fi.isFile() || !fi.exists())) || (skipSymlinks && fi.isSymLink())) {
+        if (!((includeHidden && !dotOrDotDot && fi.isHidden())
+            || (includeSystem && !fi.exists() && fi.isSymLink())))
             return false;
     }
 
+    // filter permissions
+    const bool filterPermissions = ((filters & QDir::PermissionMask)
+                                    && (filters & QDir::PermissionMask) != QDir::PermissionMask);
+    const bool doWritable = !filterPermissions || (filters & QDir::Writable);
+    const bool doExecutable = !filterPermissions || (filters & QDir::Executable);
+    const bool doReadable = !filterPermissions || (filters & QDir::Readable);
     if (filterPermissions
         && ((doReadable && !fi.isReadable())
             || (doWritable && !fi.isWritable())
             || (doExecutable && !fi.isExecutable()))) {
         return false;
     }
-
-    if (!includeSystem && !dotOrDotDot && ((fi.exists() && !fi.isFile() && !fi.isDir() && !fi.isSymLink())
-                                           || (!fi.exists() && fi.isSymLink()))) {
-        return false;
-    }
     
     return true;
 }
diff --git a/src/corelib/io/qfileinfo.cpp b/src/corelib/io/qfileinfo.cpp
index 4f1b943..3442a1e 100644
--- a/src/corelib/io/qfileinfo.cpp
+++ b/src/corelib/io/qfileinfo.cpp
@@ -59,7 +59,6 @@ QFileInfoPrivate::QFileInfoPrivate(const QFileInfo *copy)
         data = copy->d_func()->data;
     } else {
         data = new QFileInfoPrivate::Data;
-        data->clear();
     }
 }
 
@@ -134,11 +133,11 @@ void QFileInfoPrivate::detach()
 
 QString QFileInfoPrivate::getFileName(QAbstractFileEngine::FileName name) const
 {
-    if(data->cache_enabled && data->fileNames.contains((int)name))
-        return data->fileNames.value(name);
+    if(data->cache_enabled && !data->fileNames[(int)name].isNull())
+        return data->fileNames[(int)name];
     QString ret = data->fileEngine->fileName(name);
     if(data->cache_enabled)
-        data->fileNames.insert((int)name, ret);
+        data->fileNames[(int)name] = ret;
     return ret;
 }
 
diff --git a/src/corelib/io/qfileinfo_p.h b/src/corelib/io/qfileinfo_p.h
index 8155bcb..e46365d 100644
--- a/src/corelib/io/qfileinfo_p.h
+++ b/src/corelib/io/qfileinfo_p.h
@@ -95,14 +95,15 @@ public:
                 (void)fileEngine->fileFlags(QFSFileEngine::Refresh);
         }
         inline void clear() {
-            fileNames.clear();
             clearFlags();
+            for (int i = QAbstractFileEngine::NFileNames - 1 ; i >= 0 ; --i)
+                fileNames[i].clear();
         }
         mutable QAtomicInt ref;
 
         QAbstractFileEngine *fileEngine;
         mutable QString fileName;
-        mutable QHash<int, QString> fileNames;
+        mutable QString fileNames[QAbstractFileEngine::NFileNames];
 
         mutable uint cachedFlags : 31;
         mutable uint cache_enabled : 1;
diff --git a/tests/benchmarks/qdir/qdir.pro b/tests/benchmarks/qdir/qdir.pro
new file mode 100644
index 0000000..2cdebfd
--- /dev/null
+++ b/tests/benchmarks/qdir/qdir.pro
@@ -0,0 +1,8 @@
+load(qttest_p4)
+TEMPLATE = app
+TARGET = tst_qdir
+DEPENDPATH += .
+INCLUDEPATH += .
+
+# Input
+SOURCES += tst_qdir.cpp
diff --git a/tests/benchmarks/qdir/tst_qdir.cpp b/tests/benchmarks/qdir/tst_qdir.cpp
new file mode 100644
index 0000000..c95ff96
--- /dev/null
+++ b/tests/benchmarks/qdir/tst_qdir.cpp
@@ -0,0 +1,96 @@
+#include <QtTest/QtTest>
+
+#include<dirent.h>
+#include <sys/types.h>
+#include <sys/stat.h>
+#include <unistd.h>
+
+class Test : public QObject{
+  Q_OBJECT
+public slots:
+    void initTestCase() {
+        QDir testdir = QDir::tempPath();
+
+        const QString subfolder_name = QLatin1String("test_speed");
+        QVERIFY(testdir.mkdir(subfolder_name));
+        QVERIFY(testdir.cd(subfolder_name));
+
+        for (uint i=0; i<10000; ++i) {
+            QFile file(testdir.absolutePath() + "/testfile_" + QString::number(i));
+            file.open(QIODevice::WriteOnly);
+        }
+    }
+    void cleanupTestCase() {
+        {
+            QDir testdir(QDir::tempPath() + QLatin1String("/test_speed"));
+
+            foreach (const QString &filename, testdir.entryList()) {
+                testdir.remove(filename);
+            }
+        }
+        const QDir temp = QDir(QDir::tempPath());
+        temp.rmdir(QLatin1String("test_speed"));
+    }
+private slots:
+    void sizeSpeed() {
+        QDir testdir(QDir::tempPath() + QLatin1String("/test_speed"));
+        QBENCHMARK {
+            QFileInfoList fileInfoList = testdir.entryInfoList(QDir::Files, QDir::Unsorted);
+            foreach (const QFileInfo &fileInfo, fileInfoList) {
+                fileInfo.isDir();
+                fileInfo.size();
+            }
+        }
+    }
+    void sizeSpeedWithoutFilter() {
+        QDir testdir(QDir::tempPath() + QLatin1String("/test_speed"));
+        QBENCHMARK {
+            QFileInfoList fileInfoList = testdir.entryInfoList(QDir::NoFilter, QDir::Unsorted);
+            foreach (const QFileInfo &fileInfo, fileInfoList) {
+                fileInfo.size();
+            }
+        }
+    }
+    void sizeSpeedWithoutFileInfoList() {
+        QDir testdir(QDir::tempPath() + QLatin1String("/test_speed"));
+        testdir.setSorting(QDir::Unsorted);
+        QBENCHMARK {
+            QStringList fileList = testdir.entryList(QDir::NoFilter, QDir::Unsorted);
+            foreach (const QString &filename, fileList) {
+                QFileInfo fileInfo(filename);
+                fileInfo.size();
+            }
+        }
+    }
+    void iDontWantAnyStat() {
+        QDir testdir(QDir::tempPath() + QLatin1String("/test_speed"));
+        testdir.setSorting(QDir::Unsorted);
+        testdir.setFilter(QDir::AllEntries | QDir::System | QDir::Hidden);
+        QBENCHMARK {
+            QStringList fileList = testdir.entryList(QDir::NoFilter, QDir::Unsorted);
+            foreach (const QString &filename, fileList) {
+
+            }
+        }
+    }
+    void testLowLevel() {
+        QDir testdir(QDir::tempPath() + QLatin1String("/test_speed"));
+        DIR *dir = opendir(qPrintable(testdir.absolutePath()));
+        QVERIFY(!chdir(qPrintable(testdir.absolutePath())));
+        QBENCHMARK {
+            struct dirent *item = readdir(dir);
+            while (item) {
+                char *fileName = item->d_name;
+
+                struct stat fileStat;
+                QVERIFY(!stat(fileName, &fileStat));
+
+                item = readdir(dir);
+            }
+        }
+        closedir(dir);
+    }
+};
+
+QTEST_MAIN(Test)
+#include "tst_qdir.moc"