[Top][All Lists]

[Date Prev][Date Next][Thread Prev][Thread Next][Date Index][Thread Index]

Re: Goals of threaded sort

From: Jim Meyering
Subject: Re: Goals of threaded sort
Date: Mon, 23 Nov 2009 21:28:17 +0100

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?


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.

reply via email to

[Prev in Thread] Current Thread [Next in Thread]