当前位置：网站首页>Interviewers, ThreadLocal if you ask me that, I'll hang up! "

Interviewers, ThreadLocal if you ask me that, I'll hang up! "

2020-11-06 01:23:11 【Bugstack wormhole stack】

author ： Little brother Fu
Blog ：https://bugstack.cn

precipitation 、 Share 、 grow up , Let yourself and others have something to gain ！

One 、 Preface

At the end of the day , Do you really know how to build rockets ？

It's often said that interviews make rockets , Screw in . But do you really have the ability to build rockets , Most of them are self mockery that they dare not admit their knowledge blind areas, technical bottlenecks and lack of experience .

During the interview ：

  • I hope you understand data structure , Because you're using HashMap、ArrayList、LinkedList, More handy .
  • I hope you understand hashing , Because then when you design the route , There will be a lot of choices ; division method 、 Square hash 、 Fibonacci （Fibonacci） Hashing etc. .
  • I hope you understand open source code , Because then when you have a problem , Can quickly locate , It is also possible to create middleware for system services , To better decouple the system .
  • I hope you understand design patterns , Because then you can write extensible 、 Easy to maintain program , Let the whole team develop in a better direction .

therefore , Never CRUD I chose you , It's not making screws to make you a tool maker . It's your technical ability that determines your vision , Vision determines the code you write ！

Two 、 Interview questions

Thank you plane , Notes I haven't got offer The plane , Get up early , Finish two oil bars , I went to the company to ask the interviewer for advice ！

Soul painter & Old age

interviewer ： The plane , Listen to the tank , You've been up in the dark to study .

Thank you plane ： Mm-hmm , Yes , I've lost my hair recently ！

interviewer ： Let's talk about it today ThreadLocal, It can be used in any scene ？

Thank you plane ： Um. ,ThreadLocal The solution is to share resources within threads (This class provides thread-local variables.), So it is usually used in full link monitoring , Or like a log framework MDC In such components .

interviewer ： The plane is good , I did learn recently . So you know ThreadLocal What kind of data structure is it , What kind of hashing is used ？

Thank you plane ： Array ？ Um. , It's not clear how to hash …

interviewer ： that ThreadLocal There is a risk of memory leaks , How did it happen ？ In addition, you know the process of , Probing and heuristic cleaning ？

Thank you plane ： this …, Blind area , Blind area , coke I put it on the table , I'll go home and read again ！

3、 ... and 、ThreadLocal analysis

ThreadLocal, author ：Josh Bloch and Doug Lea, Two great gods

If it's just daily business development , This is a relatively cold category , The frequency of use is not high . And the method it provides is very simple , One function is just to scribble lines of code . but , If you dig deep into the source code of the implementation part , It's not that simple . There are too many knowledge points involved here , Include ; data structure 、 Zipper storage 、 Fibonacci scattered 、 magical 0x61c88647、 Weak reference Reference、 Be overdue key Probe cleanup and heuristic cleanup wait .

Next , We're going to learn this step by step Blind area knowledge . This paper involves more code and practical verification drawings , Welcome to the official account ：bugstack Wormhole stack , Reply to download to get a link after opening , find ID：19🤫 obtain ！*

1. Application scenarios

1.1 SimpleDateFormat

private SimpleDateFormat f = new SimpleDateFormat("yyyy-MM-dd HH:mm:ss");

public void seckillSku(){
    String dateStr = f.format(new Date());
    //  The business process 
}

Have you ever written this code ？ If you still write like this , A thread safe error has been made .SimpleDateFormat, It's not a thread safe class .

1.1.1 Thread unsafe verification 
private static SimpleDateFormat f = new SimpleDateFormat("yyyy-MM-dd HH:mm:ss");

public static void main(String[] args) {
    while (true) {
        new Thread(() -> {
            String dateStr = f.format(new Date());
            try {
                Date parseDate = f.parse(dateStr);
                String dateStrCheck = f.format(parseDate);
                boolean equals = dateStr.equals(dateStrCheck);
                if (!equals) {
                    System.out.println(equals + " " + dateStr + " " + dateStrCheck);
                } else {
                    System.out.println(equals);
                }
            } catch (ParseException e) {
                System.out.println(e.getMessage());
            }
        }).start();
    }
}

This is a multithread under SimpleDateFormat The verification code of . When equals by false when , Prove that threads are unsafe . The operation results are as follows ;

