Jail AtomicLong?

The atomic class in Java Kingdom provide very handy and powerful functionalities in cases where our program’s state is simple enough to delegate to a atomic variable. If we look at the packages – java.util.concurrent.atomic, there exists five general kinds of atomic class:

Atomic
| | | | \__ Primitives: Long, Integer, Boolean, Reference
| | | \---- Arrasy element: LongArray, IntegerArray, ReferenceArray
| | \______ Refelction related: LongFieldUpdater, IntegerFieldUpdater, ReferenceFieldUpdater
| \-------- Reference with state: MarkableReference, StampedReference
\__________ Primitives: Striped64, LongAdder, DoubleAdder, LongAccumulator, DoubleAccumulator[*]

[*]: Other four kinds of classes all start with `Atomic`, except this one.

Each kinds of class has different usages domains as above list concludes, except the first and last type. They seems have some duplication: that is this three similar class

• AtomicLong
• AtomicAdder
• AtomicAccumulator

Obviously enough, the AtomicAccumulator is the abstraction of AtomicAdder, i.e. which support more general operations but not so efficient compared with a simple “Adder”. So, the newcomer LongAdder (who comes in JDK since 1.8) report to the Java Kingdom that “we should jail the AtomicLong and deprecate it in the future.”

Today, the Java Judge Committee open a meeting to let AtomicLong and LongAdder to do “face-to-face confrontation”.

---

Memory for Speed

LongAdder start with documentation that Doug Lea write:

Under low update contention, the two classes have similar characteristics. But under high contention, expected throughput of this class is significantly higher

“As all of you seen, LongAdder will be significantly efficient under high contention.” LongAdder said.

“But we should notice why it is more efficient? The AtomicLong is already very fast which use optimistic lock CAS to avoid heavy lock path. So how LongAdder make it more efficient? He must hide some fact.” AtomicLong challenged.

“Em, right. LongAdder make it at the expense of higher space consumption.” LongAdder added.

"Yes. He didn’t tell all truth. The original document of LongAdder is

But under high contention, expected throughput of this class is significantly higher, at the expense of higher space consumption.

"In details, It maintains one or more variables which sum to the real value. So explains it!

One or more variables that together maintain an initially zero long sum

LongAdder think the drawback is exposed, he has to show his advantages "Ok, Let’s start with documentation

When updates (method add) are contended across threads, the set of variables may grow dynamically to reduce contention. Method sum (or, equivalently, longValue) returns the current total combined across the variables maintaining the sum.

"So we can grasp a general idea that under high contention, different thread will update different variables, which avoid contention as AtomicLong did. We can compare the implementations:

// AtomicLong
public final long addAndGet(long delta) {  
  return unsafe.getAndAddLong(this, valueOffset, delta) + delta;  
}
// Unsafe
public final long getAndAddLong(Object obj, long offset, long delta) {  
  long old;  
  do {  
    old = this.getLongVolatile(obj, offset);  
  } while(!this.compareAndSwapLong(obj, offset, old, old + delta));
  return old;  
}

"As you can see, the implementation of AtomicLong will continue to try if CAS failed under high thread contention. But our LongAdder is different:

public void add(long x) {
    Cell[] as; long b, v; int m; Cell a;
    if ((as = cells) != null || !casBase(b = base, b + x)) {
        boolean uncontended = true;
        if (as == null || (m = as.length - 1) < 0 ||
            (a = as[getProbe() & m]) == null ||
            !(uncontended = a.cas(v = a.value, v + x)))
            longAccumulate(x, null, uncontended);
    }
}

"Our LongAdder has a long base and Cell[] cells to store sum value. Under low contention, thread will just update the base use CAS which is the same with LongAdder. But under high contention, most thread will CAS failed and enter the if condition.

"those threads will check whether the cells array is already init

as == null || (m = as.length - 1) < 0

"whether the a random (getProbe is a thread local random number generation) cell is init

a = as[getProbe() & m]) == null

“and finally, whether that cell contented. If all those trial failed, we will init cells or try to attach new Cell, or in more special cases, expand size of cells to reduce the collision.” LongAdder finished.

if (…
!(uncontended = a.cas(v = a.value, v + x)))
longAccumulate(x, null, uncontended);

People are almost overwhelmed by the complex but dedicated implementation of LongAdder, but except AtomicLong. He found some other drawbacks.

“But” AtomicLong said loudly, “you pay for it more than space”, he wait a while and continue “You are not accurate. The following is the citation from your sum() method”

Returns the current sum. The returned value is NOT an atomic snapshot; invocation in the absence of concurrent updates returns an accurate result, but concurrent updates that occur while the sum is being calculated might not be incorporated.

“The sum is accumulated dynamically by iterating all cells (if exists), which, without lock, can be updated during iteration, so is not accurate. By the way, your sum() is of course not efficient than mine.” AtomicLong finished.

All people nod and LongAdder is blushed.

“So you are very suitable for situations like collecting statistics, which has high contention and endure the accuracy loss, just like the ConcurrentHashMap's size().” AtomicLong close the debate and return to work.

---

PS

One more questions let reader to ponder:

if ((as = cells) != null || !casBase(b = base, b + x)) {

During add, what about check base first then cells?

Written with StackEdit.