java - Java ExecutorService 上的 Fibonacci 顺序运行比并行运行更快

Question

我正在尝试 Java 中的执行程序服务，并编写了以下代码来运行斐波那契数列(是的，大规模递归版本，只是为了强调执行程序服务)。

令人惊讶的是，如果我将nThreads设置为1，它会运行得更快。这可能与提交给执行器服务的每个“任务”的大小非常小有关。但如果我将 nThreads 设置为 1，它仍然必须是相同的数字。

为了查看对共享原子变量的访问是否会导致此问题，我用注释“see text”注释掉了这三行，并查看系统监视器以查看执行需要多长时间。但结果是一样的。

知道为什么会发生这种情况吗？

顺便说一句，我想将它与 Fork/Join 的类似实现进行比较。事实证明它比 F/J 实现慢得多。

public class MainSimpler {
    static int N=35;
    static AtomicInteger result = new AtomicInteger(0), pendingTasks = new AtomicInteger(1);
    static ExecutorService executor;

    public static void main(String[] args) {
        int nThreads=2;
        System.out.println("Number of threads = "+nThreads);
        executor = Executors.newFixedThreadPool(nThreads);
        Executable.inQueue = new AtomicInteger(nThreads);
        long before = System.currentTimeMillis();
        System.out.println("Fibonacci "+N+" is ... ");
        executor.submit(new FibSimpler(N));
        waitToFinish();
        System.out.println(result.get());
        long after = System.currentTimeMillis();        
        System.out.println("Duration: " + (after - before) + " milliseconds\n");
    }

    private static void waitToFinish() {
        while (0 < pendingTasks.get()){
            try {
                Thread.sleep(1000);
            } catch (InterruptedException e) {
                e.printStackTrace();
            }
        }
        executor.shutdown();
    }
}



class FibSimpler implements Runnable {
    int N;
    FibSimpler (int n) { N=n; }

    @Override
    public void run() {
        compute();
        MainSimpler.pendingTasks.decrementAndGet(); // see text
    }

    void compute() {
        int n = N;
        if (n <= 1) {
            MainSimpler.result.addAndGet(n); // see text
            return;
        }
        MainSimpler.executor.submit(new FibSimpler(n-1));
        MainSimpler.pendingTasks.incrementAndGet(); // see text
        N = n-2;
        compute();  // similar to the F/J counterpart
    }
}

运行时间(大约):

• 1 个线程:11 秒
• 2 个线程:19 秒
• 4 个线程:19 秒

更新:我注意到，即使我在执行程序服务中使用一个线程，整个程序也会使用我机器的所有四个核心(每个核心平均使用率约为 80%)。这可以解释为什么在执行程序服务中使用更多线程会减慢整个进程的速度，但是现在，如果执行程序服务中只有一个线程处于 Activity 状态，为什么这个程序要使用 4 个核心？

Answer 1

It might be related to the fact that the size of each "task" submitted to the executor service is really small.

情况确实如此，因此您主要测量上下文切换的开销。当n == 1时，没有上下文切换，因此性能更好。

But still it must be the same number also if I set nThreads to 1.

我猜你在这里的意思是“高于1”。

您遇到了严重的锁争用问题。当您有多个线程时，结果上的锁始终处于竞争状态。线程必须互相等待才能更新结果，这会减慢它们的速度。当只有一个线程时，JVM 可能会检测到这一点并执行锁省略，这意味着它实际上根本不执行任何锁定。

如果您不将问题划分为 N 个任务，而是将其划分为 N/nThreads 个任务，那么您可能会获得更好的性能，这些任务可以通过线程(假设您选择的 nThreads 最多为可用物理核心/线程的数量)。然后，每个线程执行自己的工作，计算自己的总数，并仅在线程完成时将其添加到总计中。即便如此，对于 fib(35) 我预计线程管理的成本将超过其 yield 。也许可以尝试fib(1000)。