true
true
false 2020-09-23 11:40:42 2230-09-23 11:40:42
true
true
false 2020-09-23 11:40:42 2020-09-23 11:40:00
false 2020-09-23 11:40:42 2020-09-23 11:40:00
false 2020-09-23 11:40:00 2020-09-23 11:40:42
true
false 2020-09-23 11:40:42 2020-08-31 11:40:42
true
1.1.2 Use ThreadLocal Optimize

The most direct way for thread safety , That is, every call is direct new SimpleDateFormat. But it's not the best way after all , So we use ThreadLocal , To optimize this code .

private static ThreadLocal<SimpleDateFormat> threadLocal = ThreadLocal.withInitial(() -> new SimpleDateFormat("yyyy-MM-dd HH:mm:ss"));
public static void main(String[] args) {
    while (true) {
        new Thread(() -> {
            String dateStr = threadLocal.get().format(new Date());
            try {
                Date parseDate = threadLocal.get().parse(dateStr);
                String dateStrCheck = threadLocal.get().format(parseDate);
                boolean equals = dateStr.equals(dateStrCheck);
                if (!equals) {
                    System.out.println(equals + " " + dateStr + " " + dateStrCheck);
                } else {
                    System.out.println(equals);
                }
            } catch (ParseException e) {
                System.out.println(e.getMessage());
            }
        }).start();
    }
}

As above, we put SimpleDateFormat , Put it in ThreadLocal For use in , That is, there is no need to repeat new object , It also avoids thread insecurity . The test results are as follows ;

true
true
true
true
true
true
true
...

1.2 Link tracking

In recent years, it is based on Google Dapper This paper realizes the non-invasive full link tracing , It's used more and more widely . In short, this is a monitoring system , But you don't have to hardcode your monitoring methods , It's based on its design javaagent + Bytecode The way of inserting piles , Dynamic collection method execution information . If you want to know about bytecode instrumentation , Read my bytecode programming column ：https://bugstack.cn/itstack-demo-agent/itstack-demo-agent.html

a key , Dynamic collection method execution information . This is the main part , Follow ThreadLocal relevant . Bytecode stub It's about non intrusive programming , So in a service call , Calls of multiple methods between and within systems , All need to be collected . You need to use ThreadLocal Record method execution ID, Of course, there are cross thread calls, which are also enhanced versions ThreadLocal, But in any case, the basic principle remains the same .

1.2.1 Trace code

Here's an example of a full link method call chain trace , Part of the code 

public class TrackContext {

    private static final ThreadLocal<String> trackLocal = new ThreadLocal<>();

    public static void clear(){
        trackLocal.remove();
    }

    public static String getLinkId(){
        return trackLocal.get();
    }

    public static void setLinkId(String linkId){
        trackLocal.set(linkId);
    }

}

@Advice.OnMethodEnter()
public static void enter(@Advice.Origin("#t") String className, @Advice.Origin("#m") String methodName) {
    Span currentSpan = TrackManager.getCurrentSpan();
    if (null == currentSpan) {
        String linkId = UUID.randomUUID().toString();
        TrackContext.setLinkId(linkId);
    }
    TrackManager.createEntrySpan();
}

@Advice.OnMethodExit()
public static void exit(@Advice.Origin("#t") String className, @Advice.Origin("#m") String methodName) {
    Span exitSpan = TrackManager.getExitSpan();
    if (null == exitSpan) return;
    System.out.println(" Link tracking (MQ)：" + exitSpan.getLinkId() + " " + className + "." + methodName + "  Time consuming ：" + (System.currentTimeMillis() - exitSpan.getEnterTime().getTime()) + "ms");
}
  • The above part is about non intrusion monitoring , The process of link tracking . Specific case and code can refer to read , Series of special articles 《 be based on JavaAgent Full link monitoring of 》
  • It's just one way to do it , Bytecode instrumentation uses byte-buddy, In fact, we still use ,ASM perhaps Javassist.
1.2.2 test result

The test method

Configuration parameters ：-javaagent:E:\itstack\GIT\itstack.org\itstack-demo-agent\itstack-demo-agent-06\target\itstack-demo-agent-06-1.0.0-SNAPSHOT.jar=testargs

public void http_lt1(String name) {
    try {
        Thread.sleep((long) (Math.random() * 500));
    } catch (InterruptedException e) {
        e.printStackTrace();
    }
    System.out.println(" test result ：hi1 " + name);
    http_lt2(name);
}

