preface

ThreadLocal: ThreadLocal: ThreadLocal: ThreadLocal: ThreadLocal: ThreadLocal: ThreadLocal: ThreadLocal: ThreadLocal: ThreadLocal I must also give you a full sense of the ideas behind it! So I’d like to write an article about ThreadLocal in a more straightforward way, using a lot of graphical parsing to prove: I’m dry, not water!

The ThreadLocal class, with its huge comments, is only about 700 lines long, and if you copy the code for this class, you’ll notice that it rarely returns an error! Very low coupling! (The only error is that the ThreadLocal class references a visible variable in the Thread class, so copy the code and the variable access will fail, only here!)

The ThreadLocal thread isolation, replacement, and erasing algorithms are all important to understand. A small amount of code can achieve such a subtle function. Let’s take a look at the work of Josh Bloch and Doug Lea.

Some instructions

This article drew a lot of diagrams, about 18 diagrams, about the replacement algorithm and erase algorithm, these two methods do things, if you do not draw pictures, only words describe, very abstract and difficult to understand; I hope these flow charts can make you more understand the charm of these refined code!

use

Before the beep principle, you have to take a look at how it works

  • Surprisingly easy to use, just useset()andget()Methods can be
public class Main {

    public static void main(String[] args) {
        ThreadLocal<String> threadLocalOne = new ThreadLocal<>();
        ThreadLocal<String> threadLocalTwo = new ThreadLocal<>();

        new Thread(new Runnable() {
            @Override
            public void run(a) {
                threadLocalOne.set("Thread 1 data -- threadLocalOne");
                threadLocalTwo.set("Data from thread 1 -- threadLocalTwo");
                System.out.println(threadLocalOne.get());
                System.out.println(threadLocalTwo.get());
            }
        }).start();

        new Thread(new Runnable() {
            @Override
            public void run(a) {
                System.out.println(threadLocalOne.get());
                System.out.println(threadLocalTwo.get());
                threadLocalOne.set("Data for Thread two -- threadLocalOne");
                threadLocalTwo.set("Data from thread two -- threadLocalTwo"); System.out.println(threadLocalOne.get()); System.out.println(threadLocalTwo.get()); } }).start(); }}Copy the code
  • Print the result
    • Typically, we create a variable in main memory (or worker thread); The variable data is modified in the child thread. When the child thread ends, the modified data is synchronized to the variable in main memory
    • Here, however, you can see that both threads use the same variable, but the data set in thread one does not affect thread two at all
    • Cool! Easy to use and also implements data isolation with different threads
ThreadLocalOne Data for thread one threadLocalTwonull
nullThreadLocalOne Thread two data threadLocalTwoCopy the code

Front knowledge

Before explaining the overall logic of ThreadLocal, there are a few prerequisites

The following are some of the things you need to know before you talk about set and GET

Thread isolation

One of the interesting things about ThreadLocal is that it seems to store different data in different threads, just as ThreadLocal has storage capabilities that allow different threads to make different ‘copies’ of the data

Actually, how does ThreadLocal do it?

  • Let’s take a look at the set() method to see how the data is stored: this involves the ThreadLocalMap type, which is treated as a Map for the moment
    • The Thread and ThreadLocal classes work together to isolate Thread data
    • As you can see in the code below, when data is plugged, the current thread performing the operation is retrieved
    • Get the current thread, get the threadLocals variable, and stuff the map as if the current instance is the key and the data value.
    • When a ThreadLocal is used to write data on different threads, data is actually bound to the current thread instance. A ThreadLocal is only responsible for reading and writing data, but it does not store data
    • Do you feel that this kind of thinking is a little clever!
/ / data
public void set(T value) {
    Thread t = Thread.currentThread();
    ThreadLocal.ThreadLocalMap map = getMap(t);
    if(map ! =null)
        map.set(this, value);
    else
        createMap(t, value);
}

// Get the threadLocals variable of the current Thread
ThreadLocal.ThreadLocalMap getMap(Thread t) {
    return t.threadLocals;
}

/ / Thread class
public class Thread implements Runnable {.../* ThreadLocal values pertaining to this thread. This map is maintained * by the ThreadLocal class. */
    ThreadLocal.ThreadLocalMap threadLocals = null; . }Copy the code
  • Take a look at the diagram
    • The graph only draws one ThreadLocal, wants to spend more, then the lines cross, dizzy
    • ThreadLocals can store multiple threadLocals. The process for accessing multiple threadLocals is similar to the following

  • To summarize: with the very simple code above, data isolation of threads is achieved, and a few conclusions can be drawn
    • ThreadLocal objects themselves do not store data and perform set, GET, and other operations
    • An instance of the current thread that stores data passed in by ThreadLocal’s set operation and is bound to the instance of the current thread
    • A ThreadLocal instance can store only one type of data in a thread, and subsequent set operations overwrite the previous set
    • ThreadLocals is an array structure that stores data from several different ThreadLocal instance sets

Entry

  • When it comes to Entry, you need to know the basics of the following four references

Strong references: No matter how memory is tight, the GC will never reclaim strongly referenced objects

Soft reference: When memory runs out, gc reclaims soft reference objects

