Multithreaded Java does not speed up

Question

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.000 cache size      : 3072 KB physical id     : 0 siblings        : 4 core id         : 0 cpu cores       : 2 apicid          : 0 initial apicid  : 0 fdiv_bug        : no hlt_bug         : no f00f_bug        : no coma_bug        : no fpu             : yes fpu_exception   : yes cpuid level     : 13 wp              : yes flags           : fpu vme de pse tsc msr pae mce cx8 apic sep mtrr pge mca cmov pat pse36 clflush dts acpi mmx fxsr sse sse2 ss ht tm pbe nx rdtscp lm constant_tsc arch_perfmon pebs bts xtopology nonstop_tsc aperfmperf pni pclmulqdq dtes64 monitor ds_cpl vmx est tm2 ssse3 cx16 xtpr pdcm sse4_1 sse4_2 x2apic popcnt xsave avx lahf_lm ida arat epb xsaveopt pln pts dts tpr_shadow vnmi flexpriority ept vpid bogomips        : 4589.60 clflush size    : 64 cache_alignment : 64 address sizes   : 36 bits physical, 48 bits virtual power management: 

Answer 1

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.

Answer 2

The Core i5 has 2 cores and hyperthreading technology so it seems that it has 4 cores. Those extra two logical cores will not help nearly as much as two physical cores since your sorting algorithm does a good job at keeping the CPU busy.

Since you asked for a "credible" source, I will point to an article from the Intel website that I read a while back: performance-insights-to-intel-hyper-threading-technology. In particular note the following section on "limitations of hyperthreading":

Extremely compute-efficient applications. If the processor's execution resources are already well utilized, then there is little to be gained by enabling Intel HT Technology. For instance, code that already can execute four instructions per cycle will not increase performance when running with Intel HT Technology enabled, as the process core can only execute a maximum of four instructions per cycle.

Also note this section about the memory subsystem contention:

Extremely high memory bandwidth applications. Intel HT Technology increases the demand placed on the memory subsystem when running two threads. If an application is capable of utilizing all the memory bandwidth with Intel HT Technology disabled, then the performance will not increase when Intel HT Technology is enabled. It is possible in some circumstances that performance will degrade, due to increased memory demands and/or data caching effects in these instances. The good news is that systems based on the Nehalem core with integrated memory controllers and Intel® QuickPath Interconnects greatly increase available memory bandwidth compared to older Intel CPUs with Intel HT technology. The result is that the number of applications that will experience a degradation using Intel HT Technology on the Nehalem core due to lack of memory bandwidth is greatly reduced.

Other interesting points can be found in the Intel Guide for Developing Multithreaded Applications. Here is another snippet from detecting-memory-bandwidth-saturation-in-threaded-applications:

As an increasing number of threads or processes share the limited resources of cache capacity and memory bandwidth, the scalability of a threaded application can become constrained. Memory-intensive threaded applications can suffer from memory bandwidth saturation as more threads are introduced. In such cases, the threaded application won’t scale as expected, and performance can be reduced.