StackOverflow2013

Note that there are some explanatory texts on larger screens.

plurals

POMultithreaded Java does not speed up
text
Body
copied!<p>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.</p> <p>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 <code>2.6.40.6-0.fc15.i686.PAE</code>, and an Intel Core i5 .</p> <p>I am benchmarking time with the unix <code>time</code> 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).</p> 1 Thread <pre> $ echo "100000000" | time -p java mergeSortTest Enter n: [SUCCESS] real 40.73 user 40.86 sys 0.22 </pre> 2 Threads <pre> $ echo "100000000" | time -p java mergeSortTest Enter n: [SUCCESS] real 26.90 user 49.65 sys 0.48 </pre> 4 Threads <pre> $ echo "100000000" | time -p java mergeSortTest Enter n: [SUCCESS] real 25.13 user 76.53 sys 0.43 </pre> <p>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.</p> <p>I was expecting some speedup when run in 4 threads. Am I wrong anywhere.</p> <p><strong>UPDATE 1</strong></p> <p>Here is the code: <a href="http://pastebin.com/y0gmaDCA" rel="nofollow">http://pastebin.com/9hQPhCa8</a></p> <p><strong>UPDATE 2</strong> I have a Intel Core i5 second generation processor.</p> <p>Output of <code>cat /proc/cpuinfo | less</code> (only core 0 is shown).</p> <pre> 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: </pre>

Querying!

Guidance

An individual column

Larger individual text columns get their own page to allow for proper reading.

SQuiL has stopped working due to an internal error.

If you are curious you may find further information in the browser console, which is accessible through the devtools (F12).

Reload