Multithreaded Java does not speed up

Asked 2011-11-15T14:53:30.933

I have implemented a simple parallel merge sort algorithm in Java. This cuts the array into equal sections and passes them to be sorted independently by each thread. After the array segments are sorted, they are merged by a single thread. Because there are no shared resources, so no synchronization is used when the sub lists are sorted. The last thread which merges the result array though waits for the other threads to complete.

When two threads are used there is performance gain almost 66%. When I use 4 threads, then the time taken does not differ from the 2 threads version. I am on linux 2.6.40.6-0.fc15.i686.PAE, and an Intel Core i5 .

I am benchmarking time with the unix time command (array is assigned uniform random integers). At the end of the sorting I am checking if the array ordering is correct or not (not parallel).

1 Thread

$ echo "100000000" | time -p java mergeSortTest

Enter n: 
[SUCCESS]

real 40.73
user 40.86
sys 0.22

2 Threads

$ echo "100000000" | time -p java mergeSortTest

Enter n: 
[SUCCESS]

real 26.90
user 49.65
sys 0.48

4 Threads

$ echo "100000000" | time -p java mergeSortTest

Enter n: 
[SUCCESS]

real 25.13
user 76.53
sys 0.43

The CPU usage is around 80% to 90% when using 4 threads, and around 50% when using 2 threads, and around 25% when using single thread.

I was expecting some speedup when run in 4 threads. Am I wrong anywhere.

UPDATE 1

Here is the code: http://pastebin.com/9hQPhCa8

UPDATE 2 I have a Intel Core i5 second generation processor.

Output of cat /proc/cpuinfo | less (only core 0 is shown).

processor       : 0
vendor_id       : GenuineIntel
cpu family      : 6
model           : 42
model name      : Intel(R) Core(TM) i5-2410M CPU @ 2.30GHz
stepping        : 7
cpu MHz         : 800.0

java multithreading

Edit Report

2 Answers

The intel core i5-xxM series has 2 cores so using more than 2 threads will reduce performance due to more context switching.

Edit:

Here is an expansion on my answer where I take up Core i7 architecture-specific factors that may affect the performance of a CPU and memory intensive operations such as a sort.

Turbo boost technology

Intel Core i7 has variable processor frequency. At high loads, the frequency will be limited by heat, reducing the performance gain of utilising more cores.

Shared L3 cache

Sorting large data sets (>>8 Mb) will result in a lot of L3 page faults. Using too many threads may increase the number of page faults, decreasing efficiency. I'm not sure if that is the case for a mergesort. (BTW: how do you measure L3 cache misses in Linux?) I am not sure this is a factor, though.

I must say that I am surprised that you don't get any performance boost from using all four cores of the i7. I'll try to run some tests at home this weekend.

answered 2011-11-15T15:53:14.853

As a comparison, try using merge sort with java 7 and the fork join framework. There is an example of how to do that here. This will show you if it is a problem with your implementation, or a limitation of the machine.

answered 2011-11-15T15:02:23.160

Multithreaded Java does not speed up

2 Answers

Your Answer