当前位置：网站首页>9 atomic operation class 18 Rohan enhancement

public final int get()
public final int getAndSet(int new Value)
public final int getAndIncrement()
public final int getAndDecrement()
public final int getAndAdd(int delta)
public comapreAndSet(int expect,int update)// If

Case-CountDownLatch

Case study

class MyNumber{
    
    AtomicInteger atomicInteger = new AtomicInteger();
    public void addPlusPlus(){
    
        atomicInteger.getAndIncrement();
    }
}

public class AtomicIntegerDemo {
    
    public static final int SIZE = 50;
    public static void main(String[] args) {
    
        MyNumber myNumber = new MyNumber();
        for(int i = 1;i <= SIZE;i ++){
    
            new Thread(() -> {
    
                for(int j = 1;j <= 1000;j ++){
    
                    myNumber.addPlusPlus();
                }
            },String.valueOf(i)).start();
        }
        System.out.println(Thread.currentThread().getName()+"\t"+"result: "+myNumber.atomicInteger);
    }
}
// It should have been 50000
//1 try -main result: 39000
//2 try -main result: 40178
//? Is there something wrong with our procedure ？

// Because of the above 50* 1000 The calculation is not over yet , He will go get Number 
```*

    solve 

```java
// Method 1 （ Not recommended , do Demo ok ）
public class AtomicIntegerDemo {
    
    public static final int SIZE = 50;
    public static void main(String[] args) {
    
        MyNumber myNumber = new MyNumber();
        for(int i = 1;i <= SIZE;i ++){
    
            new Thread(() -> {
    
                for(int j = 1;j <= 1000;j ++){
    
                    myNumber.addPlusPlus();
                }
            },String.valueOf(i)).start();
        }
        try {
    
            TimeUnit.SECONDS.sleep(2);
        } catch (InterruptedException e) {
    
            e.printStackTrace();
        }
        System.out.println(Thread.currentThread().getName()+"\t"+"result: "+myNumber.atomicInteger);
    }
}

// Method 2 - Subtraction counter CountDownLatch
public class AtomicIntegerDemo {
    
    public static final int SIZE = 50;
    public static void main(String[] args) throws InterruptedException {
    
        MyNumber myNumber = new MyNumber();
        CountDownLatch countDownLatch = new CountDownLatch(SIZE);
        for(int i = 1;i <= SIZE;i ++){
    
            new Thread(() -> {
    
                try {
    
                    for(int j = 1;j <= 1000;j ++){
    
                        myNumber.addPlusPlus();
                    }
                } finally {
    
                    countDownLatch.countDown();
                }
            },String.valueOf(i)).start();
        }
        countDownLatch.await();
        System.out.println(Thread.currentThread().getName()+"\t"+"result: "+myNumber.atomicInteger);
    }
}
//main result: 50000

Array type, atomic class

The basic principle is the same as above , Don't show too much

AtomicIntegerArray
AtomicLongArray
AtomicRreferenceArray

Case

public class AtomicIntegerArrayDemo
{
    
    public static void main(String[] args)
    {
    
        AtomicIntegerArray atomicIntegerArray = new AtomicIntegerArray(new int[5]);//0 0 0 0 0
        //AtomicIntegerArray atomicIntegerArray = new AtomicIntegerArray(5);
        //AtomicIntegerArray atomicIntegerArray = new AtomicIntegerArray(new int[]{1,2,3,4,5});//1 2 3 4 5 

        for (int i = 0; i <atomicIntegerArray.length(); i++) {
    
            System.out.println(atomicIntegerArray.get(i));
        }
        System.out.println();
        System.out.println();
        System.out.println();
        int tmpInt = 0;

        tmpInt = atomicIntegerArray.getAndSet(0,1122);
        System.out.println(tmpInt+"\t"+atomicIntegerArray.get(0));
        atomicIntegerArray.getAndIncrement(1);
        atomicIntegerArray.getAndIncrement(1);
        tmpInt = atomicIntegerArray.getAndIncrement(1);
        System.out.println(tmpInt+"\t"+atomicIntegerArray.get(1));
    }
}

