iOS进阶-05cache_t

上一章讲了objc_class中的bits中存储的属性、成员变量、实例方法等，这一章探究下cache_t cache。
日常面试当中面试官一般会问objc_class中的cache作用是什么？大家都会回答用于方法缓存：

每当调用方法的时候，会先去cache中查找是否有缓存的方法，如果没有缓存，在去类对象方法列表中查找，以此类推直到找到方法之后，就会将方法直接存储在cache中，下一次在调用这个方法的时候，就会在类对象的cache里面找到这个方法，直接调用了。

那这个cache究竟是如何工作的呢？

cache_t源码

先看源码：

//objc_class部分源码
struct objc_class : objc_object {
    // Class ISA;
    Class superclass;
    cache_t cache;             // formerly cache pointer and vtable
    class_data_bits_t bits;    // class_rw_t * plus custom rr/alloc flags

    class_rw_t *data() { 
        return bits.data();
    }
    void setData(class_rw_t *newData) {
        bits.setData(newData);
    }
    ...
    ...
}

cache位于objc_class中，是cache_t类型的属性

//cache_t部分源码
struct cache_t {
    struct bucket_t *_buckets;//散列表 数组
    mask_t _mask;//散列表的长度 -1(为什么是-1 下面说明)
    mask_t _occupied;//已经缓存的方法数量
    ...
    ...
};

cache_t 是一个结构体，一个用于储存方法桶(_buckets),一个表示方法桶(_buckets)长度的_mask，还有一个表示已经缓存方法的数量的_occupied

//bucket_t源码
struct bucket_t {
private:
    // IMP-first is better for arm64e ptrauth and no worse for arm64.
    // SEL-first is better for armv7* and i386 and x86_64.
#if __arm64__
    MethodCacheIMP _imp;//函数实现指针
    cache_key_t _key;//由SEL转化而来的常数Key
#else
    cache_key_t _key;
    MethodCacheIMP _imp;
#endif
};

//getKey()方法源码
cache_key_t key = getKey(sel);
cache_key_t getKey(SEL sel) //将字符创sel转成cache_key_t 类型的数值，方便储存
{
    assert(sel);
    return (cache_key_t)sel;
}

bucket_t储存_imp和_key，而_key又是通过getKey(SEL sel)函数转换而来的。_imp和_key类似于key-value
所以：

• cache_t存着维护着一张含有多个bucket_t的散列表，即_buckets
• 每个方法都会以bucket_t形式储存，并且方法的SEL会转化成key，imp就是方法实现。简单说：bucket_t封装了sel和imp。
  通过一张图来展示一下cache_t的结构。
  cache_t

cache工作机制
探究cache工作机制，必然离不开objc-cache源码，我将截取源码中部分重要的方法进行解读：

cache_fill_nolock() 主线

static void cache_fill_nolock(Class cls, SEL sel, IMP imp, id receiver)
{
    cacheUpdateLock.assertLocked();
    // 如果没有initialize直接return
    if (!cls->isInitialized()) return;
    // 确保线程安全，没有其他线程添加缓存
    if (cache_getImp(cls, sel)) return;
    // 通过类对象获取到cache 
    cache_t *cache = getCache(cls);
    // 将SEL包装成Key
    cache_key_t key = getKey(sel);
   // 占用空间+1,这里就解释了mask_t _mask;散列表的长度 -1
    mask_t newOccupied = cache->occupied() + 1;
   // 获取缓存列表的缓存能力，能存储多少个键值对
    mask_t capacity = cache->capacity();
    if (cache->isConstantEmptyCache()) {
        // 如果为空的，则创建空间，这里创建的空间为4个。
        cache->reallocate(capacity, capacity ?: INIT_CACHE_SIZE);
    }
    else if (newOccupied <= capacity / 4 * 3) {
        // 如果所占用的空间占总数的3/4一下，则继续使用现在的空间
    }
    else {
       // 如果占用空间超过3/4则扩展空间
        cache->expand();
    }
    // 通过key查找合适的存储空间。
    bucket_t *bucket = cache->find(key, receiver);
    // 如果key==0则说明之前未存储过这个key，占用空间+1
    if (bucket->key() == 0) cache->incrementOccupied();
    // 存储key，imp 
    bucket->set(key, imp);
}

reallocate()

