Synchronizing access to ArrayList

Question

I am trying to calculate all the primes up to an arbitrary number by computing them in parallel. I'm aware that isPrime() can be improved from what it is now, but the main problem is that I can't synchronize access to the ArrayList that is storing the results. I've instantiated a dummy object "m" to serve as a monitor and control access to the array. Obviously I've made a mistake in reasoning somewhere because I get a java.util.ConcurrentModificationException every time. NB: gist

EDIT: updated to show completion after suggestions.

import java.util.ArrayList;
public class Main {
    static final int MAX = 100000000;
    static final int THREADS = Runtime.getRuntime().availableProcessors();
    static final int ARRINITSIZE = 100000;
    static ArrayList<Integer> primes = new ArrayList<Integer>(ARRINITSIZE);

    public static void main(String[] args) {
        Thread[] t = new Thread[THREADS];
        PrimeRun.m = new Monitor();

        for (int i=0; i<THREADS; i++) {
            t[i] = new Thread(new PrimeRun(i) );
            t[i].start();
        }

        // wait for threads to finish
        for (int i=0; i<THREADS; i++)
            t[i].join();

        // NOTE: primes will be out of order because of random thread scheduling 
        for (int n : primes)
            System.out.print("" + n + " ");
        System.out.println();
    }

    static boolean isPrime(int n) {
        if (n == 2 || n == 3 || n == 5) return true;
        if (n <= 1 || (n&1) == 0) return false;

        for (int i = 3; i*i <= n; i += 2)
            if (n % i == 0) return false;

        return true;
    }

    synchronized static void addPrime(int n) {
        primes.add(n);
    }

}

class PrimeRun implements Runnable {
    public static Monitor m;
    final int ID;
    public PrimeRun(int i) {
        ID = i;
    }

    public void run() {
    for(int i=0; i < Main.MAX; i++) {
        if(i % Main.THREADS == ID)
            if(Main.isPrime(i)) 
                m.addPrime(i);
        }
    }
}

class Monitor {
    public synchronized void addPrime(int n) {
        Main.addPrime(n);
    }
}

I've included my ant script for convenience :)

<project default="cmp">
  <target name="cmp"><javac srcdir="." debug="true"/></target>
  <target name="run" depends="cmp"><java classname="Main" classpath="."/></target>
  <target name="cln"><delete><fileset dir="." includes="*.class"/></delete></target>
</project>

Answer 1

How about declaring primes as

static List<Integer> primes = Collections.synchronizedList(new ArrayList<Integer>(ARRINITSIZE));

And you should be able to get rid of the Monitor and the synchronized blocks... Oh and you will have to wait till the threads that calculates primes to finish before starting to print values from primes list

Edit

Here is the modified program where it just waits for the threads to finish

    import java.util.ArrayList;
    import java.util.List;

    public class Main {
        static final int MAX = 1000;
        static final int THREADS = Runtime.getRuntime().availableProcessors();
        static final int ARRINITSIZE = 100000;
        static ArrayList<Integer> primes = new ArrayList<Integer>(ARRINITSIZE);

    public static void main(String[] args) {
        PrimeRun.m = new Monitor();

        List<Thread> thread = new ArrayList<Thread>();
        for (int i=0; i<THREADS; i++){
            Thread t = new Thread(new PrimeRun(i));
            t.start();
           thread.add(t);
        }

        for (Thread t : thread) {
            if (t.isAlive()){
                try {
                    t.join();
                } catch (InterruptedException e) {

                }
            }

        }

        for (int n : primes)
            System.out.print("" + n + " ");
    }

    static boolean isPrime(int n) {
        if (n <= 1 || (n&1) == 0) return false;
        if (n == 2 || n == 3 || n == 5) return true;

        for (int i = 3; n*n <= i; i += 2)
            if (n % i == 0) return false;

        return true;
    }

    synchronized static void addPrime(int n) {
        primes.add(n);
    }

}

    class PrimeRun implements Runnable {
        public static Monitor m;
        final int ID;
        public PrimeRun(int i) {
            ID = i;
        }

        public void run() {
        for(int i=0; i < Main.MAX; i++) {
            if(i % Main.THREADS == ID)
                if(Main.isPrime(i)) 
                    m.addPrime(i);
            }
        }
    }

    class Monitor {
        public synchronized void addPrime(int n) {
            Main.addPrime(n);
        }
    }

Answer 2

You get ConcurrentModificationException because you are iterating over array while adding to it. It has nothing to do with multiple threads and will happen even in a single thread. But in your specific case it happens because threads are still adding primes when you start iterating over the list. To prevent that you must wait for all threads to finish before printing. To do it you can iterate array of threads and call join() on each one of them. Or you can use CountdownLatch.

List can be made synchronized via Collections.synchronizedList() as suggested in the other answer.

Answer 3

Reason fro ConcurrentModificationException is not bad synchronization. The reason is that you are modifying list during iteration on it.

The only iteration I found in your code is

for (int n : primes)
      System.out.print("" + n + " ");

Here is what happens. You are running several threads that do their job and add elements to collection. The code that runs threads is immediately following by code that iterates over list and prints its elements. So the iteration and your working threads are running simultaneously.

To fix this you should wait until all your working threads have finished and then print. Indeed you want to print the results only when all calculations have been finished. Check out method Thread.join() to implement this.

And obviously do what @maneesh recommended you, i.e. use Collections.synchronizedList() instead of your manual synchronization.