Reference type atomic class

These three are relatively important

AtomicReference
AtomicStampedReference
AtomicMarkableReference
```*

   `AtomicReference`  Can take generics （ I talked about it before. ）

`AtomicReference<xxx> `*

   `AtomicStampedReference`  With version number in case CAS Medium ABA problem （ I talked about it before. ）

 Reference type atomic class with version number , Can solve ABA problem . Solve the problem that has been modified several times .*

   `AtomicMarkableReference` Similar to the above  , But the solution ** Disposable ** problem 

 Construction method `AtomicMarkableReference(V initialRef, boolean initialMark)`

 Atom updates reference type objects with tag bits 

 Solve whether it has been modified , Its definition is to ` Status stamp `** simplify ** by `true|false`, Similar to disposable chopsticks 

```java
// Here's a case 
public class AtomicMarkableReferenceDemo {
    

    static AtomicMarkableReference markableReference = new AtomicMarkableReference(100,false);

    public static void main(String[] args) {
    
        new Thread(()->{
    
            boolean marked = markableReference.isMarked();
            System.out.println(Thread.currentThread().getName()+"\t"+" The default ID "+marked);
            // Pause 1 Second thread , Wait for the next T2 The thread is in the same mode as I got flag identification , All are false
            try {
    TimeUnit.SECONDS.sleep(1);} catch (InterruptedException e) {
    e.printStackTrace();}
            markableReference.compareAndSet(100, 1000, marked, !marked);
        },"t1").start();

        new Thread(()->{
    
            boolean marked = markableReference.isMarked();
            System.out.println(Thread.currentThread().getName()+"\t"+" The default ID "+marked);
            // Stop here 2 second , Give Way t1 First modify , then t2 Try to modify 
            try {
    TimeUnit.SECONDS.sleep(2);} catch (InterruptedException e) {
    e.printStackTrace();}
            boolean t2Result = markableReference.compareAndSet(100, 1000, marked, !marked);
            System.out.println(Thread.currentThread().getName()+"\t"+"t2 Threads result--"+t2Result);
            System.out.println(Thread.currentThread().getName()+"\t"+markableReference.isMarked());
            System.out.println(Thread.currentThread().getName()+"\t"+markableReference.getReference());

        },"t2").start();
    }
}

Object's properties modify the atomic class

key word FieldUpdater

AtomicIntegerFieldUpdater// Atomic update object int The value of the type field 
AtomicLongFieldUpdater// Atomic update object Long The value of the type field 
AtomicReferenceFieldUpdater// Atom updates the value of the reference type field

Atomic updates in a more granular range
Insert picture description here

Purpose of use

With a thread safety belt Method to manipulate some fields in non thread safe objects *

for instance （ It is more granular / Image a field , Without locking the entire object ）

Insert picture description here

Use requirement

Updated object properties must use public volatile Modifier *

Because the attribute modification types of objects are all atomic classes abstract class * *, So every time you use it, you have to use static methods newUpdater() Create a Updater * *, And you need to set the classes and properties you want to update .

Case

AtomicIntegerFieldUpdater- This is for int type

class BankAccount{
    
    String bankName = "CCB";
    public volatile int money = 0;// Conditions for a 

    //synchronized edition 
// public synchronized void add(){
    
// money++;
// }
    //AtomicIntegerFieldUpdater edition 
    AtomicIntegerFieldUpdater<BankAccount> fieldUpdater =
            AtomicIntegerFieldUpdater.newUpdater(BankAccount.class,"money");// It only limits money This field , Condition 2 

    public void transMoney(BankAccount bankAccount){
    
        fieldUpdater.getAndIncrement(bankAccount);
    }

}

public class AtomicIntegerFieldUpdaterDemo {
    