void cache_t::reallocate(mask_t oldCapacity, mask_t newCapacity)
{
    // 旧的散列表能否被释放
    bool freeOld = canBeFreed();
    // 获取旧的散列表
    bucket_t *oldBuckets = buckets();
    // 通过新的空间需求量创建新的散列表
    bucket_t *newBuckets = allocateBuckets(newCapacity);

    assert(newCapacity > 0);
    assert((uintptr_t)(mask_t)(newCapacity-1) == newCapacity-1);
    // 设置Buckets和Mash，Mask的值为散列表长度-1
    setBucketsAndMask(newBuckets, newCapacity - 1);
    // 释放旧的散列表
    if (freeOld) {
        cache_collect_free(oldBuckets, oldCapacity);//为什么使用cache_collect_free消除记忆，而不是重新读写、内存拷贝的方式？一是重新读写不安全；二是抹掉速度快
        cache_collect(false);
    }
}

上述源码中首次传入reallocate()函数的newCapacity为INIT_CACHE_SIZE，INIT_CACHE_SIZE是个枚举值，也就是4。因此散列表最初创建的空间就是4个

enum {
    INIT_CACHE_SIZE_LOG2 = 2,
    INIT_CACHE_SIZE      = (1 << INIT_CACHE_SIZE_LOG2)
};

还有就是方法最后调用了cache_collect_free()方法释放原有的内存空间，而不是重新读写、内存拷贝的方式？一是重新读写不安全；二是抹掉速度快

expand ()

void cache_t::expand()
{
    cacheUpdateLock.assertLocked();
    // 获取旧的散列表的存储空间
    uint32_t oldCapacity = capacity();
    // 将旧的散列表存储空间扩容至两倍
    uint32_t newCapacity = oldCapacity ? oldCapacity*2 : INIT_CACHE_SIZE;
    // 为新的存储空间赋值
    if ((uint32_t)(mask_t)newCapacity != newCapacity) {
        newCapacity = oldCapacity;
    }
    // 调用reallocate函数，重新创建存储空间
    reallocate(oldCapacity, newCapacity);
}

当散列表的空间被占用超过3/4的时候，散列表会调用expand ()函数进行扩展,上述源码中可以发现散列表进行扩容时会将容量增至之前的2倍。为什么是2倍？2倍的扩容法是在高速计算中最快且相对节省内存空间；

find()

bucket_t * cache_t::find(cache_key_t k, id receiver)
{
    assert(k != 0);
    // 获取散列表
    bucket_t *b = buckets();
    // 获取mask
    mask_t m = mask();
    // 通过key找到key在散列表中存储的下标
    mask_t begin = cache_hash(k, m);
    // 将下标赋值给i
    mask_t i = begin;
    // 如果下标i中存储的bucket的key==0说明当前没有存储相应的key，将b[i]返回出去进行存储
    // 如果下标i中存储的bucket的key==k，说明当前空间内已经存储了相应key，将b[i]返回出去进行存储
    do {
        if (b[i].key() == 0  ||  b[i].key() == k) {
            // 如果满足条件则直接reutrn出去
            return &b[i];
        }
    // 如果走到这里说明上面不满足，那么会往前移动一个空间重新进行判定，知道可以成功return为止
    } while ((i = cache_next(i, m)) != begin);

    // hack
    Class cls = (Class)((uintptr_t)this - offsetof(objc_class, cache));
    cache_t::bad_cache(receiver, (SEL)k, cls);
}

######cache_hash()
static inline mask_t cache_hash(cache_key_t key, mask_t mask) 
{
    return (mask_t)(key & mask);
}

fin()函数就是通过key找到相应的bucket的过程；其内部cache_hash()方法中只进行了(mask_t)(key & mask)按位与运算得到下标即存储在相应的位置上，这样可以保证计算速度更快。

LRU算法

LRU - (Least Recently Used):最近最少使用策略——先淘汰最近最少使用的内容，在方法缓存中也用到了这种算法

缓存流程总结

• 由cache_fill_nolock()函数进入缓存流程，判断是否有缓存。有，直接return;
• 没有的话，先将sel转成key，然后读取occupied(占用)
• 再判断是否为一个空的缓存表；如果是空的，那就reallocate()创建空间，并且通过allocateBuckets()创建buckets。
  -如果缓存表不空，会判断缓存数量否达到了3/4的临界值，超过了，就会进行expand()扩容操作；
• 最后不管缓存空不空，又或者是缓存数量否达到了3/4的临界值，都会将此次sel(key)和imp的缓存到bucket中

参考 xx_cc iOS底层原理总结 - 探寻Runtime本质（二）