Last active
October 2, 2023 11:04
-
-
Save rcmlz/552726f93e0134480e7517159947901b to your computer and use it in GitHub Desktop.
some implementations of qicksort showing some nice Raku features
This file contains bidirectional Unicode text that may be interpreted or compiled differently than what appears below. To review, open the file in an editor that reveals hidden Unicode characters.
Learn more about bidirectional Unicode characters
#!/usr/bin/env raku --optimize=3 | |
#| Recursive, single-thread, single-pass, quicksort implementation | |
sub quicksort(@a) { | |
return @a if @a.elems < 2; | |
my $pivot = @a.pick; | |
my %prt{Order} is default([]) = @a.classify: * cmp $pivot; | |
|samewith(%prt{Less}), |%prt{Same}, |samewith(%prt{More}) | |
} | |
#| Recursive, parallel, single-pass, quicksort implementation | |
sub quicksort-parallel-naive(@a) { | |
return @a if @a.elems < 2; | |
my $pivot = @a.pick; | |
my %prt{Order} is default([]) = @a.classify( * cmp $pivot ); | |
my Promise $less = start { samewith(%prt{Less}) } | |
my $more = samewith(%prt{More}); | |
await $less andthen |$less.result, |%prt{Same}, |$more; | |
} | |
#| Recursive, parallel, batch tuned, single-pass, quicksort implementation | |
sub quicksort-parallel(@a, $batch = 2**9) { | |
return @a if @a.elems < 2; | |
# separate unsorted input into Order Less, Same and More compared to a random $pivot | |
my $pivot = @a.pick; | |
my %prt{Order} is default([]) = @a.classify( * cmp $pivot ); | |
# decide if we sort the Less partition on a new thread | |
my $less = %prt{Less}.elems >= $batch | |
?? start { samewith(%prt{Less}, $batch) } | |
!! samewith(%prt{Less}, $batch); | |
# meanwhile use current thread for sorting the More partition | |
my $more = samewith(%prt{More}, $batch); | |
# if we went parallel, we need to await the result | |
await $less andthen $less = $less.result if $less ~~ Promise; | |
# concat all sorted partitions into a list and return | |
|$less, |%prt{Same}, |$more; | |
} | |
say "x" x 10 ~ " Testing " ~ "x" x 10; | |
use Test; | |
my @functions-under-test = &quicksort, &quicksort-parallel-naive, &quicksort-parallel; | |
my @testcases = | |
() => (), | |
<a>.List => <a>.List, | |
<a a> => <a a>, | |
("b", "a", 3) => (3, "a", "b"), | |
<h b a c d f e g> => <a b c d e f g h>, | |
<a 🎮 3 z 4 🐧> => <a 🎮 3 z 4 🐧>.sort | |
; | |
plan @testcases.elems * @functions-under-test.elems; | |
for @functions-under-test -> &fun { | |
say &fun.name; | |
is-deeply &fun(.key), .value, .key ~ " => " ~ .value for @testcases; | |
} | |
done-testing; | |
say "x" x 11 ~ " Benchmarking " ~ "x" x 11; | |
use Benchmark; | |
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"; | |
my %results = timethese $runs, { | |
single-thread => { quicksort(@unsorted) }, | |
parallel-naive => { quicksort-parallel-naive(@unsorted) }, | |
parallel-tiny-batch => { quicksort-parallel(@unsorted, $t-batch) }, | |
parallel-small-batch => { quicksort-parallel(@unsorted, $s-batch) }, | |
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" | |
} |
Sign up for free
to join this conversation on GitHub.
Already have an account?
Sign in to comment