comparison of code performance, threaded versus non-threaded

Question

I have some thread-related questions, assuming the following code. Please ignore the possible inefficiency of the code, I'm only interested in the thread part.

//code without thread use
public static int getNextPrime(int from) {
    int nextPrime = from+1;
    boolean superPrime = false;
    while(!superPrime) {
        boolean prime = true;
        for(int i = 2;i < nextPrime;i++) {
            if(nextPrime % i == 0) {
                prime = false;
            }
        }
        if(prime) {
            superPrime = true;
        } else {
            nextPrime++;
        }
    }
    return nextPrime;
}

public static void main(String[] args) {
   int primeStart = 5;
   ArrayList list = new ArrayList();
   for(int i = 0;i < 10000;i++) {
       list.add(primeStart);
       primeStart = getNextPrime(primeStart);
   }
}

If I'm running the code like this and it takes about 56 seconds. If, however, I have the following code (as an alternative):

public class PrimeRunnable implements Runnable {

    private int from;
    private int lastPrime;

    public PrimeRunnable(int from) {
        this.from = from;
    }

    public boolean isPrime(int number) {
        for(int i = 2;i < from;i++) {
            if((number % i) == 0) {
                return false;
            }
        }
        lastPrime = number;
        return true;
    }

    public int getLastPrime() {
        return lastPrime;
    }

    public void run() {
        while(!isPrime(++from))
            ;
    }
}

public static void main(String[] args) {
   int primeStart = 5;
   ArrayList list = new ArrayList();
   for(int i = 0;i < 10000;i++) {
     PrimeRunnable pr = new PrimeRunnable(primeStart);
     Thread t = new Thread(pr);
     t.start();
     t.join();
     primeStart = pr.getLastPrime();
     list.add(primeStart);
   }
}

The whole operation takes about 7 seconds. I am almost certain that even though I only create one thread at a time, a thread doesn't always finish when another is created. Is that right? I am also curious: why is the operation ending so fast?

When I'm joining a thread, do other threads keep running in the background, or is the joined thread the only one that's running?

Answer 1

By putting the join() in the loop, you're starting a thread, then waiting for that thread to stop before running the next one. I think you probably want something more like this:

public static void main(String[] args) {
   int primeStart = 5;

   // Make thread-safe list for adding results to
   List list = Collections.synchronizedList(new ArrayList());

   // Pull thread pool count out into a value so you can easily change it
   int threadCount = 10000;
   Thread[] threads = new Thread[threadCount];

   // Start all threads
   for(int i = 0;i < threadCount;i++) {
     // Pass list to each Runnable here
     // Also, I added +i here as I think the intention is 
     //    to test 10000 possible numbers>5 for primeness - 
     //    was testing 5 in all loops
     PrimeRunnable pr = new PrimeRunnable(primeStart+i, list);
     Thread[i] threads = new Thread(pr);
     threads[i].start();  // thread is now running in parallel
   }

   // All threads now running in parallel

   // Then wait for all threads to complete
   for(int i=0; i<threadCount; i++) {
     threads[i].join();
   }
}

By the way pr.getLastPrime() will return 0 in the case of no prime, so you might want to filter that out before adding it to your list. The PrimeRunnable has to absorb the work of adding to the final results list. Also, I think PrimeRunnable was actually broken by still having incrementing code in it. I think this is fixed, but I'm not actually compiling this.

public class PrimeRunnable implements Runnable {    
    private int from;
    private List results;   // shared but thread-safe

    public PrimeRunnable(int from, List results) {
        this.from = from;
        this.results = results;
    }

    public void isPrime(int number) {
        for(int i = 2;i < from;i++) {
                if((number % i) == 0) {
                        return;
                }
        }
        // found prime, add to shared results
        this.results.add(number);
    }

    public void run() {
        isPrime(from);      // don't increment, just check one number
    }    
}

Running 10000 threads in parallel is not a good idea. It's a much better idea to create a reasonably sized fixed thread pool and have them pull work from a shared queue. Basically every worker pulls tasks from the same queue, works on them and saves the results somewhere. The closest port of this with Java 5+ is to use an ExecutorService backed by a thread pool. You could also use a CompletionService which combines an ExecutorService with a result queue.

An ExecutorService version would look like:

public static void main(String[] args) {
   int primeStart = 5;

   // Make thread-safe list for adding results to
   List list = Collections.synchronizedList(new ArrayList());

   int threadCount = 16;  // Experiment with this to find best on your machine
   ExecutorService exec = Executors.newFixedThreadPool(threadCount);

   int workCount = 10000;  // See how # of work is now separate from # of threads?
   for(int i = 0;i < workCount;i++) {
     // submit work to the svc for execution across the thread pool 
     exec.execute(new PrimeRunnable(primeStart+i, list));
   }

   // Wait for all tasks to be done or timeout to go off
   exec.awaitTermination(1, TimeUnit.DAYS);
}

Hope that gave you some ideas. And I hope the last example seemed a lot better than the first.

Answer 2

JesperE is right, but I don't believe in only giving hints (at least outside a classroom):

Note this loop in the non-threaded version:

for(int i = 2;i < nextPrime;i++) {
  if(nextPrime % i == 0) {
    prime = false;
  }
}

As opposed to this in the threaded version:

for(int i = 2;i < from;i++) {
  if((number % i) == 0) {
    return false;
  }
}

The first loop will always run completely through, while the second will exit early if it finds a divisor.

You could make the first loop also exit early by adding a break statement like this:

for(int i = 2;i < nextPrime;i++) {
  if(nextPrime % i == 0) {
    prime = false;
    break;
  }
}

Answer 3

You can test this better by making the exact code in your first example run with threads. Sub your main method with this:

    private static int currentPrime;
public static void main(String[] args) throws InterruptedException {
    for (currentPrime = 0; currentPrime < 10000; currentPrime++) {
        Thread t = new Thread(new Runnable() {
            public void run() {
                getNextPrime(currentPrime);
            }});
        t.run();
        t.join();
    }
}

This will run in the same time as the original.

To answer your "join" question: yes, other threads can be running in the background when you use "join", but in this particular case you will only have one active thread at a time, because you are blocking the creation of new threads until the last thread is done executing.

Answer 4

Running a test, the second one doesn't seem to take 9 seconds--in fact, it takes at least as long as the first (which is to be expected, threding can't help the way it's implemented in your example.

Thread.join will only return when the thread.joined terminates, then the current thread will continue, the one you called join on will be dead.

For a quick reference--think threading when starting one iteration does not depend on the result of the previous one.

Answer 5

Read your code carefully. The two cases aren't doing the same thing, and it has nothing to do with threads.

When you join a thread, other threads will run in the background, yes.