iOS 底层 - runtime之方法缓存

本文源自本人的学习记录整理与理解，其中参考阅读了部分优秀的博客和书籍，尽量以通俗简单的语句转述。引用到的地方如有遗漏或未能一一列举原文出处还望见谅与指出，另文章内容如有不妥之处还望指教，万分感谢 ！

Class内部结构中有个方法缓存(cache_t),用散列表(哈希表)来缓存曾经调用过的方法，可以提高方法的查找速度

• 缓存查找
• objc-cache.mm
• void cache_t::insert(Class cls, SEL sel, IMP imp, id receiver)

//简化后的源码

struct bucket_t {
cache_key_t  _key; //SEL作为key  如: _key --> @selecter(test)
IMP _imp;   //函数的内存地址       如: _imp --> test 方法的地址
}

struct cache_t {
struct bucket_t   *_buckets; //散列表
mask_t   _mask;   //散列表的长度减一；_mask的值是随着存储的增加会发生变化，当内存空间用完了就会扩容（变为原来空间的两倍），扩容后清空缓存，再来一遍
mask_t _occupied; //已经缓存的方法数量
}

散列表原理

存储时通过算法获得存储位，读取时通过算法拿到存取位置直接读取，不需要遍历查找；

特点：空间换时间，且在一开始就预留了一个空位

以方法缓存举例

_key ： @selector(test)
_imp ：test 方法的地址

存入

• 方法地址值&(按位与)_mask，得到的值就是存储位，然后就把要存储的值(bucket_t)以key、value形式存储；比如得到值是4，那就直接存储到列表的第四个下标位，前面的位置直接存空值；
• 如果该存储位已经存储有值了，存储位向前移一位存储，直到存储成功；

读取

• 方法地址值&(按位与)_mask，得到的值就是存储位; 拿着下标位的值直接从数组中取，判断取出的key和传入的是否相同，如果不是就向前移一位查找判断，直到确定是相同的key为止（如果移到第0位依然没有，那就直接从最后一位向前找）；

1 << 1 : 左移位运算，左移就乘以2；
1 >> 1: 右移位运算符，右移就除以2；

缓存列表的长度限制最大64k,最小4字节

/* Initial cache bucket count. INIT_CACHE_SIZE must be a power of two. */
enum {
    INIT_CACHE_SIZE_LOG2 = 2,
    INIT_CACHE_SIZE      = (1 << INIT_CACHE_SIZE_LOG2),//最小4字节
    MAX_CACHE_SIZE_LOG2  = 16,
    MAX_CACHE_SIZE       = (1 << MAX_CACHE_SIZE_LOG2),//65536字节,最大64k
};

// Class points to cache. SEL is key. Cache buckets store SEL+IMP.
// Caches are never built in the dyld shared cache.
static inline mask_t cache_hash(SEL sel, mask_t mask) 
{
    return (mask_t)(uintptr_t)sel & mask;
}

static inline mask_t cache_next(mask_t i, mask_t mask) {
    return i ? i-1 : mask;
}

