Why this piece of Java code is not running concurrently

Question

I have written Sieve of Eratosthenes which is supposed to work in parallel, but it's not. When I increase number of threads, time of computing is not getting lower. Any ideas why?

Main class

import java.util.Date;
import java.util.concurrent.ExecutorService;
import java.util.concurrent.Executors;

public class ConcurrentTest {
    public static void main(String[] args) throws InterruptedException {
        Sieve task = new Sieve();
        int x = 1000000;
        int threads = 4;
        task.setArray(x);
        Long beg = new Date().getTime();
        ExecutorService exec = Executors.newCachedThreadPool();
        for (int i = 0; i < threads; i++) {
            exec.execute(task);
        }
        exec.shutdown();
        Long time = 0L;
    // Main thread is waiting until all threads are terminated
    // ( it means that computing is done)
        while (true)
            if (exec.isTerminated()) {
                time = new Date().getTime() - beg;
                break;
            }

        System.out.println("Time is " + time);
    }
}

Sieve class

import java.util.concurrent.ConcurrentHashMap;

public class Sieve implements Runnable {
    private ConcurrentHashMap<Integer, Boolean> array = 
                       new ConcurrentHashMap<Integer, Boolean>();
    private int x;
    public void run() {
        while(true){
    // I am getting synchronized number to check if it's prime
            int n = getCounter();
    // If no more numbers to check, stop loop
            if( n == -1)
                break;
    // If HashMap contains number, we can further
            if(!array.containsKey(n))continue;
            for (int i = 2 * n; i <= x; i += n) {
    // Compound numbers are removed from HashMap, Eg. 6, 12 and much more.
                    array.remove(i);
            }
        }
    }
    private synchronized int getCounter(){
        if( counter < x)
            return counter++;
        else return -1;
    }
    public void setArray(int x) {
        this.x = x;
        for (int i = 2; i <= x; i++)
            array.put(i, false);
    }
}

I made some tests with different number of threads. These are results:

Nr of threads 1    Time is 1850, 1795, 1825
Nr of threads 2    Time is 1845, 1836, 1814
Nr of threads 3    Time is 1767, 1820, 1756
Nr of threads 4    Time is 1732, 1840, 2083
Nr of threads 5    Time is 1791, 1795, 1803
Nr of threads 6    Time is 1825, 1728, 1707
Nr of threads 7    Time is 1754, 1729, 1686
Nr of threads 8    Time is 1760, 1717, 1817
Nr of threads 9    Time is 1721, 1699, 1673
Nr of threads 10   Time is 1661, 1722, 1718

Answer 1

When I increase number of threads, time of computing is not getting lower

tl;dr: your problem size is too small. If you increase x to 10000000, the differences will become more obvious. They won't be what you're expecting, though.

I tried your code on an eight core machine with two slight modifications:

1. For timing, I used System.nanoTime() instead of getTime() on a Date.
2. I used the awaitTermination method of ExecutorService rather than a spinloop to check for the end of run.

I tried launching your Sieve tasks using a fixed thread pool, a cached thread pool and a fork join pool and comparing the results of different values for your thread variable.

I see the following results (in milliseconds) on my machine with x=10000000:

    Thread count      = 1    2    4    8    16
    Fixed thread pool = 5451 3866 3639 3227 3120
    Cached thread pool= 5434 3763 3709 3258 3078
    Fork-join pool    = 6732 3670 3735 3190 3102

What these results show us is a clear benefit of changing from a single thread of execution to two threads. However, the benefit of additional threads drops off rapidly. There's an interesting plateau going from two to four threads and marginal benefits up to 16.

In addition, you can also see that the different threading mechanisms have different initial overhead: I didn't expect the Fork-Join pool to cost that much more to start than the other mechanisms.

So, as written, you shouldn't really expect a benefit past two threads for small but non-trivial problem sets.

If you'd like to increase the benefit of additional threads, you're going to need to look at your current implementation. For example, when I switched from your synchronized getCounter() to an AtomicInteger using incrementAndGet(), I eliminated the overhead of the synchronized method. The result is that all of my four thread numbers dropped on the order of 1000 milliseconds.