FastThreadLocal原理简析

FastThreadLocal原理简析

本文将深入探讨Java中的ThreadLocal和FastThreadLocal的原理及性能优化。首先介绍ThreadLocal的基本工作原理及其存在的性能问题，然后详细讲解Netty中FastThreadLocal的优化方案，最后讨论FastThreadLocal的使用限制和空间换时间的权衡。

ThreadLocal基本原理

上图为ThreadLocal示意图，每个线程拥有一个ThreadLocalMap（数组），ThreadLocal在取值或者赋值的时候根据自身计算hashcode得到索引。

ThreadLocal的问题

问题就在于ThreadLocal在存放/读取的性能问题。

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

1. ThreadLocal在存放数据时发生哈希冲突时，采用的是线性探针法，当哈希冲突严重时一次查找/存放的时间复杂度是O(n)

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;
3
        }
    }
    tab[i] = new Entry(key, value);
    int sz = ++size;
    if (!cleanSomeSlots(i, sz) && sz >= threshold)
        rehash();
}

2. 在查找元素时，也面临着相同哈希的问题。此外，还需要进行一次与运算来获得在Map上的索引，别小看了这个与运算，在极致的场景下下多一个运算带来的损耗是巨大的

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

FastThreadLocal

FTL(FastThreadLocal)是Netty对ThreadLocal的优化。针对ThreadLocal的性能问题，FTL主要采用了空间换时间的方式，将原本的哈希索引替换为数字索引，即省去了一次哈希运算。

FTL对象在新建时会被分配当前线程下的数组索引Index，生成采用的是AutomicInteger如下代码第六行所示。在所有的FastThreadLocalMap中该FTL的索引都为创建时候分配的Index。

public FastThreadLocal() {
    index = InternalThreadLocalMap.nextVariableIndex();
}
public static int nextVariableIndex() {
    int index = nextIndex.getAndIncrement();
    if (index >= ARRAY_LIST_CAPACITY_MAX_SIZE || index < 0) {
        nextIndex.set(ARRAY_LIST_CAPACITY_MAX_SIZE);
        throw new IllegalStateException("too many thread-local indexed variables");
    }
    return index;
}

FTL查询元素的代码如下，

public final V get() {
    // 获取当前线程的 InternalThreadLocalMap
    InternalThreadLocalMap threadLocalMap = InternalThreadLocalMap.get();
    // 根据index查询元素
    Object v = threadLocalMap.indexedVariable(index);
    if (v != InternalThreadLocalMap.UNSET) {
        return (V) v;
    }
    return initialize(threadLocalMap);
}

FTL的存放元素的代码如下

public boolean setIndexedVariable(int index, Object value) {
    Object[] lookup = indexedVariables;
    if (index < lookup.length) {
        Object oldValue = lookup[index];
        lookup[index] = value;
        return oldValue == UNSET;
    } else {
        expandIndexedVariableTableAndSet(index, value);
        return true;
    }
}

综合上述的代码，FastThreadLocal使用一个全局的顺序的索引生成器来指定FTL对象在FTLMap中所存放的位置，免去了ThreadLocal的一次与运算与解哈希冲突。因此，FTL的存放与查询的时间复杂都都恒定为O(1)。

使用限制

但在使用FTL的时候也有一些限制和需要知道的事情。

1. FTL必须搭配FastThreadLocalThread使用，否则会走老的ThreadLocal的方式查询

public static InternalThreadLocalMap get() {
    Thread thread = Thread.currentThread();
    if (thread instanceof FastThreadLocalThread) {
        return fastGet((FastThreadLocalThread) thread);
    } else {
        return slowGet();
    }
}

2. FTL实质上使用空间换时间

假设目前程序中FastThreadLocal的总数为32（FastThreadLocalMap的初始化大小为32），此时新建一个线程，该线程使用了一个新的FastThreadLocal对象。新的FastThreadLocal在使用时会触发当前线程FastThreadLocalMap的扩容，扩容的大小为大于当前FTL index的最小的2的幂次方。此时FastThreadLocalMap为64，对于当前线程而言，该Map只使用了一个位置。

但是就一般程序而言，ThreadLocal的数量都不会太多，在这种场景下，空间换时间是一个极具性价比的操作。

private void expandIndexedVariableTableAndSet(int index, Object value) {
    Object[] oldArray = indexedVariables;
    final int oldCapacity = oldArray.length;
    int newCapacity;
    if (index < ARRAY_LIST_CAPACITY_EXPAND_THRESHOLD) {
        newCapacity = index;
        newCapacity |= newCapacity >>>  1;
        newCapacity |= newCapacity >>>  2;
        newCapacity |= newCapacity >>>  4;
        newCapacity |= newCapacity >>>  8;
        newCapacity |= newCapacity >>> 16;
        newCapacity ++;
    } else {
        newCapacity = ARRAY_LIST_CAPACITY_MAX_SIZE;
    }
    Object[] newArray = Arrays.copyOf(oldArray, newCapacity);
    Arrays.fill(newArray, oldCapacity, newArray.length, UNSET);
    newArray[index] = value;
    indexedVariables = newArray;
}