memcpy-optimized version of qsort.
Wolfgang Glas
wolfgang.glas@ev-i.at
Tue Jun 8 07:06:00 GMT 2004
Am Montag, 7. Juni 2004 21:33 schrieb Paul Eggert:
> Wolfgang Glas <wolfgang.glas@ev-i.at> writes:
> > 3) merge tmp and b+n1 into b.
>
> But the C Standard requires that qsort's comparison function be passed
> pointers into the original array, not into a temporary copy like 'tmp'.
Hi Paul,
Thanks for the clarification, it would have saved me a couple of hours, if
knew this before ;-) However I got some new insight in the design and
shortcomings of a library implementing a standard, which is a valuable
experience.
In my own programs I now use a special-purpose, hand-coded version of merge
sort, which involves an inlined version of the comparison function plus
optimized memory handling as described in my original mail and supposedly
used by many other implementations.
I'd like to state a further amendement to the the msort implementation
inside glibc, namely the the specialization for aligned, word-sized items.
The check for this is done inside each and every call of msort_with_tmp().
IMHO it would be a better practise to use functions
msort_with_tmp_general() for arbitrary items
and
msort_with_tmp_words() for aligned, word-sized items and do the decision,
which version to use inside the driver routine qsort().
The speedup would not be dramatic, but it enabled us to implement a third
specialized version for 64bit items. This could IMO dramatically speed up
this special case on modern pentium4 or 64bit architectures.
Best regards,
Wolfgang
More information about the Libc-alpha
mailing list