AtomicInteger in multithreaded mode

Question

I want to find all primes from 0 to 1,000,000. For this, I am writing a stupid method:

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

and it’s good for me and doesn’t need editing . How will I write the following code:

 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(); } } 

Note the (1) and (2) marked lines. When (1) is turned on, the program runs quickly, but if turned on (2), it runs slower: I get small portions with a long delay:

 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! 

And the threads get an equal 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! 

Please explain to me why option (2) is slower and why the threads get the same value for the number, even though the AtomicInteger multithreading is safe?

Answer 1

In case (2), up to 11 threads compete to access AtomicInteger (ten of the ExecutorService plus the main thread), while in case (1) only the main thread accesses it. In fact, for case (1), you can use int instead of AtomicInteger .

The AtomicInteger class uses CAS . He does this by reading the value, incrementing, and then replacing the value with the value in the register if it still has the same value that was originally read (compare and replace). If another thread has changed the value that it repeats, starting again: read - increment - compare-and-swap, until it succeeds.

The advantage is that it is a lock and therefore potentially faster than using locks. But it is ineffective under heavy contention. More conflict means more effort.

Edit

As @teppic points out, another problem makes register (2) slower than case (1). Since the increment of numbers occurs in published tasks, the condition of the cycle remains true for much longer than necessary. While all 10 streams of performers beat off to determine if their given number is, the main stream continues to publish new tasks for the performer. These new tasks do not have the ability to increase the number until the previous tasks are completed. Therefore, while they are in the numbers queue, it does not increase, and the main thread, meanwhile, can complete one or more cycles of cycles, placing new jobs. The end result is that you can create and post many more tasks than the necessary 1,000,000.

Answer 2

Your outer loop: while (numbers.get() < 1000000)

This allows you to keep sending more Runnables than intended for the ExecutorService in the main thread.

You can try changing the loop: for(int i=0; i < 1000000; i++)

(As already mentioned, you are obviously increasing the number of rivals , but I suspect that additional workflows are a more significant slowdown factor that you see.)

As for your second question, I'm sure this is against the AtomicInteger contract for the two child threads to see the same getAndIncrement value. So something else needs to happen that I don’t see in your code example. Maybe you see the output from two separate program runs?

Answer 3

Explain to me why option (2) is slower?

Just because you do it inside run() . Thus, several threads will try to do this at the same time, so release will wait . Bowmore gave a low-level explanation.

In (1) he is consistent. Thus, such a scenario will not be.

Why do threads get the same value for a number despite AtomicInteger multithreading?

I do not see the possibility of this. If such a case should occur from 0.

Answer 4

You are missing two main points: what is AtomicInteger and how does multithreading work in general.
Regarding why Option 2 is slower, @bowmore has provided an excellent answer right now. Now about printing the same issue twice. AtomicInteger is like any other object. You start your threads and they check the value of this object. Since they compete with your main thread, which increases the counter, the two child threads can still see the same value. I would pass an int for each Runnable to avoid this.