20 / 12 / 18

「重学 OC」内存管理05 - Objective-C中的方法缓存

我们在分析清楚方法列表和方法的结构后,我们再来看一下方法的调用是怎么一个流程呢?是直接去方法列表里面遍历查找对应的方法吗?

其实不然,我们在分析类的结构的时候,除了bits(指向类的具体信息,包括rw_t、ro_t等等一些内容)外,还有一个方法缓存:cache,用来缓存曾经调用过的方法。

所以系统查找对应方法不是通过遍历rw_t这个二维数组来寻找方法的,这样做太慢,效率太低,系统是先从方法缓存中找有没有对应的方法,有的话就直接调用缓存里的方法,根据imp去调用方法,没有的话,就再去方法数组中遍历查找,找到后调用并保存到方法缓存里,流程如下:

那么方法是怎么缓存到cache中的呢?系统又是怎么查找缓存中的方法的呢?我们通过源码来看一下cache的结构:

散列表(Hash table,也叫哈希表),是根据关键码值(Key value)而直接进行访问的数据结构。也就是说,它通过把关键码值映射到表中一个位置来访问记录,以加快查找的速度。这个映射函数叫做散列函数,存放记录的数组叫做散列表。

我们可以看到,cache_t里面就三个成员,后两个代表长度和数量,是int类型,肯定不是存储方法的地方,所以方法应该是存储在_buckets这个散列表中。散列存储的是一个个的bucket_t的结构体,那么这个bucket_t又是个什么结构呢?

所以cache_t底部结构是这样的:

我们看到,bucket_t就两个值,一个key一个imp,key的话就是方法名,也就是SEL,而imp就是Value,也就是当我们调用一个方法是来到方法缓存中查找,通过比对方法名是不是一致,一致的话就返回对应的imp,也就是方法地址,从而可以调用方法,那么这个散列表是怎么查找的呢?难道也是通过遍历吗?我们通过阅读源码来一探究竟:

通过上面代码的阅读,我们可以知道系统在cache_t中查找方法并不是通过遍历,而是通过方法名SEL&mask得到一个索引,直接去读数组索引中的方法,如果该方法的SEL与我们调用的方法名SEL一致,那么就返回这个方法,否则就一直向下寻找直到找完为止。

好,既然取值的时候不是遍历,而是直接读的索引,那么将方04法存储到缓存中也肯定是通过这种方式了,直接方法名&mask拿到索引,然后将_key和_imp存储到对应的索引上,这一点我们通过源码也可以确认:

我们看到无论是存还是读,都是调用了find函数,查看SEL&mask对应的索引的方法,不合适的话再向下寻找直到找到合适的位置。

  • 那么这里有两个疑问,为什么SEL&mask会出现不是该方法名(读)或者不为空(写)的情况呢?散列表扩容后方法还在吗?

    首先,SEL&mask这个问题,是因为不同的方法名&mask可能出现同一个结果,比如test方法的SEL是011,run方法的SEL是010,mask是010,那么无论是test的SEL&mask还是run的SEL&mask 记过都是010,如果大家都存在这个索引里面是会出问题的,所以为了解决这个索引重复的问题需要先做判断,即拿到索引后先判断这个索引对应的值是不是你想要的,是的话你拿走用,不是的话向下继续找,方法缓存也是同样的道理。我们先调用test方法,缓存到010索引,再调用run方法,发现010位置不为空了,那就判断010下面的索引是否为空,为空的话就将run方法缓存到这个位置。

    关于散列表扩容后,缓存方法在不在的问题,通过源码就可以知道,旧散列表已经释放掉了,所以是不存在的,再次调用的时候就得重新去rw_t中遍历找方法然后重新缓存到散列表中,比如下面这个例子:

我们前面讲到当SEL&mask出来一个索引发现被占用或者不是我想要的时候,系统是向索引下一位再次寻找,这个地方失误了,不是向下是向上寻找,这个地方看源码的时候忽略了条件,在x86或者i386架构中是向下寻找,在arm64架构中是向上寻找:(因为上面图片资源都已经删掉了就没有再更改,这里需要注意一下)

到现在我们清楚了,那就是散列表中并不是按照索引依次排序或者遍历索引依次读取,那么就会出现个问题,因为SEL&mask是个小于mask的随机值且散列表存储空间超过3/4的时候就要扩容,那就会导致散列表中有一部分空间始终被限制。确实,散列表当分配内存后,每个地方最初都是null的,当某个位置的索引被用到时,对应的位置才会存储方法,其余位置仍处于空闲状态,但是这样做可以极大提高查找速度(比遍历快很多),所以这是一种空间换时间的方式。