public void http_lt2(String name) {
    try {
        Thread.sleep((long) (Math.random() * 500));
    } catch (InterruptedException e) {
        e.printStackTrace();
    }
    System.out.println(" test result ：hi2 " + name);
    http_lt3(name);
}

Running results 

onTransformation：class org.itstack.demo.test.ApiTest
 test result ：hi2  The wu is empty 
 test result ：hi3  The wu is empty 
 Link tracking (MQ)：90c7d543-c7b8-4ec3-af4d-b4d4f5cff760 org.itstack.demo.test.ApiTest.http_lt3  Time consuming ：104ms

init: 256MB	 max: 3614MB	 used: 44MB	 committed: 245MB	 use rate: 18%
init: 2MB	 max: 0MB	 used: 13MB	 committed: 14MB	 use rate: 95%

name: PS Scavenge	 count:0	 took:0	 pool name:[PS Eden Space, PS Survivor Space]
name: PS MarkSweep	 count:0	 took:0	 pool name:[PS Eden Space, PS Survivor Space, PS Old Gen]
-------------------------------------------------------------------------------------------------
 Link tracking (MQ)：90c7d543-c7b8-4ec3-af4d-b4d4f5cff760 org.itstack.demo.test.ApiTest.http_lt2  Time consuming ：233ms

init: 256MB	 max: 3614MB	 used: 44MB	 committed: 245MB	 use rate: 18%
init: 2MB	 max: 0MB	 used: 13MB	 committed: 14MB	 use rate: 96%

name: PS Scavenge	 count:0	 took:0	 pool name:[PS Eden Space, PS Survivor Space]
name: PS MarkSweep	 count:0	 took:0	 pool name:[PS Eden Space, PS Survivor Space, PS Old Gen]
  • These are the test results of link tracking , You can see that both methods will type the corresponding code ID：90c7d543-c7b8-4ec3-af4d-b4d4f5cff760 .
  • This part is also the core application of full link tracking , And you can see that some simple systems are printed here JVM Monitoring indicators , It's also part of monitoring .

Cough , In addition to this, all the , All need to use ThreadLocal, for example MDC Log framework, etc . Now we start to analyze in detail ThreadLocal The implementation of the .

2. data structure

Before understanding a function , First understand its data structure . This is equivalent to looking at its foundation first , With this, it's easy to understand in the future . Here are ThreadLocal Simple use and part of the source code .

new ThreadLocal<String>().set(" Little brother Fu ");

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)]) {
    ...
}

You can see from this part of the source code ,ThreadLocal The bottom layer uses array structure to store data , At the same time, hash value is used to calculate the subscript , This shows that it is an array structure of hash table , The demonstration is shown in the following figure ;

Little brother Fu & threadLocal data structure

As shown in the figure above ThreadLocal The underlying data structure that holds the data , The knowledge points are as follows ;

  1. It's an array structure .
  2. Entry, There's no use opening it here , It's actually a weak reference implementation ,static class Entry extends WeakReference<ThreadLocal<?>>. This shows that as long as there is no strong reference , happen GC You'll be garbage collected .
  3. Data elements are stored in hash hash , But the hash here uses Fibonacci （Fibonacci） Hashing , It will be analyzed in detail later .
  4. And because it's different from HashMap Data structure of , Hash collision will not be saved as linked list or red black tree , It's about zipper storage . That is, when the same subscript position conflicts , be +1 Address backwards , Until an empty location or garbage collection location is found for storage .

3. Hash algorithm

since ThreadLocal Is based on the array structure of zipper storage , Then there must be a hash calculation . But after we read the source code , Find out that this hash calculation is related to HashMap The hash method of array subscript calculation in hash is different . If you forget HashMap, You can read articles 《HashMap Source code analysis , Insert 、 lookup 》、《HashMap Disturbance function 、 Load factor 》

3.1 Mysterious numbers 0x61c88647

When we look at ThreadLocal When executing the setting element , There is such a code to calculate hash value ;

private static final int HASH_INCREMENT = 0x61c88647;

private static int nextHashCode() {
    return nextHashCode.getAndAdd(HASH_INCREMENT);
}

You must have such a question when you see it here , This is how hash is calculated ？ How did this number come from ？

