Runtime：方法缓存

夜景

目录
一，objc_class
二，class_ro_t和class_rw_t
三，method_t
四，方法缓存原理
五，方法缓存验证

一，objc_class

1，底层代码（源码下载地址）

struct objc_object {
    isa_t isa;
};

struct objc_class : objc_object {
    Class superclass;
    cache_t cache; // 方法缓存
    class_data_bits_t bits;
    class_rw_t* data() { 
        return (class_rw_t *)(bits & FAST_DATA_MASK);
    }
};

struct class_rw_t {
    const class_ro_t *ro;
    method_array_t methods;      // 原类+分类方法列表
    property_array_t properties; // 原类+分类属性列表
    protocol_array_t protocols;  // 原类+分类协议列表
};

struct class_ro_t {
    const ivar_list_t *ivars;        // 成员变量列表
    method_list_t *baseMethodList;   // 原类方法列表
    property_list_t *baseProperties; // 原类属性列表
    protocol_list_t *baseProtocols;  // 原类协议列表
};

2，图解

objc_class

二，class_ro_t和class_rw_t

1，class_ro_t

• 系统在编译时会将原类的数据存放在该结构体中

• 该结构体是只读的，ro是readonly的缩写

• 该结构体中的列表都是一维数组，数组的元素都是结构体

class_ro_t

2，class_rw_t

• 系统在运行时会将原类和分类的数据合并后存放在该结构体中

• 该结构体是可读可写的，rw是readwrite的缩写

• 该结构体中的列表都是二维数组，数组的元素也都是数组

class_rw_t

3，底层代码

// 编译时只创建了class_ro_t，bits里面存储的也是class_ro_t
static Class realizeClassWithoutSwift(Class cls) {
    // 取出class_ro_t
    ro = (const class_ro_t *)cls->data();
    if (ro->flags & RO_FUTURE) { // class_rw_t已创建
        rw = cls->data();
        ro = cls->data()->ro;
        cls->changeInfo(RW_REALIZED|RW_REALIZING, RW_FUTURE);
    } else { // class_rw_t未创建
        // 创建class_rw_t
        rw = (class_rw_t *)calloc(sizeof(class_rw_t), 1);
        // 将class_ro_t赋值给class_rw_t的ro指针
        rw->ro = ro;
        rw->flags = RW_REALIZED|RW_REALIZING;
        // 将class_rw_t存储到bits中
        cls->setData(rw);
    }
}

三，method_t

1，它是对函数的封装

struct method_t {
    SEL name; // 函数名
    const char *types; // 返回值类型和参数类型的编码
    IMP imp; // 指向函数的指针
};

2，IMP

它是implementation的缩写，存储函数实现的地址

typedef id _Nullable (*IMP)(id _Nonnull, SEL _Nonnull, ...);

3，SEL

• 它是selector的缩写，一般叫做选择器

typedef struct objc_selector *SEL;

• 获取方式

SEL sel1 = @selector(init);
SEL sel2 = sel_registerName("init");

• 它是不区分类的，只要方法名相同，对应的选择器就相等

NSLog(@"%p---%p---%p", @selector(init), sel_registerName("init"), @selector(init));

// 打印
0x7fff5271b057---0x7fff5271b057---0x7fff5271b057

4，types

• 实例代码

// Class无法查看具体的信息，所以用yj_objc_class代替，它就是objc_class，只是加了个前缀而已

@interface Person : NSObject
- (int)eat:(int)food run:(float)meter;
@end

@implementation Person
- (int)eat:(int)food run:(float)meter {
    return 1;
}
@end

int main(int argc, char * argv[]) {
    @autoreleasepool {
        yj_objc_class *clas = (__bridge yj_objc_class *)[Person class];
        class_rw_t *data = clas->data();
    }
    return 0;
}

• 底层结构

types

• 分析

i 24 @ 0 : 8 i 16 f 20

1>第一个字母是返回值类型的编码（i=int）

2>后面的字母依次是参数类型的编码（Person *=@，:=SEL，i=int，f=float）

// 系统会默认添加两个参数
static int _I_Person_eat_run_(Person *self, SEL _cmd, int food, float meter) {
   return 1;
}

3>第一个数字是所有参数占的总字节数（24 = 8（Person *）+ 8（SEL）+ 4（int）+ 4（float））

4>后面的数字依次是参数所占字节在总字节中的起始位置

起始位置

• @encode

将具体的类型转换为字符串编码

NSLog(@"%s---%s---%s---%s", @encode(Person *), @encode(SEL), @encode(int), @encode(float));

// 打印
@---:---i---f

四，方法缓存原理

1，为何缓存

• 调用某个方法，首先通过isa和superclass指针找到该方法所在的class对象或meta-class对象，然后遍历对象中的方法列表，找到方法后再进行调用
• 如果每次调用该方法都走上面的流程，效率就太低了，所以系统会在第一次调用该方法时将其存入cache_t中，第二次开始直接从cache_t中取出进行调用，从而提高了效率

2，cache_t

struct cache_t {
    struct bucket_t *_buckets; // 散列表
    mask_t _mask; // 散列表长度 - 1
    mask_t _occupied; // 已缓存数量
};

// 与字典类似
struct bucket_t {
    SEL _sel; // SEL为key
    IMP _imp; // IMP为value
};

3，散列表

• 结构

散列表

• 存储

1>系统会预先为散列表分配一段内存空间用做方法缓存

