Parallel sieve of Eratosthenes - Java Multithreading

Question

I wanted to write sieve of Eratosthenes which will work using specific number of threads. I figured out, that it will work in following way: For 2 threads up to 17. Thread-1 takes 2, and starts to remove multiple of 2 from List. Parallel Thread-2 takes 3 and does the same. After that Thread-1 takes 5( because there is no 4 in List) and Thread-2 takes 7 and so on until they reach end. I wrote following piece of code:

private List<Integer> array = new ArrayList<Integer>();
private List<Integer> results = new ArrayList<Integer>();
public synchronized void run(){
    while(array.size() > 0){
        Integer tmp = array.get(0);
        for(int i = 1; i < array.size(); i++){
            if( (array.get(i).intValue() % tmp.intValue()) == 0)
                array.remove(i);
        }
        results.add(array.get(0));
        array.remove(0);
    }
}

public void setArray(int x){
    for(int i = 2; i < x; i++)
        array.add(Integer.valueOf(i));
}
public void printArray(){
    for(Integer i: results){
        System.out.println(i);
    }
}

This code works, but I added time measurement "tool" to my main class:

ThreadTask task = new ThreadTask();
task.setArray(5000);
Long beg = new Date().getTime();
for(int i = 0; i < 3;i++){
    new Thread(task).start();
}
Long sleep = 1000L;
Thread.sleep(sleep);// I am sleeping main thread to wait until other Threads are done
task.printArray();
System.out.println("Time is "+(new Date().getTime()-beg-sleep));

The problem is that running this with 2 threads is slower than running with 1 thread, and 3 threads are slower than 2 threads. Could anyone explain me, why?

EDIT:

There is one important thing about that. I don't need it to be done as fast as it can be. I need it working on Threads for one reason. My Teacher wants to compare runtimes of running same program with 1, 2 .. n threads. Results should look like in this graph.

EDIT2:

I have rewritten code to following

private HashMap<Integer,Boolean> array = new HashMap<Integer,Boolean>();
private int counter = 1;
private int x;
public void run(){
    while(counter < x-1){
        do{
            counter++;
        }
        while( array.get(counter));
        int tmp = counter;
        for(int i = tmp; i < array.size(); i+=tmp){
            if( i!= tmp)
                array.put(i,true);
        }
        try{
        Thread.sleep(0L, 1);
        }
        catch (Exception e){}
    }
}

public void setArray(int x){
    this.x = x;
    for(int i = 2; i < x; i++)
        array.put(i, false);
}
public void printArray(){

    for(int i = 2; i < array.size();i++){
        if( !array.get(i))
        System.out.println(i);

    }
}

Now it uses HashMap and this is how it works:

1. Fill HashMap with keys from 2 to n and false values.
2. New thread goes into while loop which is based on counter variable. Counter represents current key.
3. Increment counter on the begging so new threads doesn't operate on counter of earlier started thread.
4. Put counter value into temporary variable tmp so we can work even when another thread increment counter
5. Iterate through the HashMap by incrementing i with tmp ( it is actually jumping on the multiplies of i) and set their values to true.
6. All keys which has true value are ignored in print method. Also counter skips them when incremented.

The problem is that it still works slower with more threads. What's wrong now?

Answer 1

The mistake is simpler than I first thought. All your threads are doing the same thing so each thread does more work. To make a multi-threaded program work faster you have to divide up the work, which has to be performed concurrently.

---

When you have one thread accessing a data structure, it can be in the fastest cache of one core, use multiple threads and they need to co-ordinate their actions and since most of the work is updating the data structure, a lot of time is lost as overhead. This is the case even though your data structure is not thread safe and is likely to have a corrupted result.

BTW updating an ArrayList is very expensive and using a collection objects is also an overhead.

You will get a much faster result using a BitSet and just one thread.

public class BitSetSieveMain {
    private final BitSet set;
    private final int size;

    public BitSetSieveMain(int x) {
        size = x + 1;
        set = new BitSet(size);
        set.flip(2, size);
    }

    public static void main(String[] args) {
        for (int i = 0; i < 10; i++) {
            long start = System.nanoTime();
            BitSetSieveMain bitSetSieveMain = new BitSetSieveMain(5000);
            bitSetSieveMain.sieve();
            long time = System.nanoTime() - start;
            System.out.println(time / 1000 + " micro-seconds to perform " + bitSetSieveMain);
        }
    }

    public void sieve() {
        int i = 2;
        do {
            for (int j = i*2; j < size; j += i)
                set.clear(j);
            i = set.nextSetBit(i+1);
        } while (i > 0);
    }

    public String toString() {
        return set.toString();
    }
}

finally prints

