Objective-C 方法缓存探密

众所周知 Objective-C 在查找方法的 imp 时会先查找缓存，那么缓存是如何实现的呢？本文就记录下阅读 runtime 源码的过程。

objc-runtime-new.h

先从 objc-runtime-new.h 中 objc_class 的定义开始。

在 objc_class 中有一个结构体 cache_t，这个就是方法的缓存。而 cache_t 的第一个成员变量是 _bucketsAndMaybeMask，熟悉数据结构相关知识的同学应该会马上联想到哈希表。没错，方法缓存就是通过哈希表实现的。

再仔细看看 cache_t ，根据CACHE_MASK_STORAGE宏定义了不同的字段，而 CACHE_MASK_STORAGE 定义在 objc-config.h 中。

以 __arm64__ && __LP64__ 为例：

定义了成员变量：

• maskShift mask 偏移量 48
• maskZeroBits mask 后方必须为 0 的 bits 4
• maxMask mask 最大值 1111 1111 1111 1111，即 16 bits
  • 1 << (64 - maskShift) 表示 1 左移 16 位，结果为 1 0000 0000 0000 0000
  • 1 0000 0000 0000 0000 - 1 ，结果为 0 1111 1111 1111 1111
• bucketsMask buckets 的 mask 1111 ... 1111 (44 个 1)
  • 1 << (maskShift - maskZeroBits) 表示 1 左移 44 位，结果为 1 0000 ... 0000 (44 个 0)
  • 1 0000 ... 0000 (44 个 0) - 1， 结果为 1111 ... 1111 (44 个 1)

定义了以下方法：

下面到 objc-cache.mm 看看具体实现

objc-cache.mm

从最主要 insert 方法开始，大致分为三个部分。

Part 1 initialize 判断

第一部分是对 cls +initialize 方法是否执行完成的判断，如果没有则直接 return

Part 2 初始化及扩容

isConstantEmptyCache

首先会获取哈希表当前的元素个数 occupied 以及容量 capacity， 然后通过isConstantEmptyCache判断哈希表是否为空

其中通过 buckets 函数获取了当前桶数组，是将_bucketsAndMaybeMask 指针与 bucketsMask 做位与，前面我们知道了bucketsMask 的值为 44，所以 _bucketsAndMaybeMask 中的低 44 位存储的是 buckets 数组的地址。

INIT_CACHE_SIZE

再回到 insert 中，如果哈希表为空则进行初始化分配空间，大小为 INIT_CACHE_SIZE, INIT_CACHE_SIZE为枚举值

这里又引入了一个新的宏定义 CACHE_END_MARKER

从注释和命名可以得知，这是用于标记缓存的终止位置，在 __arm64__ && __LP64__ 的 case 下有很多寄存器，缓存扫描是递减的，不需要 marker 。

所以这里缓存的初始大小是 1 << 1 , 即 2 。

reallocate

再再回到 insert 中，调用了 reallocate 函数

获取旧的 buckets，调用allocateBuckets开辟新的空间，调用 setBucketsAndMask 设置新的 buckets 和 mask 到 _bucketsAndMaybeMask, mask 值为当前 buckets 的最大 index。最后再释放旧的 buckets

这里用到前面在 .h 中看到的 maskShift（48），所以这里可以得出 _bucketsAndMaybeMask 的高 16 位是 mask，低 44 位是 buckets，中间 4 位是 maskZeroBits 为 0

Objective-C 方法缓存探密

cache_fill_ratio

再再再回到 insert 中，会调用 cache_fill_ratio判断是否需要扩容

Part 3 插入数据

再再再再回到 insert 中，看看第三部分

cache_hash

通过 cache_hash 函数计算 sel 在 buckets 中的索引

和哈希表的基本思想一致，把 sel 与 mask 做位与运算，等同于模运算 % (mask + 1)。

do - while

再再再再再回到 insert 中，是一个 do - while 循环

• 如果 bucket 的 sel 值为 0，则表示这是一个空槽可以插入数据。
• 如果 sel 的值和当前 sel 相等，则表示其他线程已经缓存过该方法。
• 如果都不满足，则会调用 cache_next 查找下一个位置，是哈希表解决哈希冲突方式的开放寻址-线性探测

在 __arm64__ && __LP64__ case 下，只要 i 不为 0，就会一直递减，和前面 CACHE_END_MARKER 的注释相对应。

总结

• 方法缓存是基于哈希表的数据结构实现的
• 确定索引的哈希算法是将 sel 与 buckets 大小做位与运算，即取余数
• 哈希表解决哈希冲突的方式是线性探查

以上内容基于 objc4-906.2 纯理论阅读所写，省去了部分逻辑分支，如有错误，欢迎指正。