Re: new module "mpsort" for faster sorting

[Jim Meyering]

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.