    public static void main(String[] args) throws InterruptedException {
    
        BankAccount bankAccount = new BankAccount();
        CountDownLatch countDownLatch = new CountDownLatch(10);
        for(int i = 1;i <= 10;i ++){
    
            new Thread(()->{
    
                try {
    
                    for(int j = 1;j <= 1000;j ++){
    
                       // bankAccount.add();
                        bankAccount.transMoney(bankAccount);
                    }
                } finally {
    
                    countDownLatch.countDown();
                }
            },String.valueOf(i)).start();
        }
        countDownLatch.await();
        System.out.println(Thread.currentThread().getName()+"\t"+"result: "+bankAccount.money);
    }
}
//main result: 10000

```*

   `AtomicReferenceFieldUpdater`- Wider applicability 

```java
// For example, this case is for boolean Type of 
class MyVar{
    
    public volatile Boolean isInit = Boolean.FALSE;
    AtomicReferenceFieldUpdater<MyVar,Boolean> referenceFieldUpdater =
            AtomicReferenceFieldUpdater.newUpdater(MyVar.class,Boolean.class,"isInit");
    public void init(MyVar myVar){
    
        if(referenceFieldUpdater.compareAndSet(myVar,Boolean.FALSE,Boolean.TRUE)){
    
            System.out.println(Thread.currentThread().getName()+"\t"+"-----start init,needs 3 seconds");
            try {
    TimeUnit.SECONDS.sleep(3);} catch (InterruptedException e) {
    e.printStackTrace();}
            System.out.println(Thread.currentThread().getName()+"\t"+"-----over init");
        }else{
    
            System.out.println(Thread.currentThread().getName()+"\t"+" I'm sorry , Other threads have been initialized ");
        }
    }
}

public class AtomicReferenceFieldUpdaterDemo {
    
    public static void main(String[] args) {
    
        MyVar myVar = new MyVar();
        for(int i = 1;i <= 5;i ++){
    
            new Thread(()->{
    
                myVar.init(myVar);
            },String.valueOf(i)).start();
        }
    }
}
//1 -----start init,needs 3 seconds
//5  I'm sorry , Other threads have been initialized 
//4  I'm sorry , Other threads have been initialized 
//2  I'm sorry , Other threads have been initialized 
//3  I'm sorry , Other threads have been initialized 
//1 -----over init

interview

The interviewer asked you ： Where did you use volatile?

stay AtomicReferenceFieldUpdater in , Because it is stipulated that it must be volatile Embellished

And before that, we were DCL In a single case , Also used. volatile Guaranteed visibility

Deep analysis of the principle of atomic operation enhancement class

At the beginning, we divide atoms into red boxes and blue boxes , Here is the content of the blue box

// These are java8 At first , The front ones are java5 And then there is 
DoubleAccumulator
DoubleAdder
LongAccumulator
LongAdder

Ali is dying

Insert picture description here

Hot products like calculator , Like number plus Statistics , No real-time accuracy is required
A big one List, It's full of int type , How to realize Jiajia , Talk about ideas

Simulate the like counter , Look at the performance

requirement ： Hot products like calculator , Like number plus Statistics , No real-time accuracy is required

Look at this. LongAdder

Look at this. LongAccumulator

Insert picture description here

Commonly used API

Insert picture description here

Introduction

LongAdder Can only be used to calculate addition . And start from zero

LongAccumulator Provides custom function operations ( utilize lambda expression )

public class LongAdderAPIDemo {
    
    public static void main(String[] args) {
    
        LongAdder longAdder = new LongAdder();

        longAdder.increment();
        longAdder.increment();
        longAdder.increment();

        System.out.println(longAdder.longValue());//3

        LongAccumulator longAccumulator = new LongAccumulator((x, y) -> x + y, 0);//lambda expression 
        longAccumulator.accumulate(1);//1
        longAccumulator.accumulate(3);//4
        System.out.println(longAccumulator.get());//4
    }
}

LongAdder High performance comparison Code demonstration

// demand ：50 Threads , Every thread 100w Time , Calculate the total likes 
class ClickNumber{
    
    int number = 0;
    public synchronized void add1(){
    
        number++;
    }

    AtomicLong atomicLong =  new AtomicLong(0);
    public void add2(){
    
        atomicLong.incrementAndGet();
    }

