Re: qsort can get very slow

On Sat, Feb 18, 2012 at 07:54:45AM +0400, Valeriy E. Ushakov wrote:
> For me ("gmane" is from newsrctable):
> 
>   $ time tin -g gmane gmane.comp.lang.lua.general 
> 
> gives
> 
>   real    1m1.770s
>   user    0m15.600s
>   sys     0m2.261s
> 
> vs.
> 
>   real    2m32.274s
>   user    1m58.352s
>   sys     0m2.303s
> 
> 
> Where the time in the original version with qsort is spent between
> 
>   Group gmane.comp.lang.lua.general ('q' to quit)...  99% (0:00 remaining)
> 
> and 
> 
>   Threading articles ...
> 
> The machine is B&W G3 running NetBSD/macppc
> 
> cpu0 at mainbus0: 750 (Revision 2.2), ID 0 (primary)
> cpu0: HID0 8090c0a4<EMCP,DOZE,DPM,ICE,DCE,SGE,BTIC,BHT>, powersave: 1
> cpu0: 400.00 MHz, no-parity 1MB WT L2 cache (PB SRAM) at 2:1 ratio

With the attached patch configure looks for system heapsort() (but is
doesn't check if it is qsort(3)-api compatible) and if not found the
heapsort() from heapsort.c is used (switching back to qsort can be done
via the tin_sort degine in tin.h).

This is not well tested and should either be switched into a runtime
option or at least a configure option (--enable-heapsort or whatever)
and the configure check for a system heapsort should also check if the
one found is sort(3)-api compatible.

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