Re: qsort can get very slow

On Sat, Feb 18, 2012 at 03:13:22AM +0400, Valeriy E. Ushakov wrote:

fullquote as I Cc tin-dev

> tin uses qsort() for sorting.  While qsort is generally quick, its
> worst case performance is known to be bad.
> 
> Opening gmane.comp.lang.lua.general on news.gmane.org takes ages
> (>1min spent in sorting article on my oldish 400MHz powerpc) because
> mailing list archives were, apparently, fed to the newsgroup out of
> order, so mail from 90s is somwhere in the middle, after mail from
> early 2000s.  This triggers qsort worst-case slowdown.
> 
> As a brute force hack I changed my tin to use heapsort, that
> guarantees O(n*log(n)).  That _dramatically_ improved user experience
> for me.  gmane.comp.lang.lua.general opens in sane time now and I
> don't see noticeable slowdown elsewhere.
> 
> qsort() is provided by c99, so I can see while using it is convenient.
> heapsort() is available in NetBSD libc, so this s/qsort/heapsort/ hack
> was easy for me.  I'm not sure what would be an acceptable solution
> for general use.

I don't see a big win over here (Linux on a Pentium 4) in what I
assume is normal usage (but I also see that filtering/sorting _is_
faster). quick and dirty test case:

enter a group with 88510 articles, group is read via nntp from remote
server (100mbit uplink), my normal filter file (around 50 complex rules)
is used, quit tin once all the filtering is done (press 'Q' during
filtering),

tin with qsort from libc:
>>> [01:14:48.858233] LISTGROUP gmane.comp.lang.lua.general
>>> [01:15:27.924200] QUIT
= 39.065967 secs.

tin with heapsort.c from freebsd:
>>> [01:16:30.504984] LISTGROUP gmane.comp.lang.lua.general
>>> [01:17:05.069478] QUIT
= 35.564494 secs.

the heapsort version is about 3.5 secs faster most of the time is
spent for fetching data via nntp.

An acceptable solution for general should IMHO look like (after someone
did some more testing with just timing the sorting with more data):

configure check for qsort compatible heapsort in libc like it
is done for qsort with CF_COMPTYPE (aclocal.m4).

if heapsort is found use that, otherwise stick to qsort.

or if we like to benefit from the speed improvement (if there is any
notable) of heapsort over qsort on systems where heapsort is not
present in libc provide a heapsort fallback implementation (i.e. the
one used in *BSDs libc).

urs
-- 
"Only whimps use tape backup: _real_ men just upload their important stuff
 on ftp, and let the rest of the world mirror it ;)" - Linus