java threading question

[centenial100]

Hey everyone,

Let me state up front that this is a homework assignment.

I'm supposed to take a simple task (flipping a coin n number of times) and use threading to increase the execution speed of the program. The basic idea is that to flip a coin 1,000,000 times, you could launch n threads and have it execute approx. n times as fast.

I've been working on it for a few days. The code is complete in that the task gets divided up and runs on multiple threads. However, the execution time doesn't nearly reflect what I would expect it to be.

For example, flipping 10,000,000 "coins" takes:

~700ms using 1 thread.
~980ms using 2 threads.
~920ms using 4 threads.

I would expect that the execution time would decrease as I add more threads. This time difference is magnified as I increase the number of coin flips. For example, flipping 100,000,000 "coins" takes:

~7 seconds using 1 thread.
~10 seconds using 2 threads.

Does this make sense? My code isn't very long, and I've included it below. Am I just missing something obvious?

The project contains three files:
- CoinFlip.java (the main program)
- FlipCoins.java (implements Runnable - used to execute some number of coin tosses on a separate thread)
- CoinData.java (basically a struct to store the coin toss statistics)

CoinFlip.java

public class CoinFlip
{
	public static void main(String[] args)
	{
		// declare needed variables
		int numTosses = 10000000;
		int numThreads = 8;
		int numTossesPerThread = numTosses / numThreads;
		int numTossesLeftover = numTosses - numTossesPerThread * numThreads;
		int workload;
		long startTime, endTime, totalTime;
		
		// basically a struct to hold the coin toss statistics 
		CoinData data = new CoinData();
		
		// array of threads
		Thread[] threads = new Thread[numThreads];
		
		// set the start time
		startTime = System.currentTimeMillis();
		
		// spawn the threads
		for (int i = 0; i < numThreads; i++)
		{
			// calculate the workload for each thread
			if (i == numThreads - 1)
			{
				workload = numTossesPerThread + numTossesLeftover;
			}
			else
			{
				workload = numTossesPerThread;
			}
			
			// spawn the thread
			threads[i] = new Thread(new FlipCoins(data,workload));
			threads[i].start();
		}
		
		// wait for the threads to complete
		for (int i = 0; i < numThreads; i++)
		{
			try
			{
				threads[i].join();
			}
			catch (InterruptedException e)
			{
				e.printStackTrace();
			}
		}
		
		// calculate the total execution time
		endTime = System.currentTimeMillis();
		totalTime = endTime - startTime;
		
		// print out the results
		System.out.println("Execution Time: " + totalTime + "ms");
		System.out.println("Num Heads: " + data.numHeads());
		System.out.println("Num Tails: " + data.numTails());
	}
}

FlipCoins.java

public class FlipCoins implements Runnable
{
	private int mNumIterationsToRun = 0;
	private CoinData mCoinData;
	
	public FlipCoins(CoinData d, int n)
	{
		mCoinData = d;
		mNumIterationsToRun = n;
	}
	
	@Override
	public void run()
	{
		int numHeads = 0;
		int numTails = 0;
		
		for (int i = 0; i < mNumIterationsToRun; i++)
		{
			if (flipCoin())
				numHeads++;
			else
				numTails++;
		}
		
		mCoinData.addHeadData(numHeads);
		mCoinData.addTailData(numTails);
	}
	
	private boolean flipCoin()
	{
		if (Math.random() > 0.5)
			return true;
		else 
			return false;
	}
}

CoinData.java

public class CoinData
{
	private volatile int mNumHeads = 0;
	private volatile int mNumTails = 0;
	
	public synchronized void addHeadData(int n)
	{
		mNumHeads += n;
	}
	
	public synchronized void addTailData(int n)
	{
		mNumTails += n;
	}
	
	public int numHeads()
	{
		return mNumHeads;
	}
	
	public int numTails()
	{
		return mNumTails;
	}
}

I appreciate your time and any thoughts you might have. Thanks!

[Oralloy]

Actually, your results are probably reasonable.

First off, does your system have multiple CPUs? Or at least multiple cores? If not, all the threads will have to share the CPU, and consequently your performance will drop, as the calculation will take the same amount of time, plus there will be additional time spent managing the multiple threads and swapping them.

Even if your system has multiple cores, if there's a sequencing point in the code, then your program still has to visit that point every time for every thread. Unless the sequencing time cost is less than the cost of a coin flip, you'll see an increase in execution time.

About the only way that your throughput will increase in this case is if you can guarantee that the threads are completely disjoint. That means that there is no shared resource (e.g. a counter or I/O), and you have a true multiple processing system that you can exploit.

Still, even in that case, the CPU time will probably go up, because you have the minimum cost (the execution time of the coin flips) plus some overhead time for synchronization . Wall-clock time may go down, however, in this case.

Also, given the jitter in clocks, tests that run under one second are generally dubious at best. Try to increase the execution time by a factor of 100, if you can. This will eliminate small statistical issues associated with the clock.

Good luck!