Weak references: When gc finds a weak reference, it immediately reclaims the weak reference object

Virtual references: Can be collected by the garbage collector at any time

Entry is an entity class that has two attributes: key and value. Key is a weak reference

When we perform the set operation on a ThreadLocal, the first new Entry or subsequent set overwrites the value of the changed Entry and inserts it into the ThreadLocals variable of the current Thread

  • Take a look at the Entry code
    • Here, the key acquisition is an instance of ThreadLocal itself. It can be seen that the key attribute held by Entry is a weak reference attribute
    • Value is the data we pass in: the type depends on the generics we define
static class Entry extends WeakReference<ThreadLocal<? >>{
    /** The value associated with this ThreadLocal. */Object value; Entry(ThreadLocal<? > k, Object v) {super(k); value = v; }}Copy the code
  • Entry has a clever structure. It inherits a weak reference class and then defines a strong reference property within itself, making the class strong and weak
  • chart

You might be thinking, what? I’m using ThreadLocal to set a data, and then I’m going to gc it, and I’m going to break the key variable reference chain in my Entry, okay?

  • To have a try
public class Main {

    public static void main(String[] args) {
        ThreadLocal<String> threadLocalOne = new ThreadLocal<>();

        new Thread(new Runnable() {
            @Override
            public void run(a) {
                threadLocalOne.set("Thread 1 data -- threadLocalOne"); System.gc(); System.out.println(threadLocalOne.get()); } }).start(); }}Copy the code
  • The results of
Thread one data - threadLocalOneCopy the code

Looks like it’s getting lonely in here…

Here, we must make it clear that gc collects weak reference objects first, and the weak reference chain is naturally broken. Instead of breaking the chain of references and then reclaiming the object. The Entry key’s reference to the ThreadLocal is weak, but threadLocalOne’s reference to the ThreadLocal is strong, so the ThreadLocal object cannot be reclaimed

  • Take a look at the actual reference relationship of the code above

  • Here you can see how a threadLocalOne reference to a ThreadLocal breaks and the key reference in the Entry is reclaimed by the GC
public class Main {
    static ThreadLocal<String> threadLocalOne = new ThreadLocal<>();

    public static void main(String[] args) {
        new Thread(new Runnable() {
            @Override
            public void run(a) {
                threadLocalOne.set("Thread 1 data -- threadLocalOne");
                try {
                    threadLocalOne = null;
                    System.gc();

                    / / the following code from: https://blog.csdn.net/thewindkee/article/details/103726942
                    Thread t = Thread.currentThread();
                    Class<? extends Thread> clz = t.getClass();
                    Field field = clz.getDeclaredField("threadLocals");
                    field.setAccessible(true); Object threadLocalMap = field.get(t); Class<? > tlmClass = threadLocalMap.getClass(); Field tableField = tlmClass.getDeclaredField("table");
                    tableField.setAccessible(true);
                    Object[] arr = (Object[]) tableField.get(threadLocalMap);
                    for (Object o : arr) {
                        if (o == null) continue; Class<? > entryClass = o.getClass(); Field valueField = entryClass.getDeclaredField("value");
                        Field referenceField = entryClass.getSuperclass().getSuperclass().getDeclaredField("referent");
                        valueField.setAccessible(true);
                        referenceField.setAccessible(true);
                        System.out.println(String.format(Weak reference key:%s value :%s, referenceField.get(o), valueField.get(o))); }}catch(Exception e) { } } }).start(); }}Copy the code
  • The results of
    • Key is null! ThreadLocalOne = null breaks a strong reference to a ThreadLocal object
    • If you’re interested, you can get rid of threadLocalOne = null, and run it again, and you’ll see that the key is not empty
    • The function of the reflection code is to obtain the threadLocals variable from the Thread, cycle through the Entry, and print the key and value of the Entry
A weak reference key: null values: thread a data - threadLocalOne weak references key: Java. Lang. ThreadLocal @ 387567 b2 values: Java. Lang. Ref. Fb3f SoftReference @ 2021Copy the code
  • conclusion
    • You might think, well, this variable has a strong reference all the time, but key doesn’t have a weak reference, and child thread code doesn’t take long to execute
    • In fact, if we think about the main thread in the Android app, it is an endless loop, driven by events, which can do a lot of very difficult logic, and this strongly referenced variable is likely to be assigned other values
      • If the key is a strong reference, then the ThreadLocal inside the Entry is basically hard to reclaim
      • Key is a weak reference. When the strong reference chain of a ThreadLocal object is broken, it can be easily reclaimed. The relevant cleanup algorithm can also easily clean up entries with null keys
    • There’s so much you can do with a weak reference

ThreadLocalMap ring structure

  • Let’s look at the ThreadLocalMap code
    • Let’s get rid of a bunch of code that we don’t need to focus on for now
    • The table is the main structure of ThreadLocalMap, and the data is stored in this array
    • So the body structure of a ThreadLocalMap is an array of entries
public class ThreadLocal<T> {...static class ThreadLocalMap {

