moritz/advent.pod Secret

## advent.pod

      
    Raw
  

              advent.pod
            
          
    Webscale sorting of the sleepy kind


In the emerging tradition of writing about sort on the 23rd, let me elaborate on a particularly silly kind of sorting algorithm: sleepsort.

The idea is that to sort a list of numbers, you spawn a separate process (or thread), sleep for as long as the number specifies, and then print the result. That way the numbers are printed in ascending order.

Rakudo on the MoarVM backend has threads, so let's put them to good use:

use v6;

my @unsorted = (1..10).pick(5);

say "Unsorted: @unsorted[]";

await @unsorted.map: -> $t {
    start {
        sleep $t;
        say $t;
    }
};

If you run it, you should get output like this:

$ ./perl6-m sleepsort-01.p6
Unsorted: 1 7 5 8 3
1
3
5
7
8

How did we get there? (1..10).pick(5) randomly picks (without replacing) five numbers from 1 to 10. start { ... } starts a thread and returns a Promise object. We do that for all the numbers, and await blocks until all promises that have passed to it are fullfilled (or broken, but that won't happen here). Or in other words: until all the newly spawned threads have finished.

Now let's make it web scale! Well, sort (sic) of.

First an obvious improvement is to not sleep for the whole second. Let's just scale it with a constant factor: sleep $t / 10, and we're about ten times as fast!

But there's another scaling problem: If you want to sort hundreds of thousands of numbers with sleep sort (you'd do that, right?), our program would spawn as many threads. So lots of memory wasted. Also sleep maps pretty much directly to the underlying libc call, and thus blocks the thread. We can do better:

use v6;

 my @unsorted = (1..10).pick(5);

await @unsorted.map: -> $t {
    Promise.in($t / 10 ).then({ say $t });
};

Promise.in($s) creates a Promise that will be kept in $s seconds. .then creates a chained promise whose block is executed when the first one is kept.

This also removes the need to spawn processes explicitly. The standard scheduler takes care of that. We're basically web scale!

Now it's also time to address an issue of correctness. The sleepsort algorithm is a kind of divide-and-conquer approach, but there's no joining of the results. There is no single point in the program that can access the entire the sorted list. To fix that, we use a Channel. There several use cases for channels, but we use it as a thread-safe queue:

use v6;
my @unsorted = (1..10).pick(5);

my $channel = Channel.new;

await @unsorted.map: -> $t {
    Promise.in($t / 10 ).then({ $channel.send($t) });
};
$channel.close;

say $channel.list;

This prints the sorted list all from the main thread.

So now it can be encapsulated in a nice subroutine.

sub sleepsort(*@values, :$factor) {
    my $channel = Channel.new;

    await @unsorted.map: -> $t {
        Promise.in($t * $factor ).then({ $channel.send($t) });
    };
    $channel.close;

    $channel.list;
}

Another issue of correctness remains: Both sleep and Promise.in only specify a minimal time to be slept; implementation-dependent, longer sleep times are possible. If $factor is too small, the promises might executed out of the desired order.

So let's find the minimal factor with which it still works:

my $previous = Inf;
for 0.1, */1.5 ... * -> $factor {
    say "Trying $factor";
    my $success = [<=] sleepsort(:$factor, @unsorted);
    say $success ?? 'Success' !! 'Failed';
    unless $success {
        say "Last good factor: ", $previous;
        last;
    }
    $previous = $factor;
}

On my machine, this produces the following output:

Trying 0.1
Success
Trying 0.066667
Success
Trying 0.044444
Success
Trying 0.029630
Success
Trying 0.019753
Success
Trying 0.013169
Success
Trying 0.008779
Success
Trying 0.005853
Failed
Last good factor: 0.008779

So a :$factor of around 0.01 or 0.09 seems to work on my setup.

Your output/mileage may vary.

Over and out, sleeping until Christmas Eve.