Problem: Write a ring benchmark. Create N processes in a ring. Send a message round the ring M times so that a total of N * M messages get sent. Time how long this takes for different values of N and M. Write a similar program in some other programming language you are familiar with. compare the results. Write a blog, and publish the results on the Internet!

You can find quite a few Java solutions on the Internet for this exercise, which is at the end of chapter 8 in Programming Erlang by Joe Armstrong. I wanted to post a solution for these reasons:

1. Some Java solutions I saw on the web, do not pass messages in a ring. I think of ring as a circular linked list. The last member in the list has to pass the message to the first member (the one that started message passing). Otherwise, it isn’t a ring – its just an open ended chain.
2. Code written using wait()/notify() makes me dizzy and when you have Java 6, you have to take advantage of java.util.concurrent library.
3. The Java program here – http://www.sics.se/~joe/ericsson/du98024.html – written in 1998 on JDK 1.1.6 needs a makeover.
4. Lastly, the problem itself states that you should write the ring benchmark in another language and post the results.

So, here’s my solution. The driver class:

/**
 * @(#) Ring.java Feb 28, 2009 4:30:40 PM
 */
package ring;

import java.util.Arrays;
import java.util.LinkedList;
import java.util.Scanner;
import java.util.concurrent.CountDownLatch;
import java.util.concurrent.ExecutorService;
import java.util.concurrent.Executors;

/**
 * This is a driver class that starts a variable size ring.
 *
 * @author $Author: vijaykandy $
 * @version $Revision: 1.0 $
 */
public class Ring {
	public static void main(String args[]) throws InterruptedException {
		Scanner scanner = new Scanner(System.in);
		System.out.println("Enter N:");
		int N = scanner.nextInt();
		System.out.println("Enter M:");
		int M = scanner.nextInt();

		long beginInit = System.currentTimeMillis();
		CountDownLatch passComplete = new CountDownLatch(N);
		LinkedList<RingMember<Integer>> ring = initRing(N, M, passComplete);
		long endInit = System.currentTimeMillis();

		Integer messages[] = createMessages(M);

		long beginPassing = System.currentTimeMillis();
		ring.getFirst().startPassing(Arrays.asList(messages));
		passComplete.await();
		long endPassing = System.currentTimeMillis();

		System.err.format("Initing ring of %d threads took: %d millis%n", N, (endInit - beginInit));
		System.err.format("Passing a message %d times took: %d millis%n", M, (endPassing - beginPassing));
	}

	private static LinkedList<RingMember<Integer>> initRing(int N, int M, CountDownLatch doneSignal) {
		LinkedList<RingMember<Integer>> ring = new LinkedList<RingMember<Integer>>();

		// Create the first member with name = 1 and neighbor as null
		RingMember<Integer> starter = new RingMember<Integer>(1, M, doneSignal);
		starter.setNeighbor(null);
		ring.add(starter);

		// Initialize the rest of the ring
		for (int name = 2; name <= N; name++) {
			RingMember<Integer> member = new RingMember<Integer>(name, M, doneSignal);
			member.setNeighbor(ring.getLast());
			ring.add(member);
		}
		ring.getFirst().setNeighbor(ring.getLast());

		// Start threads
		ExecutorService pool = Executors.newFixedThreadPool(N);
		for (RingMember<Integer> member : ring) {
			pool.execute(member);
		}
		pool.shutdown();

		return ring;
	}

	private static Integer[] createMessages(int size) {
		Integer[] messages = new Integer[size];
		for (int i = 0; i < size; i++) {
			messages[i] = i;
		}
		return messages;
	}
}

The RingMember class:

/**
 * @(#) RingMember.java Feb 28, 2009 4:30:40 PM
 */
package ring;

import java.util.Collection;
import java.util.concurrent.ArrayBlockingQueue;
import java.util.concurrent.CountDownLatch;

/**
 * Represents a ring member.
 *
 * Each member is "smart" enough to know when to pass a message to its neighbor.
 * The member that starts passing messages is a <i>starter</i> and has
 * <code>isStarter</code> set to <code>true</code>.
 *
 * This is a generic class and hence any type of message can be passed around
 * the ring.
 *
 * Each member <b>is an</b> <code>ArrayBlockingQueue</code> of size 1. Hence
 * 1 message is passed at a time.
 *
 * @author $Author: vijaykandy $
 * @version $Revision: 1.0 $
 */
class RingMember<T> extends ArrayBlockingQueue<T> implements Runnable {
	private static final long serialVersionUID = 8627995769853843195L;
	private int M;
	private int name;
	private boolean isStarter;
	private RingMember<T> neighbor;
	private CountDownLatch doneSignal;

	public RingMember(int name, int M, CountDownLatch doneSignal) {
		super(1);
		this.M = M;
		this.name = name;
		this.doneSignal = doneSignal;
	}

	@Override
	public void run() {
		try {
			while (M-- > 0) {
				T message = neighbor.take();
				System.out.format("Thread#%s took %s from Thread#%s%n", name, message, neighbor.name);
				if (!isStarter) {
					put(message);
				}
			}
			doneSignal.countDown();
		} catch (InterruptedException e) {
			Thread.currentThread().interrupt();
		}
	}

	public void setNeighbor(RingMember<T> n) {
		this.neighbor = n;
	}

	public void startPassing(Collection<T> messages) {
		isStarter = true;
		for (T message : messages) {
			try {
				put(message);
			} catch (InterruptedException e) {
				Thread.currentThread().interrupt();
			}
		}
	}
}

Usage:

Enter N:
10
Enter M:
5
Initing ring of 10 threads took: 187 millis
Passing a message 5 times took: 78 millis

You can shorten the program by a few lines but I like this version as it is more readable. In my next entry, I’ll post a solution in Erlang and compare message passing times in Java and in Erlang for different values of N and M.