Rawtherapee: Something is O(n²) in file browser

[heckflosse]

The following patch clearly shows that something is O(n²) in file browser.
Precisely the number of calls to

ThumbBrowserEntryBase::setPosition

is 2*n + n*(n+1)/2

where n is the number of files in a folder.

This can (and will) be problematic when a folder contains a lot of files.
For example on a folder with 1000 files the function will be called 502500 times.

diff --git a/rtgui/thumbbrowserentrybase.cc b/rtgui/thumbbrowserentrybase.cc
index cf0ce1bb..755e3226 100644
--- a/rtgui/thumbbrowserentrybase.cc
+++ b/rtgui/thumbbrowserentrybase.cc
@@ -20,6 +20,7 @@
 #include "thumbbrowserbase.h"
 #include "options.h"
 #include "../rtengine/mytime.h"
+#include <iostream>

 ThumbBrowserEntryBase::ThumbBrowserEntryBase (const Glib::ustring& fname)
     : fnlabw(0), fnlabh(0), dtlabw(0), dtlabh(0), exlabw(0), exlabh(0), prew(0), preh(0),
@@ -495,6 +496,7 @@ void ThumbBrowserEntryBase::draw (Cairo::RefPtr<Cairo::Context> cc)

 void ThumbBrowserEntryBase::setPosition (int x, int y, int w, int h)
 {
+    std::cout << "ThumbBrowserEntryBase::setPosition" << std::endl;
     MYWRITERLOCK(l, lockRW);

     exp_width = w;

[agriggio]

This is because FileBrowser::redraw is called whenever a new entry is added (by FileBrowser::addEntry_). A possible solution would be to use some caching to avoid unnecessary recomputations. Probably this is not a one-liner though...

[Floessie]

Probably this is not a one-liner though...

How about a (atomic?) bool set_position_pending and IdleRegister? Not a one-liner but maybe a ten-liner...

[agriggio]

@Floessie you need to show me the ten lines, otherwise I don't follow :wink:

[Floessie]

@agriggio I haven't yet looked at the code, but from what you just posted, I wonder if a bool member set to true in ThumbBrowserEntryBase::setPosition() and moving the workload to the idle loop would suffice...

But maybe there are side effects that matter for the setPosition() call, and calling it only once isn't enough.

[agriggio]

@Floessie I also didn't dig deep in the code -- what you propose might be enough, but I don't know.

The current version of the code maintains no state to decide whether only a subset of the thumbnails need to be repositioned. Rather, it performs the whole computation every time. This makes the code easier (fewer state elements, fewer things that can go out of sync) but with big folders it can slow things down. I assume @heckflosse has measured this and seen that the performance impact is non-negligible. If someone wants to introduce some intermediate state, he/she should analyze the situations in which the state needs to be updated. That's part of the "not a one-liner" above :-)

[heckflosse]

@agriggio @Floessie
Thanks for helping with this. The setposition() call was only an example to show the O(n²).
FileBrowser::addEntry_ is a good hint. I will take a look.

[Floessie]

@heckflosse FileBrowser::addEntry_() rings a bell: Didn't we do something about it in the past?

Edit: The call is already IdleRegistered in FileBrowser::addEntry(). Maybe that was it... Doesn't seem to help, though.

[heckflosse]

@agriggio It's a bit hard to measure. But when you open a folder with for example 3000 files it takes very long with rt looking like frozen in between.

[Floessie]

@heckflosse Very slow compile machine here, so I could not yet test, but here is a quick patch:

diff --git a/rtgui/filebrowser.cc b/rtgui/filebrowser.cc
index c026b63a..c73c6b18 100644
--- a/rtgui/filebrowser.cc
+++ b/rtgui/filebrowser.cc
@@ -126,6 +126,7 @@ void findOriginalEntries (const std::vector<ThumbBrowserEntryBase*>& entries)
 }

 FileBrowser::FileBrowser () :
+    needs_redraw(false),
     menuLabel(nullptr),
     selectDF(nullptr),
     thisIsDF(nullptr),
