Urs Janßen
2012-02-18 01:45:10 UTC
On Sat, Feb 18, 2012 at 03:13:22AM +0400, Valeriy E. Ushakov wrote:
fullquote as I Cc tin-dev
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),
= 39.065967 secs.
= 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
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 Iworst 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.
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),
[01:14:48.858233] LISTGROUP gmane.comp.lang.lua.general
[01:15:27.924200] QUIT
[01:15:27.924200] QUIT
[01:16:30.504984] LISTGROUP gmane.comp.lang.lua.general
[01:17:05.069478] QUIT
[01:17:05.069478] QUIT
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
"Only whimps use tape backup: _real_ men just upload their important stuff
on ftp, and let the rest of the world mirror it ;)" - Linus