//核心代码
void cache_t::insert(Class cls, SEL sel, IMP imp, id receiver)
{
#if CONFIG_USE_CACHE_LOCK
    cacheUpdateLock.assertLocked();
#else
    runtimeLock.assertLocked();
#endif

    ASSERT(sel != 0 && cls->isInitialized());

    // Use the cache as-is if it is less than 3/4 full
    mask_t newOccupied = occupied() + 1;
    unsigned oldCapacity = capacity(), capacity = oldCapacity;
    if (slowpath(isConstantEmptyCache())) {空的散列表
        // Cache is read-only. Replace it.
        if (!capacity) capacity = INIT_CACHE_SIZE;
        reallocate(oldCapacity, capacity, /* freeOld */false);
    }
    else if (fastpath(newOccupied <= capacity / 4 * 3)) {//不满4分之3，继续存
        // Cache is less than 3/4 full. Use it as-is.
    }
    else {
       //扩容两倍
        capacity = capacity ? capacity * 2 : INIT_CACHE_SIZE;
        if (capacity > MAX_CACHE_SIZE) {
            capacity = MAX_CACHE_SIZE;
        }
        扩容时，清除老的缓存
        reallocate(oldCapacity, capacity, true); 
    }
   //重点逻辑
    bucket_t *b = buckets();
    mask_t m = capacity - 1;
   //sel:方法地址 m:散列表长度减一
    mask_t begin = cache_hash(sel, m);
   //索引值
    mask_t i = begin;

    // Scan for the first unused slot and insert there.
    // There is guaranteed to be an empty slot because the
    // minimum size is 4 and we resized at 3/4 full.
    查找到第一个未使用的插槽并插入，保证有一个空槽，因为最小尺寸是4，我们调整大小为3/4满。
    do {
        if (fastpath(b[i].sel() == 0)) {
            incrementOccupied();
            b[i].set<Atomic, Encoded>(sel, imp, cls);
            return;
        }
        if (b[i].sel() == sel) {
            // The entry was added to the cache by some other thread
            // before we grabbed the cacheUpdateLock.
            return;
        }
    } while (fastpath((i = cache_next(i, m)) != begin));

    在单独的步骤中进行日志记录，以防日志记录本身导致崩溃。
    cache_t::bad_cache(receiver, (SEL)sel, cls);

}

void cache_fill(Class cls, SEL sel, IMP imp, id receiver)
{
    runtimeLock.assertLocked();

#if !DEBUG_TASK_THREADS
    // Never cache before +initialize is done
    if (cls->isInitialized()) {
        cache_t *cache = getCache(cls);
#if CONFIG_USE_CACHE_LOCK
        mutex_locker_t lock(cacheUpdateLock);
#endif
        cache->insert(cls, sel, imp, receiver);
    }
#else
    _collecting_in_critical();
#endif
}

读取散列表简单逻辑演示（非源码）

#if __arm__  ||  __x86_64__  ||  __i386__
// objc_msgSend has few registers available.
// Cache scan increments and wraps at special end-marking bucket.
#define CACHE_END_MARKER 1
static inline mask_t cache_next(mask_t i, mask_t mask) {
    return (i+1) & mask;
}

#elif __arm64__
// objc_msgSend has lots of registers available.
// Cache scan decrements. No end marker needed.
#define CACHE_END_MARKER 0
static inline mask_t cache_next(mask_t i, mask_t mask) {
    return i ? i-1 : mask;
}

#else
#error unknown architecture
#endif

struct cache_t {

    bucket_t *_buckets; 散列表
    mask_t _mask;         散列表长度减一的值
    mask_t _occupied;  已经缓存的方法数量

    //传入selecter 返回 对应的IMP
    /**
     思路：
     1. mask&selector 拿到索引
     2. 拿到索引到散列表中取出对应的_key
     如果取出的_key和传入的selector相同说明是想要的直接返回IMP;
     如果条件不成立，进入while循环重新生成(算法-->i-1:当前索引向前移一位)一遍索引来取值，当然索引值肯定不能等于第一次的索引值;
     如果还是没找到符合条件的就返回NULL
     */
    IMP imp(SEL selector)
    {
        mask_t begin = _mask & (long long)selector;
        mask_t i = begin;
        do {
            if (_buckets[i]._key == 0  ||  _buckets[i]._key == (long long)selector) {
                return _buckets[i]._imp;
            }
        } while ((i = cache_next(i, _mask)) != begin);
        return NULL;
    }
};

输出示例

cache@2x.png

总结

方法缓存手段：通过散列表的形式快速读取和存储信息(@selecter(test)和方法地址)
缓存位置：缓存到类对象的cache_t或元类对象的cache_t中
存储特点：

• 第一次调用后就会缓存起来，方便下次快速调用
• 如果调用是父类的方法时，会把父类的方法缓存到当前消息接收者(自己)的缓存列表中
  简单来说就是：通过消息接收者调用成功的所有方法都会缓存一份到自己缓存列表中，方便以后快速调用提升效率
  注意：这并不代表父类缓存中就没有这个方法的缓存，这两者不影响
• 一直保持一个空槽，将要满了就以两倍内存扩容
• 扩容的逻辑: 申请新的内存-->把当前查询的方法缓存起来，注意在此之前的缓存是不会被添加回来的