This post originated from an RSS feed registered with Ruby Buzz by Eric Hodel. Original Post: Finding primes with Rinda::TupleSpace Feed Title: Segment7 Feed URL: http://blog.segment7.net/articles.rss Feed Description: Posts about and around Ruby, MetaRuby, ruby2c, ZenTest and work at The Robot Co-op. Latest Ruby Buzz Posts Latest Ruby Buzz Posts by Eric Hodel Latest Posts From Segment7

While at FOSCON 2006 I watched Lucas Carlson's presentation on Rinda and DRb, but he barely scratched the surface of Rinda's capabilities with his prime finding implementation.

Rinda::TupleSpace is more powerful than just a name service for DRb. Since a TupleSpace has synchronized access to all its items, you can use a TupleSpace to coordinate processes as well.

I started rewriting Lucas' DRb using prime finder at FOSCON, but wasn't able to finish it until now. This version coordinates all the activities of the prime finding via the TupleSpace. No locking is necessary in any of the code because the TupleSpace takes care of it for us.

Here's the server:

require 'rinda/ring'
require 'rinda/tuplespace'

class TupleSpacePrimeFinder

  def self.run
    DRb.start_service
    new.run
  end

  def initialize
    @ts = Rinda::TupleSpace.new
  end

  ##
  # Lists primes as they are added to the TupleSpace.

  def list_primes
    Thread.start do
      notifier = @ts.notify 'write', [:prime, nil]

      puts "primes found:"
      notifier.each do |_, t|
        puts t.last
      end
    end
  end

  def run
    list_primes

    @ts.write [:prime, 2] # seed prime
    @ts.write [:current, 2] # next value to search
    @ts.write [:step, 100] # range of values to search

    rp = Rinda::RingProvider.new :TSPF, @ts, 'PrimeFinder using TupleSpace'
    rp.provide

    DRb.thread.join
  end

end

TupleSpacePrimeFinder.run

It doesn't do much besides place some seed values in the TupleSpace and print out the primes as they get added to the TupleSpace. The service is published to the RingServer (download ringserver.rb from my tutorial on tutorial on Rinda::Ring) and everything is ready to go.

And next the client:

require 'rinda/ring'
require 'rinda/tuplespace'

class PrimeFinder

  def self.run
    DRb.start_service
    new.find
  end

  def initialize
    ts = Rinda::RingFinger.primary.read([:name, :TSPF, DRbObject, nil])[2]
    @ts = Rinda::TupleSpaceProxy.new ts # for safety
  end

  def find
    loop do
      start = @ts.take([:current, nil]).last # start of our search space
      finish = start + @ts.read([:step, nil]).last # items in our search space
      @ts.write [:current, finish] # write it back

      primes = @ts.read_all([:prime, nil]).map { |_,v| v } # read all primes

      start.upto finish do |candidate|
        next unless prime_in? candidate, primes

        top = Math.sqrt(candidate).to_i

        next unless prime_in? candidate, (start..top)

        @ts.write [:prime, candidate] # add to the found list
        primes << candidate
      end
    end
  end

  def prime_in?(candidate, range)
    range.all? do |value|
      value < candidate and candidate % value != 0
    end
  end

end

PrimeFinder.run

The client runs in a loop and grabs the current unsearched prime candidate from the TupleSpace, increments it, then puts it back into the TupleSpace. This take/write operation forms a Mutex. Only one client will be allowed to remove :current at a time, and the rest will block. No need to worry about any synchronization, TupleSpace takes care of that for us.