Handler message mechanism (2) ThreadLocal principle

The original link

In this paper, the implementation of ThreadLocal data storage between threads, a deep exploration, source code using Android SDK version 28 for analysis.

1. What is ThreadLocal

First post the official description:

This class provides thread-local variables. These variables differ from their normal counterparts in that each thread that accesses one (via its get or set method) has its own.

This class provides thread-local variables. These variables are different from normal variables because each thread operates (through its GET or set methods) on its own.

From our understanding of the official description, we know that the variables of a ThreadLocal record are thread-specific and cannot be retrieved or modified by other threads. This feature is well used in Handler, helping the Handler to communicate messages across threads. The next series of articles will examine how to use this feature to communicate messages across threads. ThreadLocal can only record one variable for a thread, but a thread can record multiple variables through multiple ThreadLocal. When recording multiple variables, due to the storage mode, there may be a problem of hash conflict. We will further analyze how to solve hash conflict based on the source code. So let’s actually verify that.

2. Use ThreadLocal

public static void main(String[] args) { sThreadLocal.set("Jon"); new Thread(new OneRunnable(), "SubThread").start(); String name = sThreadLocal.get(); System.out.println(Thread.currentThread().getName() + ", name: " + name); } private static class OneRunnable implements Runnable { @Override public void run() { sThreadLocal.set("jaymzyang"); String name = sThreadLocal.get(); System.out.println(Thread.currentThread().getName() + ", name: " + name); }}Copy the code

Output: main, name: Jon SubThread, name: JaymzyangCopy the code

In the main thread we set “Jon”, in the SubThread we set “jaymzyang”, in the corresponding thread print get value, we found that in the main thread print “Jon”, in the SubThread print “jaymzyang”, So ThreadLocal records values by thread. If you call set again in the main thread, you will only change the value of the sThreadLocal variable in the main thread to the new value.

3. ThreadLocal source code analysis

public void set(T value) { Thread t = Thread.currentThread(); ThreadLocalMap map = getMap(t); if (map ! = null) map.set(this, value); else createMap(t, value); } public T get() { 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; return result; } } return setInitialValue(); } ThreadLocalMap getMap(Thread t) { return t.threadLocals; } void createMap(Thread t, T firstValue) { t.threadLocals = new ThreadLocalMap(this, firstValue); }Copy the code

The thread holds the ThreadLocalMap object via the threadLocals parameter.

The set method:
- If the thread does not have a map, a ThreadLocalMap object is created using createMap and stored in the threadLocals variable. The value is then passed to the ThreadLocalMap constructor when the map is constructed. The value is stored in the map object.
- If a thread holds a map, the thread retrieves the held ThreadLocalMap object and stores the value into the map object.
The get method:
- The ThreadLocalMal object held by the thread is retrieved and the value stored in the map is queried.

3.1 How does ThreadLocalMap implement storage?

ThreadLocalMap should be a map-type data structure by name, but does not inherit from the Map interface. Then, it is found that map maintains an Entry array with a default size of 16 inside, which inherits WeakReference<ThreadLocal<? >>, the key-value structure model is adopted. Key is of ThreadLocal type and stored in WeakReference object. Therefore, key is of WeakReference type and easy to be recovered by GC.

3.1.1 ThreadLocalMap constructor

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

Initialize an Entry array of size 16. Then calculate the index position stored in the array using the hash value of the thradLocal object. Then create an Entry object, pass the key and value as construction arguments, and increment the array size by one. Finally, setThreshold(INITIAL_CAPACITY) is used to calculate the expansion factor, that is, when the elements in the array reach 2/3 of the array size, the array will be expanded.

SetThreshold method:

  private void setThreshold(int len) {
       threshold = len * 2 / 3;
  }
Copy the code

Here is why the expansion is performed when the array length reaches 2/3, mainly due to hash conflicts:

Hash conflicts occur when indexes are computed using hash. When the array capacity is large, the probability of hash conflicts decreases

3.1.2 ThreadLocalMap Set method

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(); }Copy the code

