logo标签列表

多线程Java并不能提高速度

javamultithreading
30
我已在Java中实现了一个简单的并行归并排序算法。这将数组划分成相等的部分，并将它们传递给每个线程独立地排序。在数组段被排序后，它们由单个线程合并。因为没有共享资源，所以在子列表排序时不需要同步。然而，最后一个线程合并结果数组时会等待其他线程完成。
使用两个线程时，性能提高了近66％。当我使用4个线程时，所需的时间与2个线程版本无异。我的系统是Linux 2.6.40.6-0.fc15.i686.PAE，处理器是Intel Core i5。
使用unix time命令（数组分配均匀的随机整数）对时间进行基准测试。在排序结束时，我会检查数组是否正确排序（非并行）。
使用4个线程时，CPU使用率约为80％至90％；使用2个线程时，CPU使用率约为50％；使用单个线程时，CPU使用率约为25％。
我本来期望在使用4个线程时有所加速。请问我有哪里出错了？
附：UPDATE 1这是代码：http://pastebin.com/9hQPhCa8。UPDATE 2我使用的处理器是Intel Core i5第二代。

cat /proc/cpuinfo | less 命令的输出结果（只显示核心0）。

处理器编号   ：0
供应商ID     ：GenuineIntel
CPU系列       ：6
型号         ：42
型号名称      ：Intel(R) Core(TM) i5-2410M CPU @ 2.30GHz
步进         ：7
CPU主频      ：800.000 MHz
缓存大小      ：3072 KB
物理ID       ：0
同级处理器个数：4
核心编号     ：0
CPU核心数量   ：2
APIC ID     ：0
初始APIC ID  ：0
fdiv_bug    ：不受影响
hlt_bug     ：不受影响
f00f_bug    ：不受影响
coma_bug    ：不受影响
FPU支持      ：是
FPU异常支持   ：是
cpuid level ：13
wp          ：启用了写保护
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大小 ：64
缓存对齐方式   ：64
地址位数     ：物理36位，虚拟48位
电源管理     ：
7
Core i5只有两个物理核心，对吗？ - trojanfoe
1
@Ted Hopp，部分Core i5有4个核心，而另一些则只有2个核心。 - Nettogrof
3
我认为并不是所有的Core i5都相同 - 旧款的只有2个物理核心和2个超线程核心。你需要确定你使用的是哪种Core i5。 - trojanfoe
3
即使使用四核处理器，除非输入的数组足够长以至于并行排序所花费的时间远远大于最终合并过程的时间，否则您可能不会注意到任何改进。 - Mister Smith
6
谨防天真的微基准测试所带来的风险。想要宣称某个程序比另一个程序快X％，你需要针对不同的输入规模和机器配置运行大量测试。这里有一篇由Goetz撰写的好论文：http://www.ibm.com/developerworks/java/library/j-jtp02225/index.html - Mister Smith
显示剩余13条评论
8个回答
10

Intel Core i5-xxM系列有2个核心，因此使用超过2个线程将会降低性能，因为会有更多的上下文切换。

编辑：

在这里，我对Core i7架构特定因素进行了扩展，这些因素可能会影响CPU和内存密集型操作（如排序）的性能。

睿频技术

Intel Core i7具有可变处理器频率。在高负载情况下，频率将受热量限制，降低利用更多核心的性能增益。

共享L3缓存

对大数据集（>>8 Mb）进行排序将导致大量的L3页故障。使用太多的线程可能会增加页面故障的数量，降低效率。不确定对于归并排序是否是这种情况。（顺便说一下：如何在Linux中测量L3缓存未命中？）虽然我不确定这是否是一个因素。

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

