java - 多线程Java没有加速

Question

我在 Java 中实现了一个简单的并行合并排序算法。这会将数组分成相等的部分，并将它们传递给每个线程独立排序。数组段排序后，由单个线程合并。因为没有共享资源，所以子列表排序时不使用同步。合并结果数组的最后一个线程等待其他线程完成。

当使用两个线程时，性能提升近 66%。当我使用 4 个线程时，所花费的时间与 2 个线程版本没有区别。我在 linux 2.6.40.6-0.fc15.i686.PAE 和 Intel Core i5 上。

我正在使用 unix time 命令对时间进行基准测试(数组被分配了统一的随机整数)。在排序结束时，我正在检查数组排序是否正确(不平行)。

1 线程

$ echo "100000000" | time -p java mergeSortTest

Enter n: 
[SUCCESS]

real 40.73
user 40.86
sys 0.22

2 线程

$ echo "100000000" | time -p java mergeSortTest

Enter n: 
[SUCCESS]

real 26.90
user 49.65
sys 0.48

4 线程

$ echo "100000000" | time -p java mergeSortTest

Enter n: 
[SUCCESS]

real 25.13
user 76.53
sys 0.43

使用 4 线程时 CPU 使用率约为 80% 到 90%，使用 2 线程时约为 50%，使用单线程时约为 25%。

我期待在 4 个线程中运行时会有所加快。我是不是哪里错了。

更新 1

这里是代码:http://pastebin.com/9hQPhCa8

更新 2 我有一个 Intel Core i5 第二代处理器。

cat/proc/cpuinfo 的输出 |少(只显示核心0)。

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

intel core i5-xxM系列有 2 个内核，因此使用超过 2 个线程会由于更多的上下文切换而降低性能。

编辑:

这是我的答案的扩展，我使用了 Core i7 architecture - 可能影响 CPU 性能和内存密集型操作(例如排序)的特定因素。

涡轮增压技术

英特尔酷睿 i7 具有可变处理器频率。在高负载时，频率会受到热量的限制，从而降低使用更多内核的性能增益。

共享 L3 缓存

对大型数据集 (>>8 Mb) 进行排序会导致很多 L3 页面错误。使用过多的线程可能会增加页面错误的数量，从而降低效率。我不确定合并排序是否属于这种情况。 (顺便说一句:你如何测量 Linux 中的 L3 缓存未命中？) 不过，我不确定这是一个因素。

我必须说，我很惊讶使用 i7 的所有四个内核并没有获得任何性能提升。这个周末我会尝试在家里进行一些测试。