为什么这段Java代码不能并发运行

Question

我已经编写了埃拉托色尼筛法的代码，本来应该可以并行运行，但实际上并不能。当我增加线程数时，计算时间并没有减少。您有什么想法吗？

Main类

import java.util.Date;
import java.util.concurrent.ExecutorService;
import java.util.concurrent.Executors;

public class ConcurrentTest {
    public static void main(String[] args) throws InterruptedException {
        Sieve task = new Sieve();
        int x = 1000000;
        int threads = 4;
        task.setArray(x);
        Long beg = new Date().getTime();
        ExecutorService exec = Executors.newCachedThreadPool();
        for (int i = 0; i < threads; i++) {
            exec.execute(task);
        }
        exec.shutdown();
        Long time = 0L;
    // Main thread is waiting until all threads are terminated
    // ( it means that computing is done)
        while (true)
            if (exec.isTerminated()) {
                time = new Date().getTime() - beg;
                break;
            }

        System.out.println("Time is " + time);
    }
}

Sieve类

Sieve类是与素数相关的一个类。

import java.util.concurrent.ConcurrentHashMap;

public class Sieve implements Runnable {
    private ConcurrentHashMap<Integer, Boolean> array = 
                       new ConcurrentHashMap<Integer, Boolean>();
    private int x;
    public void run() {
        while(true){
    // I am getting synchronized number to check if it's prime
            int n = getCounter();
    // If no more numbers to check, stop loop
            if( n == -1)
                break;
    // If HashMap contains number, we can further
            if(!array.containsKey(n))continue;
            for (int i = 2 * n; i <= x; i += n) {
    // Compound numbers are removed from HashMap, Eg. 6, 12 and much more.
                    array.remove(i);
            }
        }
    }
    private synchronized int getCounter(){
        if( counter < x)
            return counter++;
        else return -1;
    }
    public void setArray(int x) {
        this.x = x;
        for (int i = 2; i <= x; i++)
            array.put(i, false);
    }
}

我进行了一些不同线程数的测试，以下是结果:

Nr of threads 1    Time is 1850, 1795, 1825
Nr of threads 2    Time is 1845, 1836, 1814
Nr of threads 3    Time is 1767, 1820, 1756
Nr of threads 4    Time is 1732, 1840, 2083
Nr of threads 5    Time is 1791, 1795, 1803
Nr of threads 6    Time is 1825, 1728, 1707
Nr of threads 7    Time is 1754, 1729, 1686
Nr of threads 8    Time is 1760, 1717, 1817
Nr of threads 9    Time is 1721, 1699, 1673
Nr of threads 10   Time is 1661, 1722, 1718

- nervosol

---

你正在更改任务计数，而不是线程计数。你的每个任务都执行相同数量的工作并且同时执行，因此你的时间通常应该相同，直到硬件用尽为止（此时速度将变慢）。 - lscoughlin

Answer 1

当我增加线程数量时，计算时间并没有变短。 tl;dr: 你的问题规模太小了。如果将x增加到10000000，差异会更加明显。不过它们可能不是你期望的结果。

我在一个8核机器上尝试了你的代码，并进行了两个微小的修改：

1. 为了计时，我使用了System.nanoTime()而不是Date上的getTime()。
2. 我使用了ExecutorService的awaitTermination方法来检查运行结束，而不是自旋循环。

我尝试使用固定线程池、缓存线程池和分叉合并线程池来启动您的Sieve任务，并比较不同线程变量值的结果。在我的机器上，x=10000000时，我看到以下结果（以毫秒为单位）：

    线程数           = 1    2    4    8    16
    固定线程池       = 5451 3866 3639 3227 3120
    缓存线程池       = 5434 3763 3709 3258 3078
    分叉合并线程池   = 6732 3670 3735 3190 3102

这些结果告诉我们，从单线程执行转变为两个线程有明显的好处。然而，额外线程的好处迅速下降。从两个线程到四个线程存在一个有趣的平台，而16个线程以上只有微小的好处。

此外，您还可以看到不同的线程机制具有不同的初始开销：我没有预料到Fork-Join池的启动成本会比其他机制高那么多。

因此，按照目前的编写方式，对于小但非微不足道的问题集，您实际上不应该期望超过两个线程的好处。

如果您想增加额外线程的好处，您需要查看当前的实现。例如，当我从您的同步getCounter()切换到AtomicInteger使用incrementAndGet()时，我消除了同步方法的开销。结果是，我所有的四个线程数字都下降了约1000毫秒。

- Bob Cross