        static class Entry extends WeakReference<ThreadLocal<? >>{
            /** The value associated with this ThreadLocal. */Object value; Entry(ThreadLocal<? > k, Object v) {super(k); value = v; }}/** * The table, resized as necessary. * table.length MUST always be a power of two. */
        privateEntry[] table; . }}Copy the code
  • Now again, you might wonder, isn’t this thing just an array? How does that relate to the ring structure?

  • Arrays normally do look like this

  • However, there is a method in the ThreadLocalMap class that does a dirty operation. Look at the code
public class ThreadLocal<T> {...static class ThreadLocalMap {...private static int nextIndex(int i, int len) {
            return ((i + 1 < len) ? i + 1 : 0); }... }}Copy the code
  • Does this nextIndex method make sense?
    • All it does is add one to the incoming index
    • But! When the index exceeds the length of the array, it returns 0, back to the head of the array, and completes the loop structure

  • conclusion
    • One of the big benefits of doing this is that it saves a lot of memory and makes full use of the array space
    • It’s a little bit less efficient when it comes to fetching data, time replaces space

set

The total process

  • The following code is very simple
    1. Gets the current thread instance
    2. Gets the threadLocals instance from the current thread
    3. ThreadLocals does not perform a plug value operation for null
    4. If threadLocals is empty, new assigns a ThreadLocalMap to threadLocals and inserts an Entry
public void set(T value) {
    Thread t = Thread.currentThread();
    ThreadLocalMap map = getMap(t);
    if(map ! =null)
        map.set(this, value);
    else
        createMap(t, value);
}

ThreadLocalMap getMap(Thread t) {
    return t.threadLocals;
}

void createMap(Thread t, T firstValue) {
    t.threadLocals = new ThreadLocalMap(this, firstValue); } ThreadLocalMap(ThreadLocal<? > firstKey, Object firstValue) { table =new Entry[INITIAL_CAPACITY];
    int i = firstKey.threadLocalHashCode & (INITIAL_CAPACITY - 1);
    table[i] = new Entry(firstKey, firstValue);
    size = 1;
    setThreshold(INITIAL_CAPACITY);
}
Copy the code
  • Note that ThreadLocalMap generates an Entry array with a default length of 16
 private static final int INITIAL_CAPACITY = 16; ThreadLocalMap(ThreadLocal<? > firstKey, Object firstValue) { table =newEntry[INITIAL_CAPACITY]; . }Copy the code
  • The flow chart

map.set

  • After a few details, let’s move on to the most important map.set(this, value) method
private void set(ThreadLocal
        key, Object value) {

    // We don't use a fast path as with get() because it is at
    // least as common to use set() to create new entries as
    // it is to replace existing ones, in which case, a fast
    // path would fail more often than not.

    Entry[] tab = table;
    int len = tab.length;
    int i = key.threadLocalHashCode & (len-1);

    for(Entry e = tab[i]; e ! =null; e = tab[i = nextIndex(i, len)]) { ThreadLocal<? > k = e.get();if (k == key) {
            e.value = value;
            return;
        }

        if (k == null) {
            replaceStaleEntry(key, value, i);
            return;
        }
    }

    tab[i] = new Entry(key, value);
    int sz = ++size;
    if(! cleanSomeSlots(i, sz) && sz >= threshold) rehash(); }Copy the code

Take a hash value

  • The code above has an operation to calculate the hash value
    • From the key.threadLocalHashCode line, it looks as if it is computing the hash value from its own instance
    • Instead of converting the current ThreadLocal object into a hash value, the key is passed in to call the nextHashCode method
public class ThreadLocal<T> {
    private final int threadLocalHashCode = nextHashCode();

    private static final int HASH_INCREMENT = 0x61c88647;
    
    private static AtomicInteger nextHashCode = new AtomicInteger();

    private void set(ThreadLocal
        key, Object value) {...int i = key.threadLocalHashCode & (len-1); . }private static int nextHashCode(a) {
        returnnextHashCode.getAndAdd(HASH_INCREMENT); }}Copy the code
  • I’m using an atomic class operation here. Let’s seegetAndAdd()Function of method
    • This is a function that adds, and then returns the old value, ensuring that the operation is atomic and indivisible
public class Main {
    public static void main(String[] args) {
        AtomicInteger atomicInteger = new AtomicInteger();
        
        System.out.println(atomicInteger.getAndAdd(1));  / / 0
        System.out.println(atomicInteger.getAndAdd(1));  / / 1
        System.out.println(atomicInteger.getAndAdd(1));  / / 2}}Copy the code
  • 1,2,3,4,5,6 HASH_INCREMENT = 0x61c88647

The addition of these values, in accordance with Fibonacci hashing, results in a more uniform distribution of the lower-order binary values, which reduces the number of hash collisions in the array

See the hash algorithm from the implementation of ThreadLocal

Wait, did you see threadLocalHashCode = nextHashCode(), nextHashCode() is the method to get the next node, what the hell is that?

Does the HashCode change every time you use key.threadLocalHashCode?

  • Take a look at the complete assignment statement
    • This is defined directly when the variable is initialized
    • When instantiating the class, nextHashCode() gets the HashCode once and does not get it again
    • With the final modifier, it can only be assigned once
    • So the threadLocalHashCode variable, when you instantiate a ThreadLocal, gets the HashCode once, and that value is fixed and never changed in the instance
