当我在四核计算机上使用多个线程时，为什么此代码没有看到任何显着的性能提升？

Question

我编写了一些 Java 代码来了解有关 Executor 框架的更多信息。

具体来说，我编写了代码来验证 Collat​​z 假设 - 这表示如果您迭代地应用以下函数对于任何整数，最终都会得到 1：

f(n) = ((n % 2) == 0) ？ n/2 : 3*n + 1

CH 尚未得到证实，我认为这将是了解 Executor 的好方法。每个线程都被分配了一个 [l,u] 范围的整数来进行检查。

具体来说，我的程序需要 3 个参数 - N（我要检查 CH 的数字）、RANGESIZE（线程必须处理的时间间隔的长度）和 NTHREAD（线程池的大小）。

我的代码工作正常，但我看到的加速比我预期的要少得多 - 当我从 1 个线程变为 4 个线程时，加速大约为 30%。

我的逻辑是，计算完全受 CPU 限制，并且每个子任务（检查 CH 的固定大小范围）花费的时间大致相同。

有人知道为什么我没有看到速度提高 3 到 4 倍吗？

如果您可以在增加线程数量（以及机器、JVM 和操作系统）时报告运行时间，那就太好了。

具体

运行时：

java -d64 -server -cp 。科拉茨 10000000 1000000 4 => 4 个线程，需要 28412 毫秒

java -d64 -server -cp 。科拉茨 10000000 1000000 1 => 1 个线程，需要 38286 毫秒

处理器：

四核 Intel Q6600，2.4GHZ，4GB。机器已卸载。

Java：

java版本“1.6.0_15” Java(TM) SE 运行时环境（版本 1.6.0_15-b03） Java HotSpot(TM) 64 位服务器 VM（版本 14.1-b02，混合模式）

操作系统：

Linuxquad0 2.6.26-2-amd64 #1 SMP Tue Mar 9 22:29:32 UTC 2010 x86_64 GNU/Linux

