AtomicInteger in multithreading

Question

I want to find out all the prime numbers from 0 to 1000000. For that I wrote this stupid method:

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

It's good for me and it doesn't need any edit. Than I wrote 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();
    }
}

Please, pay attention to (1) and (2) marked rows. When (1) is enabled the program runs fast, but when (2) is enabled it works slower.

The output shows small portions with large 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 threads get equal number value:

 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 me why option (2) is more slowly and why threads get equal value for number despite AtomicInteger multithreading safe?

I didn't see duplicates when I ran this. I checked by adding the results to a `Set`. — teppic, Nov 30 '16 at 07:14
Don't do it this way; _chunk_ up the range and process without **any** shared resources; if you want to be fancy, use [fork-join](https://docs.oracle.com/javase/tutorial/essential/concurrency/forkjoin.html). Or, better yet, use a [sieve](https://en.wikipedia.org/wiki/Sieve_of_Eratosthenes) - I'd wager it's orders of magnitude faster than any naive multi-threading solution. — Boris the Spider, Nov 30 '16 at 08:48
@ScaryWombat this `final` would have been a requirement in Java < 8. — Boris the Spider, Nov 30 '16 at 08:54
i am confuse if you loop 1000000 thread with a limit of 10 concurrect thread at time limited in Executors.newFixedThreadPool(10); the time be alway slow. because it start job after executor.shutdown() — toto, Dec 02 '16 at 00:38

bowmore · Answer 1 · 2016-11-30T18:26:14.167

In the (2) case, up to 11 threads (the ten from the ExecutorService plus the main thread) are contending for access to the AtomicInteger, whereas in case (1) only the main thread accesses it. In fact, for case (1) you could use int instead of AtomicInteger.

The AtomicInteger class makes use of CAS registers. It does this by reading the value, doing the increment, and then swapping the value with the value in the register if it still has the same value that was originally read (compare and swap). If another thread has changed the value it retries by starting again : read - increment - compare-and-swap, until it is succesful.

The advantage is that this is lockless, and therefore potentially faster than using locks. But it performs poorly under heavy contention. More contention means more retries.

Edit

As @teppic points out, another problem makes case (2) slower than case (1). As the increment of numbers happens in the posted jobs, the loop condition remains true for much longer than needed. While all 10 threads of the executor are churning away to determine whether their given number is a prime, the main thread keeps posting new jobs to the executor. These new jobs don't get an opportunity to increment numbers until preceding jobs are done. So while they're on the queue numbers does not increase and the main thread can meanwhile complete one or more loops loop, posting new jobs. The end result is that many more jobs can be created and posted than the needed 1000000.

While this contributes, it was a small effect in my testing. The larger problem is that the outer loop spins quickly, creating millions of unneeded jobs before reaching the terminal count. — teppic, Nov 30 '16 at 09:54
in 1 `number` is incremented once every loop. In 2 `number` is incremented after the short delay it takes to hand the job off to another thread. The delay is longer than the time it takes to create a new job, so many more jobs are created than are needed to process the 1000000 numbers. Millions more, it turns out. — teppic, Nov 30 '16 at 17:44

Patrick Parker · Answer 2 · 2016-11-30T07:20:51.343

4

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

This allows you to continue submitting more Runnables than intended to the ExecutorService in the main thread.

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

(As others have mentioned you are obviously increasing the amount of contention, but I suspect the extra worker threads are a larger factor in the slowdown you are seeing.)

As for your second question, I'm pretty sure that it is against the contract of AtomicInteger for two child threads to see the same value of getAndIncrement. So something else must be going on which I am not seeing from your code sample. Might it be that you are seeing output from two separate runs of the program?

edited Nov 30 '16 at 07:20

answered Nov 30 '16 at 06:53

Patrick Parker

4,863
4
19
51

1

This is the correct answer. It's slow because it's spamming the heap with jobs in a tight loop. – teppic Nov 30 '16 at 08:01
@BoristheSpider no it is not the same in both cases... when you are doing `while(numbers.get()...)` in the same thread as the `getAndIncrement` then you will not submit more Runnables than intended. Moving the `getAndIncrement` to the worker threads is precisely what allows the main thread to submit far too many workers. – Patrick Parker Nov 30 '16 at 14:31
@BoristheSpider Furthermore, I would say that the increasing of contention is more obvious and more irrelevant if the whole point of his exercise is to practice using the AtomicInteger as a shared resource. Otherwise why would he be considering putting it inside at all? Moving getAndIncrement outside the runnable improves performance but defeats the entire premise, contrived though it may be. – Patrick Parker Nov 30 '16 at 14:42
@PatrickParker I see it now; and you're absolutely right - incrementing the value asynchronously allows excess workers. – Boris the Spider Nov 30 '16 at 14:44

score 1 · Answer 3 · answered Nov 30 '16 at 07:17

Explain me why option (2) is more slowly?

Simply because you do it inside run(). So multiple threads will try to do it at the same time hence there will be wait s and release s. Bowmore has given a low level explanation.

In (1) it is sequential. So there will be no such a scenario.

Why threads get equal value for number despite AtomicInteger multithreading safe?

I don't see any possibility to happen this. If there's such a case it should happen from 0.

score 0 · Answer 4 · answered Nov 30 '16 at 07:01

You miss two main points here: what AtomicInteger is for and how multithreading works in general.
Regarding why Option 2 is slower, @bowmore provided an excellent answer already.
Now regarding printing same number twice. AtomicInteger is like any other object. You launch your threads, and they check the value of this object. Since they compete with your main thread, that increases the counter, two child threads still may see same value. I would pass an int to each Runnable to avoid that.

AtomicInteger in multithreading

4 Answers4