If the key of the Entry element in the subscript is the same ThreadLocal object as the key to be modified, set the new value to e.value = value and set the new value. If keys are different, a hash conflict will occur. ThreadLocalMap handles hash conflicts using a linear detection method. It continues to detect the entry element of the next index and checks whether the key is the same as the found entry. Otherwise, the value is not stored in the current array. Create an Entry element and store it in the table. Table [I] = New Entry(key, value). The set process is as follows:

When setting data, operations such as hash conflicts, clearing of leaked data, and capacity expansion are involved

1. Hash conflict handling

The linear detection method of ThreadLocalMap and the chain address method of HashMap are both used to deal with hash conflicts. The linear detection method is to search for storage locations in the storage range sequentially when hash conflicts occur until appropriate locations are found. Linked address method is to set up a linked list structure at the index subscript and insert new data into the linked list. Assume that the sequence is “47, 34, 13, 12, 52, 38, 33, 27, 3” and the hash array table length is 11, which is stored using the hash algorithm modulo 11. Hash(47) = 47 % 11 = 3 Hash(34) = 34 % 11 = 1 Hash(13) = 13 % 11 = 2 … Hash(3) = 3% 11 = 3 Since 47 has been stored at subscript 3, 3 needs to be linearly probed until the vacant position 7 is found. All the preceding positions are occupied by the Hash algorithm or probe. The table after using the linear detection method to deal with hash conflicts is as follows:

Hash address	0	1	2	3	4	5	6	7	8	9	10
The keyword	33	34	13	47	38	27	3	52
Advantages and disadvantages of linear detection method:

Method is simple
Easy to produce aggregation phenomenon, low efficiency

2. Clean up leaked data

Because Entry inherits the type of WeakReference<ThreadLoacl>, its key of ThreadLoacl type is saved in the WeakReference object. If the key is not strongly referenced externally, it will be recycled according to GC rules. If the thread that created the ThreadLocal is always running, the value in the Entry object cannot be reclaimed, resulting in a memory leak. How do I clean up the value that caused the leak? The replaceStaleEntry method is called if key == null during a set operation.

ReplaceStaleEntry method:

private void replaceStaleEntry(ThreadLocal<? > key, Object value, int staleSlot) { ... 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; }... } 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

Finally, expungeStaleEntry cleans up entries with null keys and rehash the entries in the array. ExpungeStaleEntry: expungeStaleEntry: expungeStaleEntry: expungeStaleEntry: expungeStaleEntry: expungeStaleEntry: expungeStaleEntry: expungeStaleEntry: Automatically detect whether the object that threadLocal serves as the key has been collected by GC. If so, the threadLocal serves as the key’s entry will be cleaned up, or remove will be manually called to clean up unwanted threadLocal objects to prevent memory leaks. Good code habits:

try { sThreadLocal.get(); . } finally {// Discard sthreadlocal.remove (); }Copy the code

Expansion and 3.

Set filling is rarely used. A thread can expand its capacity only when it records the data recorded by 10 ThreadLocal objects. When the capacity of the table is initialized to 16 and the capacity expansion factor reaches 2/3, data will be expanded and rehash will be performed.

Rehash method:

  private void rehash() {
      expungeStaleEntries();

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

ExpungeStaleEntry () is the actual expungeStaleEntry() operation. Data with a null key is cleaned up and the resize method is used to expand the entries.

The resize method:

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; }Copy the code

Resize will double the size of the array, then re-hash the original data into the new array, and finally set the new expansion factor and the number of array elements.

3.2 ThreadLocalMap getEntry method

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

The getEntry method queries the element stored in ThreadLocalMap with threadLocal as the key, and returns the entry object. If not, the getEntryAfterMiss method is called to continue the search.

GetEntryAfterMiss method:

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

In the getEntryAfterMiss method, if an element with the same key is found, the getEntryAfterMiss method returns the value. If the element’s key is null, the previously analyzed method expungeStaleEntry is called to clean up the entry to prevent a memory leak, or null is returned if it is not found.

Note: A ThreadLocal is a data structure that stores variables according to the thread. A ThreadLocal can only hold one variable of type T. It is a good habit to call remove after using it.