@@ -610,7 +611,19 @@ void FileBrowser::addEntry_ (FileBrowserEntry* entry)

         initEntry (entry);
     }
-    redraw ();
+
+    needs_redraw = true;
+
+    const auto func = [](gpointer data) -> gboolean {
+        FileBrowser* const self = static_cast<FileBrowser*>(data);
+        if (self->needs_redraw.exchange(false)) {
+            self->redraw();
+        }
+
+        return FALSE;
+    };
+
+    idle_register.add(func, this);

     // newly added item might have been already trashed in a previous session
     trash_changed().emit();
diff --git a/rtgui/filebrowser.h b/rtgui/filebrowser.h
index 4efdb721..e5052159 100644
--- a/rtgui/filebrowser.h
+++ b/rtgui/filebrowser.h
@@ -19,8 +19,11 @@
 #ifndef _FILEBROWSER_
 #define _FILEBROWSER_

-#include <gtkmm.h>
+#include <atomic>
 #include <map>
+
+#include <gtkmm.h>
+
 #include "thumbbrowserbase.h"
 #include "exiffiltersettings.h"
 #include "filebrowserentry.h"
@@ -66,6 +69,7 @@ private:

     IdleRegister idle_register;
     unsigned int session_id_;
+    std::atomic<bool> needs_redraw;

 protected:
     Gtk::MenuItem* rank[6];

[agriggio]

@Floessie in the meantime I was testing essentially the same (after rereading more carefully what you wrote :-)
Unfortunately, I get a segfault as soon as the RT window is shown :-/ no idea though about why...

[Floessie]

@agriggio Sorry for the overlapping.

Hm, I also got a SEGV the first time I started, but now I don't get one, otherwise I could debug...

[agriggio]

@Floessie no problem! It was your suggestion in fact... and I can't dig deeper anyway at the moment

[Floessie]

Here's a BT:

#0  0x00007ffff32e5f6b in Cairo::Context::set_source(Cairo::RefPtr<Cairo::Surface> const&, double, double) () from /usr/lib/x86_64-linux-gnu/libcairomm-1.0.so.1
#1  0x0000555555e746d2 in ThumbBrowserEntryBase::draw (this=0x7fffb407a110, cc=...) at /home/floessie/src/rawtherapee/rtgui/thumbbrowserentrybase.cc:481
#2  0x0000555555c33861 in FileBrowserEntry::draw (this=0x7fffb407a110, cc=...) at /home/floessie/src/rawtherapee/rtgui/filebrowserentry.cc:716
#3  0x0000555555e6ea13 in ThumbBrowserBase::Internal::on_draw (this=0x555559234470, cr=...) at /home/floessie/src/rawtherapee/rtgui/thumbbrowserbase.cc:862
#4  0x00007ffff3f97b71 in Gtk::Widget_Class::draw_callback(_GtkWidget*, _cairo*) () from /usr/lib/x86_64-linux-gnu/libgtkmm-3.0.so.1

[heckflosse]

I measured the time to open a folder with increasing amount of files (all thumbs are in file system cache)

512 files => 10 s
1024 files => 23 s
2048 files => 67 s

[heckflosse]

