[Top][All Lists]
[Date Prev][Date Next][Thread Prev][Thread Next][Date Index][Thread Index]
Re: new module "mpsort" for faster sorting
From: |
Jim Meyering |
Subject: |
Re: new module "mpsort" for faster sorting |
Date: |
Mon, 29 Jan 2007 18:59:49 +0100 |
Paul Eggert <address@hidden> wrote:
> Bruno Haible <address@hidden> writes:
>
>> Does the major speedup come from the transition a) -> b), or from the
>> transition b) -> c) ?
>
> I didn't code those solutions separately, so I don't know.
>
> I have written a replacement qsort that has the same API as standard
> qsort, but uses mpsort internally. It creates an array of pointers to
> to the qsort elements, sorts the array, and then uses this info to
> reshuffle the qsort array a la Knuth vol. 3 (2nd ed.) exercise 5.2-10
> (with a few extra tricks). For 'ls' my intuition that mpsort was the
> better interface, due to less data overhead. If I find the time I may
> try the qsort replacement, but I think it'll be slower.
>
> I was surprised to see Jim's report that the C locale made no
> difference to him, compared to the en_US.UTF-8 locale.
I hope I didn't say that.
The only locale I tried was "C".
> This does not
> match my results, as I recall. Perhaps my UTF-8 strcoll is much
> slower than his? I'm using Debian stable, which has glibc 2.3.2.
For those tests, I was using Debian/unstable, hence glibc-2.3.6.
> I'd like to use mpsort in some other apps, too, of course. 'sort' is
> an obvious candidate, but it already uses mergesort, so mpsort won't
> be as big a win there I suspect. fts is another candidate.
I seem to recall that coreutils uses of fts do not sort entry names.