7

我想找出从 0 到 1000000 的所有素数。为此，我编写了这个愚蠢的方法：

public static boolean isPrime(int n) {
    for(int i = 2; i < n; i++) {
        if (n % i == 0)
            return false;
    }
    return true;
}

这对我有好处，不需要任何编辑。比我写了以下代码：

private static ExecutorService executor = Executors.newFixedThreadPool(10);
private static AtomicInteger counter = new AtomicInteger(0);
private static AtomicInteger numbers = new AtomicInteger(0);

public static void main(String args[]) {
    long start = System.currentTimeMillis();
    while (numbers.get() < 1000000) {
        final int number = numbers.getAndIncrement();  // (1) - fast
        executor.submit(new Runnable() {
            @Override
            public void run() {
  //               int number = numbers.getAndIncrement(); // (2) - slow
                if (Main.isPrime(number)) {
                    System.out.println("Ts: " + new Date().getTime() + " " + Thread.currentThread() + ": " + number + " is prime!");
                    counter.incrementAndGet();
                }
            }
        });
    }
    executor.shutdown();
    try {
        executor.awaitTermination(Long.MAX_VALUE, TimeUnit.NANOSECONDS);
        System.out.println("Primes: " + counter);
        System.out.println("Delay: " + (System.currentTimeMillis() - start));
    } catch (Exception e) {
        e.printStackTrace();
    }
}

请注意 (1) 和 (2) 标记的行。启用 (1) 时，程序运行速度快，但启用 (2) 时，运行速度较慢。

输出显示延迟较大的小部分

Ts: 1480489699692 Thread[pool-1-thread-9,5,main]: 350431 is prime!
Ts: 1480489699692 Thread[pool-1-thread-6,5,main]: 350411 is prime!
Ts: 1480489699692 Thread[pool-1-thread-4,5,main]: 350281 is prime!
Ts: 1480489699692 Thread[pool-1-thread-5,5,main]: 350257 is prime!
Ts: 1480489699693 Thread[pool-1-thread-7,5,main]: 350447 is prime!
Ts: 1480489711996 Thread[pool-1-thread-6,5,main]: 350503 is prime!

和线程获得相同的number价值：

 Ts: 1480489771083 Thread[pool-1-thread-8,5,main]: 384733 is prime!
 Ts: 1480489712745 Thread[pool-1-thread-6,5,main]: 384733 is prime!

请解释一下为什么选项 (2) 更慢以及为什么尽管 AtomicInteger 多线程安全，线程的数字值相等？

4

4 回答 4

9

在 (2) 的情况下，多达 11 个线程（ExecutorService主线程中的 10 个）正在竞争对 的访问AtomicInteger，而在情况 (1) 中只有主线程访问它。事实上，对于案例 (1)，您可以使用int而不是AtomicInteger.

该类AtomicInteger使用CAS寄存器。它通过读取值、执行增量，然后将值与寄存器中的值交换，如果它仍然具有最初读取的相同值（比较和交换）。如果另一个线程更改了值，它会通过重新开始重试：读取 - 增量 - 比较和交换，直到成功。

优点是这是无锁的，因此可能比使用锁更快。但它在激烈的竞争下表现不佳。更多的争用意味着更多的重试。

编辑

正如@teppic 指出的那样，另一个问题使案例（2）比案例（1）慢。随着数字的增加发生在发布的作业中，循环条件保持真实的时间比需要的长得多。当执行器的所有 10 个线程都在忙于确定它们给定的数字是否是素数时，主线程不断向执行器发布新作业。在完成之前的工作之前，这些新工作没有机会增加数字。所以当他们在队列中的numbers时候不会增加并且主线程可以同时完成一个或多个循环循环，发布新的工作。最终结果是可以创建和发布比所需的 1000000 更多的工作。

于 2016-11-30T06:57:04.133 回答
4

你的外循环是： while (numbers.get() < 1000000)

这允许您继续向主线程中的 ExecutorService 提交比预期更多的 Runnables。

您可以尝试将循环更改为：for(int i=0; i < 1000000; i++)

（正如其他人提到的那样，您显然在增加争用量，但我怀疑额外的工作线程是您看到的减速的更大因素。）

至于你的第二个问题，我很确定两个子线程看到相同的 getAndIncrement 值违反了 AtomicInteger 的合同。因此，我在您的代码示例中没有看到其他必须发生的事情。可能是您看到了程序两次单独运行的输出？

于 2016-11-30T06:53:12.860 回答
1

解释一下为什么选项（2）更慢？

只是因为你在里面做run()。因此，多个线程将尝试同时执行此操作，因此会有wait和release。鲍莫尔给出了低层次的解释。

在（1）中它是顺序的。所以不会有这样的场景。

尽管 AtomicInteger 多线程安全，为什么线程的数字值相等？

我不认为有任何可能发生这种情况。如果有这种情况，它应该从 0 开始。

于 2016-11-30T07:17:49.867 回答
0

您在这里错过了两个要点：AtomicInteger 的用途以及多线程的一般工作方式。
关于为什么选项 2 较慢，@bowmore 已经提供了一个很好的答案。
现在关于两次打印相同的数字。AtomicInteger 就像任何其他对象一样。你启动你的线程，它们会检查这个对象的值。由于它们与您的主线程竞争，这增加了计数器，两个子线程仍然可能看到相同的值。我会将一个 int 传递给每个 Runnable 以避免这种情况。

于 2016-11-30T07:01:27.130 回答