为什么Java多线程不能使线程数量线性增加

Question

我的Java多线程代码如下所示。我预计，如果我使用n线程(n<可用内核)，总执行时间将是使用单个线程的1/n。但实验结果并没有证明这一点：1个线程4128ms，2个线程2200ms，3个线程3114ms，4个线程3031ms。

public static void main(String[] args) {
List<Document> doc = createDocuments(50000);
int numThreads = 4;
List<List> partitionedDocs = partitionData(doc, numThreads);
CountDownLatch latch = new CountDownLatch(numThreads);
List<Thread> threads = new ArrayList<>();
List<Runnable> executors = new ArrayList<>();
for (List input : partitionedDocs) {
Runnable executor = new SplitDocuments(input, " ", latch);
executors.add(executor);
threads.add(new Thread(executor));
}
for (Thread t : threads) {
t.start();
}
try {
latch.await();
} catch (InterruptedException e) {
e.printStackTrace();
}

对于主要使用的方法：

public static List<Document> createDocuments(Integer size) {
List<Document> x = new ArrayList<>();
String text = "";
for (int i=0; i<500; i++) {
text += "abc ";
}
for (int i=0; i<size; i++) {
Document doc = new Document(i, text);
x.add(doc);
}
return x;
}
private static List<List> partitionData(List input, int numThreads) {
List<List> results = new ArrayList<>();
int subListSize = input.size()/numThreads;
for (int i=0; i<numThreads; i++) {
if (i==numThreads-1) {
results.add(input.subList(i*subListSize, input.size()));
}
else {
results.add(input.subList(i*subListSize, (i+1)*subListSize));
}
}
return results;
}

对于SplitDocument类：

public class SplitDocuments implements Runnable {
private String splitter;
private List<Document> docs = new ArrayList<>();
private CountDownLatch latch;
private List<Document> result = new ArrayList<>();
public SplitDocuments(List<Document> docs, String splitter, CountDownLatch latch) {
this.docs = docs;
this.splitter = splitter;
this.latch = latch;
}
@Override
public void run() {
System.out.println("number of docs: " + this.docs.size());
long start = System.currentTimeMillis();
for (Document t : this.docs) {
Document temp = new Document(t);
temp.setTokens(Arrays.asList(t.text.split(this.splitter)));
this.result.add(temp);
}
this.latch.countDown();
System.out.println(String.format("split documents costs: %d ms", System.currentTimeMillis() - start));
}
public List<Document> getResult() {
return result;
}
}

Answer 1

我不确定我能不能具体说明你的时间安排，因为还不清楚你是如何准确测量/计算数字的，但你是对的，"多线程处理不会使线程数量线性增加1/n"；在大多数情况下。为什么？

我相信你听说过Amdahl定律(https://en.wikipedia.org/wiki/Amdahl%27s_law)。您可以实现"；1/n"；只有当您没有程序的任何顺序部分，即程序中无法并行化的部分时。但是，即使您自己的代码/业务逻辑/算法(或其要并行化的部分)没有这样的部分，也有执行代码的底层软件和硬件层，这些层可能会因为某些资源的争用而引入一些顺序部分。例如，通过单模光纤或单双绞线，一次只能传输一个以太网数据包；您的硬盘驱动器一次只能在其磁头的一个位置写入数据；由于前端总线和内存总线，您可以顺序访问主内存；L2/L3高速缓存失效需要额外的工作来同步；翻译后备缓冲器(TLB)未命中导致走到主存储器(参见上面关于前侧总线和存储器总线的内容)；要在堆中的JVM中分配一个新对象(当线程本地分配缓冲区(TLAB)已满时)，需要一些内部同步；在压缩时，您可以在GC上获得stop-theworld暂停，这看起来像是代码的顺序部分；类加载和JIT的活动将它们的顺序相似部分添加到应用程序中；第三方库可以对静态值进行一些同步；等等。

所以，你可以看到"；1/n"；只有在非常简单的情况下，应用程序代码和底层都没有使用任何共享资源。以下是的示例

public class Test {
public static int NUM_OF_THREADS = 4;
public static int NUM_OF_ITERATIONS = 100_000_000;
static class Job extends Thread {
private final AtomicLong counter = new AtomicLong();
@Override
public void run() {
for (int i = 0; i < NUM_OF_ITERATIONS; i++) {
counter.incrementAndGet();
}
}
}
public static void main(String[] args) throws Exception {
final Job[] jobs = new Job[NUM_OF_THREADS];
for (int i = 0; i < jobs.length; i++) {
jobs[i] = new Job();
}
final long startNanos = System.nanoTime();
for (Job job : jobs) {
job.start();
}
for (Job job : jobs) {
job.join();
}
final long spentNanos = System.nanoTime() - startNanos;
System.out.printf("Time spent (s): %f%n", (spentNanos / 1_000_000_000d));
}
}

每个线程递增其自己的计数器实例。对于NUM_OF_THREADS={1,2,3,4}，我得到相同的执行时间~0.6秒。这意味着我们有"；1/n"；。我们增加了计算次数，但不会花费更多时间。我们不分配新的内存，因此我们不会经历GC暂停，因此我们不在线程之间共享任何数据(一个单独的计数器/volatile long位于所有者核心的一级缓存中)

现在，让我们在线程之间共享一个资源。现在，线程递增计数器的一个实例。这将导致缓存失效和密集的核心间通信：

public class Test {
...
private static final AtomicLong counter = new AtomicLong();
...
static class Job extends Thread {
@Override
public void run() {
for (int i = 0; i < NUM_OF_ITERATIONS; i++) {
counter.incrementAndGet();
}
}
}
...

经过如此小的修改，我们看到性能急剧下降。4个线程花费了~8秒来完成所有迭代8秒vs 0.6秒(！)

这说明，仅仅理解big-O这样的理论事物是不够的，但了解事物在引擎盖下是如何工作的，计算机是如何准确执行我们的代码的，这一点非常重要。重要的是要有一个性能模型，即使是一个非常简化的模型。

更新：将度量值添加到代码中后。。。您的测量看起来是正确的，以及您如何对输入数据进行分区。这意味着您在执行过程中确实有一个隐藏的顺序部分。玩过代码后，我认为您遇到了内存管理瓶颈，您在代码中分配了太多内存，这会影响执行。我到底做了什么。。。

我接受了您的代码并添加了一个伪Document类。然后，我尝试配置JVM，让所有数据都适合Eden/Young一代，选项是：-Xmx8G -Xms8G -XX:NewRatio=10 -XX:+PrintGCDetails

numThreads=1的运行提供了约1秒，numThreads＝4的运行提供约0.2x-0.3x秒。比率为~1/4-1/3。这是意料之中的事。GC详细信息如下：

Heap
PSYoungGen      total 2446848K, used 1803997K [0x0000000715580000, 0x00000007c0000000, 0x00000007c0000000)
eden space 2097664K, 86% used [0x0000000715580000,0x0000000783737448,0x0000000795600000)
from space 349184K, 0% used [0x00000007aab00000,0x00000007aab00000,0x00000007c0000000)
to   space 349184K, 0% used [0x0000000795600000,0x0000000795600000,0x00000007aab00000)
ParOldGen       total 5592576K, used 0K [0x00000005c0000000, 0x0000000715580000, 0x0000000715580000)
object space 5592576K, 0% used [0x00000005c0000000,0x00000005c0000000,0x0000000715580000)
Metaspace       used 2930K, capacity 4494K, committed 4864K, reserved 1056768K
class space    used 299K, capacity 386K, committed 512K, reserved 1048576K

你看，伊甸园既没有满，GC也没有满。

然后，我将文档数从50_000更改为100_000…numThreads=1的运行时间约为2秒，numThreads＝4的运行时间为1秒。比率为~1/2。发生了什么？。。。GC详细信息包含以下新消息：

[GC (Allocation Failure) [PSYoungGen: 2097664K->349175K(2446848K)] 2097664K->1627175K(8039424K), 0,5229844 secs] [Times: user=4,78 sys=0,45, real=0,53 secs] 

这意味着JVM无法在Eden中分配新对象，必须触发垃圾回收过程。我们花了"；实数＝0.53秒"；GC内部。

如果你在代码中分配更多的内存或堆大小更小，你会得到最糟糕的结果(我给出了1个线程与4个线程的比率~1/1.4)，因为全GC触发：

[Full GC (Ergonomics) [PSYoungGen: 349172K->0K(2446848K)] [ParOldGen: 4675608K->4925474K(5592576K)] 5024780K->4925474K(8039424K), [Metaspace: 2746K->2746K(1056768K)], 5,7606117 secs] [Times: user=56,58 sys=0,26, real=5,76 secs] 

这就是为什么我们(在金融科技领域)更喜欢用Java编写分配/GC免费代码：)