Why is my multi threading not efficient?

Question

I've designed a class that fills an array with integers using a various number of threads, in order to see the power of multi threading. But according to my result, there is none...

The idea: The idea was too fill an array of 100000000 integers with the value "1". Starting with 1 thread (one threads fills the whole array) and incrementing it until 100 threads (each thread fills a sub array of size 100000000/nbThreads)

Example: With 10 threads, I create 10 threads and each is filling an array of 10000000 integers.

Here is my code:

public class ThreadedArrayFilling extends Thread{
    private int start;
    private int partitionSize;
    public static int[] data;
    public static final int SIZE = 100000000;
    public static final int NB_THREADS_MAX = 100;


    public static void main(String[] args){
        data = new int[SIZE];
        long startTime, endTime;
        int partition, startIndex, j;
        ThreadedArrayLookup[] threads;

        for(int i = 1; i <= NB_THREADS_MAX; i++){       
            startTime = System.currentTimeMillis();
            partition = SIZE / i;
            startIndex = 0;
                threads = new ThreadedArrayLookup[i];
            for(j = 0; j < i; j++){         
                threads[j] = new ThreadedArrayLookup(startIndex, partition);
                startIndex += partition;
            }
            for(j = 0; j < i; j++){
                try {
                    threads[j].join();
                } catch (InterruptedException e) {
                    // TODO Auto-generated catch block
                    e.printStackTrace();
                }
            }
            endTime = System.currentTimeMillis();       
            System.out.println(i + " THREADS: " + (endTime - startTime) + "ms");
        }
    }

    public ThreadedArrayFilling(int start, int size){
        this.start = start;
        this.partitionSize = size;
        this.start();
    }

    public void run(){
        for(int i = 0; i < this.partitionSize; i++){
            data[this.start + i] = 1;
        }
    }

    public static String display(int[] d){
        String s = "[";

        for(int i = 0; i < d.length; i++){
            s += d[i] + ", ";
        }

        s += "]";
        return s;
    }

}

And here are my results:

1 THREADS: 196ms
2 THREADS: 208ms
3 THREADS: 222ms
4 THREADS: 213ms
5 THREADS: 198ms
6 THREADS: 198ms
7 THREADS: 198ms
8 THREADS: 198ms
9 THREADS: 198ms
10 THREADS: 206ms
11 THREADS: 201ms
12 THREADS: 197ms
13 THREADS: 198ms
14 THREADS: 204ms
15 THREADS: 199ms
16 THREADS: 203ms
17 THREADS: 234ms
18 THREADS: 225ms
19 THREADS: 235ms
20 THREADS: 235ms
21 THREADS: 234ms
22 THREADS: 221ms
23 THREADS: 211ms
24 THREADS: 203ms
25 THREADS: 206ms
26 THREADS: 200ms
27 THREADS: 202ms
28 THREADS: 204ms
29 THREADS: 202ms
30 THREADS: 200ms
31 THREADS: 206ms
32 THREADS: 200ms
33 THREADS: 205ms
34 THREADS: 203ms
35 THREADS: 200ms
36 THREADS: 206ms
37 THREADS: 200ms
38 THREADS: 204ms
39 THREADS: 205ms
40 THREADS: 201ms
41 THREADS: 206ms
42 THREADS: 200ms
43 THREADS: 204ms
44 THREADS: 204ms
45 THREADS: 206ms
46 THREADS: 203ms
47 THREADS: 204ms
48 THREADS: 204ms
49 THREADS: 201ms
50 THREADS: 205ms
51 THREADS: 204ms
52 THREADS: 207ms
53 THREADS: 202ms
54 THREADS: 207ms
55 THREADS: 207ms
56 THREADS: 203ms
57 THREADS: 203ms
58 THREADS: 201ms
59 THREADS: 206ms
60 THREADS: 206ms
61 THREADS: 204ms
62 THREADS: 201ms
63 THREADS: 206ms
64 THREADS: 202ms
65 THREADS: 206ms
66 THREADS: 205ms
67 THREADS: 207ms
68 THREADS: 210ms
69 THREADS: 207ms
70 THREADS: 203ms
71 THREADS: 207ms
72 THREADS: 205ms
73 THREADS: 203ms
74 THREADS: 211ms
75 THREADS: 202ms
76 THREADS: 207ms
77 THREADS: 204ms
78 THREADS: 212ms
79 THREADS: 203ms
80 THREADS: 210ms
81 THREADS: 206ms
82 THREADS: 205ms
83 THREADS: 203ms
84 THREADS: 203ms
85 THREADS: 209ms
86 THREADS: 204ms
87 THREADS: 206ms
88 THREADS: 208ms
89 THREADS: 263ms
90 THREADS: 216ms
91 THREADS: 230ms
92 THREADS: 216ms
93 THREADS: 230ms
94 THREADS: 234ms
95 THREADS: 234ms
96 THREADS: 217ms
97 THREADS: 229ms
98 THREADS: 228ms
99 THREADS: 215ms
100 THREADS: 232ms

What did I miss?

EDIT: Additional infos:

My machine is running a dual core.

Expectations:

• I was expecting to see a huge increase in performances between 1 and 2 threads (to make use of the dual core)
• I was also expecting to see a slowdown after that for a large number of threads.

But this verifies none of my expectations. Are my expectations false, or is this a problem with my algo?

Answer 1

With two cores, the best performance you could possibly expect is 2 threads taking half the time as one thread. Any additional threads are only creating useless overhead after that - assuming that you're completely CPU-bound, but you are actually not.

The question is why you're not seeing an improvement when going from 1 to 2 threads. And the reason is probably that your program is not CPU-bound, but memory-bound. Your bottleneck is main memory access, and the 2 threads are just taking turns writing to main memory. The actual CPU cores are doing nothing most of the time. You'll see the expected difference if instead of doing little actual work on a large area of memory you do a lot of CPU-intensive work on a small amount of memory. Because then each CPU core can work completel inside its cache.