public class ThreadLocal<T> {
    private final int threadLocalHashCode = nextHashCode();
}
Copy the code

Seems to have found another problem! ThreadHashCode gets HashCode from nextHashCode(), and nextHashCode is added to nextHashCode variables using AtomicInteger. Isn’t this thing zero every time it is instantiated?

Do we add from zero every time a new ThreadLocal instance gets HashCode?

  • Take a look at the complete code
    • If you look at the nextHashCode variable of type AtomicInteger, its modifier keyword is static
    • This means that the value of the variable is bound to the class, independent of the instance generated by the class, and will only be instantiated once from start to finish
    • When different ThreadLocal instances call nextHashCode, their values are added once
    • Also, the nextHashCode() method can only be called once per instance, and the nextHashCode value changes evenly
public class ThreadLocal<T> {
    private final int threadLocalHashCode = nextHashCode();

    private static final int HASH_INCREMENT = 0x61c88647;
    
    private static AtomicInteger nextHashCode = new AtomicInteger();

    private static int nextHashCode(a) {
        returnnextHashCode.getAndAdd(HASH_INCREMENT); }}Copy the code

conclusion

  • By initializing a few lines, a few keywords, you can form a HashCode value that changes steadily from instance to instance
  • These basic knowledge we probably know, and how much can be so handy?

The index value

In the above code, the hash value is computed with the sum of the array length subtracted by one from the ThreadLocalMap instance

This is important because high hash values greater than length are not needed

This will compute a hash value for the ThreadLocal instance that is passed in. This will compute a hash value for the ThreadLocal instance that is passed in. This will compute a hash value for the ThreadLocal instance that is passed in

  • For example, the hash value is 010110011101
  • Length (select the default value 16-1) : 01111
  • As you can see in the figure below, this and operation removes high hash values that are useless and fetches index values that are limited to the length of the array

Plug the value

  • Take a look at the operation of the plug value into the ThreadLocalMap array
    • About Key: because Entry is an inherited WeakReference class, the get() method is to get its internal WeakReference object, so you can get the current ThreadLocal instance through get()
    • For value: just.value is OK
private void set(ThreadLocal
        key, Object value) {
    Entry[] tab = table;
    int len = tab.length;
    int i = key.threadLocalHashCode & (len-1);

    for(Entry e = tab[i]; e ! =null; e = tab[i = nextIndex(i, len)]) { ThreadLocal<? > k = e.get();if (k == key) {
            e.value = value;
            return;
        }

        if (k == null) {
            replaceStaleEntry(key, value, i);
            return;
        }
    }

    tab[i] = newEntry(key, value); . }Copy the code

Analyze the plug value process

  • It’s actually worth thinking about the loop, and thinking about what this loop deals with

  • Loop to get the current index value, from the Entry array to the current index position of the Entry object

  1. If the Entry is null, the loop body is terminated
    • Insert a newly generated node into the index of the Entry array
  2. If the Entry obtained is not NULL
    1. If the key value is equal, the Entry object exists
    2. If the key is null, the node can be replaced (the replacement algorithm will be discussed later). An Entry object is created and data is stored in this node
    3. If the key is not equal and not null, the loop retrieves the Entry object of the next node and repeats the above logic

The overall logic is clear. If the key already exists, the key is overwritten. Does not exist, index position is available, yes use the node, not available, find available node later: linear detection method

  • Replace the logic of the old node, it is a bit round, put forward separately below to explain

Replacement algorithm

In the set method above, when the generated index node is occupied, the available nodes are probed backwards

  • If the node being probed is null, it is used directly
  • If the key value of the detected nodes is the same, the value value will be overwritten
  • If the key values of the detected nodes are different, continue to probe backward
  • If the node key value is null, an operation will be performed to replace the old node
private void set(ThreadLocal
        key, Object value) {
    Entry[] tab = table;
    int len = tab.length;
    int i = key.threadLocalHashCode & (len-1);

    for(Entry e = tab[i]; e ! =null; e = tab[i = nextIndex(i, len)]) { ThreadLocal<? > k = e.get(); .if (k == null) {
            replaceStaleEntry(key, value, i);
            return; }}... }Copy the code
  • Take a look at the logic in the replaceStaleEntry method
private static int prevIndex(int i, int len) {
    return ((i - 1> =0)? i -1 : len - 1);
}

