Re: memcpy-optimized version of qsort.

[Wolfgang Glas <wolfgang dot glas at ev-i dot at>]

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