Re: Goals of threaded sort

[Jim Meyering]

Chen Guo wrote:
> Hi all,

Hi Chen,

Thanks for following up.
It's been frustrating all around.

>     I'm looking for some group input/guidance. Is there a kind of
> performance goal we want for a threaded sort implementation? Something I
> can work towards?

Perhaps over-optimistically,
I've been hoping for results that indicate higher efficiency.

>     I submitted a patch earlier, but obviously it had its problems:
> copious amounts of copying, worst case n^2, high variance in results,
> and in the end it was only slightly faster than the previous threaded
> sort patch, and only at 8 threads and up. I've optimized the code further,
> but obviously the copying, O(n^2), and variance issues still exist.
...

Have you considered writing a program like the one suggested here?

  http://thread.gmane.org/gmane.comp.gnu.coreutils.bugs/15789/focus=15790

Given a seekable input file, INPUT, you might do this on a quad-core system:

    sort -m \
        <(sort <(dice -k1,4 INPUT)) \
        <(sort <(dice -k2,4 INPUT)) \
        <(sort <(dice -k3,4 INPUT)) \
        <(sort <(dice -k4,4 INPUT)) \
      > out

Timing that should give us a useful point of reference with
which to compare the performance of your multi-threaded sort.

Maybe the inefficiency we're seeing is simply unavoidable, given the
current algorithms, and we should view the resulting speed-up as a lot
better than no speed-up.