private void replaceStaleEntry(ThreadLocal<? > key, Object value,int staleSlot) {
    Entry[] tab = table;
    int len = tab.length;
    Entry e;

    // Back up to check for prior stale entry in current run.
    // We clean out whole runs at a time to avoid continual
    // incremental rehashing due to garbage collector freeing
    // up refs in bunches (i.e., whenever the collector runs).
    int slotToExpunge = staleSlot;
    for (inti = prevIndex(staleSlot, len); (e = tab[i]) ! =null; i = prevIndex(i, len))
        if (e.get() == null)
            slotToExpunge = i;

    // Find either the key or trailing null slot of run, whichever
    // occurs first
    for (inti = nextIndex(staleSlot, len); (e = tab[i]) ! =null; i = nextIndex(i, len)) { ThreadLocal<? > k = e.get();// If we find key, then we need to swap it
        // with the stale entry to maintain hash table order.
        // The newly stale slot, or any other stale slot
        // encountered above it, can then be sent to expungeStaleEntry
        // to remove or rehash all of the other entries in run.
        if (k == key) {
            e.value = value;

            tab[i] = tab[staleSlot];
            tab[staleSlot] = e;

            // Start expunge at preceding stale entry if it exists
            if (slotToExpunge == staleSlot)
                slotToExpunge = i;
            cleanSomeSlots(expungeStaleEntry(slotToExpunge), len);
            return;
        }

        // If we didn't find stale entry on backward scan, the
        // first stale entry seen while scanning for key is the
        // first still present in the run.
        if (k == null && slotToExpunge == staleSlot)
            slotToExpunge = i;
    }

    // If key not found, put new entry in stale slot
    tab[staleSlot].value = null;
    tab[staleSlot] = new Entry(key, value);

    // If there are any other stale entries in run, expunge them
    if(slotToExpunge ! = staleSlot) cleanSomeSlots(expungeStaleEntry(slotToExpunge), len); }Copy the code

  • In the above code, it is clear that two loops are the key logic. There are two very important fields: slotToExpunge and staleSlot

    • StaleSlot: records the position where the key of the imported node is null
    • SlotToExpunge: indicates whether the last cleaning method needs to be performed

  • The first loop obviously probes the front table header to see if there are any other nodes with a null key, and assigns their subscripts to slotToExpunge. The probe is a continuous non-null chain of nodes, empty nodes, and immediately ends the loop

  • The second loop: it’s obviously going backwards, exploring the entire array, and there’s a lot of logic here

    • This place is starting to get a little convoluted, I Giao. Think about it
    • When the detected key is the same as the incoming key that needs to be set, the value of the detected Entry is overwritten, and the detected position and the incoming position are swapped

  • Why is the detected Entry the same as the incoming key?

    • The same is true because a hash conflict occurs when an array is entered, which automatically probes back to the appropriate location for storage
    • When you use ThreadLocal the second time, the index produced by the hash and the key produced by the hash cannot be the same, because there is a hash collision, and the actual Entry is stored later; So you need to probe backwards
    • Assume that no Entry with a null key is encountered during the detection. In a normal loop, an Entry with the same key must be detected and the value operation is overwritten
    • But what about an Entry with a null key? At this point, the old Entry replacement algorithm is entered, so the replacement algorithm also has a backward-probing logic
    • If an Entry with the same key value is detected, the Entry instance that we need to duplicate value is found

  • Why do you want to switch places?

    • This question, you can think about, we will detect later, and this Entry instance with a null key is one of the faster detected entries

    • The key of the Entry instance is null, indicating that the Entry can be reclaimed, and it is occupying the manger

    • At this point, I can swap the Entry instance I need to duplicate with the Entry whose key is null

    • In this way, the Entry instance that we need to operate can be found as soon as possible in the next operation

  • After the transposition, the erase old node algorithm is performed

  • Check for consecutive Entry nodes without encountering null nodes. If a null node is encountered, the probe ends
    • Notice if there’s a node in the array that needs to overwrite value; At the calculated hash value, the process of probing backwards must not encounter null nodes
    • After all, the first time you explore the available nodes backwards is when you hit the first null node and stop to use it

  • In the second loop, there’s another piece of code, which is a little bit more interesting, which is what the logic does
    • An Entry with the key null as the boundary
    • No Entry with a null key was encountered during the forward detection. Procedure
    • When probing backwards, a null Entry is encountered
    • Then change the value of slotToExpunge so that it is not equal to staleSlot
private void replaceStaleEntry(ThreadLocal<? > key, Object value,int staleSlot) {...for (inti = nextIndex(staleSlot, len); (e = tab[i]) ! =null; i = nextIndex(i, len)) {
        ...
        if (k == null&& slotToExpunge == staleSlot) slotToExpunge = i; }... }Copy the code

  • You can see that the operations of these two loops are related to each other

Why are both loops so obsessed with changing the value of slotToExpunge?

  • Take a look at the key code for slotToExpunge
private void replaceStaleEntry(ThreadLocal<? > key, Object value,int staleSlot) {...intslotToExpunge = staleSlot; .if(slotToExpunge ! = staleSlot) cleanSomeSlots(expungeStaleEntry(slotToExpunge), len); }Copy the code

Get it! All to replace the last piece of logic in the method: to determine whether an erasing algorithm needs to be performed

