[Development] Faster locale aware string list sorting

Zeno Endemann zeno.endemann at googlemail.com
Sat Mar 9 20:57:09 CET 2013

I've been playing around with different sorting methods and have noticed
that the naive way to sort a QStringList with localeAwareCompare is
atrociously slow on my system (64bit Linux, German locale - up to a
thousand times slower than using the lessThan-operator). While a
locale aware sorting is obviously inherently slower than basically a
memory compare I believe we can do a lot better.

As many desktop application need to sort lists of strings in a
locale aware fashion, I think Qt should provide something to do this
efficiently. In fact, there are already two places in Qt that would
benefit from faster sorting (QDir and QSortFilterProxyModel are
currently using the slow naive method).

The most simple approach to speed this up is to generate the ICU sort
keys for all the strings and sort the list with them. But this method
can be pretty inefficient for longer strings and uses a lot of RAM. A
more adaptive method would be to generate (and cache) on each string
comparison only the sort key prefix necessary to distinguish the two
strings. Or we could go all out - I have an idea for a parallelizable
bucket/merge sort combination ;)

So my questions: Is there interest in (or even plans for) something like
this? Also, I can hardly believe I'm the first to do something about
this. Does anyone know of a library that deals with the problem already?

Anyway, if there is interest, I can upload my small benchmark to the Qt
bug tracker.

Best regards,
Zeno Endemann

More information about the Development mailing list