Adventures with libdispatch

Apple released Snow Leopard to the world last Thursday, and with it came this interesting piece of technology called Grand Central Dispatch. It totally changes the way C, C++, and Objective-C programmers will approach concurrency and threading if they were used to anything at all like pthreads.

Having built up a bit of a functional programming background for myself, I'm no stranger to new ways to do concurrent programming. Scheme has its ways. Haskell has a couple of ways (explicitly forkIO'ng sparks that might be run on threads, or data parallelism). Also, I've tinkered with such things as typed data channels in Limbo from the folks at Bell Labs (seemingly inspired by Newsqueak by Rob Pike and CSP itself).

When I first looked at Grand Central Dispatch from Apple, I was a bit puzzled by the API. There's queues, event sources, asynchronous dispatching, and this interesting feature they've added to their implementation C language (though some of my fellow 9fans have been somewhat outspoken against it) called blocks. Blocks are closures for C. If you want to know more about closures consult a good book on Scheme or a Scheme tutorial. (or Lisp!)

I'm more used to a CSP-like programming interface, and I wondered if I could port a rather famous demo in Newsqueak, and Limbo to this interface. It's a Prime Number Sieve (Pike?).

The algorithm may be explained as such (poorly?):

1. Create a channel of integers
2. Start a process that puts onto the channel from step 1 all the numbers from [2,N]
3. Start a process that reads from the channel all incoming numbers. The first number read is "special" and becomes that process's special number. This process prints it's number and creates another channel of ints, that it will feed all numbers that fail the test (incoming_number % my_special_num == 0). In this way it filters out all numbers that are multiples of it's special number.
4. Start another process and feed it the first number that passes through this filter.... the new process follows the same step 3 as above.

This creates us a sieve that only lets prime numbers escape.

A good animation of how one works is here.

My prose is rather lacking, so without further ado, here is the code I came up with to try to approach a prime number sieve, using pipes, and blocks, and libdispatch routines to concurrently schedule the sieve on my mac.

// David Leimbach
// September 4, 2009
//
// First, unclean attempt at a prime number sieve in C with libdispatch
//
// Special thanks to Kevin Van Vechten and Jordan Hubbard for guidance through this new API!
//
// Thanks to Apple for making Snow Leopard so affordable!

#include <dispatch/dispatch.h>
#include <stdio.h>
#include <stdlib.h>
#include <sys/types.h>
#include <sys/uio.h>
#include %lt;unistd.h>

#define MAX 300

struct context
{
int mynum;
int has_spawned;
int writefd;
};

void setup_block(int read_fd) {
dispatch_source_t piperead;
struct context * ctx;
piperead = dispatch_source_create(DISPATCH_SOURCE_TYPE_READ, read_fd,
        0, dispatch_get_global_queue(DISPATCH_QUEUE_PRIORITY_LOW, 0));

ctx = calloc(sizeof(struct context), 1);

ctx->has_spawned = 0;

dispatch_source_set_event_handler(piperead,
        ^{
          int val;
          int fd[2];
          struct context * ctx = dispatch_get_context(piperead);

          read(read_fd, &val, 4);

          if (ctx->has_spawned == 0) {
     pipe(fd);
     ctx->writefd = fd[1];
     ctx->mynum = val;
     ctx->has_spawned = 1;
     setup_block(fd[0]);
     printf("%d\n", val);
          }
          else {
     if (val % ctx->mynum != 0) {
       write(ctx->writefd, &val, 4);
     }
          }
        });

dispatch_set_context(piperead, ctx);  // associate this state with this context
      
dispatch_resume(piperead);
}


void run_sieve(int writefd) {
int x;

for(x=2; x <= MAX; ++x)

   write(writefd, &x, 4);

   sleep(2); 

}  

int main () {

    int fd[2];

    pipe(fd);

    setup_block(fd[0]);    

    run_sieve(fd[1]);    

    return 0; 

}

 (Please forgive the code formatting, I'm having great difficulty with blogspot on this stuff with their editor)