2>当有方法需要缓存时，先用方法的SEL & _mask得到索引，然后将方法转换为bucket_t存储到索引对应的位置（由于&的特点，索引只会小于或等于_mask，也就肯定小于散列表的长度）

3>如果索引对应的位置已经存储方法了（不同方法的SEL & _mask得到的索引可能相等），就将索引-1继续查找（当索引为0时将其置为_mask），直到索引对应的位置为NULL为止（举例：2 → 1 → 0 → 4 → 3）

4>当散列表快存满时，系统会扩大散列表的缓存空间（之前的两倍），并将之前缓存的方法全部移除

• 查找

1>当调用某个方法时，先查看散列表是否已存储该方法，如果有存储就直接调用，如果没有存储就走正常查找流程

2>当查找散列表时，先用方法的SEL & _mask得到索引，然后查看索引对应位置的bucket_t，如果_sel等于方法的SEL，就用_imp进行方法调用

3>如果_sel不等于方法的SEL，就将索引-1继续查找（当索引为0时将其置为_mask），直到它们相等为止

• 底层代码

1>查找方法

bucket_t * cache_t::find(SEL s, id receiver) {
    assert(s != 0);

    // 获取散列表
    bucket_t *b = buckets();
    // 获取_mask
    mask_t m = mask();
    // 获取索引
    mask_t begin = cache_hash(s, m);
    mask_t i = begin;
    do {
        // _sel == SEL
        if (b[i].sel() == 0 || b[i].sel() == s) {
            return &b[i];
        }
    // 修改索引继续查找
    } while ((i = cache_next(i, m)) != begin);

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

static inline mask_t cache_hash(SEL sel, mask_t mask) {
    // SEL & _mask
    return (mask_t)(uintptr_t)sel & mask;
}

// __arm64__
static inline mask_t cache_next(mask_t i, mask_t mask) {
    // i大于0就-1，i等于0就置为_mask
    return i ? i - 1 : mask;
}

2>扩大缓存空间

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(oldCapacity, newCapacity);
}

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);

    setBucketsAndMask(newBuckets, newCapacity - 1);
    
    if (freeOld) {
        // 释放旧散列表和旧空间
        cache_collect_free(oldBuckets, oldCapacity);
        cache_collect(false);
    }
}

五，方法缓存验证

1，cache_t

• 实例代码

// Person
@interface Person : NSObject
- (void)eat;
@end

@implementation Person
- (void)eat {}
@end

// Student
@interface Student : Person
- (void)study;
@end

@implementation Student
- (void)study {}
@end

// Boy
@interface Boy : Student
- (void)basketball;
@end

@implementation Boy
- (void)basketball {}
@end

• 扩大缓存空间前

1>_mask = 3：说明系统为散列表分配了4个缓存空间
2>_occupied = 3：说明已经缓存了3个方法（init，eat，study）

扩大前

• 扩大缓存空间后

当准备缓存basketball时系统发现散列表快存满了，所以就扩大了缓存空间，并将之前缓存的3个方法全部移除

1>_mask = 7：说明系统为散列表分配了8个缓存空间（4的两倍）
2>_occupied = 1：说明已经缓存了1个方法（basketball）

扩大后

⚠️注意⚠️：子类调用父类的方法，父类的方法就会缓存到子类的class对象或meta-class对象中

2，bucket_t

int main(int argc, char * argv[]) {
    @autoreleasepool {
        yj_objc_class *boyClass = (__bridge yj_objc_class *)[Boy class];
        Boy *boy = [[Boy alloc] init];
        [boy eat];
        [boy study];
        [boy basketball];
        [boy study];
        [boy eat];
        
         // 遍历散列表
        cache_t cache = boyClass->cache;
        bucket_t *buckets = cache._buckets;
        for (int i = 0; i <= cache._mask; i++) {
            bucket_t bucket = buckets[i];
            NSLog(@"%@---%p", NSStringFromSelector(bucket._sel), bucket._imp);
        }
    }
    return 0;
}

// 打印
eat---0x100000bd0
(null)---0x0
basketball---0x100000c30
(null)---0x0
study---0x100000c00
(null)---0x0
(null)---0x0
(null)---0x0

3，SEL & _mask

• 直接取出

// 从散列表中取出某个方法
cache_t cache = boyClass->cache;
bucket_t *buckets = cache._buckets;
int index = (uintptr_t)@selector(basketball) & cache._mask;
bucket_t bucket = buckets[index];
NSLog(@"%@---%p", NSStringFromSelector(bucket._sel), bucket._imp);

// 打印
basketball---0x100000c80

• 优化

struct cache_t {
    bucket_t *_buckets;
    mask_t _mask;
    mask_t _occupied;
    
    // 避免不同方法的SEL & _mask得到的索引可能相等的问题
    bucket_t bucket(SEL sel) {
        mask_t begin = (uintptr_t)sel & _mask;
        mask_t i = begin;
        do {
            if (_buckets[i]._sel == 0 || _buckets[i]._sel == sel) {
                return _buckets[i];
            }
        } while ((i = (i ? i - 1 : _mask)) != begin);
        return bucket_t();
    }
};

// 从散列表中取出某个方法
cache_t cache = boyClass->cache;
bucket_t bucket = cache.bucket(@selector(basketball));
NSLog(@"%@---%p", NSStringFromSelector(bucket._sel), bucket._imp);

// 打印
basketball---0x100000b70