    LongAdder longAdder =new LongAdder();
    public void add3(){
    
        longAdder.increment();
    }

    LongAccumulator longAccumulator = new  LongAccumulator((x,y) -> x + y,0);
    public void add4(){
    
        longAccumulator.accumulate(1);
    }
}
public class AccumulatorCompareDemo {
    
    public static final int _1W = 1000000;
    public static final int threadNumber = 50;
    public static void main(String[] args) throws InterruptedException {
    

        ClickNumber clickNumber = new ClickNumber();
        Long startTime;
        Long endTime;
        CountDownLatch countDownLatch1 = new CountDownLatch(50);
        CountDownLatch countDownLatch2 = new CountDownLatch(50);
        CountDownLatch countDownLatch3 = new CountDownLatch(50);
        CountDownLatch countDownLatch4 = new CountDownLatch(50);

        startTime = System.currentTimeMillis();
        for(int i = 1;i <= threadNumber;i ++){
    
            new Thread(()->{
    
                try {
    
                    for(int j = 1;j <=_ 1W;j ++){
    
                        clickNumber.add1();
                    }
                } finally {
    
                    countDownLatch1.countDown();
                }
            },String.valueOf(i)).start();
        }
        countDownLatch1.await();
        endTime = System.currentTimeMillis();
        System.out.println("costTime---"+(endTime-startTime)+" millisecond "+"\t"+"synchronized---"+clickNumber.number);

        startTime = System.currentTimeMillis();
        for(int i = 1;i <= threadNumber;i ++){
    
            new Thread(()->{
    
                try {
    
                    for(int j = 1;j <=_ 1W;j ++){
    
                        clickNumber.add2();
                    }
                } finally {
    
                    countDownLatch2.countDown();
                }
            },String.valueOf(i)).start();
        }
        countDownLatch2.await();
        endTime = System.currentTimeMillis();
        System.out.println("costTime---"+(endTime-startTime)+" millisecond "+"\t"+"atomicLong---"+clickNumber.atomicLong);

        startTime = System.currentTimeMillis();
        for(int i = 1;i <= threadNumber;i ++){
    
            new Thread(()->{
    
                try {
    
                    for(int j = 1;j <=_ 1W;j ++){
    
                        clickNumber.add3();
                    }
                } finally {
    
                    countDownLatch3.countDown();
                }
            },String.valueOf(i)).start();
        }
        countDownLatch3.await();
        endTime = System.currentTimeMillis();
        System.out.println("costTime---"+(endTime-startTime)+" millisecond "+"\t"+"LongAdder---"+clickNumber.longAdder.sum());

        startTime = System.currentTimeMillis();
        for(int i = 1;i <= threadNumber;i ++){
    
            new Thread(()->{
    
                try {
    
                    for(int j = 1;j <=_ 1W;j ++){
    
                        clickNumber.add4();
                    }
                } finally {
    
                    countDownLatch4.countDown();
                }
            },String.valueOf(i)).start();
        }
        countDownLatch4.await();
        endTime = System.currentTimeMillis();
        System.out.println("costTime---"+(endTime-startTime)+" millisecond "+"\t"+"LongAccumulator---"+clickNumber.longAccumulator.longValue());
    }
    //costTime---2205 millisecond  synchronized---50000000
    //costTime---435 millisecond  atomicLong---50000000
    //costTime---86 millisecond  LongAdder---50000000
    //costTime---84 millisecond  LongAccumulator---50000000
}// It confirms what alikafa manual says  【 If it is JDK8, Recommended LongAdder object , Than AtomicLong Better performance （ Reduce the number of retries for optimistic locks ）】

Source code 、 Principle analysis

framework

Insert picture description here

LongAdder yes Striped64 Subclasses of

public class LongAdder extends Striped64 implements Serializable {
    
