diff --git a/src/kitemviews/private/kdirectorycontentscounter.h b/src/kitemviews/private/kdirectorycontentscounter.h
--- a/src/kitemviews/private/kdirectorycontentscounter.h
+++ b/src/kitemviews/private/kdirectorycontentscounter.h
@@ -23,9 +23,8 @@
 
 #include "kdirectorycontentscounterworker.h"
 
-#include <QQueue>
 #include <QSet>
-#include <QHash>
+#include <QVector>
 
 class KDirWatch;
 class KFileItemModel;
@@ -72,7 +71,9 @@
 private:
     KFileItemModel* m_model;
 
-    QQueue<QString> m_queue;
+    // priority_queue items are treated before queue
+    QVector<QString> m_priority_queue;
+    QVector<QString> m_queue;
 
     static QThread* m_workerThread;
 
diff --git a/src/kitemviews/private/kdirectorycontentscounter.cpp b/src/kitemviews/private/kdirectorycontentscounter.cpp
--- a/src/kitemviews/private/kdirectorycontentscounter.cpp
+++ b/src/kitemviews/private/kdirectorycontentscounter.cpp
@@ -35,6 +35,7 @@
 KDirectoryContentsCounter::KDirectoryContentsCounter(KFileItemModel* model, QObject* parent) :
     QObject(parent),
     m_model(model),
+    m_priority_queue(),
     m_queue(),
     m_worker(nullptr),
     m_workerIsBusy(false),
@@ -103,8 +104,12 @@
         m_watchedDirs.insert(resolvedPath);
     }
 
-    if (!m_queue.isEmpty()) {
-        startWorker(m_queue.dequeue());
+    if (!m_priority_queue.isEmpty()) {
+        // dequeue tail
+        startWorker(m_priority_queue.takeLast());
+    } else if (!m_queue.isEmpty()) {
+        // dequeue tail
+        startWorker(m_queue.takeLast());
     }
 
     if (s_cache->contains(resolvedPath)) {
@@ -152,12 +157,14 @@
             }
             m_watchedDirs.clear();
             m_queue.clear();
+            m_priority_queue.clear();
         } else {
             QMutableSetIterator<QString> it(m_watchedDirs);
             while (it.hasNext()) {
                 const QString& path = it.next();
                 if (m_model->index(QUrl::fromLocalFile(path)) < 0) {
                     m_dirWatcher->removeDir(path);
+                    s_cache->remove(path);
                     it.remove();
                 }
             }
@@ -167,15 +174,24 @@
 
 void KDirectoryContentsCounter::startWorker(const QString& path)
 {
-    if (s_cache->contains(path)) {
+    bool alreadyInCache = s_cache->contains(path);
+    if (alreadyInCache) {
         // fast path when in cache
         // will be updated later if result has changed
         const auto pair = s_cache->value(path);
         emit result(path, pair.first, pair.second);
     }
 
     if (m_workerIsBusy) {
-        m_queue.enqueue(path);
+        if (!m_priority_queue.contains(path) && !m_queue.contains(path)) {
+            if (!alreadyInCache) {
+                // path is not in cache, will treat it first
+                m_priority_queue.insert(0, path);
+            } else {
+                // unprioritized path to visit
+                m_queue.insert(0, path);
+            }
+        }
     } else {
         KDirectoryContentsCounterWorker::Options options;