87 micro-seconds to perform {2, 3, 5, 7, 11, 13, 17, 19, 23, 29, 31, 37, 41, 43, 47, 53, 59, 61, 67, 71, 73, 79, 83, 89, 97, 101, 103, 107, 109, 113, 127, 131, 137, 139, 149, 151, 157, 163, 167, 173, 179, 181, 191, 193, 197, 199, 211, 223, 227, 229, 233, 239, 241, 251, 257, 263, 269, 271, 277, 281, 283, 293, 307, 311, 313, 317, 331, 337, 347, 349, 353, 359, 367, 373, 379, 383, 389, 397, 401, 409, 419, 421, 431, 433, 439, 443, 449, 457, 461, 463, 467, 479, 487, 491, 499, 503, 509, 521, 523, 541, 547, 557, 563, 569, 571, 577, 587, 593, 599, 601, 607, 613, 617, 619, 631, 641, 643, 647, 653, 659, 661, 673, 677, 683, 691, 701, 709, 719, 727, 733, 739, 743, 751, 757, 761, 769, 773, 787, 797, 809, 811, 821, 823, 827, 829, 839, 853, 857, 859, 863, 877, 881, 883, 887, 907, 911, 919, 929, 937, 941, 947, 953, 967, 971, 977, 983, 991, 997, 1009, 1013, 1019, 1021, 1031, 1033, 1039, 1049, 1051, 1061, 1063, 1069, 1087, 1091, 1093, 1097, 1103, 1109, 1117, 1123, 1129, 1151, 1153, 1163, 1171, 1181, 1187, 1193, 1201, 1213, 1217, 1223, 1229, 1231, 1237, 1249, 1259, 1277, 1279, 1283, 1289, 1291, 1297, 1301, 1303, 1307, 1319, 1321, 1327, 1361, 1367, 1373, 1381, 1399, 1409, 1423, 1427, 1429, 1433, 1439, 1447, 1451, 1453, 1459, 1471, 1481, 1483, 1487, 1489, 1493, 1499, 1511, 1523, 1531, 1543, 1549, 1553, 1559, 1567, 1571, 1579, 1583, 1597, 1601, 1607, 1609, 1613, 1619, 1621, 1627, 1637, 1657, 1663, 1667, 1669, 1693, 1697, 1699, 1709, 1721, 1723, 1733, 1741, 1747, 1753, 1759, 1777, 1783, 1787, 1789, 1801, 1811, 1823, 1831, 1847, 1861, 1867, 1871, 1873, 1877, 1879, 1889, 1901, 1907, 1913, 1931, 1933, 1949, 1951, 1973, 1979, 1987, 1993, 1997, 1999, 2003, 2011, 2017, 2027, 2029, 2039, 2053, 2063, 2069, 2081, 2083, 2087, 2089, 2099, 2111, 2113, 2129, 2131, 2137, 2141, 2143, 2153, 2161, 2179, 2203, 2207, 2213, 2221, 2237, 2239, 2243, 2251, 2267, 2269, 2273, 2281, 2287, 2293, 2297, 2309, 2311, 2333, 2339, 2341, 2347, 2351, 2357, 2371, 2377, 2381, 2383, 2389, 2393, 2399, 2411, 2417, 2423, 2437, 2441, 2447, 2459, 2467, 2473, 2477, 2503, 2521, 2531, 2539, 2543, 2549, 2551, 2557, 2579, 2591, 2593, 2609, 2617, 2621, 2633, 2647, 2657, 2659, 2663, 2671, 2677, 2683, 2687, 2689, 2693, 2699, 2707, 2711, 2713, 2719, 2729, 2731, 2741, 2749, 2753, 2767, 2777, 2789, 2791, 2797, 2801, 2803, 2819, 2833, 2837, 2843, 2851, 2857, 2861, 2879, 2887, 2897, 2903, 2909, 2917, 2927, 2939, 2953, 2957, 2963, 2969, 2971, 2999, 3001, 3011, 3019, 3023, 3037, 3041, 3049, 3061, 3067, 3079, 3083, 3089, 3109, 3119, 3121, 3137, 3163, 3167, 3169, 3181, 3187, 3191, 3203, 3209, 3217, 3221, 3229, 3251, 3253, 3257, 3259, 3271, 3299, 3301, 3307, 3313, 3319, 3323, 3329, 3331, 3343, 3347, 3359, 3361, 3371, 3373, 3389, 3391, 3407, 3413, 3433, 3449, 3457, 3461, 3463, 3467, 3469, 3491, 3499, 3511, 3517, 3527, 3529, 3533, 3539, 3541, 3547, 3557, 3559, 3571, 3581, 3583, 3593, 3607, 3613, 3617, 3623, 3631, 3637, 3643, 3659, 3671, 3673, 3677, 3691, 3697, 3701, 3709, 3719, 3727, 3733, 3739, 3761, 3767, 3769, 3779, 3793, 3797, 3803, 3821, 3823, 3833, 3847, 3851, 3853, 3863, 3877, 3881, 3889, 3907, 3911, 3917, 3919, 3923, 3929, 3931, 3943, 3947, 3967, 3989, 4001, 4003, 4007, 4013, 4019, 4021, 4027, 4049, 4051, 4057, 4073, 4079, 4091, 4093, 4099, 4111, 4127, 4129, 4133, 4139, 4153, 4157, 4159, 4177, 4201, 4211, 4217, 4219, 4229, 4231, 4241, 4243, 4253, 4259, 4261, 4271, 4273, 4283, 4289, 4297, 4327, 4337, 4339, 4349, 4357, 4363, 4373, 4391, 4397, 4409, 4421, 4423, 4441, 4447, 4451, 4457, 4463, 4481, 4483, 4493, 4507, 4513, 4517, 4519, 4523, 4547, 4549, 4561, 4567, 4583, 4591, 4597, 4603, 4621, 4637, 4639, 4643, 4649, 4651, 4657, 4663, 4673, 4679, 4691, 4703, 4721, 4723, 4729, 4733, 4751, 4759, 4783, 4787, 4789, 4793, 4799, 4801, 4813, 4817, 4831, 4861, 4871, 4877, 4889, 4903, 4909, 4919, 4931, 4933, 4937, 4943, 4951, 4957, 4967, 4969, 4973, 4987, 4993, 4999}