Here we are. , In fact, the way hashes are calculated , It's not just that we see String A way to get a hash value , It also includes ; division method 、 Square hash 、 Fibonacci （Fibonacci） Hashing 、 Random number method etc. .

and ThreadLocal What you use is Fibonacci （Fibonacci） Hashing + Zipper method stores data into array structure . The reason why we use Fibonacci sequence , It's to make the data more hash , Reduce hash collisions . It comes from the calculation and evaluation of mathematical formulas , The formula ：f(k) = ((k * 2654435769) >> X) << Y For common 32 Bit integers , That is to say f(k) = (k * 2654435769) >> 28

The second question is , Numbers 0x61c88647, How did you get it ？

In fact, this is the golden section of a hash value , That is to say 0.618, Do you remember the math you learned ？ The calculation method is as follows ;

//  Golden Point ：(√5 - 1) / 2 = 0.6180339887     1.618:1 == 1:0.618
System.out.println(BigDecimal.valueOf(Math.pow(2, 32) * 0.6180339887).intValue());      //-1640531527
  • If you have studied mathematics, you should know , The golden point is ,(√5 - 1) / 2, take 10 The bit approximation 0.6180339887.
  • After use 2 ^ 32 * 0.6180339887, And what you get is ：-1640531527, That is to say 16 It's binary ,0x61c88647. This is how this number comes from

3.2 Validate hash

since ,Josh Bloch and Doug Lea, The two men chose to use the Fibonacci sequence , Calculate the hash value . There must be something special about it , It's better hashing , Reduce hash collisions .

Next, we get the hash value and calculate the subscript in the source code , Put this part of the code out for verification .

3.2.1 Part of the source code 
private static AtomicInteger nextHashCode = new AtomicInteger();
 
private static final int HASH_INCREMENT = 0x61c88647;

//  Compute hash 
private static int nextHashCode() {
    return nextHashCode.getAndAdd(HASH_INCREMENT);
}

//  Get subscript 
int i = key.threadLocalHashCode & (len-1);

Above , The source code part uses AtomicInteger, Atomic method computes subscripts . We don't need to be thread safe , It only needs a simple implementation . in addition ThreadLocal Initialization array length is 16, We also initialize this length .

3.2.2 unit testing 
@Test
public void test_idx() {
    int hashCode = 0;
    for (int i = 0; i < 16; i++) {
        hashCode = i * HASH_INCREMENT + HASH_INCREMENT;
        int idx = hashCode & 15;
        System.out.println(" Fibonacci scattered ：" + idx + "  General hash ：" + (String.valueOf(i).hashCode() & 15));
    }
}

Test the code part , The Fibonacci sequence is used , At the same time, we add ordinary hash algorithm to compare the hash effect . Of course String This hash doesn't look like HashMap To disturb

test result ：

 Fibonacci scattered ：7  General hash ：0
 Fibonacci scattered ：14  General hash ：1
 Fibonacci scattered ：5  General hash ：2
 Fibonacci scattered ：12  General hash ：3
 Fibonacci scattered ：3  General hash ：4
 Fibonacci scattered ：10  General hash ：5
 Fibonacci scattered ：1  General hash ：6
 Fibonacci scattered ：8  General hash ：7
 Fibonacci scattered ：15  General hash ：8
 Fibonacci scattered ：6  General hash ：9
 Fibonacci scattered ：13  General hash ：15
 Fibonacci scattered ：4  General hash ：0
 Fibonacci scattered ：11  General hash ：1
 Fibonacci scattered ：2  General hash ：2
 Fibonacci scattered ：9  General hash ：3
 Fibonacci scattered ：0  General hash ：4

Process finished with exit code 0

Found not ？, Fibonacci's hash is very uniform , General hash to 15 After that, we have developed and produced collision . This is the charm of Fibonacci hash , Reducing collisions can also make data storage more decentralized , The complexity of data acquisition is kept at the basic level O(1).

4. Source code interpretation

4.1 initialization

new ThreadLocal<>()

The initialization process is also very simple , It can be set according to the generic type you need . But in ThreadLocal There is a very important point in the source code of , Is to get threadLocal To get the hash value of ,threadLocalHashCode.

private final int threadLocalHashCode = nextHashCode();

/**
 * Returns the next hash code.
 */
private static int nextHashCode() {
    return nextHashCode.getAndAdd(HASH_INCREMENT);
}

