Why did we launch LongAdder in JDK1.8 with AtomicLong?
The problem of AtomicLong
A technology must have emerged to solve some problem. The JDK1.8 update to LongAdder is definitely addressing some of the problems that have already occurred. In 1.5, AtomicLong was introduced, and its function is the same as LongAdder; AtomicLong must have some issues to fix; See AtomicLong source code:
// Take the getAndAddLong method as an example
public final long getAndAddLong(Object var1, long var2, long var4) {
long var6;
do {
var6 = this.getLongVolatile(var1, var2);
} while(!this.compareAndSwapLong(var1, var2, var6, var6 + var4));
return var6;
}
Copy the codeLooking through the source code, you can see that many methods almost all of these operations use CAS operations. So what’s wrong with CAS? When the number of concurrent operations is not very large, there is no problem. When the number of concurrent operations is large, it can be imagined: for example, if there are N threads adding 1 and then CAS, only one thread will succeed in CAS, and n-1 threads will fail, and then spin. Then another thread succeeds, leaving n-2 threads to spin again; Repeat until all threads execute successfully! Does this description suggest that the efficiency of CAS will decrease in the case of high concurrency, which is the problem of AtomicLong? The emergence of LongAdder is to solve this problem, so let’s look at how LongAdder solves this problem;
LongAdder principle introduction
Before introducing the source code, the principle of LongAdder is introduced roughly:
It can be said that LongAdder makes up for AtomicLong’s bottleneck by swapping space for time.
The basic idea of LongAdder is to spread out the hot spots. AtomicLong maintains a value regardless of how many threads accumulate it. LongAdder maintains an array as well as a volatile long base value
transient volatile Cell[] cells;
@sun.misc.Contended static final class Cell {
volatile long value;
Cell(long x) {
value = x;
}
final boolean cas(long cmp, long val) {
return UNSAFE.compareAndSwapLong(this, valueOffset, cmp, val); }}Copy the codeThis array is maintained indirectly but that’s not the point; The important thing to remember is that this array also maintains a value, just for the simple purpose of adding up; Different threads will hit different slots in the array, and each thread only performs CAS operation on the value in its slot, thus achieving the purpose of hotspot dispersion. When the concurrency is not high, the base value is directly operated through CAS. When the concurrency is high, CASbase may fail. After the failure, CAS will add 1 to the value in Cell[I] in Cell[] array. The principle is very simple, let’s look at the source code;
LongAdder source code analysis
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 ||
//getProbe() &m getProbe() &m
(a = as[getProbe() & m]) == null| |! (uncontended = a.cas(v = a.value, v + x))) longAccumulate(x,null, uncontended); }}Copy the codeAdd () checks to see if cells is empty, and casBase() adds to base. If casBase(b = base, b + x) returns true and false. Then the whole thing is false, it doesn’t go into the if() method and the whole thing ends; That’s the end of this article… Ha ha!
As ==null and (m = as.length-1) < 0 also false. GetProbe () gets the hase value of the current thread, and then adds it to m(the length of the array) to get the Cell[getProbe() &m] at the specified position and assigns it to A; A. cas(v = a.value, v + x); If the concurrency is not high, there is a good chance that the summation will succeed. We can only assume that the summation fails. If another thread is suming the value, the cas summation will fail. Methods;
final void longAccumulate(long x, LongBinaryOperator fn,
boolean wasUncontended) {
int h;
// Get the hash value of the current thread and assign it to h
if ((h = getProbe()) == 0) {
ThreadLocalRandom.current();
h = getProbe();
wasUncontended = true;
}
boolean collide = false;
for (;;) {
Cell[] as; Cell a; int n; long v;
// #1 determines whether cells are empty and the array length is greater than 0
if((as = cells) ! =null && (n = as.length) > 0) {
// #2 check if there are elements in the current thread position. Since it is possible to rehash the thread, it is possible that multiple threads will initially add value to Cell[0], and after a rehash, it is possible that it will not be 0, so it is possible that it will be empty, and if it is empty it will proceed down, and if it is not empty it will go to code #3
if ((a = as[(n - 1) & h]) == null) {
// cellsBusy 0 indicates that there is no thread holding 'lock'; 1: indicates that the thread is busy. Another thread holds the lock
if (cellsBusy == 0) {
// Create a Cell object r
Cell r = new Cell(x);
//casCellsBusy() sets 0 to 1 to indicate that the other lines are busy
if (cellsBusy == 0 && casCellsBusy()) {
boolean created = false;
try {
// Assign r to rs[j]
Cell[] rs; int m, j;
if((rs = cells) ! =null &&
(m = rs.length) > 0 &&
rs[j = (m - 1) & h] == null) {
rs[j] = r;
created = true; }}finally {
cellsBusy = 0;
}
if (created)
break;
continue;
}
}
collide = false;
}
// Rehash #3 will not enter here, continue with #4
else if(! wasUncontended) wasUncontended =true;
A = as[(n-1) &h]) = null; a= as[(n-1) &h]) = null; a= as[(n-1) &h] = null; At this point, code #5 will be expanded
else if (a.cas(v = a.value, ((fn == null)? v + x : fn.applyAsLong(v, x))))break;
else if(n >= NCPU || cells ! = as) collide =false;
else if(! collide) collide =true;
// #5
//cellsBusy 0 indicates that there is no thread holding 'lock'; 1: indicates that the thread is busy. Another thread holds the lock
// casCellsBusy() sets 0 to 1 to indicate that the other lines are busy
else if (cellsBusy == 0 && casCellsBusy()) {
try {
if (cells == as) {
// Double the size
Cell[] rs = new Cell[n << 1];
for (int i = 0; i < n; ++i) rs[i] = as[i]; cells = rs; }}finally {
// Set cellsBusy to 0. The idle state is now available for other threads to operate
cellsBusy = 0;
}
// At the end of the expansion, it loops back into the code at #1
collide = false;
continue;
}
h = advanceProbe(h);
}
/ / # 6
// If cells at #1 are empty then the Cell[] array is initialized
// Initialize rs array, default size is 2
else if (cellsBusy == 0 && cells == as && casCellsBusy()) {
boolean init = false;
try {
if (cells == as) {
Cell[] rs = new Cell[2];
//h & 1: either 0 or 1. It can be used to determine whether h is singular or plural. The base 2 of 3 is 0011&0001 =0001
rs[h & 1] = new Cell(x);
cells = rs;
init = true; }}finally {
cellsBusy = 0;
}
if (init)
break;
}
// See if there are other threads adding the base value;
// Try adding CAS to base again
else if (casBase(v = base, ((fn == null)? v + x : fn.applyAsLong(v, x))))break; }}Copy the codeThe above code can be roughly divided into the following sections:
- The code at #1 determines if the cells array is empty. If it is empty, the code at #6 initializes the array Cell[]
- If the cells array at #1 is not empty, it will go to #2 again to determine whether the current thread has elements, which will be divided into two cases, one is an element, the other is no element;
- So let’s assume that this is the first case, and then we’re going to get code at #3, #4, and #5, and the code at #3 is not what we’re going to focus on, and then we’re going to execute code at #4, because it’s not empty so I’m definitely going to try to add up the value in this object; If the value of the object is changed, the value of the object is changed. If the value of the object is changed, the value of the object is changed. At this point, the code in #5 is executed to expand; On successful expansion, the code at #1 will be re-executed with continue.
- There’s another case where there’s no element at this location, and if there’s no element it’s easier to create a Cell object at that location;
conclusion
After analysis, the core idea of LongAdder is to use space to exchange time and disperse hotspot values into a Cell list to undertake concurrent CAS, so as to improve performance. So AtomicLong can be abandoned? I don’t think so. AtomicLong can save some memory if the concurrency is not that high; Or we’ll use AtomicLong if it’s memory intensive;
The principle and implementation of LongAdder are very simple, but the idea of its design is worth our taste and learning.