Re: [PATCH] sort: parallel external sort implementation

[Pádraig Brady]

On 04/03/10 06:01, Joey Degges wrote:
> Hello,
>
> Matt (cc'd, not on list) and I have developed a patch that parallelizes sort
> using pthreads. The threading approach taken here is to break up input files
> into groups based on physical device and sort each of those groups in
> parallel.
> This allows for storage and processing resources to be more fully utilized
> during the sort process.

Thanks for looking at this.
Are you aware that there is a group already working on this?
http://lists.gnu.org/archive/html/bug-coreutils/2010-02/msg00223.html

> Below is a set of experimental results and the statistics of the machine
> that
> they were run on. The test below show speed improvements from 45% - 64%.
>
> In this patch the method used to determine which device a particular file is
> on
> relies on comparisons between struct stat ->  st_dev fields. This leads to
> some
> problems in cases where files exist on different partitions of the same
> disk.

Issues like this are why it might be better to split the data
externally to sort. I've commented before that a threading
solution may only be appropriate for working on a single file:
http://lists.gnu.org/archive/html/bug-coreutils/2009-10/msg00179.html

> Preliminary tests have shown that under these situations some performance
> improvements are still seen, but they are not as dramatic as in the ideal
> case.
>
>
> system details
> CPU: Intel(R) Core(TM)2 Quad CPU    Q6600  @ 2.40GHz
> cache size: 4096 KB
> RAM: 2G
>
> disk details:
> /q/0:
>   Timing cached reads:   7556 MB in  2.00 seconds = 3781.13 MB/sec
>   Timing buffered disk reads:  320 MB in  3.00 seconds = 106.50 MB/sec
> /q/1:
>   Timing cached reads:   7772 MB in  2.00 seconds = 3888.09 MB/sec
>   Timing buffered disk reads:  224 MB in  3.03 seconds =  74.00 MB/sec
> /q/2:
>   Timing cached reads:   7444 MB in  2.00 seconds = 3724.34 MB/sec
>   Timing buffered disk reads:  222 MB in  3.01 seconds =  73.77 MB/sec
> /q/3:
>   Timing cached reads:   7512 MB in  2.00 seconds = 3758.49 MB/sec
>   Timing buffered disk reads:  240 MB in  3.02 seconds =  79.50 MB/sec
>
> before each run the cache was dropped with:
>    echo 3>  /proc/sys/vm/drop_caches
>
> store temp files in RAM:
>    mount -t tmpfs -o size=1000M /ram /ram
>    export TMPDIR=/ram
>
> multidisk sort with 4x 50M inputs
> $ time -v sort_multidisk /q/0/50M /q/1/50M /q/2/50M /q/3/50M>  /dev/null

Could you compare:

time -v sort -m <(sort /q/0/50M) \
                <(sort /q/1/50M) \
                <(sort /q/2/50M) \
                <(sort /q/3/50M) > /dev/null

cheers,
Pádraig.