Such as source code , Just instantiate one ThreadLocal , It will get a corresponding hash value , Let's make an example .

@Test
public void test_threadLocalHashCode() throws Exception {
    for (int i = 0; i < 5; i++) {
        ThreadLocal<Object> objectThreadLocal = new ThreadLocal<>();
        Field threadLocalHashCode = objectThreadLocal.getClass().getDeclaredField("threadLocalHashCode");
        threadLocalHashCode.setAccessible(true);
        System.out.println("objectThreadLocal：" + threadLocalHashCode.get(objectThreadLocal));
    }
}

because threadLocalHashCode , It's a private property , So we can get the hash value through the above method after instantiation .

objectThreadLocal：-1401181199
objectThreadLocal：239350328
objectThreadLocal：1879881855
objectThreadLocal：-774553914
objectThreadLocal：865977613

Process finished with exit code 0

Get this value , That is calculation ThreadLocalMap, When storing data ,ThreadLocal Array subscript of . As long as it's the same object , stay set、get when , You can set and get the corresponding value .

4.2 Set the element

4.2.1 Flow chart

new ThreadLocal<>().set(" Little brother Fu ");

How to set the element , It's just this code . But the process of setting elements involves more , Before analyzing the code in detail , Let's take a look at a flowchart of setting elements , First understand the process of different situations from the diagram, and then learn the source code by comparison . The flow chart is as follows ;

Little brother Fu & Set up the element flowchart

At first glance, it may feel a little dizzy , We look from left to right , They have the following knowledge points ;

  1. In the middle is ThreadLocal The array structure of , After setting the element, there are four different situations , In addition, the insertion of elements is calculated by Fibonacci hash , For storage .
  2. situation 1, Subscript to be inserted , It is an empty position to insert directly .
  3. situation 2, Subscript to be inserted , Not empty ,key identical , Direct updating
  4. situation 3, Subscript to be inserted , Not empty ,key inequality , Zip addressing
  5. situation 4, Not empty ,key inequality , I ran into an expiration date key. In fact, the situation 4, It's a weak reference that happens GC when , What happened . In this case ,ThreadLocal It's going to probe, clean up, expire key, This part of the clean-up content will be explained later .
4.2.2 Source code analysis 
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] = new Entry(key, value);
    int sz = ++size;
    if (!cleanSomeSlots(i, sz) && sz >= threshold)
        rehash();
}

With the diagram above , If you look at the code part, it's easier to understand , The corresponding contents include , as follows ;

  1. key.threadLocalHashCode & (len-1);, Fibonacci scattered , Compute array subscripts .
  2. Entry, Is a weak reference object implementation class ,static class Entry extends WeakReference<ThreadLocal<?>>, So there is no strong external reference , It's going to happen GC, Delete key.
  3. for Loop to determine whether an element exists , When there is no element in the current subscript , Set elements directly tab[i] = new Entry(key, value);.
  4. If the element exists , It will judge whether or not key The values are equal if (k == key), Equal updates the value .
  5. If it's not equal , It's just our replaceStaleEntry, In other words, the above figure refers to the detection of expired elements .

Sum up , It's the whole process of storing elements , The design of the whole structure is wonderful , Great use of hash effect , We also use weak references very much 6！

4.3 Expansion mechanism

4.3.1 Capacity expansion condition

Just use the array structure , There will be expansion 

if (!cleanSomeSlots(i, sz) && sz >= threshold)
    rehash();

As we read the settings element , There is a piece of code above , Judge whether to expand capacity .

  • First , Conduct Heuristic cleanup *cleanSomeSlots*, Get rid of outdated elements , See if the space is
  • after , Judge sz >= threshold, among threshold = len * 2 / 3, In other words, the elements of the array filled with sky , Greater than len * 2 / 3, It needs to be expanded .
  • Last , That's the focus of our analysis ,rehash();, Expand and recalculate element position .
4.3.2 Source code analysis

Exploratory cleaning and verification 

private void rehash() {
    expungeStaleEntries();
    
    // Use lower threshold for doubling to avoid hysteresis
    if (size >= threshold - threshold / 4)
        resize();
}