I also did essentially the same meanwhile (though a bit different as I just removed the redraw() in addentry_ and inserted fileBrowser->redraw(); in FileCatalog::previewsFinished.
That also segfaults. But when running rt in gdb it works...

[heckflosse]

Though completely unrelated to O(n²) the following patch reduces the time to open a folder by about 3.5 ms per file in folder, which means a folder of 2048 files opens ~7 seconds faster now at my machine.

diff --git a/rtgui/filecatalog.cc b/rtgui/filecatalog.cc
index 0d10ba12..d3f2965b 100644
--- a/rtgui/filecatalog.cc
+++ b/rtgui/filecatalog.cc
@@ -36,7 +36,8 @@
 #include "thumbimageupdater.h"
 #include "batchqueue.h"
 #include "placesbrowser.h"
-
+#define BENCHMARK
+#include "../rtengine/StopWatch.h"
 using namespace std;

 #define CHECKTIME 2000
@@ -1792,38 +1793,36 @@ void FileCatalog::on_dir_changed (const Glib::RefPtr<Gio::File>& file, const Gli

 void FileCatalog::checkAndAddFile (Glib::RefPtr<Gio::File> file)
 {
+    BENCHFUNMICRO
     if (!file) {
         return;
     }

-    if (!file->query_exists()) {
-        return;
-    }
-
     try {

-        auto info = file->query_info ();
+        const auto info = file->query_info("standard::*");

-        if (!info || info->get_file_type () == Gio::FILE_TYPE_DIRECTORY) {
+        if (!info || info->get_file_type() == Gio::FILE_TYPE_DIRECTORY) {
             return;
         }

-        if (!options.fbShowHidden && info->is_hidden ()) {
+        if (!options.fbShowHidden && info->is_hidden()) {
             return;
         }

         Glib::ustring ext;

-        const auto lastdot = info->get_name ().find_last_of ('.');
+        const auto lastdot = info->get_name().find_last_of('.');
+
         if (lastdot != Glib::ustring::npos) {
-            ext = info->get_name ().substr (lastdot + 1);
+            ext = info->get_name().substr(lastdot + 1);
         }

-        if (!options.is_extention_enabled (ext)) {
+        if (!options.is_extention_enabled(ext)) {
             return;
         }

-        previewLoader->add (selectedDirectoryId, file->get_parse_name (), this);
+        previewLoader->add(selectedDirectoryId, file->get_parse_name(), this);
         previewsToLoad++;

     } catch(Gio::Error&) {}

[heckflosse]

Edit: the key to the speedup was to use

file->query_info("standard::*");

instead of

file->query_info ();

and to get rid of

file->query_exists()

because that's a convenience function which calls

file->query_info ();

for reference: query_exists

and that should be handled well in the try-catch

[Floessie]

@heckflosse And I thought, it was the const in const auto info = file->query_info("standard::*");. 😁

[heckflosse]

@Floessie

Maybe we can do the same here and here?

But I've not enough raw files on my Linux box to measure it reliably.

[agriggio]

@heckflosse just create say 10k hardlinks to the same raw, wouldn't that work?

[heckflosse]

@agriggio @Floessie

Here's a patch:

diff --git a/rtgui/cachemanager.cc b/rtgui/cachemanager.cc
index 3f5ea958..811042e2 100644
--- a/rtgui/cachemanager.cc
+++ b/rtgui/cachemanager.cc
@@ -32,7 +32,8 @@
 #include "options.h"
 #include "procparamchangers.h"
 #include "thumbnail.h"
-
+#define BENCHMARK
+#include "../rtengine/StopWatch.h"
 namespace
 {

@@ -296,39 +297,38 @@ void CacheManager::deleteFiles (const Glib::ustring& fname, const std::string& m

 std::string CacheManager::getMD5 (const Glib::ustring& fname)
 {
-
-    auto file = Gio::File::create_for_path (fname);
-
-    if (file && file->query_exists ())   {
+BENCHFUNMICRO

 #ifdef WIN32

-        std::unique_ptr<wchar_t, GFreeFunc> wfname (reinterpret_cast<wchar_t*>(g_utf8_to_utf16 (fname.c_str (), -1, NULL, NULL, NULL)), g_free);
+    std::unique_ptr<wchar_t, GFreeFunc> wfname(reinterpret_cast<wchar_t*>(g_utf8_to_utf16 (fname.c_str (), -1, NULL, NULL, NULL)), g_free);

-        WIN32_FILE_ATTRIBUTE_DATA fileAttr;
-        if (GetFileAttributesExW (wfname.get (), GetFileExInfoStandard, &fileAttr)) {
-            // We use name, size and creation time to identify a file.
-            const auto identifier = Glib::ustring::compose ("%1-%2-%3-%4", fileAttr.nFileSizeLow, fileAttr.ftCreationTime.dwHighDateTime, fileAttr.ftCreationTime.dwLowDateTime, fname);
-            return Glib::Checksum::compute_checksum (Glib::Checksum::CHECKSUM_MD5, identifier);
-        }
+    WIN32_FILE_ATTRIBUTE_DATA fileAttr;
+    if (GetFileAttributesExW(wfname.get(), GetFileExInfoStandard, &fileAttr)) {
+        // We use name, size and creation time to identify a file.
+        const auto identifier = Glib::ustring::compose("%1-%2-%3-%4", fileAttr.nFileSizeLow, fileAttr.ftCreationTime.dwHighDateTime, fileAttr.ftCreationTime.dwLowDateTime, fname);
+        return Glib::Checksum::compute_checksum(Glib::Checksum::CHECKSUM_MD5, identifier);
+    }

 #else

+    const auto file = Gio::File::create_for_path(fname);
+    if (file) {
+
         try
         {

-            if (auto info = file->query_info ()) {
+            if (const auto info = file->query_info("standard::*")) {
                 // We only use name and size to identify a file.
-                const auto identifier = Glib::ustring::compose ("%1%2", fname, info->get_size ());
-                return Glib::Checksum::compute_checksum (Glib::Checksum::CHECKSUM_MD5, identifier);
+                const auto identifier = Glib::ustring::compose("%1%2", fname, info->get_size());
+                return Glib::Checksum::compute_checksum(Glib::Checksum::CHECKSUM_MD5, identifier);
             }

         } catch(Gio::Error&) {}
+    }

 #endif

-    }
-
     return {};
 }

I tested with a few files on Linux. It's a bit faster than before but nothing to write home about because on Linux it already was much faster than on Windows.
On Windows it's a lot faster than before. In my test with 2048 files it's about 4 seconds faster.

[Floessie]

@heckflosse Great, Ingo! 👍

-            if (auto info = file->query_info ()) {
+            if (const auto info = file->query_info("standard::*")) {

Maybe move that definition to a line above the if (like it is for file). I know, this is a valid pattern, but I think we use the "single definition" pattern throughout the code.

[heckflosse]

I pushed the two patches from above with 11e3a72

[heckflosse]

I found the culprit. The following quick&dirty patch reduces the time to open a folder with 2048 copies of amsterdam.pef from 54 seconds to 15 seconds.

diff --git a/rtgui/filebrowser.cc b/rtgui/filebrowser.cc
index c026b63a..05ee7acf 100644
--- a/rtgui/filebrowser.cc
+++ b/rtgui/filebrowser.cc
@@ -600,13 +600,20 @@ void FileBrowser::addEntry_ (FileBrowserEntry* entry)
     {
         MYWRITERLOCK(l, entryRW);

-        std::vector<ThumbBrowserEntryBase*>::iterator i = fd.begin();
-
-        while (i != fd.end() && *entry < * ((FileBrowserEntry*)*i)) {
-            ++i;
+        size_t first = 0;
+        size_t last = fd.size();
+        size_t middle = last / 2;
+        while(middle != first && middle != last) {
+            if(*(ThumbBrowserEntryBase*)entry < *fd[middle]) {
+                first = middle;
+                middle = (first + last) / 2;
+            } else if(*fd[middle] < *(ThumbBrowserEntryBase*)entry) {
+                last = middle;
+                middle = (first + last) / 2;
+            }
         }
-
-        fd.insert (i, entry);
+        std::vector<ThumbBrowserEntryBase*>::iterator i = fd.begin();
+        fd.insert (i + middle, entry);

         initEntry (entry);
     }

@Floessie @agriggio please review

[agriggio]

@heckflosse why not simply use std::lower_bound?

anyway, great that it gives such a nice speedup, but I don't see why it should reduce the number of calls in redraw...

[heckflosse]

@agriggio Wouldn't std::lower_bound sort by the address?
Of course the patch does not reduce the number of redraw calls, but it reduces one O(n²) to O(n*log(n))

[Floessie]

@heckflosse Good catch!

I agree with Alberto on std::lower_bound() (is has a version with a comparator, today a lamba will suffice for it). But wouldn't it be even better, to have a std::set<> instead of a hand-sorted std::vector<>?

[heckflosse]

@Floessie
I also thought about using a std::set instead of std::vector but that would require a lot of changes...
Could you please explain me how to use std::lower_bound in this context (vector of pointers)?

[heckflosse]

@Floessie std::lower_bound : I think I got it

[Floessie]

@heckflosse A std::vector<> doesn't really seem to be the right thing. I was digging in the code a bit, and there are many places, where items are inserted and erased from fd. A std::vector<> is the worst container to act on like this, as all elements behind that point must be copied.

Untested use of std::lower_bound():

fd.insert(
    std::lower_bound(
        fd.begin(),
        fd.end(),
        [](FileBrowserEntry* a, FileBrowserEntry* b)
        {
            return *a < *b;
        }
    ),
    entry
);

HTH,
Flössie

[Floessie]

BatchQueue shuffles the items in a different way, so a sorted container is too much. Thus I'd favor std::list<>, which has such nice things like splice(), merge(), and sort() all built in.

[heckflosse]

@Floessie Thanks a lot for the lower_bound
Here's a working patch which uses it:

diff --git a/rtgui/filebrowser.cc b/rtgui/filebrowser.cc
index c026b63a..d3fc71d6 100644
--- a/rtgui/filebrowser.cc
+++ b/rtgui/filebrowser.cc
@@ -600,13 +600,18 @@ void FileBrowser::addEntry_ (FileBrowserEntry* entry)
     {
         MYWRITERLOCK(l, entryRW);

-        std::vector<ThumbBrowserEntryBase*>::iterator i = fd.begin();
-
-        while (i != fd.end() && *entry < * ((FileBrowserEntry*)*i)) {
-            ++i;
-        }
-
-        fd.insert (i, entry);
+        fd.insert(
+            std::lower_bound(
+                fd.begin(),
+                fd.end(),
+                (ThumbBrowserEntryBase*)entry,
+                [](ThumbBrowserEntryBase* a, ThumbBrowserEntryBase* b)
+                {
+                    return *b < *a;
+                }
+            ),
+            (ThumbBrowserEntryBase*)entry
+        );

         initEntry (entry);
     }

For using std::list or std::set instead of std::vector we should open new issues. What do you think?

[Floessie]

@heckflosse

For using std::list or std::set instead of std::vector we should open new issues. What do you think?

I'd say yes, but must admit, that I can spend some time on it forseeably only earliest in mid-October.

[heckflosse]

@Floessie No need to hurry. I had a deeper look at the code and I absolutely agree that we should change this, but I also measured a bit: Changing fd from std::vector to std::set would decrease the time to open a folder with 2048 copies of amsterdam.pef only by max. 200 ms.

[heckflosse]

The following small patch reduces the time to open a folder of 2048.... by another second

diff --git a/rtgui/filebrowser.cc b/rtgui/filebrowser.cc
index d3fc71d6..c3d64eb7 100644
--- a/rtgui/filebrowser.cc
+++ b/rtgui/filebrowser.cc
@@ -616,9 +616,6 @@ void FileBrowser::addEntry_ (FileBrowserEntry* entry)
         initEntry (entry);
     }
     redraw ();
-
-    // newly added item might have been already trashed in a previous session
-    trash_changed().emit();
 }

 FileBrowserEntry* FileBrowser::delEntry (const Glib::ustring& fname)
diff --git a/rtgui/filecatalog.cc b/rtgui/filecatalog.cc
index fba3f432..eafe32fc 100644
--- a/rtgui/filecatalog.cc
+++ b/rtgui/filecatalog.cc
@@ -825,6 +825,9 @@ void FileCatalog::previewsFinishedUI ()
         refImageForOpen_fname = "";
         actionNextPrevious = NAV_NONE;
     }
+
+    // newly added items might have been already trashed in a previous session
+    trashChanged();
 }

 void FileCatalog::previewsFinished (int dir_id)

[heckflosse]

Any objections to close this issue for now?

[heckflosse]

I just tested with a folder of 4096 copies of amsterdam.pef.
Took 30 seconds. So now we have almost linear processing time which makes this issue obsolete => closing!

[Floessie]

@heckflosse Here's another little cleanup for the lambda. Interestingly, ThumbBrowserEntryBase::operator <() was only used in the FileBrowser, so I corrected the comparison in both places:

diff --git a/rtgui/filebrowser.cc b/rtgui/filebrowser.cc
index c3d64eb7..10d4809e 100644
--- a/rtgui/filebrowser.cc
+++ b/rtgui/filebrowser.cc
@@ -604,13 +604,13 @@ void FileBrowser::addEntry_ (FileBrowserEntry* entry)
             std::lower_bound(
                 fd.begin(),
                 fd.end(),
-                (ThumbBrowserEntryBase*)entry,
-                [](ThumbBrowserEntryBase* a, ThumbBrowserEntryBase* b)
+                entry,
+                [](const ThumbBrowserEntryBase* a, const ThumbBrowserEntryBase* b)
                 {
-                    return *b < *a;
+                    return *a < *b;
                 }
             ),
-            (ThumbBrowserEntryBase*)entry
+            entry
         );

         initEntry (entry);
diff --git a/rtgui/thumbbrowserentrybase.h b/rtgui/thumbbrowserentrybase.h
index 561d652d..55d7179a 100644
--- a/rtgui/thumbbrowserentrybase.h
+++ b/rtgui/thumbbrowserentrybase.h
@@ -167,9 +167,9 @@ public:
     void setPosition        (int x, int y, int w, int h);
     void setOffset (int x, int y);

-    bool operator< (ThumbBrowserEntryBase& other)
+    bool operator <(const ThumbBrowserEntryBase& other) const
     {
-        return shortname.casefold() > other.shortname.casefold();
+        return shortname.casefold() < other.shortname.casefold();
     }

     ThumbBrowserEntryBase* getOriginal () const;

Best,
Flössie

[heckflosse]

@Floessie
Thanks for the cleanup. I just pushed it.

[Floessie]

@heckflosse

No need to hurry. I had a deeper look at the code and I absolutely agree that we should change this, but I also measured a bit: Changing fd from std::vector to std::set would decrease the time to open a folder with 2048 copies of amsterdam.pef only by max. 200 ms.

I think I can spare some time this weekend turning the std::vector<> into a std::list<>. I'll push on a new branch, so we can monitor the fallout.

[agriggio]

note though that lower_bound on a list will be much worse than a vector, so I'm not sure you will gain much (if anything). relocating a pointer vector of a few thousand elements in this context doesn't feel like a big deal to me (but I haven't measured, so I may be wrong!)

[Floessie]

@agriggio As so often, you are right. 👍

[heckflosse]

@Floessie @agriggio

Maybe also related

[Floessie]

@heckflosse Interesting, indeed. Maybe we should pimp ThumbBrowserEntryBase::operator <() accordingly. I'll have a look at it tomorrow.

[Floessie]

@heckflosse Ingo, here's my little patch. Maybe you still have your testbed in place?

diff --git a/rtgui/thumbbrowserentrybase.cc b/rtgui/thumbbrowserentrybase.cc
index cf0ce1bb..ff7e58d4 100644
--- a/rtgui/thumbbrowserentrybase.cc
+++ b/rtgui/thumbbrowserentrybase.cc
@@ -17,33 +17,73 @@
  *  along with RawTherapee.  If not, see <http://www.gnu.org/licenses/>.
  */
 #include "thumbbrowserentrybase.h"
-#include "thumbbrowserbase.h"
+
 #include "options.h"
+#include "thumbbrowserbase.h"
+
 #include "../rtengine/mytime.h"

-ThumbBrowserEntryBase::ThumbBrowserEntryBase (const Glib::ustring& fname)
-    : fnlabw(0), fnlabh(0), dtlabw(0), dtlabh(0), exlabw(0), exlabh(0), prew(0), preh(0),
-      prex(0), prey(0), upperMargin(6), borderWidth(1), textGap(6), sideMargin(8), lowerMargin(8),
-      preview(nullptr), dispname(Glib::path_get_basename (fname)), buttonSet(nullptr), width(0), height(0),
-      exp_width(0), exp_height(0), startx(0), starty(0), ofsX(0), ofsY(0), redrawRequests(0),
-      parent(nullptr), original(nullptr), bbSelected(false), bbFramed(false), bbPreview(nullptr), cursor_type(CSUndefined),
-      thumbnail(nullptr), filename(fname), shortname(dispname), exifline(""), datetimeline(""),
-      selected(false), drawable(false), filtered(false), framed(false), processing(false), italicstyle(false),
-      edited(false), recentlysaved(false), updatepriority(false), withFilename(WFNAME_NONE) {}
+ThumbBrowserEntryBase::ThumbBrowserEntryBase (const Glib::ustring& fname) :
+    fnlabw(0),
+    fnlabh(0),
+    dtlabw(0),
+    dtlabh(0),
+    exlabw(0),
+    exlabh(0),
+    prew(0),
+    preh(0),
+    prex(0),
+    prey(0),
+    upperMargin(6),
+    borderWidth(1),
+    textGap(6),
+    sideMargin(8),
+    lowerMargin(8),
+    preview(nullptr),
+    dispname(Glib::path_get_basename(fname)),
+    buttonSet(nullptr),
+    width(0),
+    height(0),
+    exp_width(0),
+    exp_height(0),
+    startx(0),
+    starty(0),
+    ofsX(0),
+    ofsY(0),
+    redrawRequests(0),
+    parent(nullptr),
+    original(nullptr),
+    bbSelected(false),
+    bbFramed(false),
+    bbPreview(nullptr),
+    cursor_type(CSUndefined),
+    collate_name(dispname.casefold().collate_key()),
+    thumbnail(nullptr),
+    filename(fname),
+    shortname(dispname),
+    exifline(""),
+    datetimeline(""),
+    selected(false),
+    drawable(false),
+    filtered(false),
+    framed(false),
+    processing(false),
+    italicstyle(false),
+    edited(false),
+    recentlysaved(false),
+    updatepriority(false),
+    withFilename(WFNAME_NONE)
+{
+}

 ThumbBrowserEntryBase::~ThumbBrowserEntryBase ()
 {
-
-    if (preview) {
-        delete [] preview;
-    }
-
+    delete[] preview;
     delete buttonSet;
 }

 void ThumbBrowserEntryBase::addButtonSet (LWButtonSet* bs)
 {
-
     buttonSet = bs;
 }

diff --git a/rtgui/thumbbrowserentrybase.h b/rtgui/thumbbrowserentrybase.h
index 55d7179a..f4779faa 100644
--- a/rtgui/thumbbrowserentrybase.h
+++ b/rtgui/thumbbrowserentrybase.h
@@ -88,6 +88,9 @@ protected:
     // called during updateBackBuffer for custom overlays
     virtual void customBackBufferUpdate (Cairo::RefPtr<Cairo::Context> c) {}

+private:
+    const std::string collate_name;
+
 public:

     Thumbnail* thumbnail;
@@ -169,7 +172,7 @@ public:

     bool operator <(const ThumbBrowserEntryBase& other) const
     {
-        return shortname.casefold() < other.shortname.casefold();
+        return collate_name < other.collate_name;
     }

     ThumbBrowserEntryBase* getOriginal () const;

Best,
Flössie

[heckflosse]

@Floessie Thanks! Unfortunately I reduced my testbed from 2048 to 867 files.
I measured only the sorting part.

First using the original O(n²) code with and without collate_key:

without collate_key : ~ 7200 ms
with collate_key : ~ 11 ms

Then the std::lower_bound version:

without collate_key : ~ 80 ms
with collate_key : < 1 ms

[heckflosse]

@Floessie Will you commit or shall I do?

[Floessie]

@heckflosse I'll commit directly to dev tonight. Impressive results, BTW. 👍

[heckflosse]

@Floessie I did not expect this difference. Comparisons of Glib::ustring seem to be REALLY expensive.
I made a last test comparing loading time of a folder with 867 files using rt 5.1 and current dev + your patch

5.1         : 18 seconds
dev + patch :  6 seconds

[heckflosse]

@Floessie

I compared RT 5.1 and current dev with loading a folder of 6936 files (all thumbs cached)

5.1 needed 621 seconds
dev needed 53 seconds

\o/