类（元类）对象方法缓存原理

一、摘要

1.阅读该篇，需要对runtime底层及类对象数据结构有一定了解，本篇仅着重讲解方法缓存的算法；

2.以下以类对象来论述，元类对象以此类推；

 

二、类对象数据结构

//rumtime源码

 

 

//小码哥图片

 

 

说明：其中cache_t类型变量cache就是用来缓存曾经调度过的方法；

 

三、方法调度原理

person *per = [[person alloc] init];
createcaches(original_mask);
handlemethod("test1", @selector(test1), [per test1]);
handlemethod("test2", @selector(test2), [per test2]);
handlemethod("test1", @selector(test1), [per test1]);
handlemethod("test3", @selector(test3), [per test3]);
handlemethod("test4", @selector(test4), [per test4]);
handlemethod("test5", @selector(test5), [per test5]);
handlemethod("test4", @selector(test4), [per test4]);
handlemethod("test6withheight:age:", @selector(test6withheight:age:), [per test6withheight:1.7 age:30]);
handlemethod("test7withname:", @selector(test7withname:), [per test7withname:@"张三"]);
        
free(methodcaches);

如上所示：

1.实例对象per调test1/2/3等方法时，runtime底层本质是通过msgsend向per对象发送消息；

2.系统会通过per的isa指针找到其类对象，然后优先到该类对象的cache里面去查找，如果能找到则直接调用；如果没有找到则再到struct_rw_t中的methods方法列表中查找；如果还没找到，则通过superclass指针到父类中查找（查找顺序同前所述）；如果一级父类没找到，则一直往上级父类查找，直到根父类；如果根父类也没有，则返回空；

 

四、cache缓存算法

1.方法底层结构

 

 

说明：cache内部包含三个变量：buckets（散列表），_mask（散列表的长度-1），_occupied（已经缓存的方法数量）；bucket_t包含两个变量：类似于字典的键值对，_key是

方法sel（整型数据），_imp缓存函数的内存地址；

2.算法思路——散列表（空间换时间）：

1）用散列表（即数组）来缓存调用的方法，先开辟固定长度的内存（此处设置为3），数组元素则为键值对的结构体；

//创建散列表

void createcaches(mask_t mask) {
    //创建散列表
    struct bucket_t *originalbuckets = (struct bucket_t *)malloc(sizeof(struct bucket_t)*mask);
    for (int i = 0; i < mask; i++) {
        originalbuckets[i]._name = "";
        originalbuckets[i]._key = 0;
        originalbuckets[i]._imp = null;
        originalbuckets[i]._types = "null";
    }
    
    methodcaches = (struct cache_t *)malloc(sizeof(struct cache_t));
    methodcaches->_mask = (mask_t)(mask-1);
    methodcaches->_occupied = 0;
    methodcaches->_buckets = originalbuckets;
}

 

2）用_mask与_key进行按位与运算，得到每个元素的下标index——这样得出的index不会大于_mask（原因：可以看位域那篇文章），同时为随机数；

 

3）每次调方法，会先进行按位与计算得出下标a，然后查找该下标位置处是否缓存了方法：如果有且缓存的方法跟被调方法相同，则直接调用缓存中的方法；如果没有，则下标-1进行遍历查找（为0时，直接回到数组末尾，再-1继续查找），直至回到a处，如果找到了，则直接调，如果没有找到，则将该方法进行缓存；

//查找核心代码

//inline关键字：c++关联函数，表示在调用该函数处，直接替换成函数体内的代码（好处：避免频繁调用该函数导致内存消耗）
static inline mask_t cache_next(mask_t i, mask_t mask) {
    return i ? i-1 : mask;
}



//查找方法
    imp findsel(sel selector) {
        mask_t begin = _mask & (long long)selector;
        mask_t i = begin;
        do {//如果查到直接返回，否则-1往回查找，直到又回到begin位置处
            if (_buckets[i]._key == (long long)selector) {
                return _buckets[i]._imp;
            }
        } while ((i = cache_next(i, _mask)) != begin);
        return null;//没有找到，返回null
    }

 

4）如果a处是空，则直接缓存至a处，否则-1查找遍历空余位置（原理同上）；

//缓存核心代码

void savesel(char const*method, sel selector, imp methodimp, char const*types) {
    //散列表是否为空
    if (methodcaches->_buckets && methodcaches->_mask+1 > 0) {
        mask_t begin = methodcaches->_mask & (long long)selector;
        mask_t i = begin;
        do {
            if (methodcaches->_buckets[i]._imp == null) {
                methodcaches->_buckets[i]._name = method;
                methodcaches->_buckets[i]._key = (long long)selector;
                methodcaches->_buckets[i]._imp = methodimp;
                methodcaches->_buckets[i]._types = types;
                methodcaches->_occupied++;
                return ;//保存成功
            }
        } while ((i = cache_next(i, methodcaches->_mask)) != begin);
    }
}

 

5）如果散列表存满了，则需扩容：数组长度扩大2倍，并且会清空散列表，重新做缓存操作；

void expandcaches() {
    //清空内存
    mask_t lastmask = methodcaches->_mask;
    free(methodcaches->_buckets);
    free(methodcaches);
    
    mask_t newmaskt = (lastmask+1)*2;
    createcaches(newmaskt);
}

 

补充：

1）在bucket_t中加入了两个成员变量：_name（方法阅读具体调的是哪个方法），_types（描述方法返回值、形参类型，及所有参数所占字节总数和每个参数的内存起始位置）；

2）通过@encode获取数据类型编码，_types具体描述如下：

// "i24@0:8i16f20"
// 0id 8sel 16int 20float  == 24
/*说明
 1.每个方法默认隐式自带两个参数：self自身（id类型），@selector()方法（sel类型）；
 2.每种类型可通过@encode(类型名称)指令翻译；
 3.参数含义：
 1>符号：
 i表示返回值类型；
 @表示id类型；
 :表示sel类型；
 i（第二个）表示age变量类型；
 f表示height变量类型；
 2>数字：
 24表示所有类型所占字节数：8（id为指针类型）+8（sel为指针类型）+4（age）+4（height）；
 0表示self自身是从第零个字节开始——以此类推：8表示selector从第八个字节开始。。。height是从第20个字节开始；
 */
- (int)test:(int)age height:(float)height;

 

 

五、总结

ios系统runtime方法缓存核心思想为：用散列表来缓存，用空间来换时间，通过按位与计算来确定方法下标索引；

 

注意：如果工程打开碰到以下错误，则按下面操作解决

 

 

 

 

github