java - 多线程中的 AtomicInteger

Question

我想找出从 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 多线程安全但线程获得相等的数字值？

Answer 1

在 (2) 的情况下，最多 11 个线程(来自 ExecutorService 的十个线程加上主线程)正在竞争访问 AtomicInteger，而如果(1) 只有主线程访问它。事实上，对于情况 (1)，您可以使用 int 而不是 AtomicInteger。

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

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

编辑

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