Ideas for improving sorting. Goal: under 1 second for 200.000 files.

[Frank Reininghaus]

Hi Mark,

2013/1/3 Mark:
[...]
>>> Don't bother thinking about this issue anymore. My brother (a far
>>> better programmer then me) managed to make a extremely fast natural
>>> sorting algorithm. 1 second for 1 million items. If you include init
>>> stuff then it's 1.8 seconds. For 200.000 items it's even far less!
>>> That's just on a cheap fusion pc.
>>>
>>> I will blog about that sometime this week or next week. Depends a bit
>>> on my experiments with a KDirModel rewrite :)
>>
>> Sounds interesting. I'm looking forward to seeing the code.
>>
>> I've recently done some experiments with picking up some ideas from
>> Python's Timsort, which I might also blog about soon. That greatly
>> reduces the number of comparisons if there is some structure in the
>> data, which happens, e.g., when resorting the items after reversing
>> the sort order. In this and some other "best cases", only N
>> comparisons are needed for N items. But for random data, we're still
>> at O(N*log(N)), of course. In that sense, it's orthogonal to your
>> approach of speeding up the comparison function and might also be
>> interesting for other apps because real world data are often not in
>> random order.
>>
>> Best regards,
>> Frank
>
> Hi Frank,
>
> I will ask my brother if i'm allowed to share his code or if he
> managed to get in some more cycle optimizations ;)

Note that taking great efforts to save a few more CPU cycles should
not be the main goal. What's more important is that the code is easy
to read and maintainable.

And most importantly, it should not cause any regressions, i.e., it
must be locale-aware, it must pass the natural compare unit tests in
kdelibs, and ideally, one would test it on a large number of file
names (like all files on your hard drive) and verify that it sorts
them like KStringHandler::naturalCompare does. If you're planning to
write on your blog that there is a possibility that your and your
brother's code might be included in KDE soon, it might make sense to
ensure that these things work OK.

> Anyway, the sorting that i have now is internally (also) converted to
> aligned integers so i think it's fairly safe to look at this
> comparison: http://gamasutra.com/view/news/172542/Indepth_Smoothsort_vs_Timsort.php#.UOWJc2_K6uI
> Timsort isn't bad, but quicksort seems to win there.
>
> Timsort only seems to be better if the data is mostly sorted already.
> Also a note, we tried this using plain C++ and std::sort. While it's
> speed is truly massive, it is actually twice as fast on a dual core
> machine when the gcc parallel mode is enabled:
> http://gcc.gnu.org/onlinedocs/libstdc++/manual/parallel_mode.html It's
> experimental, but i'm seriously thinking about using that for my
> sorting. It just gives you parallel sorting without doing anything
> special. All you need is compile against openmp and include the
> parallel/algorithm header instead of the usual algorithm include.
> These things might be something you could consider for Dolphin?

What exactly is the benefit compared to a Qt-based parallel sorting
implementation? I mean, I use OpenMP myself for my scientific work,
but KDE does currently not have any OpenMP dependency AFAIK. Moreover,
relying on an experimental feature of GCC and the standard library
shipped with it might not exactly improve portability.

Best regards,
Frank