Logo Questions Linux Laravel Mysql Ubuntu Git Menu
 

Is each cycle of a for loop an atomic operation?

Is the incrementAndGet method of the following AtomicBigInteger implementation an atomic operation? I'm particularly wondering about the for (; ; ) part. Does the JVM somehow guarantee that each cycle in a for loop is executed atomicly?

public final class AtomicBigInteger {

    private final AtomicReference<BigInteger> valueHolder = new AtomicReference<>();

    public AtomicBigInteger(BigInteger bigInteger) {
        valueHolder.set(bigInteger);
    }

    public BigInteger incrementAndGet() {
        for (; ; ) {
            BigInteger current = valueHolder.get();
            BigInteger next = current.add(BigInteger.ONE);
            if (valueHolder.compareAndSet(current, next)) {
                return next;
            }
        }
    }
}

I got this code from here: Possible to safely increment BigInteger in a thread safe way, perhaps with AtomicReference, w/o locking? However this implementation was making its rounds and you can find it on many different places across the internet.

like image 234
eztam Avatar asked Nov 07 '21 01:11

eztam


People also ask

What makes an operation atomic?

"An operation acting on shared memory is atomic if it completes in a single step relative to other threads. When an atomic store is performed on a shared memory, no other thread can observe the modification half-complete.

Is ++ an atomic operation?

On objects without an atomic type, standard never defines ++ as an atomic operation.

What are atomic memory operations?

What Is an Atomic Memory Operation? ▪ Uninterruptable read-modify-write memory operation. — Requested by threads. — Updates a value at a specific address. ▪ Serializes contentious updates from multiple threads.

What are atomic operations in Java?

Atomicity. Atomic operations are those operations that ALWAYS execute together. Either all of them execute together, or none of them executes. If an operation is atomic, then it cannot be partially complete, either it will be complete, or not start at all, but will not be incomplete.

What happens when you break a loop in C?

The break statement causes the inner-most loop to be terminated immediately when executed. The continue statement will move at once to the next iteration without further progress through the loop body for the current iteration. A for statement also terminates when a break, goto, or return statement within the statement body is executed.

What are the parts of a for loop?

A for-loop has two parts: a header specifying the iteration, and a body which is executed once per iteration. The header often declares an explicit loop counter or loop variable, which allows the body to know which iteration is being executed. For-loops are typically used when the number of iterations is known before entering the loop.

What happens to a loop variable when it terminates?

The programmer must still code the problem correctly, but some possible blunders will be blocked. Different languages specify different rules for what value the loop variable will hold on termination of its loop, and indeed some hold that it "becomes undefined".

What is the purpose of a for loop?

In computer science, a for-loop (or simply for loop) is a control flow statement for specifying iteration, which allows code to be executed repeatedly. Various keywords are used to specify this statement: descendants of ALGOL use "for", while descendants of Fortran use "do".


2 Answers

The method incrementAndGet in your class will not be atomic. Here's why.

The Atomic* classes use volatile value references. The memory offset to these values are also held inside the instances using which they are able to fetch-increment-compare-set in loop till the current thread is able to do all operations in one go (i.e., without another thread performing an increment in between).

This is possible for these Atomic*, as I see, due to the access the intrinsic "trusted" classes have to the Unsafe implementations. The Unsafe implementations have methods to compare-and-set atomically using native functions.

In cases like what you have mentioned, we will have to resort to either using synchronized blocks, its equivalent Lock based implementations or simply use the methods in AtomicReference. Like this:

public class AtomicBigInteger{
    private final AtomicReference<BigInteger> valueHolder = new AtomicReference<>();

    public AtomicBigInteger(BigInteger bigInteger) {
        valueHolder.set(bigInteger);
    }

    public BigInteger incrementAndGet() {
        return valueHolder.updateAndGet( bigInt -> bigInt.add( BigInteger.ONE ) );
    } 
}

However, since we are dealing with BigInteger, this implementation too will have to be reviewed because the number of iterations that AtomicReference.updateAndGet(..) may have to perform may be significant, because BigInteger.add( BigInteger ) involves a lot of steps, unlike an addition of two ints.

like image 70
Sree Kumar Avatar answered Oct 11 '22 14:10

Sree Kumar


No, it is not atomic, but if another thread has modified the AtomicReference then the compareAndSet call will fail and it will loop again, get the value, increment it, and try to set it again. Sooner or later (probably) it will succeed and update the BigInteger held by the AtomicReference to the next number.

like image 36
David Conrad Avatar answered Oct 11 '22 15:10

David Conrad