13
请注意，这个说法并不是普遍正确的。它只适用于CPU密集型进程。例如，如果你正在进行一些IO轮询，通过添加超过可用核心数的线程，你可以大幅提高整体性能。 - Bruno Reis
1
此外，他的特定处理器可能有2个核心，但它支持4个并发线程。详细信息在这里 - icirellik
除非他在BIOS中禁用了超线程。 - sarumont
9
Core i5有2个核心和超线程技术，所以看起来它有4个核心。这两个额外的逻辑核心不会像两个物理核心那样有很大帮助，因为你的排序算法已经很好地让CPU保持繁忙状态。
既然你要求“可信”的来源，我会指向我之前读过的Intel网站上的一篇文章：performance-insights-to-intel-hyper-threading-technology。特别是请注意“超线程的限制”部分：
极其计算密集型的应用程序。如果处理器的执行资源已经得到很好的利用，那么启用Intel HT技术将无济于事。例如，可以每个周期执行四条指令的代码在启用Intel HT技术时不会增加性能，因为进程内核每个周期只能执行最多四条指令。
还请注意关于内存子系统争用的部分：
极高的内存带宽应用程序。当运行两个线程时，Intel HT技术会增加对内存子系统的需求。如果一个应用程序在禁用Intel HT技术时就能够利用所有的内存带宽，那么启用Intel HT技术将不会增加性能。在某些情况下，性能可能会降低，因为这些情况下增加了内存需求和/或数据缓存效应。好消息是，基于Nehalem核心、具有集成内存控制器和Intel® QuickPath互连技术的系统相对于具有Intel HT技术的旧版Intel CPU大大增加了可用内存带宽。结果是，在Nehalem核心上使用Intel HT技术由于缺乏内存带宽而导致性能下降的应用程序数量大大减少。
其他有趣的观点可以在Intel多线程应用程序开发指南中找到。以下是来自检测线程应用程序中内存带宽饱和的方法的另一个片段：
随着越来越多的线程或进程共享缓存容量和内存带宽有限的资源，线程应用程序的可扩展性可能会受到限制。内存密集型的线程应用程序在引入更多线程时可能会遭受内存带宽饱和。在这种情况下，线程应用程序的扩展性不会像预期的那样，并且性能可能会降低。
根据@Peters Lawrey的说法，即使使用Core i7处理器也没有任何性能提升，这该如何描述呢？ - phoxis
1
Core i7有4个核心，但它们很可能在单个内存总线上竞争，这也会影响性能。我还在答案中添加了一句引言来说明这一点。 - Tudor
4
3

我在i7上试过这个，即使有4个核心，从2到4个线程也没有任何改善。我怀疑问题是你的数据不适合缓存，所以你正在测试单个内存总线的吞吐量。

2
@phoxis：看起来你的i5有2个L2缓存（每个核心一个）和一个共享的L3缓存，这可能允许2个线程具有良好的缓存命中率，而4个线程可能会花费大量开销在缓存未命中上。至于Peter和他的i7，我不确定型号，但是可能有4个L2缓存和共享的L3缓存，我预计在4个线程下会看到更好的性能 - 也许它是4核心8超线程，导致工作在一个核心上的2个线程引起了与i5上可能看到的相同的L2抖动。Peter，也许尝试8个线程？ - philwb
2个线程比1个线程快大约70％，但4、8和16个线程的速度都相同。 - Peter Lawrey
3

在双核i7上使用-server JVM选项、100000000个整数和2GB Xmx内存时，我得到了预期的结果：

1个线程：23秒
2个线程：14秒
4个线程：10秒

而且我还去掉了手动垃圾回收，并在同一个JVM实例中按顺序执行排序，先进行热身排序。

正如Smith先生所评论的那样，微基准测试（JVM hotspot）相当复杂。对于4个或更多核心，归并排序可以由一半的线程数量执行，与现在单线程执行有所不同，因此您的基准测试并不完全符合多线程方法。

您可能还想查看此问题。

2
作为比较，尝试使用Java 7和Fork/Join框架进行归并排序。这里有一个示例在此处。这将向您展示问题是您的实现问题还是机器的限制。
1

很有趣，因为我在尝试并行合并排序时也有同样的观察。尝试了两种不同的工作生成方法，但没有获得加速。我的并行合并排序方法是使合并过程并行化，并在不同的核心上执行单个合并？在这种情况下，递归截止和线程数影响加速。再次强调，加速不能超过串行速度。这种技术出现在Morgan Kaufman的《结构化并行编程模式与实践》一书中。

并行合并排序

0

我最近不得不做一份论文，比较了i7架构下的冒泡排序、归并排序和双调排序。我使用这里提供的第一个代码来进行归并，并且遇到了同样的问题：8个线程并没有比4个更好。之后我阅读了SMT（英特尔超线程）相关内容，并找到了问题和解决方案：

在归并方法中删除这些行：

if (Runtime.getRuntime().freeMemory() < ((n1 + n2) * 4)) Runtime.getRuntime().gc();

这段代码释放了L1和L2级别物理核的内存，但是在那几KB中我们有两个逻辑线程的缓冲区（不仅仅是一个），因此一个线程会擦除该物理核上兄弟线程的缓冲区。

删除了这个if之后，我看到了SMT提供的4个和8个线程之间1.25倍的改进。如果有人能在i5上尝试一下那就太好了。

如果您能编辑上述内容以删除其中的几个错误，那将非常有帮助。 - Hot Licks
网页内容由stack overflow 提供, 点击上面的
可以查看英文原文，
原文链接