conclusion

  • Bidirectional detection flow

    • The replacement algorithm detects both sides of a contiguous Entry range by taking the Entry node with a null key as the boundary
      • What is a contiguous Entry range? None of the nodes in this array can be NULL. If a node is null, the probe ends
    • Probe ahead: If an Entry with a null key is encountered, its subscript is assigned to slotToExpunge
    • Backward probe: If the forward probe does not encounter a node with key, if the backward probe encounters a node with null, its subscript is assigned to slotToExpunge
    • SlotToExpunge is not equal to staleSlot when a node whose key is null is encountered

  • If an Entry with the same key value is encountered during backward detection, it indicates that we need to duplicate the value of the Entry

    • At this point, the value Entry is overwritten with the value value we pass in
    • Then, the Entry with a null key (known by the subscript) is swapped with the Entry whose value needs to be copied
    • Finally, the erase algorithm is performed

  • If no Entry with the same key value is encountered during the backward detection

    • Pass an Entry with a null key, assign its value to NULL, and disconnect the reference
    • Create a new node and place it at this location with key as the current ThreadLocal instance and value as the value data passed in
    • Then, according to whether lotToExpunge and staleSlot are equal, it decides whether to perform the erase algorithm

conclusion

To sum up the

  • Let’s look at the overall process

  • After analyzing the logic of replacing old nodes, we can finally complete the process of replacing map.set algorithm
    • The Entry with a null key will be replaced regardless of whether the Entry encounters a NULL key or an Entry that needs to be duplicated

These two diagrams roughly describe how a ThreadLocal performs a set operation. Now, on to the next column, let’s look at the ThreadLocal GET operation!

get

The GET process, which is generally much simpler than the SET process, can be relaxed

The total process

  • Let’s look at the code
    • The overall process is pretty simple: pass itself as the key, pass map.getentry, get an Entry that matches the instance, get the value, and return it
public T get(a) {
    Thread t = Thread.currentThread();
    ThreadLocalMap map = getMap(t);
    if(map ! =null) {
        ThreadLocalMap.Entry e = map.getEntry(this);
        if(e ! =null) {
            @SuppressWarnings("unchecked")
            T result = (T)e.value;
            returnresult; }}return setInitialValue();
}
Copy the code
  • If the Entry obtained through map.getEntry is NULL, the value is returnedsetInitialValue()Let’s see what this method does
    • If we do get instead of set, it will give the initial value to the threadLocals function
    • The setInitialValue() method returns data from the initialValue() method
    • If no Entry is found through the key, the get method returns NULL
private T setInitialValue(a) {
    T value = initialValue();
    Thread t = Thread.currentThread();
    ThreadLocalMap map = getMap(t);
    if(map ! =null)
        map.set(this, value);
    else
        createMap(t, value);
    return value;
}

protected T initialValue(a) {
    return null;
}

void createMap(Thread t, T firstValue) {
    t.threadLocals = new ThreadLocalMap(this, firstValue);
}
Copy the code

map.getEntry

  • As you can see from the code above, the getEntry method retrieves the eligible nodes
    • The logic here is simple: get the HashCode from the current ThreadLocal instance and calculate the index value
    • Get the current index subscript Entry and compare its key to the current ThreadLocal instance to see if it is the same
    • Same: Indicates that no Hash collision occurs and can be used directly
    • Different: Indicates that a Hash collision has occurred, and the getEntryAfterMiss() method needs to be executed
    • At this point, you need to look at the getEntryAfterMiss() method logic
private Entry getEntry(ThreadLocal
        key) {
    int i = key.threadLocalHashCode & (table.length - 1);
    Entry e = table[i];
    if(e ! =null && e.get() == key)
        return e;
    else
        return getEntryAfterMiss(key, i, e);
}
Copy the code

getEntryAfterMiss

  • Let’s look at the code
private Entry getEntryAfterMiss(ThreadLocal<? > key,int i, Entry e) {
    Entry[] tab = table;
    int len = tab.length;

    while(e ! =null) { ThreadLocal<? > k = e.get();if (k == key)
            return e;
        if (k == null)
            expungeStaleEntry(i);
        else
            i = nextIndex(i, len);
        e = tab[i];
    }
    return null;
}
Copy the code

The overall logic is pretty clear. We keep getting the next node in the Entry array through the while loop, and there are three logical directions in the loop

  1. The key of the current node is equal to the current ThreadLocal instance: the Entry of this node is returned directly
  2. If the key of the current node is null, the erasing algorithm is performed and the loop continues
  3. The current node may not be equal to the current ThreadLocal instance and not null: get the subscript of the next node and continue with the above logic
  • If no Entry node matching the conditions is obtained, NULL is returned

conclusion

ThreadLocal’s process is generally simple

  • Use the current ThreadLocal instance as the key to find if the current Entry node (index calculated using the magic value in ThreadLocal) matches the condition

  • Null is returned if the condition is not met

    • Never performed a set operation
    • No key matching the conditions is found. Procedure

  • If the condition is met, the current node is returned directly

    • If a hash conflict occurs, the computed index contains an array of entries, but the keys are not equal
    • If an Entry with a null key is encountered, the erasing algorithm is performed and the search continues
    • If an Entry with the same key is encountered, the search ends and the Entry node is returned

  • Here we must be clear about a concept: in the process of set, when a hash conflict occurs, it is to find the eligible node storage on the consecutive node behind the conflicting node. Therefore, when searching, we only need to search on the consecutive node. If we encounter a null node, we can directly end the search

Erase the algorithm