private void expungeStaleEntries() {
    Entry[] tab = table;
    int len = tab.length;
    for (int j = 0; j < len; j++) {
        Entry e = tab[j];
        if (e != null && e.get() == null)
            expungeStaleEntry(j);
    }
}
  • This part is mainly about probing to clean up expired elements , And judge whether the capacity expansion conditions are met after cleaning ,size >= threshold * 3/4
  • After meeting the requirements, expand the capacity , In fact, the core operation after the expansion is to recalculate the hash value , Fill in the new array with elements .

rehash() Capacity expansion 

private void resize() {
    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;
}

above , Code is the overall operation of the expansion , It includes the following steps ;

  1. First expand the length of the array to the original 2 times ,oldLen * 2, Instantiate the new array .
  2. Traverse for, All the elements in the old array , Put it back in the new array .
  3. In the process of placing arrays , If there is a hash collision , Then the chain method is extended .
  4. At the same time, there's testing key The operation of the value if (k == null), convenient GC.

4.4 Get elements

4.4.1 Flow chart

new ThreadLocal<>().get();

Similarly, getting elements is just like this code , If there is no source code analysis before , You can think about it in different data structures , Did you do anything to get the elements . Let's take a look at the figure below , It can be divided into the following situations ;

Little brother Fu & Get the element diagram

According to different data element storage conditions , It basically includes the following situations ;

  1. Go straight to , There is no hash conflict , Return the element directly .
  2. No direct positioning to ,key Different , Need zipper search .
  3. No direct positioning to ,key Different , Zip search , encounter GC Clean up elements , Need to be probe cleaned up , Look for elements again .
4.4.2 Source code analysis 
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);
}

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

Okay , This part is to get the source code part of the element , It is consistent with what we have shown in the figure .expungeStaleEntry, It was found that there was key == null when , To clean up expired elements , And put the elements of subsequent positions , Move forward .

4.5 Element cleanup

4.5.1 Probe cleaning [expungeStaleEntry]

Probe cleaning , It's based on what I've come across right now GC The element begins , Clean up back and forth . Until I met null until , Just stop rehash Calculation Rehash until we encounter null.

expungeStaleEntry

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

above , Exploratory cleaning is used in getting elements ; new ThreadLocal<>().get() -> map.getEntry(this) -> getEntryAfterMiss(key, i, e) -> expungeStaleEntry(i)

4.5.2 Heuristic cleanup [cleanSomeSlots]
Heuristically scan some cells looking for stale entries.
This is invoked when either a new element is added, or
another stale one has been expunged. It performs a
logarithmic number of scans, as a balance between no
scanning (fast but retains garbage) and a number of scans
proportional to number of elements, that would find all
garbage but would cause some insertions to take O(n) time.

Heuristic cleanup , There's a note , Roughly meaning ; Scan some cells tentatively , Looking for expired elements , That is, the elements that are garbage collected . When you add a new element or delete another obsolete element , This function will be called . It performs logarithmic scans , As not scanning （ Fast but keep garbage ） And the number of scans proportional to the number of elements , This will find all the rubbish , But it can lead to some insertion costs O（n） Time .

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

while The loop is constantly moving right to find out the expired elements that need to be cleaned up , They will eventually use expungeStaleEntry To deal with , There's also element shifting .

Four 、 summary

  • Write this is to say ThreadLocal The analysis of a corner of knowledge is finished , stay ThreadLocal There is also Netty Used in ,FastThreadLocal. Get call links between full link and cross service threads , also TransmittableThreadLocal, And then there is JDK A thread passing solution with its own InheritableThreadLocal. But on the basis of this article , Understand the most basic principles , In understanding other development designs , It's easier to accept .
  • In addition, we often see probe cleaning in our analysis , In fact, this is also very time-consuming . For this we are using ThreadLocal Remember that new ThreadLocal<>().remove(); operation . Avoid weak references GC after , The problem that caused the memory leak .
  • Last , Did you find out ！ We learn the underlying principles , It's all about data structure and good design , Or the shadow of the algorithm . This code is the foundation of the whole system , If we can extract some ideas into the core business processes we develop , It can also greatly improve performance .

5、 ... and 、 Series recommendation

bugstack Wormhole stack
precipitation 、 Share 、 grow up , Let yourself and others have something to gain
Wechat scan QR code , Follow my public number

（ Please indicate the author and source of this article WeChat official account ：bugstack Wormhole stack | author ： Little brother Fu ）

Show Disqus Comments

版权声明
本文为[Bugstack wormhole stack]所创，转载请带上原文链接，感谢

边栏推荐

猜你喜欢

随机推荐