Re: [PATCH] sort: Add --threads option, which parallelizes internal sort.

[Ralf Wildenhues]

Hi Paul, all,

Paul Eggert writes:
> 
> This patch is by Glen Lenker, Matt Pham, Benjamin Nuernberger, Sky
> Lin, TaeSung Roh, and Paul Eggert.  It adds support for parallelism
> within an internal sort.  On our simple tests on a 2-core desktop x86,
> overall performance improved by roughly a factor of 1.6.

This is too interesting to pass up.

Example run, on an 8-way, and with cat'ed instances of the dictionary,
on tmpfs, timings best of three:

runtime [s]     threads
file size [MB]  1       2       4       8
1               0.06    0.04    0.03    0.04
2               0.13    0.09    0.07    0.07
4               0.28    0.20    0.16    0.15
8               0.61    0.43    0.34    0.32
16              1.34    0.94    0.74    0.72
32              3.00    2.06    1.63    1.57
64              6.36    4.38    3.44    3.32
128            13.49    9.30    7.13    7.24
256            28.62   19.49   15.17   15.18

Here's the abbreviated 'time' output for the last row:

26.95user 1.67system 0:28.62elapsed 100%CPU
30.78user 1.98system 0:19.49elapsed 168%CPU
37.41user 2.04system 0:15.17elapsed 260%CPU
60.68user 2.79system 0:15.18elapsed 417%CPU

It suggests to me that too much time is spent busy-waiting in pthread_join,
or that sort is computing too much (I haven't looked at the patch in detail).

Also, I'd have expected the rate going from 1 to 2 threads to get at least
a bit better with bigger file size, but it remains remarkably constant,
around 1.45 for this setup.  What am I missing?

Cheers,
Ralf