The logic of erasing old nodes is used in both the SET and GET processes. It can timely clear the entries with null keys in the Entry array. If the key is null, it indicates that these nodes have no place to use, so it needs to be cleared

  • Take a look at the method code
private int expungeStaleEntry(int staleSlot) {
    Entry[] tab = table;
    int len = tab.length;

    // expunge entry at staleSlot
    tab[staleSlot].value = null;
    tab[staleSlot] = null;
    size--;

    // Rehash until we encounter null
    Entry e;
    int i;
    for(i = nextIndex(staleSlot, len); (e = tab[i]) ! =null; i = nextIndex(i, len)) { ThreadLocal<? > k = e.get();if (k == null) {
            e.value = null;
            tab[i] = null;
            size--;
        } else {
            int h = k.threadLocalHashCode & (len - 1);
            if(h ! = i) { tab[i] =null;

                // Unlike Knuth 6.4 Algorithm R, we must scan until
                // null because multiple entries could have been stale.
                while(tab[h] ! =null) h = nextIndex(h, len); tab[h] = e; }}}return i;
}
Copy the code

The prefix

As you can see from the code above, there is a pre-operation to proceed to the main body of the loop

private int expungeStaleEntry(int staleSlot) {
    Entry[] tab = table;
    int len = tab.length;

    // expunge entry at staleSlot
    tab[staleSlot].value = null;
    tab[staleSlot] = null; size--; . }Copy the code
  • If the key of the Entry node is empty, the node can be cleared, the value is empty, and the array link is broken

The main logic

  • Obviously, the logic inside the body of the loop is the most important, and there’s a pretty interesting operation going on inside the body of the loop!
private int expungeStaleEntry(int staleSlot) {
    Entry[] tab = table;
    intlen = tab.length; .// Rehash until we encounter null
    Entry e;
    int i;
    for(i = nextIndex(staleSlot, len); (e = tab[i]) ! =null; i = nextIndex(i, len)) { ThreadLocal<? > k = e.get();if (k == null) {
            e.value = null;
            tab[i] = null;
            size--;
        } else {
            int h = k.threadLocalHashCode & (len - 1);
            if(h ! = i) { tab[i] =null;

                // Unlike Knuth 6.4 Algorithm R, we must scan until
                // null because multiple entries could have been stale.
                while(tab[h] ! =null) h = nextIndex(h, len); tab[h] = e; }}}return i;
}
Copy the code
  • In the body of the loop above, it is to continuously obtain the Entry instance of the next node, and then judge the key value for relevant processing
  • If the key is null, the value is null and the array is disconnected
  • Key is not null: this is where it gets interesting
    • First, the hash value of the current ThreadLocal instance is retrieved, followed by the index value
    • Check whether h(idNEx value) and I are equal. If they are not equal, perform the following operations because the Entry array is a ring structure
      1. Will empty the current loop to the node whose Entry is denoted as E
      2. The loop begins at the point where the index is retrieved from the hash value of the hreadLocal instance
      3. The loop ends when the Entry of the node is null
      4. Assign e to a node that is null
    • This is where the logic comes in
  • You might think of this as an abstract description, but let me give you a picture to see the beauty of just a few lines of code

conclusion

Very little code, but not a lot of functionality

  • Method of erasing old nodes when probing on Entry
    • When a node whose key is empty is encountered, the node is empty
    • When encountering a node whose key is not empty, the node will be moved to the earlier position (for the specific move logic, please refer to the above instructions).
  • It can be seen that the main purpose of interaction with the front node is to:
    • The position after the index node position calculated by the ThreadLocal instance keeps the node continuous
    • It also allows switching nodes to be operated more quickly

capacity

During the set operation, related capacity expansion operations are performed

  • Take a look at the expansion code entry: the resize method is the expansion method
public void set(T value) {...if(map ! =null)
        map.set(this, value);
    else
        createMap(t, value);
}

private void set(ThreadLocal
        key, Object value) {... tab[i] =new Entry(key, value);
    int sz = ++size;
    if(! cleanSomeSlots(i, sz) && sz >= threshold) rehash(); }private void rehash(a) {
    expungeStaleEntries();

    // Use lower threshold for doubling to avoid hysteresis
    if (size >= threshold - threshold / 4)
        resize();
}
Copy the code
  • Take a look at the expansion code
private void resize(a) {
    Entry[] oldTab = table;
    int oldLen = oldTab.length;
    int newLen = oldLen * 2;
    Entry[] newTab = new Entry[newLen];
    int count = 0;

    for (int j = 0; j < oldLen; ++j) {
        Entry e = oldTab[j];
        if(e ! =null) { ThreadLocal<? > k = e.get();if (k == null) {
                e.value = null; // Help the GC
            } else {
                int h = k.threadLocalHashCode & (newLen - 1);
                while(newTab[h] ! =null)
                    h = nextIndex(h, newLen);
                newTab[h] = e;
                count++;
            }
        }
    }

    setThreshold(newLen);
    size = count;
    table = newTab;
}
Copy the code

The trigger condition

Let’s look at the trigger conditions for expansion

  • The overall code
public void set(T value) {...if(map ! =null)
        map.set(this, value);
    else
        createMap(t, value);
}