    private static final long serialVersionUID = 7249069246863182397L;
 //---------------------------
 abstract class Striped64 extends Number {

principle （LongAdder Why so soon? ）

The official website description and Alibaba requirements

Ali explained

Insert picture description here

Website shows

LongAdder yes Striped64 Subclasses of

Striped64

Important member functions

//Number of CPUS, to place bound on table size 
// CPU Number , namely cells The maximum length of an array  
static final int NCPU = Runtime.getRuntime().availableProcessors();


//Table of cells. When non-null, size is a power of 2.
// Cell array |cells Array , by 2 The power of ,2,4,8,16....., Convenient for later bit operation 
transient volatile Cell[] cells;

// Basics value value , When concurrency is low , Only accumulate this value. It is mainly used when there is no competition , adopt CAS to update .
//Base value, used mainly when there is no contention, but also as
//a fallback during table initialization races. Updated via CAS.
transient volatile long base;

// Create or expand Cells The spin lock variable used when array resizes the cell （ Capacity expansion ）, Lock used when creating cells .
//Spinlock (locked via CAS) used when resizing and/or creating Cells. 
transient volatile int cellsBusy;

The two most important

Insert picture description here

Striperd64 Definition of some variables or methods in

Insert picture description here

Cell

yes java.util.concurrent.atomic Next Striped64 A static inner class of

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

        // Unsafe mechanics
        private static final sun.misc.Unsafe UNSAFE;
        private static final long valueOffset;
        static {
    
            try {
    
                UNSAFE = sun.misc.Unsafe.getUnsafe();
                Class<?> ak = Cell.class;
                valueOffset = UNSAFE.objectFieldOffset
                    (ak.getDeclaredField("value"));
            } catch (Exception e) {
    
                throw new Error(e);
            }
        }
    }

LongAdder Why so soon?

In fact, the situation is similar in small concurrency ; But in the case of high concurrency , stay AtomicLong in , The waiting thread will spin constantly , Resulting in low efficiency ; and LongAdder use cell[] Divided into several pieces , Finally, count the total result value （base+ be-all cell value ）, Disperse hot spots .

An example of image , Buy train tickets at the railway station ,AtomicLong Just one window , Everyone else is waiting in line ; and LongAdder utilize cell Many ticket windows have been opened , So the efficiency is much higher .

Insert picture description here

In a word

LongAdder The basic idea is Disperse hot spots , take value Scatter values into one Cell Array , Different threads will hit different slots in the array , Each thread only performs on that value in its own slot CAS operation , So the hot spots are scattered , The probability of conflict is much smaller . If you want to get real long value , Just add up the variable values in each slot and return to .

sum() Will bring all Cell Array value and base Accumulate as the return value , The core idea is to put the previous AtomicLong One value The update pressure is distributed to multiple value In the middle , So as to downgrade the update hotspot .

Insert picture description here

Mathematical expression

There's a base Variable , One Cell[] Array .

base Variable ： Under non competitive conditions , Add directly to the variable

Cell[] Array ： Under competitive conditions , Accumulate the slots of each thread Cell[i] in

Source code interpretation and in-depth analysis

A small summary

LongAdder In the absence of competition , Follow AtomicLong equally , Yes The same base To operate , When there is a competitive relationship, it is the practice of breaking up the whole into parts , Change time from space , Use an array \ \ , Will a value Split into this array cells. Multiple threads need to pair at the same time value During operation , Can be on the thread id Conduct hash obtain hash value , According to hash Values are mapped to this array cells A subscript of , Then the value corresponding to the subscript is automatically increased . When all threads are finished , Will array cells All values and non competitive values base All add up as the final result .
Insert picture description here

LongAdder.increment()

Second brush is required

1-add(1L)

public class LongAdder extends Striped64 implements Serializable {
    
    private static final long serialVersionUID = 7249069246863182397L;