代码：(我无法发布代码，我认为对于 SO 要求来说太长了，源代码可在 Google 文档

import java.math.BigInteger;
import java.util.Date;
import java.util.List;
import java.util.ArrayList;
import java.util.concurrent.ExecutorService;
import java.util.concurrent.Executors;

class MyRunnable implements Runnable {
  public int lower;
  public int upper;

  MyRunnable(int lower, int upper) {
    this.lower = lower;
    this.upper = upper;
  }

  @Override
  public void run() {
    for (int i = lower ; i <= upper; i++ ) {
      Collatz.check(i);
    }
    System.out.println("(" + lower + "," + upper + ")" );
  }
}


public class Collatz {

  public static boolean check( BigInteger X ) {
    if (X.equals( BigInteger.ONE ) ) {
      return true;
    } else if ( X.getLowestSetBit() == 1 ) { 
      // odd
      BigInteger Y = (new BigInteger("3")).multiply(X).add(BigInteger.ONE);
      return check(Y);
    } else {
      BigInteger Z = X.shiftRight(1); // fast divide by 2
      return check(Z);
    }
  }

  public static boolean check( int x ) {
    BigInteger X = new BigInteger( new Integer(x).toString() );
    return check(X);
  }

  static int N = 10000000;
  static int RANGESIZE = 1000000;
  static int NTHREADS = 4;

  static void parseArgs( String [] args ) {

    if ( args.length >= 1 ) {
      N = Integer.parseInt(args[0]);
    }
    if ( args.length >= 2 ) {
      RANGESIZE = Integer.parseInt(args[1]);
    }
    if ( args.length >= 3 ) {
      NTHREADS = Integer.parseInt(args[2]);
    }
  }

  public static void maintest(String [] args ) {
    System.out.println("check(1): " + check(1));
    System.out.println("check(3): " + check(3));
    System.out.println("check(8): " + check(8));
    parseArgs(args);
  }

  public static void main(String [] args) {
    long lDateTime = new Date().getTime();
    parseArgs( args );
    List<Thread> threads = new ArrayList<Thread>();
    ExecutorService executor = Executors.newFixedThreadPool( NTHREADS );
    for( int i = 0 ; i < (N/RANGESIZE); i++) {
      Runnable worker = new MyRunnable( i*RANGESIZE+1, (i+1)*RANGESIZE );
      executor.execute( worker );
    }
    executor.shutdown();
    while (!executor.isTerminated() ) {
    }
    System.out.println("Finished all threads");
    long fDateTime = new Date().getTime();
    System.out.println("time in milliseconds for checking to " + N + " is " + 
                            (fDateTime - lDateTime )  + 
                            " (" + N/(fDateTime - lDateTime ) + " per ms)" );
  }
}

Answer 1

繁忙的等待可能是一个问题：

while (!executor.isTerminated() ) { 
} 

您可以使用 awaitTermination() 代替：

while (!executor.awaitTermination(1, TimeUnit.SECONDS)) {}

Answer 2

您正在使用 BigInteger。它消耗了大量的寄存器空间。在编译器级别最有可能遇到的是寄存器溢出，这会使您的进程受到内存限制。

另请注意，当您对结果进行计时时，您没有考虑 JVM 分配线程和使用线程池所花费的额外时间。

当您使用常量字符串时，也可能会出现内存冲突。所有字符串都存储在共享字符串池中，因此它可能会成为瓶颈，除非java对此非常聪明。

总的来说，我不建议使用 Java 来处理此类事情。使用 pthreads 将是一个更好的方法。

Answer 3

正如@axtavt 回答的那样，忙碌的等待可能是一个问题。您应该首先解决这个问题，因为它是答案的一部分，但不是全部。它似乎对您的情况没有帮助（在 Q6600 上），因为由于某种原因它似乎在 2 个核心处遇到瓶颈，因此另一个可用于繁忙的循环，因此没有明显的减速，但在我的 Core i5 上显着加快了 4 线程版本的速度。

我怀疑就 Q6600 而言，您的特定应用程序受到可用共享缓存量或特定于该 CPU 架构的其他因素的限制。 Q6600有两个4MB L2缓存，这意味着CPU共享它们，并且没有L3缓存。在我的核心 i5 上，每个 CPU 都有一个专用的 L2 缓存（256K，然后还有一个更大的 8MB 共享 L3 缓存。每个 CPU 多 256K 缓存可能会有所不同......否则其他架构明智的做法会有所不同。

这里是运行 Collat​​z.java 的 Q6600 和 Core i5 750。

在我的工作 PC 上，它也是像您的一样的 Q6600 @ 2.4GHz，但具有 6GB RAM、Windows 7 64 位和 JDK 1.6.0_21* (64-位），这里是一些基本结果：

• 10000000 500000 1（三次运行的平均值）：36982 毫秒
• 10000000 500000 4（三次运行的平均值）：21252 毫秒

当然更快 - 但没有像您期望的那样在四分之一的时间内完成， 虽然大约只是一半多一点，稍后会详细介绍）。

甚至一半... （ 在我的 Core i5 750（4 核，无超线程）、4GB RAM、Windows 7 64 位、jdk 1.6.0_22（64 位）上：

• 10000000 500000 1（3 次运行的平均值）32677 ms
• 10000000 500000 4（3 次运行的平均值） ) 8825 ms
• 10000000 500000 4（3 次运行的平均值） 11475 ms（没有忙等待修复，仅供参考）

当删除忙等待循环时，4 线程版本所用时间是 1 线程版本所用时间的 27%。好多了。显然，代码可以有效地利用 4 个核心...

• 注意：Java 1.6.0_18 及更高版本修改了默认堆设置 - 因此，我的工作 PC 上的默认堆大小几乎为 1500m，家庭 PC 上的默认堆大小约为 1000m。

您可能需要增加默认堆，以防万一发生垃圾收集并稍微减慢 4 线程版本的速度。这可能有帮助，也可能没有帮助。

至少在您的示例中，较大的工作单元大小可能会稍微扭曲您的结果...将其减半可能会帮助您接近至少 2 倍的速度，因为 4 个线程将在较长的时间内保持忙碌状态。我不认为 Q6600 在这个特定任务上会做得更好......无论是缓存还是其他一些固有的架构。

在所有情况下，我只是运行“java Collat​​z 10000000 500000 X”，其中 x = 指示的线程数。

我对 java 文件所做的唯一更改是将其中一个 println 转换为打印，因此每个工作单元运行 500000 次时的换行次数较少，因此我可以立即在控制台中看到更多结果，并且我放弃了繁忙的工作等待循环，这对 i5 750 很重要，但对 Q6600 没有影响。

Answer 4

您可以尝试使用提交函数，然后观察返回的 Future，检查它们以查看线程是否已完成。

在关闭之前终止不会返回。

未来提交（可运行任务）
提交一个 Runnable 任务来执行并返回一个表示该任务的 Future。

已终止()
如果关闭后所有任务均已完成，则返回 true。

试试这个...

public static void main(String[] args) {
    long lDateTime = new Date().getTime();
    parseArgs(args);
    List<Thread> threads = new ArrayList<Thread>();
    List<Future> futures = new ArrayList<Future>();

    ExecutorService executor = Executors.newFixedThreadPool(NTHREADS);
    for (int i = 0; i < (N / RANGESIZE); i++) {
        Runnable worker = new MyRunnable(i * RANGESIZE + 1, (i + 1) * RANGESIZE);
        futures.add(executor.submit(worker));
    }
    boolean done = false;
    while (!done) {
        for(Future future : futures) {
            done = true;
            if( !future.isDone() ) {
                done = false;
                break;
            }
        }
        try {
            Thread.sleep(100);
        } catch (InterruptedException e) {
            e.printStackTrace();
        }
    }

    System.out.println("Finished all threads");
    long fDateTime = new Date().getTime();
    System.out.println("time in milliseconds for checking to " + N + " is " +
            (fDateTime - lDateTime) +
            " (" + N / (fDateTime - lDateTime) + " per ms)");
    System.exit(0);
}