private void set(ThreadLocal
        key, Object value) {... tab[i] =new Entry(key, value);
    int sz = ++size;
    if(! cleanSomeSlots(i, sz) && sz >= threshold) rehash(); }private void rehash(a) {
    expungeStaleEntries();

    // Use lower threshold for doubling to avoid hysteresis
    if (size >= threshold - threshold / 4)
        resize();
}
Copy the code

The main code above is:! cleanSomeSlots(i, sz) && sz >= threshold

  • Look atthresholdWhat is the
    • The latter criterion can be satisfied as long as the Entry array contains an Entry instance greater than two-thirds of the length of the array
ThreadLocalMap(ThreadLocal<? > firstKey, Object firstValue) { table =new Entry[INITIAL_CAPACITY];
    int i = firstKey.threadLocalHashCode & (INITIAL_CAPACITY - 1);
    table[i] = new Entry(firstKey, firstValue);
    size = 1;
    setThreshold(INITIAL_CAPACITY);
}

private void setThreshold(int len) {
    threshold = len * 2 / 3;
}
Copy the code
  • Looking at the determination in the previous paragraph, look at cleanSomeSlots, and just return false to trigger the expansion method
private boolean cleanSomeSlots(int i, int n) {
    boolean removed = false;
    Entry[] tab = table;
    int len = tab.length;
    do {
        i = nextIndex(i, len);
        Entry e = tab[i];
        if(e ! =null && e.get() == null) {
            n = len;
            removed = true; i = expungeStaleEntry(i); }}while ( (n >>>= 1) != 0);
    return removed;
}
Copy the code

N >>>= 1: the expression is unsigned right shift one bit, positive high complement 0, negative high complement 1

For example, 0011 –> 0001

In the cleanSomeSlots method above, this method returns false whenever no node with a null Entry key is encountered while probing the node

  • The rehash method is pretty simple
    • Perform the erase method
    • As long as size(including the number of Entry instances) is greater than or equal to 3/4 threshold, the capacity expansion is performed
private void rehash(a) {
    expungeStaleEntries();

    // Use lower threshold for doubling to avoid hysteresis
    if (size >= threshold - threshold / 4)
        resize();
}
Copy the code

conclusion

Meet the following two conditions

  1. The Entry array does not contain an Entry instance with a null key
  2. The number of instances in the array is greater than or equal to three quarters of the threshold.

Expansion logic

private void resize(a) {
    Entry[] oldTab = table;
    int oldLen = oldTab.length;
    int newLen = oldLen * 2;
    Entry[] newTab = new Entry[newLen];
    int count = 0;

    for (int j = 0; j < oldLen; ++j) {
        Entry e = oldTab[j];
        if(e ! =null) { ThreadLocal<? > k = e.get();if (k == null) {
                e.value = null; // Help the GC
            } else {
                int h = k.threadLocalHashCode & (newLen - 1);
                while(newTab[h] ! =null)
                    h = nextIndex(h, newLen);
                newTab[h] = e;
                count++;
            }
        }
    }

    setThreshold(newLen);
    size = count;
    table = newTab;
}
Copy the code

  • From the above logic, we can see that assigning the old array to the expanded array does not assign the whole array to the corresponding location

  • Iterate through the old array and retrieve the Entry instance

    • If key is null, the value of this object needs to be null and wait for GC (Help the GC, HHHH).
      • If the array key is not null, the expansion mechanism will be triggered.
      • In a multithreaded environment, it is perfectly true that a strong reference to the key is disconnected during capacity expansion, causing the key to be reclaimed and thus the key to be null
    • If the key is not null, calculate the index value and store it in the expanded array. If the node conflicts, find the node with the null value and store it

  • There’s a difference between expanded storage and ArrayList or something like that

conclusion

You can find

  • Set, replace, erase, expand, basically all the time, to bring the hash conflicting node closer to the conflicting node

  • This is to improve the efficiency of the read and write nodes

remove

The remove method is very simple. ThreadLocal has three apis: set, GET, and remove. It’s pretty simple, but it’s worth a little bit of understanding

  • Remove the code
public void remove(a) {
    ThreadLocalMap m = getMap(Thread.currentThread());
    if(m ! =null)
        m.remove(this);
}

private void remove(ThreadLocal
        key) {
    Entry[] tab = table;
    int len = tab.length;
    int i = key.threadLocalHashCode & (len-1);
    for(Entry e = tab[i]; e ! =null; e = tab[i = nextIndex(i, len)]) {
        if (e.get() == key) {
            e.clear();
            expungeStaleEntry(i);
            return; }}}Copy the code

The logic is very clear. The ThreadLocal instance retrieves the current index and searches for a matching Entry. If it finds one, the key is removed and an erasing algorithm is performed

E. clear is a way to clean up weak references by simply emptying the weak referent variable, which is the variable that holds the weak reference object

The last

This is the end of the article, which has written more than 10,000 words. I hope you can have a deeper understanding of ThreadLocal after reading it

ThreadLocal doesn’t have much source code, but there’s a lot of clever thinking in it. Is this really expert code?

series

  • Handler those things (swastika graphic)