9

我编写了一些 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 。Collat​​z 10000000 1000000 4 => 4 个线程，耗时 28412 毫秒

java -d64 -server -cp 。Collat​​z 10000000 1000000 1 => 1 个线程，耗时 38286 毫秒

处理器：

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

爪哇：

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

操作系统：

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

代码：（我无法发布代码，我认为对于 SO 要求来说太长了，源可在Google Docs上找到

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)" );
  }
}
4

4 回答 4

11

忙等待可能是一个问题：

while (!executor.isTerminated() ) { 
}

您可以awaitTermination()改用：

while (!executor.awaitTermination(1, TimeUnit.SECONDS)) {}
于 2010-11-24T21:04:16.580 回答
2

正如@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 毫秒

更快，当然 - 但没有像你期望的那样在四分之一的时间内完成，甚至一半......（虽然它大约只是超过一半，稍后会更多）。请注意，在我的例子中，我将工作单元的大小减半，并且默认最大堆为 1500m。

在家使用我的 Core i5 750（4 核无超线程）、4GB RAM、Windows 7 64 位、jdk 1.6.0_22（64 位）：

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

删除忙等待循环后，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 没有影响。

于 2010-11-25T02:05:44.803 回答
2

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

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

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

总的来说，我不建议将 Java 用于这类东西。使用 pthreads 对你来说是一个更好的方法。

于 2010-11-24T21:04:59.520 回答
-1

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

Terminate 在关闭之前不会返回。

Future submit(Runnable task) 提交一个 Runnable 任务以供执行，并返回一个代表该任务的 Future。

isTerminated() 如果所有任务在关闭后都已完成，则返回 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);
}
于 2010-11-24T21:10:31.030 回答