Day 23 – 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, 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 @values.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.

One thought on “Day 23 – Webscale sorting of the sleepy kind

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s