    /*** Creates a new adder with initial sum of zero.* / public LongAdder() { } /*** Adds the given value.** @param x the value to add* / 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); } } // What really works is longAccumulate //as Express cells quote  //b Represents the acquired base value  //v Indicates the expected value  //m Express cells Length of array  //a Represents the hit of the current thread cell Cell

uncontended Represents no conflict .

Let's click in this casBase I found that he was also a CAS

final boolean casBase(long cmp, long val) {
    
        return UNSAFE.compareAndSwapLong(this, BASE, cmp, val);
    }

At first, when the competition was small CAS To succeed , That is to say casBase To succeed , then cells It's also empty , So it won't go into the cycle

Insert picture description here

When the competition is big , He will Cell[] rs = new Cell[2]; Two new cell, here ≠ null , The conditions are met , Into the loop .

Then there is another layer of circulation , Here are several if side by side

Insert picture description here

To sum up
1. Only update when there is no competition at first base;
2. If updated base After failure , Create a new one for the first time Cell[] Array
3. When multiple threads compete for the same Cell When the price competition is fierce , It may be necessary to use longAccumulate Yes Cell[] Capacity expansion .

Once again, I want to summarize

Insert picture description here

2-longAccumulate

    final void longAccumulate(long x, LongBinaryOperator fn,
                              boolean wasUncontended) {
    
        int h;
        if ((h = getProbe()) == 0) {
    
            ThreadLocalRandom.current(); // force initialization
            h = getProbe();
            wasUncontended = true;
        }
        boolean collide = false;                // True if last slot nonempty
        for (;;) {
    
            Cell[] as; Cell a; int n; long v;
            if ((as = cells) != null && (n = as.length) > 0) {
    
            // Here is ③ Cell The array is no longer empty and may exist Cell Array capacity 
                if ((a = as[(n - 1) & h]) == null) {
    
                    if (cellsBusy == 0) {
           // Try to attach new Cell
                        Cell r = new Cell(x);   // Optimistically create
                        if (cellsBusy == 0 && casCellsBusy()) {
    
                            boolean created = false;
                            try {
                   // Recheck under lock
                                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;           // Slot is now non-empty
                        }
                    }
                    collide = false;
                }
                else if (!wasUncontended)       // CAS already known to fail
                    wasUncontended = true;      // Continue after rehash
                else if (a.cas(v = a.value, ((fn == null) ? v + x :
                                             fn.applyAsLong(v, x))))
                    break;
                else if (n >= NCPU || cells != as)// No more than cpu Check the number 
                    collide = false;            // At max size or stale
                else if (!collide)
                    collide = true;
                else if (cellsBusy == 0 && casCellsBusy()) {
    
                    try {
    
                        if (cells == as) {
          // Expand table unless stale
                            Cell[] rs = new Cell[n << 1];// Capacity expansion - The left one , amount to x2
                            for (int i = 0; i < n; ++i)
                                rs[i] = as[i];
                            cells = rs;
                        }
                    } finally {
    
                        cellsBusy = 0;
                    }
                    collide = false;
                    continue;                   // Retry with expanded table
                }
                h = advanceProbe(h);
            }
            else if (cellsBusy == 0 && cells == as && casCellsBusy()) {
    
            // Here is ① initialization 
                boolean init = false;
                try {
                               // Initialize table
                    if (cells == as) {
    
                        Cell[] rs = new Cell[2];
                        rs[h & 1] = new Cell(x);
                        cells = rs;
                        init = true;
//------ You can look here first , It's initialized , The length is 2
//------cells Array , by 2 The power of ,2,4,8,16, Convenient for later bit operation 
                    }
                } finally {
    
                    cellsBusy = 0;
                }
                if (init)
                    break;
            }
            else if (casBase(v = base, ((fn == null) ? v + x :
                                        fn.applyAsLong(v, x))))// Here is ② The bottom line 
                break;                          // Fall back on using base
        }
    }

LongAccumulate Introduction

Insert picture description here

Striped64 Definition of some variables or methods in

Insert picture description here

step
Let's talk about this first (a = as[getProbe() & m]) Inside probe, I actually took it here hash value , adopt hash It's worth knowing where we're going cell Slot

static final int getProbe() {
    
        return UNSAFE.getInt(Thread.currentThread(), PROBE);
    }

// In fact, you get the thread Hash value

So the first paragraph is like a new employee getting a job number （hash value ） equally
Insert picture description here

general programme

Insert picture description here

The above code first assigns a to the current thread hash value , And then into a for(;;) The spin , This spin is divided into three branches ：
CASE1：Cell[] Array has been initialized
CASE2：Cell[] Array not initialized ( New for the first time )
CASE3：Cell[] Array initializing

Calculation

① Just about to initialize Cell[] Array （ New for the first time ）

Insert picture description here

If the above conditions are executed successfully, the initialization and assignment of the array will be executed , Cell[] rs = new Cell[2] Indicates that the length of the array is 2,
rs[h & 1] = new Cell(x) To create a new Cell Elements ,value yes x value , The default is 1.
h & 1 Similar to before us HashMap Commonly used calculation hash bucket index The algorithm of , Is usually hash & (table.len - 1). Same as hashmap One meaning .

② The bottom line

Multiple threads try CAS The thread that fails to modify will go to this branch

// At the bottom 
else if (casBase(v = base, ((fn == null) ? v + x :
                                        fn.applyAsLong(v, x))))
// This branch implements direct operations base base , Accumulate the value to base On , That is, other threads are initializing , Multiple threads are updating base Value .

③Cell The array is no longer empty and may exist Cell Array capacity

Multiple threads hit one at the same time cell competition , This is The most complicated Part of

(1)
Insert picture description here

The above code determines the current thread hash Whether the data location element pointed to after is empty ,
If it is empty, it will Cell Put the data into the array , Out of the loop .
If it is not empty, continue the cycle .

(2)

[ Failed to transfer the external chain picture , The origin station may have anti-theft chain mechanism , It is suggested to save the pictures and upload them directly (img-BDY3L1CW-1656407207550)(image/image_miqNJM3b9d.png)]

(3)

Insert picture description here

Indicates that there is data in the array corresponding to the current thread , Also reset hash value ,
At this time through CAS The operation attempts to the current number of value Value is added up x operation ,x The default is 1, If CAS Success directly jumps out of the loop .

(4)

Insert picture description here

(5)

Insert picture description here

(6)

Insert picture description here

The above six steps are summarized

Insert picture description here

3-sum

Insert picture description here

//LongAdder.java
public long sum() {
    
        Cell[] as = cells; Cell a;
        long sum = base;
        if (as != null) {
    
            for (int i = 0; i < as.length; ++i) {
    
                if ((a = as[i]) != null)
                    sum += a.value;
            }
        }
        return sum;
    }

sum() Will bring all Cell Array value and base Add up As return value .
The core idea is to put the previous AtomicLong One value The update pressure is distributed to multiple value In the middle , So as to downgrade the update hotspot .

Why in the case of concurrency sum The value of is not accurate ？

sum Execution time , There is no limit to base and cells Update ( A deadly word ). therefore LongAdder Not strong consistency Of , It is Final consistency Of .

First , Finally returned sum local variable , The initial is copied as base, And when you finally return , Probably base Has been updated , At this point, the local variable sum Will not update , To cause disagreement .
secondly , Here to cell The read of cannot be guaranteed to be the last written value . therefore ,sum Methods without concurrency , You can get the right results .

Use summary

AtomicLong

Thread safety , Some performance loss is allowed , When high precision is required, it can be used

Guarantee accuracy , Performance cost

AtomicLong Multiple threads for a single hotspot value value Perform atomic operations

LongAdder

When it is necessary to have good performance under high and low performance , And the accuracy of the value is not high , have access to

Guaranteed performance , The cost of accuracy

LongAdder Each thread has its own slot , Each thread generally only checks the value in its own slot CAS operation

A small summary

AtomicLong

principle

CAS+ The spin

incrementAndGet

scene

Global computing under low concurrency

AtomicLong It can ensure the accuracy of counting in case of concurrency , It passes through CAS To solve the problem of concurrency security

defects

The performance drops sharply after high concurrency

why?AtomicLong The spin of will be called a bottleneck （N Threads CAS Modify the operation value of the thread , Only one has succeeded at a time , Other N - 1 Failure , The failure keeps spinning until success , Such a large number of failed spins , once cpu Just hit high .）