Subject: Re: [PATCH] sort: Add --threads option, which
parallelizes internal sort. - msg#00028

Ralf Wildenhues wrote:
> 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?

Thanks for doing that, Ralf.
Just to give everyone a heads-up,
I'm a little reluctant to apply this patch in its current
state, since it's not achieving reasonable efficiency.

I noticed that running the sole test,

env time make RUN_VERY_EXPENSIVE_TESTS=yes check -C tests \
TESTS=misc/sort-benchmark-random VERBOSE=yes

took about 36s on a pretty fast system.

changing the inner loop to this
print ((map {chr(32+rand(94))} (1..100)) , "\n");
reduced that to 25s

I changed it to write "exp" from within the script
that generated the data, but that didn't make a big difference.

Finally I realized that those 50M calls to "rand" were the
problem, and only about 4% of them were actually ever used
while sorting, since 94^4 is far more than 500k.

Adjusting accordingly brought the test's run time down to ~8s.
However, the resulting sort invocation took barely 1 second here,
and that's obviously too small to be useful. Ramping up to 5M lines,
the resulting test takes almost 2 minutes and the sort itself took 34s
on this particular quad-core system.

A more interesting test would be to ensure that when
run on a multi-core system sorting with --threads=2
is at least X% faster than sorting with --threads=1.

Also, it'd be nice to add the following:
- a test that uses --threads=N to exercise the new option-parsing code,
though if you adjust as suggested to compare --threads=N for
N=1&2, that's not needed.
- a NEWS item


>From b1332b9b429dfa9a8bba7286a78bbc7e37a2e419 Mon Sep 17 00:00:00 2001
From: Jim Meyering <meyering@xxxxxxxxxx>
Date: Thu, 2 Apr 2009 12:35:08 +0200
Subject: [PATCH] tests: make sort-benchmark-random more efficient, then use a
larger test

* tests/misc/sort-benchmark-random: cut 75% off run time, then
increase input size by a factor of 10, so that sort runs for more
than 1 second on fast hardware.
---
tests/misc/sort-benchmark-random | 42 +++++++++++++++++++-------------------
1 files changed, 21 insertions(+), 21 deletions(-)

diff --git a/tests/misc/sort-benchmark-random b/tests/misc/sort-benchmark-random
index 2bace4f..0c4d61d 100755
--- a/tests/misc/sort-benchmark-random
+++ b/tests/misc/sort-benchmark-random
@@ -34,33 +34,33 @@ export LC_ALL
fail=0

perl -e '
-my $num_lines = 500000;
+my $num_lines = 5000000;
my $length = 100;

+# Only the first few bytes of each line need to be random.
+# the remaining bytes are solely to simulate a more realistic work load.
+my $rand_bytes = 5; # per line, so that 94^5 >> $num_lines
+
+my @line;
for (my $i=0; $i < $num_lines; $i++)
{
- for (my $j=0; $j < $length; $j++)
- {
- printf "%c", 32 + rand(94);
- }
- print "\n";
-}' > in || framework_failure
-
-# We need to generate a lot of data for sort to show a noticeable
-# improvement in performance. Sorting it in PERL may take awhile.
-
-perl -e '
-open (FILE, "<in");
-my @list = <FILE>;
-print sort(@list);
-close (FILE);
-' > exp || framework_failure
-
-#start=$(date +%s)
+ my $line = join ("", map {chr(32+rand(94))} (1..$rand_bytes))
+ . ("0" x ($length - $rand_bytes)) . "\n";
+ print $line;
+ push @line, $line;
+}
+END {
+ open FH, ">", "exp" or die;
+ print FH sort @line;
+ close FH or die;
+}
+' > in || framework_failure
+
+start=$(date +%s)
time sort in > out || fail=1
-#duration=$(expr $(date +%s) - $start)
+duration=$(expr $(date +%s) - $start)

-#echo sorting the random data took $duration seconds
+echo sorting the random data took $duration seconds

compare out exp || fail=1

--
1.6.2.rc1.285.gc5f54


_______________________________________________
Bug-coreutils mailing list
Bug-coreutils@xxxxxxx
http://lists.gnu.org/mailman/listinfo/bug-coreutils