類(元類)對象方法緩存原理

一、摘要

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具體描述如下:

// "[email protected]: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

posted @ 2020-04-06 17:20  春天里的花骨朵  閱讀(...)  評論(...編輯  收藏