多线程中的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!

并且线程获得相等的数字变量:

 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加上主线程的10个)争用访问权限AtomicInteger,而在情况(1)中只有主线程访问它.事实上,对于案例(1),您可以使用int而不是AtomicInteger.

在AtomicInteger类利用的CAS登记.它通过读取值,执行增量,然后使用寄存器中的值交换值来实现此目的,如果它仍然具有与最初读取的值相同(比较和交换).如果另一个线程更改了它重新启动的值,则重试:read - increment - compare-and-swap,直到成功为止.

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

编辑

正如@teppic指出的那样,另一个问题使得case(2)比case(1)慢.随着数字的增量发生在已发布的作业中,循环条件将保持为真实的时间长于所需的时间.虽然执行程序的所有10个线程都在搅拌以确定它们的给定数字是否为素数,但主线程不断向执行程序发布新作业.在完成之前的工作之前,这些新工作没有机会增加数字.因此,虽然他们在队列numbers中没有增加,并且主线程可以同时完成一个或多个循环循环,发布新的作业.最终结果是,可以创建和发布比所需的1000000更多的作业.

Answer 2

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

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

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

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

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