[prev in list] [next in list] [prev in thread] [next in thread] 

List:       kde-bugs-dist
Subject:    [Bug 307585] Sorting is too cpu intensive for big folders
From:       Mark <markg85 () gmail ! com>
Date:       2012-10-06 14:45:39
Message-ID: bug-307585-17878-kf3vMRGE08 () http ! bugs ! kde ! org/
[Download RAW message or body]

https://bugs.kde.org/show_bug.cgi?id=307585

--- Comment #27 from Mark <markg85@gmail.com> ---
(In reply to comment #26)
> I don't know how "ls" does it, but the only obvious way to speed up the
> comparison that I can see at the moment would be to cache some intermediate
> results which KStringHandler::naturalCompare() needs. All these isDigit()
> calls are needed to split the string into a sequence of number and
> non-number chunks. One could do this splitting just once and use this to do
> a faster comparison. The slow part would then only be done N times, and the
> O(N*log(N)) comparisions would be fast.
> 
> I want to make clear though that I do not believe that this approach should
> be implemented. I don't think that the time saving for this corner case
> would be worth the greatly increased code complexity and maintenance effort.
> As soon as we implement this, someone will probably try to open a folder
> with a million files, and the next bottleneck will show up.

Well, i agree with you if one tries to open folders with millions of files.
That's just absurd and the user doing that should not expect it to even work.
Besides that you "might" even get into trouble with filesystem support. Ext 3
that is, ext4 can cope with it.

But optimizing it so that 100.000 files (or 50.000 since you already notice it
there) show up "fast" is something that should imho be "bearable" in dolphin.
Folders of that massive amount of files are obviously unexpected and rare to
encounter but might be possible. For instance a photographer that dumps his
entire photo collection from some long holiday in one folder ready for that
person to sort things out. Or even web development where all generated
thumbnails get dumped in one folder. Yes, those are corner cases but not that
impossible.

As for optimizing the natural sorting algorithm. I already tried one thing.
Putting all characters in a hash map like so:

QHash<QChar, bool> digitCache;

This would know for each character if it's a digit or not. That "solution" is
far from faster. In total it takes a LOT more time to calculate the hash and
find the right value then to just do isDigit.. Even though QHash is O(1),
calculating the actual hash value takes time. More time then idDigit needs to
run to do it's thing. It would have been very nice if this where working fast
since the map would be quite small since there would be no double values in it.

I don't know if pre splitting the string somewhere outside of naturalCompare
and feeding the pre parsed results to naturalCompare is going to be faster.
There will be addotional loopup time whichever container you choose, even on
the O(1) ones. Though if something like this is done the natural sorting would
obviously not end up in KStringHandler::naturalCompare anymore since it becomes
dolphin specific. It would have to be in dolphin.

-- 
You are receiving this mail because:
You are watching all bug changes.
[prev in list] [next in list] [prev in thread] [next in thread]