Sorting algorithms/Quicksort: Difference between revisions

Content added Content deleted
imported>Rcmlz
imported>Rcmlz
Line 8,229: Line 8,229:
<syntaxhighlight lang="raku" line>
<syntaxhighlight lang="raku" line>
#| Recursive, single-thread, single-pass, quicksort implementation
#| Recursive, single-thread, single-pass, quicksort implementation
multi quicksort(@unsorted where @unsorted.elems < 2) { @unsorted }
sub quicksort(@a) {
return @a if @a.elems < 2;
⚫
multi quicksort(@unsorted) {
my $pivot = @unsorted.pick;
my $pivot = @a.pick;
my %class{Order} is default([]) = @unsorted.classify: * cmp $pivot;
my %prt{Order} is default([]) = @a.classify: * cmp $pivot;
|samewith(%class{Less}), |%class{Same}, |samewith(%class{More})
|samewith(%prt{Less}), |%prt{Same}, |samewith(%prt{More})
}
}
</syntaxhighlight>
</syntaxhighlight>
Line 8,240: Line 8,240:


<syntaxhighlight lang="raku" line>
<syntaxhighlight lang="raku" line>
#| 7-Line, recursive, parallel, single-pass, quicksort implementation
#| Recursive, parallel, single-pass, quicksort implementation
multi seven-line-quicksort-parallel(@unsorted where @unsorted.elems < 2) { @unsorted }
sub quicksort-parallel-naive(@a) {
return @a if @a.elems < 2;
⚫
multi seven-line-quicksort-parallel(@unsorted) {
my $pivot = @unsorted.pick;
my $pivot = @a.pick;
my %partitions{Order} is default([]) = @unsorted.classify( * cmp $pivot );
my %prt{Order} is default([]) = @a.classify( * cmp $pivot );
my Promise $less = start { samewith(%partitions{Less}) }
my Promise $less = start { samewith(%prt{Less}) }
my $more = samewith(%partitions{More});
my $more = samewith(%prt{More});
await $less andthen |$less.result, |%partitions{Same}, |$more;
await $less andthen |$less.result, |%prt{Same}, |$more;
}
}
</syntaxhighlight>
</syntaxhighlight>


Let's tune the parallel execution by limiting the number of worker threads and introducing a minimum batch size.
Let's tune the parallel execution by applying a minimum batch size in order to spawn a new thread.


<syntaxhighlight lang="raku" line>
<syntaxhighlight lang="raku" line>
⚫
#| Recursive, parallel, batch tuned, single-pass, quicksort implementation
constant $BATCH-SIZE = 2**10;
⚫
sub quicksort-parallel(@a, $batch = 2**9) {
my atomicint $worker = $*KERNEL.cpu-cores;
return @a if @a.elems < 2;
⚫
#| Recursive, parallel, tuned, single-pass, quicksort implementation

proto quicksort-parallel(| --> Positional) {*}
multi quicksort-parallel(@unsorted where @unsorted.elems < 2) { @unsorted }
⚫
multi quicksort-parallel(@unsorted) {
# separate unsorted input into Order Less, Same and More compared to a random $pivot
# separate unsorted input into Order Less, Same and More compared to a random $pivot
my $pivot = @unsorted.pick;
my $pivot = @a.pick;
my %partitions{Order} is default([]) = @unsorted.classify( * cmp $pivot );
my %prt{Order} is default([]) = @a.classify( * cmp $pivot );


# atomically decide if we sort the Less partition on a new thread
# decide if we sort the Less partition on a new thread
my $less = ⚛$worker > 0 &&
my $less = %prt{Less}.elems >= $batch
%partitions{Less}.elems > $BATCH-SIZE
?? start { samewith(%prt{Less}, $batch) }
?? (
!! samewith(%prt{Less}, $batch);
$worker⚛--;
start {
LEAVE $worker⚛++;
samewith(%partitions{Less})
}
)
!! samewith(%partitions{Less});


# meanwhile use current thread for sorting the More partition
# meanwhile use current thread for sorting the More partition
my $more = samewith(%partitions{More});
my $more = samewith(%prt{More}, $batch);


# if we went parallel, we need to await the result
# if we went parallel, we need to await the result
Line 8,283: Line 8,274:


# concat all sorted partitions into a list and return
# concat all sorted partitions into a list and return
|$less, |%partitions{Same}, |$more;
|$less, |%prt{Same}, |$more;
}
}
</syntaxhighlight>
</syntaxhighlight>
Line 8,290: Line 8,281:


<syntaxhighlight lang="raku" line>
<syntaxhighlight lang="raku" line>
say "x" x 10 ~ " Testing " ~ "x" x 10;
use Test;
use Test;
⚫
my @functions-under-test = &quicksort, &quicksort-parallel-naive, &quicksort-parallel;
my @testcases =
my @testcases =
() => (),
() => (),
<a>.List => <a>.List,
<a>.List => <a>.List,
<a a> => <a a>,
<a a> => <a a>,
<a b> => <a b>,
("b", "a", 3) => (3, "a", "b"),
<b a> => <a b>,
<h b a c d f e g> => <a b c d e f g h>,
<h b a c d f e g> => <a b c d e f g h>,
(2, 3, 1, 4, 5) => (1, 2, 3, 4, 5),
<a 🎮 3 z 4 🐧> => <a 🎮 3 z 4 🐧>.sort
<a 🎮 3 z 4 🐧> => <a 🎮 3 z 4 🐧>.sort
;
;

