iOS实例方法cache_t的缓存逻辑
先放一份流程图：
cache_t流程图.png
一、试验：
我们先做个试验：
执行三个方法
代码：
BYTestCache_t *test = [BYTestCache_t alloc];
Class tes = [BYTestCache_t class];
[test by_run];
[test by_read];
[test by_look];
然后打印出类里面的cache
2019-12-25 17:34:08.736684+0800 LGTest[42032:1260236] -[BYTestCache_t by_run]
2019-12-25 17:34:08.737882+0800 LGTest[42032:1260236] -[BYTestCache_t by_read]
2019-12-25 17:34:08.738353+0800 LGTest[42032:1260236] -[BYTestCache_t by_look]
(lldb) x tes
0x1000027a0: 79 27 00 00 01 80 1d 00 40 f1 af 00 01 00 00 00 y'......@.......
0x1000027b0: 70 2c f9 00 01 00 00 00 03 00 00 00 03 00 00 00 p,..............
(lldb) p (cache_t *)0x1000027b0
(cache_t *) $1 = 0x00000001000027b0
(lldb) p *$1
(cache_t) $2 = {
_buckets = 0x0000000100f92c70
_mask = 3
_occupied = 3
}
(lldb)
其中
_mask是缓存池的最大容量
_occupied是缓存池缓存的方法数量
然后执行四个方法
代码
2019-12-25 17:36:30.012946+0800 LGTest[42218:1265506] -[BYTestCache_t by_run]
2019-12-25 17:36:30.013646+0800 LGTest[42218:1265506] -[BYTestCache_t by_read]
2019-12-25 17:36:30.013816+0800 LGTest[42218:1265506] -[BYTestCache_t by_look]
2019-12-25 17:36:30.013931+0800 LGTest[42218:1265506] -[BYTestCache_t by_eat]
(lldb) x tes
0x1000027a0: 79 27 00 00 01 80 1d 00 40 f1 af 00 01 00 00 00 y'......@.......
0x1000027b0: 90 44 92 01 01 00 00 00 07 00 00 00 01 00 00 00 .D..............
(lldb) p (cache_t *)0x1000027b0
(cache_t *) $1 = 0x00000001000027b0
(lldb) p *$1
(cache_t) $2 = {
_buckets = 0x0000000101924490
_mask = 7
_occupied = 1
}
(lldb)
结论：
我们发现缓存池的最大容量变成7了，但是缓存的方法数为1，初步得出结论类的缓存池的最大容量会随着缓存方法数的增加而增加，并且增加时候会把原来缓存的方法清理掉
源码探究
从上帝视角，我们知道缓存方法的入口是cache_fill_nolock，所以我们先找到cache_fill_nolock方法，查看他的实现，然后我们从上往下分析
方法缓存逻辑
static void cache_fill_nolock(Class cls, SEL sel, IMP imp, id receiver)
{
cacheUpdateLock.assertLocked();
// Never cache before +initialize is done
if (!cls->isInitialized()) return;//系统要求在类初始化完成之前，不能进行方法缓存，因此如果类还没有初始化就返回
// Make sure the entry wasn't added to the cache by some other thread
// before we grabbed the cacheUpdateLock.
//如果能取到方法指针，直接返回，因为可能其他线程已经抢先把该方法缓存进来了，因此这里还需要再检查一次缓存，
if (cache_getImp(cls, sel)) return;
//取到缓存池
cache_t *cache = getCache(cls);
//将方法强转成long类型，当做key使用，这里我们可以看到缓存池是将SEL转成一个long类型来当做key使用
cache_key_t key = getKey(sel);
// Use the cache as-is if it is less than 3/4 full
//取到当前缓存池的缓存方法数并+1
mask_t newOccupied = cache->occupied() + 1;
//取到缓存池的总容量
mask_t capacity = cache->capacity();
//缓存池如果是空，则创建一个缓存池
if (cache->isConstantEmptyCache()) {
// Cache is read-only. Replace it.
cache->reallocate(capacity, capacity ?: INIT_CACHE_SIZE);
}//再加一个缓存，如果缓存池的缓存的方法数小于缓存池容量的4/3则不管，如果大于则扩容
else if (newOccupied <= capacity / 4 * 3) {
// Cache is less than 3/4 full. Use it as-is.
}
else {//如果缓存的方法大于容量的4/3，则扩容，扩容成现有缓存池总容量的2倍
// Cache is too full. Expand it.
cache->expand();
}
// 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.
//
//从缓存池中取出该方法对应的bucket
bucket_t *bucket = cache->find(key, receiver);
//如果取到的bucket的key为0说明没从缓存池中取到改方法，那么就将缓存池已缓存的数量+1
if (bucket->key() == 0) cache->incrementOccupied();
//将执行的方法缓存的缓存池中
bucket->set(key, imp);
}
mask_t cache_t::capacity()
{
//取当前缓存池总容量时候会在目前容量上+1
return mask() ? mask()+1 : 0;
}
结论：
里面我们可以看到苹果的缓存逻辑是当新方法进来之前判断加入后缓存的值是否大于总容量的4/3，如果大于则将缓存池扩容成老缓存池的二倍，这个缓存思想比较好，不会随便建立大的缓存池，也不会导致不够用，
扩容方法
//扩容方法，将容量扩充到原来的2倍，如果为空的话则默认给个4
void cache_t::expand()
{
cacheUpdateLock.assertLocked();
uint32_t oldCapacity = capacity();
uint32_t newCapacity = oldCapacity ? oldCapacity*2 : INIT_CACHE_SIZE;
//新的容量值强转成uint32_t，和原来的不相等就用老的容量值？
if ((uint32_t)(mask_t)newCapacity != newCapacity) {
// mask overflow - can't grow further
// fixme this wastes one bit of mask
newCapacity = oldCapacity;
}
//创建新的容量池，创建完成后会将原来缓存的方法清除掉
reallocate(oldCapacity, newCapacity);
}
开辟缓存池
开辟缓存池方法
void cache_t::reallocate(mask_t oldCapacity, mask_t newCapacity)
{
//如果缓存池容量为0，且缓存的方法为空，则不能清空
bool freeOld = canBeFreed();
//q取到老的缓存池
bucket_t *oldBuckets = buckets();
//建立新容量的缓存池
bucket_t *newBuckets = allocateBuckets(newCapacity);
// Cache's old contents are not propagated.
// This is thought to save cache memory at the cost of extra cache fills.
// fixme re-measure this
assert(newCapacity > 0);
assert((uintptr_t)(mask_t)(newCapacity-1) == newCapacity-1);
//初始化缓存池，缓存池的可缓存数比缓存池的r总容量要小1
setBucketsAndMask(newBuckets, newCapacity - 1);
/*
释放老的缓存池，因为读和写是非常耗时的操作，
缓存的目的是为了节省时间，
所以在创建新的缓存池时候没有将老缓存池的内存copy过来
而且这种操作也会清理掉缓存中长时间没调用的方法
*/
if (freeOld) {
cache_collect_free(oldBuckets, oldCapacity);
cache_collect(false);
}
}
再做一个验证查看老的缓存池是被释放掉了还是在老的缓存池上做扩容
2019-12-27 09:00:04.676836+0800 LGTest[41774:3837893] -[LGPerson by_eat5111]
(lldb) x tes
0x1000027c0: 99 27 00 00 01 80 1d 00 60 28 00 00 01 00 00 00 .'......`(......
0x1000027d0: f0 64 85 01 01 00 00 00 03 00 00 00 01 00 00 00 .d..............
(lldb) p (cache_t *)0x1000027d0
(cache_t *) $1 = 0x00000001000027d0
(lldb) p *$1
(cache_t) $2 = {
_buckets = 0x00000001018564f0
_mask = 3
_occupied = 1
}
2019-12-27 09:00:36.586354+0800 LGTest[41774:3837893] -[BYTestCache_t by_run1]
2019-12-27 09:00:36.586639+0800 LGTest[41774:3837893] -[BYTestCache_t by_read]
2019-12-27 09:00:36.586748+0800 LGTest[41774:3837893] -[BYTestCache_t by_look]
(lldb) p *$1
(cache_t) $3 = {
_buckets = 0x0000000101856540
_mask = 7
_occupied = 1
}
(lldb)
由上面我们看到，当扩容后cache_t的地址依然没变，从老的地址上取值依然能取到，但是容量却变大了，说明老的缓存池未被释放，扩容是在老的缓存池上做的扩容，并且扩容后会把老方法废弃掉，这是为啥呢？
方法存储方式之哈希表
因为方法是缓存在cache_t里面，它的底层是通过散列表（哈希表）的数据结构来实现的，用于缓存曾经调用过的方法，可以提高方法的查找速度
散列/哈希表，想必大部分iOS开发这至少应该听过，而我们常用的NSDictionary其实就是一种散列表数据结构。来看一下cache_t cache的定义
struct cache_t {
struct bucket_t *_buckets;
mask_t _mask;
mask_t _occupied;
}
struct bucket_t *_buckets; —— 用来缓存方法的散列/哈希表
mask_t _mask; —— 这个值 = 散列表长度 - 1
mask_t _occupied; —— 表示已经缓存的方法的数量
上面介绍的_buckets散列表里面的存储单元是bucket_t，来看看它包含了方法的什么信息
struct bucket_t {
private:
cache_key_t _key;
IMP _imp;
}
cache_key_t _key; —— 这个key实际上就是方法的SEL，也就是方法名
IMP _imp; —— 这个就是方法对应的函数的内存地址
但是散列表的运作原理到底如何呢，这个属于数据结构问题，这里简要介绍一下。首先散列表本质上就是一个数组
image.png
在往散列表里面添加成员的时候，首先需要借助key计算出一个index，也就是cache_hash函数，然后再将元素插入散列表的index位置
image.png
那么从散列表里面取值就显而易见了，根据一个key，计算出index，然后到散列表对应位置将值取出
image.png
这里的查询方法的时候（也就是取值操作），时间复杂度为O(1), 对比我们一开始就从方法列表的遍历查询，它的时间复杂度为O(n)，因此通过缓存方法，可以极大的提高方法查询的效率，从而提高了方法调用机制的效率。
根据key计算出index值的这个算法称作散列算法，这个算法可以由你自己设计，总之目的就是尽可能减少不同的key得出相同index的情况出现，这种情况被称作哈希碰撞，同时还要保证得出的index值在合理的范围。index越大，意味着对应的散列表的长度越长，这是需要占用实际物理空间的，而我们的内存是有限的。散列表是一种通过牺牲一定空间，来换取时间效率的设计思想。
我们通过key计算出的index大小是随机的，无顺序的，因此在方法缓存的过程中，插入的顺序也是无顺序的
image.png
而且可以预见的是，散列表里面再实际使用中会有很多位置是空着的，比如散列表长度为16，最终值存储了10个方法，散列表长度为64，最终可能只会存储40个方法，有一部分空间终究是要被浪费的。但是却提高查找的效率。这既是所谓的空间换时间。
再介绍一下苹果这里所采用的散列算法，其实很简单，如下
index = @selector(XXXX) & mask 根据&运算的特点，可以得知最终index <= mask，而mask = 散列表长度 - 1，也就是说 0 <= index <= 散列表长度 - 1，这实际上覆盖了散列表的索引范围。而刚刚我们还提到过一个问题——哈希碰撞，也就是不同的key得到相同的index，该怎么处理呢？我们看一下源码，在objc源码里面搜索cache_t，可以发现一个跟查找相关的方法
//方法缓存
bucket_t * cache_t::find(cache_key_t k, id receiver) //根据key值 k 进行查找
{
assert(k != 0);
bucket_t *b = buckets();
mask_t m = mask();
mask_t begin = cache_hash(k, m); //通过cache_hash函数【begin = k & m】计算出key值 k 对应的 index值 begin，用来记录查询起始索引
mask_t i = begin; // begin 赋值给 i，用于切换索引
do {
if (b[i].key() == 0 || b[i].key() == k) {
//用这个i从散列表取值，如果取出来的bucket_t的 key = k，则查询成功，返回该bucket_t，
//如果key = 0，说明在索引i的位置上还没有缓存过方法，同样需要返回该bucket_t，用于中止缓存查询。
return &b[i];
}
} while ((i = cache_next(i, m)) != begin);
// 这一步其实相当于 i = i-1,回到上面do循环里面，相当于查找散列表上一个单元格里面的元素，再次进行key值 k的比较，
//当i=0时，也就i指向散列表最首个元素索引的时候重新将mask赋值给i，使其指向散列表最后一个元素，重新开始反向遍历散列表，
//其实就相当于绕圈，把散列表头尾连起来，不就是一个圈嘛，从begin值开始，递减索引值，当走过一圈之后，必然会重新回到begin值，
//如果此时还没有找到key对应的bucket_t，或者是空的bucket_t，则循环结束，说明查找失败，调用bad_cache方法。
// hack
Class cls = (Class)((uintptr_t)this - offsetof(objc_class, cache));
cache_t::bad_cache(receiver, (SEL)k, cls);
}
*********************************** cache_hash(k, m);
static inline mask_t cache_hash(cache_key_t key, mask_t mask)
{
return (mask_t)(key & mask);
}
*********************************** cache_next(i, m)
static inline mask_t cache_next(mask_t i, mask_t mask) {
// return (i-1) & mask; // 非arm64
return i ? i-1 : mask; // arm64
}
在cache_fill_nolock方法最后我们看到调用了cache_t::find函数，
// 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.
bucket_t *bucket = cache->find(key, receiver);
if (bucket->key() == 0) cache->incrementOccupied();
bucket->set(key, imp);
上面源码的最后一段以及它的注释说明可以明白，当通过cache->find返回的bucket->key() == 0，就说明该位置上是空的，没有缓存过方法，是一个unused slot(未使用的槽口)，因此可以进行插入操作bucket->set(key, imp);，也就是将方法缓存到这个位置上。
结论：
开辟方法不仅仅是在老缓存池基础上进行扩容，开辟新的buckets，释放老的buckets，因为苹果是通过哈希表进行缓存，并且散列算法是index = @selector(XXXX) & mask，扩容后mask发生了变化，所以里面缓存方法的index也都要发生变化，为了提高缓存效率，创建了新的buckets，老的buckets就会被释放掉
初始化缓存池方法：
void cache_t::setBucketsAndMask(struct bucket_t *newBuckets, mask_t newMask)
{
// objc_msgSend uses mask and buckets with no locks.
// It is safe for objc_msgSend to see new buckets but old mask.
// (It will get a cache miss but not overrun the buckets' bounds).
// It is unsafe for objc_msgSend to see old buckets and new mask.
// Therefore we write new buckets, wait a lot, then write new mask.
// objc_msgSend reads mask first, then buckets.
// ensure other threads see buckets contents before buckets pointer
mega_barrier();
_buckets = newBuckets;
// ensure other threads see new buckets before new mask
mega_barrier();
_mask = newMask;
_occupied = 0;
}
总结：
1、实例方法是缓存在类中，类方法是在元类中
2、方法缓存逻辑是:
（1）第一次创建缓存池时候，缓存池的大小是4，但是最大容量数为3，并且以后扩容的缓存池的最大容量数都是缓存池大小减一
（2）在缓存方法时候会判断缓存新方法后的缓冲池里的方法数是否大于缓冲池大小的4/3，如果大于则需要扩容
（3）扩容后的缓存池大小是原来缓存池大小的2倍，并且扩容后会将老缓存池里面缓存的方法全部清理掉
