Green Threads: A Classic Example

Now that I have green threads basically working with the API functionality I discussed in my last blog post, I've been working on coming up with tests/examples that clearly demonstrate both how green threads in Parrot work and that they work as advertised. With that goal in mind, this blog post is about a classic concurrent programming example: The Sieve of Eratosthenes.

This example was apparently initially suggested by Doug McIlroy. After screwing this up the first few tries from memory, I cheated and googled it. I found a good diagram here: http://swtch.com/~rsc/thread/

The Sieve of Eratosthenes finds prime numbers using simple recursive concept. Start with the first prime number, 2, and count up. For any given number, if it isn't divisible by any of the prime numbers below it then it must be a prime.

This can be implemented with communicating processes by setting up a chain of processes, one for each prime number. Starting with two and counting up, pass each number down the chain. If it's divisible by any number in the chain it's not prime and can be thrown away. If it gets to the end of the chain, it's prime and it gets to be the new end of the chain.

Below is the PIR code, using the Task API that I described in my last blog post.

# task_primes.pir
# A task-based concurrent Sieve of Eratosthenes

.include 'interpinfo.pasm'

.sub main
    .local pmc nt # "next task"

    # Make the first task in the chain
    nt = make_checker()

    # Start with the first prime, 2
    $I0 = 2
loop:
    # Send each prime to the first task in the chain
    send_int(nt, $I0)
    # Simulate synchronous message passing by waiting
    # for a response.
    $P0 = recv

    $I0 = $I0 + 1
    if $I0 < 100 goto loop
.end

# The Task#send method only takes PMCs; here's a sub
# that packs up and sends ints.
.sub send_int
    .param pmc t
    .param pmc i
    $P0 = new 'Integer'
    $P0 = i
    t.'send'($P0)
.end

# This constructs a new link in the chain,
# sending the current task as its argument.
.sub make_checker
    .local pmc cp, ct

    cp = get_global 'check_prime'
    ct = interpinfo .INTERPINFO_CURRENT_TASK
    
    $P0 = new 'Hash'
    $P0['code'] = cp
    $P0['data'] = ct

    $P1 = new 'Task', $P0
    schedule $P1
    .return($P1)
.end

.sub check_prime
    .param pmc pt
    .local pmc nt, M
    .local int N, x

    N = 0

next_msg:
    M = recv
    x = M

    # The first number we get is the prime
    # that this task will be checking.
    if N >= 2 goto check_x
    N = x
    say x # We found a prime!
    goto send_reply

check_x:
    $I0 = x % N
    if $I0 != 0 goto maybe_prime
    goto send_reply

maybe_prime:
    # Make sure there's a next task in the
    # chain to send to.
    unless null nt goto ship_it
    nt = make_checker()

ship_it:
    # More syncrhonous message passing to the
    # next task.
    nt.'send'(M)
    M = recv

send_reply:
    # And the reply for the previous task
    # that's waiting on us.
    pt.'send'(M)
    goto next_msg
.end