⚫
my @implementations = &quicksort, &seven-line-quicksort-parallel, &quicksort-parallel;
plan @testcases.elems * @implementations.elems;
plan @testcases.elems * @functions-under-test.elems;
for @implementations -> &fun {
for @functions-under-test -> &fun {
say &fun.name;
say &fun.name;
is-deeply &fun(.key), .value, .key ~ " => " ~ .value for @testcases;
is-deeply &fun(.key), .value, .key ~ " => " ~ .value for @testcases;
Line 8,310: Line 8,301:
</syntaxhighlight>
</syntaxhighlight>
<pre>
<pre>
xxxxxxxxxx Testing xxxxxxxxxx
1..24
1..18
quicksort
quicksort
ok 1 - =>
ok 1 - =>
ok 2 - a => a
ok 2 - a => a
ok 3 - a a => a a
ok 3 - a a => a a
ok 4 - a b => a b
ok 4 - b a 3 => 3 a b
ok 5 - b a => a b
ok 5 - h b a c d f e g => a b c d e f g h
ok 6 - h b a c d f e g => a b c d e f g h
ok 6 - a 🎮 3 z 4 🐧 => 3 4 a z 🎮 🐧
⚫
quicksort-parallel-naive
ok 7 - 2 3 1 4 5 => 1 2 3 4 5
ok 8 - a 🎮 3 z 4 🐧 => 3 4 a z 🎮 🐧
ok 7 - =>
⚫
ok 8 - a => a
⚫
seven-line-quicksort-parallel
ok 9 - =>
ok 9 - a a => a a
ok 10 - a => a
ok 10 - b a 3 => 3 a b
ok 11 - a a => a a
ok 11 - h b a c d f e g => a b c d e f g h
ok 12 - a b => a b
ok 12 - a 🎮 3 z 4 🐧 => 3 4 a z 🎮 🐧
⚫
ok 13 - b a => a b
ok 14 - h b a c d f e g => a b c d e f g h
ok 15 - 2 3 1 4 5 => 1 2 3 4 5
ok 16 - a 🎮 3 z 4 🐧 => 3 4 a z 🎮 🐧
quicksort-parallel
quicksort-parallel
ok 17 - =>
ok 13 - =>
ok 18 - a => a
ok 14 - a => a
ok 19 - a a => a a
ok 15 - a a => a a
ok 20 - a b => a b
ok 16 - b a 3 => 3 a b
ok 21 - b a => a b
ok 17 - h b a c d f e g => a b c d e f g h
ok 22 - h b a c d f e g => a b c d e f g h
ok 18 - a 🎮 3 z 4 🐧 => 3 4 a z 🎮 🐧</pre>
ok 23 - 2 3 1 4 5 => 1 2 3 4 5
ok 24 - a 🎮 3 z 4 🐧 => 3 4 a z 🎮 🐧
⚫
</pre>


and some benchmarking
and some benchmarking


<syntaxhighlight lang="raku" line>
<syntaxhighlight lang="raku" line>
say "x" x 11 ~ " Benchmarking " ~ "x" x 11;
my $elem-length = 8;
use Benchmark;
⚫
my @large of Str = ('a'..'z').roll($elem-length).join xx 10 * $worker * $BATCH-SIZE;
my $runs = 5;
my $elems = 10 * Kernel.cpu-cores * 2**10;
⚫
my @unsorted of Str = ('a'..'z').roll(8).join xx $elems;
my UInt $l-batch = 2**13;
my UInt $m-batch = 2**11;
my UInt $s-batch = 2**9;
my UInt $t-batch = 2**7;


say "elements: $elems, runs: $runs, cpu-cores: {Kernel.cpu-cores}, large/medium/small/tiny-batch: $l-batch/$m-batch/$s-batch/$t-batch";
say "Benchmarking by sorting {@large.elems} strings of size $elem-length - using batches of $BATCH-SIZE strings and $worker workers.";

my @benchmark = gather for @implementations -> &fun {
my %results = timethese $runs, {
&fun(@large);
⚫
single-thread => { quicksort(@unsorted) },
take (&fun.name => now - ENTER now);
parallel-naive => { quicksort-parallel-naive(@unsorted) },
⚫
}
⚫
parallel-tiny-batch => { quicksort-parallel(@unsorted, $t-batch) },
say @benchmark;
parallel-small-batch => { quicksort-parallel(@unsorted, $s-batch) },
⚫
</syntaxhighlight>
parallel-medium-batch => { quicksort-parallel(@unsorted, $m-batch) },
parallel-large-batch => { quicksort-parallel(@unsorted, $l-batch) },
⚫
};

for %results.kv -> $name, ($start, $end, $diff, $avg) {
say "$name avg $avg secs"
⚫
}</syntaxhighlight>
<pre>
<pre>
xxxxxxxxxxx Benchmarking xxxxxxxxxxx
Benchmarking by sorting 40960 strings of size 8 - using batches of 1024 strings and 4 workers.
elements: 40960, runs: 5, cpu-cores: 4, large/medium/small/tiny-batch: 8192/2048/512/128
[quicksort => 6.075300648 seven-line-quicksort-parallel => 4.889432647 quicksort-parallel => 1.147604289]</pre>
single-thread avg 6 secs
parallel-naive avg 5.6 secs
parallel-tiny-batch avg 2.8 secs
parallel-small-batch avg 2.4 secs
parallel-medium-batch avg 2.8 secs
parallel-large-batch avg 3.4 secs
⚫
</pre>


=={{header|Red}}==
=={{header|Red}}==
Retrieved from "https://rosettacode.org/wiki/Sorting_algorithms/Quicksort"