[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:       Christoph Feck <christoph () maxiom ! de>
Date:       2012-10-02 1:59:59
Message-ID: bug-307585-17878-YXwynZ3qBD () http ! bugs ! kde ! org/
[Download RAW message or body]

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

Christoph Feck <christoph@maxiom.de> changed:

           What    |Removed                     |Added
----------------------------------------------------------------------------
                 CC|                            |christoph@maxiom.de

--- Comment #17 from Christoph Feck <christoph@maxiom.de> ---
N = 100.000 => N * log N = 1.660.000, which is pretty close to the 1.800.000
compares you got.

If that needs 2.000.000.000 cycles, then over 1000 cycles are spend in each
compare. Instead of optimizing the sort algorithm, you need to optimize the
string compare algorithm. If you can get each compare down to 100 cycles, then
the sorting is faster by a factor of 10.

Currently, localeAwareCompare() allocates two temporary strings, converts each
string to a collating sequence, then compares them. To make that faster, you
could pre-generate the collating sequences for each string. Optimal would be a
localeAwareCompare() that does not need any temporary buffers at all.

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