先放一份流程圖：

cache_t流程圖.png

一、試驗(yàn)：

我們先做個(gè)試驗(yàn)：

執(zhí)行三個(gè)方法

代碼：

        BYTestCache_t *test = [BYTestCache_t alloc];
        Class tes = [BYTestCache_t class];

        [test by_run];
        [test by_read];
        [test by_look];

然后打印出類里面的cache

2019-12-25 17:34:08.736684+0800 LGTest[42032:1260236] -[BYTestCache_t by_run]
2019-12-25 17:34:08.737882+0800 LGTest[42032:1260236] -[BYTestCache_t by_read]
2019-12-25 17:34:08.738353+0800 LGTest[42032:1260236] -[BYTestCache_t by_look]
(lldb) x tes
0x1000027a0: 79 27 00 00 01 80 1d 00 40 f1 af 00 01 00 00 00  y'......@.......
0x1000027b0: 70 2c f9 00 01 00 00 00 03 00 00 00 03 00 00 00  p,..............
(lldb) p (cache_t *)0x1000027b0
(cache_t *) $1 = 0x00000001000027b0
(lldb) p *$1
(cache_t) $2 = {
  _buckets = 0x0000000100f92c70
  _mask = 3
  _occupied = 3
}
(lldb) 

其中
_mask是緩存池的最大容量
_occupied是緩存池緩存的方法數(shù)量

然后執(zhí)行四個(gè)方法

代碼

2019-12-25 17:36:30.012946+0800 LGTest[42218:1265506] -[BYTestCache_t by_run]
2019-12-25 17:36:30.013646+0800 LGTest[42218:1265506] -[BYTestCache_t by_read]
2019-12-25 17:36:30.013816+0800 LGTest[42218:1265506] -[BYTestCache_t by_look]
2019-12-25 17:36:30.013931+0800 LGTest[42218:1265506] -[BYTestCache_t by_eat]
(lldb) x tes
0x1000027a0: 79 27 00 00 01 80 1d 00 40 f1 af 00 01 00 00 00  y'......@.......
0x1000027b0: 90 44 92 01 01 00 00 00 07 00 00 00 01 00 00 00  .D..............
(lldb) p (cache_t *)0x1000027b0
(cache_t *) $1 = 0x00000001000027b0
(lldb) p *$1
(cache_t) $2 = {
  _buckets = 0x0000000101924490
  _mask = 7
  _occupied = 1
}
(lldb) 

結(jié)論：

我們發(fā)現(xiàn)緩存池的最大容量變成7了，但是緩存的方法數(shù)為1，初步得出結(jié)論類的緩存池的最大容量會(huì)隨著緩存方法數(shù)的增加而增加，并且增加時(shí)候會(huì)把原來緩存的方法清理掉

源碼探究

從上帝視角，我們知道緩存方法的入口是cache_fill_nolock，所以我們先找到cache_fill_nolock方法，查看他的實(shí)現(xiàn)，然后我們從上往下分析

方法緩存邏輯

static void cache_fill_nolock(Class cls, SEL sel, IMP imp, id receiver)
{
    cacheUpdateLock.assertLocked();

    // Never cache before +initialize is done
    if (!cls->isInitialized()) return;//系統(tǒng)要求在類初始化完成之前，不能進(jìn)行方法緩存，因此如果類還沒有初始化就返回

    // Make sure the entry wasn't added to the cache by some other thread 
    // before we grabbed the cacheUpdateLock.
    //如果能取到方法指針，直接返回，因?yàn)榭赡芷渌€程已經(jīng)搶先把該方法緩存進(jìn)來了，因此這里還需要再檢查一次緩存，
    if (cache_getImp(cls, sel)) return;
    //取到緩存池
    cache_t *cache = getCache(cls);
    //將方法強(qiáng)轉(zhuǎn)成long類型，當(dāng)做key使用，這里我們可以看到緩存池是將SEL轉(zhuǎn)成一個(gè)long類型來當(dāng)做key使用
    cache_key_t key = getKey(sel);

    // Use the cache as-is if it is less than 3/4 full
    //取到當(dāng)前緩存池的緩存方法數(shù)并+1
    mask_t newOccupied = cache->occupied() + 1;
    //取到緩存池的總?cè)萘?    mask_t capacity = cache->capacity();
    //緩存池如果是空，則創(chuàng)建一個(gè)緩存池
    if (cache->isConstantEmptyCache()) {
        // Cache is read-only. Replace it.
        cache->reallocate(capacity, capacity ?: INIT_CACHE_SIZE);
    }//再加一個(gè)緩存，如果緩存池的緩存的方法數(shù)小于緩存池容量的4/3則不管，如果大于則擴(kuò)容
    else if (newOccupied <= capacity / 4 * 3) {
        // Cache is less than 3/4 full. Use it as-is.
    }
    else {//如果緩存的方法大于容量的4/3，則擴(kuò)容，擴(kuò)容成現(xiàn)有緩存池總?cè)萘康?倍
        // Cache is too full. Expand it.
        cache->expand();
    }

    // Scan for the first unused slot and insert there.
    // There is guaranteed to be an empty slot because the 
    // minimum size is 4 and we resized at 3/4 full.
    //
    //從緩存池中取出該方法對(duì)應(yīng)的bucket
    bucket_t *bucket = cache->find(key, receiver);
    //如果取到的bucket的key為0說明沒從緩存池中取到改方法，那么就將緩存池已緩存的數(shù)量+1
    if (bucket->key() == 0) cache->incrementOccupied();
    //將執(zhí)行的方法緩存的緩存池中
    bucket->set(key, imp);
}

mask_t cache_t::capacity() 
{
//取當(dāng)前緩存池總?cè)萘繒r(shí)候會(huì)在目前容量上+1
    return mask() ? mask()+1 : 0; 
}

結(jié)論：

里面我們可以看到蘋果的緩存邏輯是當(dāng)新方法進(jìn)來之前判斷加入后緩存的值是否大于總?cè)萘康?/3，如果大于則將緩存池?cái)U(kuò)容成老緩存池的二倍，這個(gè)緩存思想比較好，不會(huì)隨便建立大的緩存池，也不會(huì)導(dǎo)致不夠用，

擴(kuò)容方法

//擴(kuò)容方法，將容量擴(kuò)充到原來的2倍，如果為空的話則默認(rèn)給個(gè)4
void cache_t::expand()
{
    cacheUpdateLock.assertLocked();
    
    uint32_t oldCapacity = capacity();
    uint32_t newCapacity = oldCapacity ? oldCapacity*2 : INIT_CACHE_SIZE;
    //新的容量值強(qiáng)轉(zhuǎn)成uint32_t，和原來的不相等就用老的容量值？
    if ((uint32_t)(mask_t)newCapacity != newCapacity) {
        // mask overflow - can't grow further
        // fixme this wastes one bit of mask
        newCapacity = oldCapacity;
    }
    //創(chuàng)建新的容量池，創(chuàng)建完成后會(huì)將原來緩存的方法清除掉
    reallocate(oldCapacity, newCapacity);
}

開辟緩存池

開辟緩存池方法

void cache_t::reallocate(mask_t oldCapacity, mask_t newCapacity)
{
    //如果緩存池容量為0，且緩存的方法為空，則不能清空
    bool freeOld = canBeFreed();
    //q取到老的緩存池
    bucket_t *oldBuckets = buckets();
    //建立新容量的緩存池
    bucket_t *newBuckets = allocateBuckets(newCapacity);

    // Cache's old contents are not propagated. 
    // This is thought to save cache memory at the cost of extra cache fills.
    // fixme re-measure this

    assert(newCapacity > 0);
    assert((uintptr_t)(mask_t)(newCapacity-1) == newCapacity-1);
    //初始化緩存池，緩存池的可緩存數(shù)比緩存池的r總?cè)萘恳?
    setBucketsAndMask(newBuckets, newCapacity - 1);
    /*
釋放老的緩存池，因?yàn)樽x和寫是非常耗時(shí)的操作，
緩存的目的是為了節(jié)省時(shí)間，
所以在創(chuàng)建新的緩存池時(shí)候沒有將老緩存池的內(nèi)存copy過來
而且這種操作也會(huì)清理掉緩存中長(zhǎng)時(shí)間沒調(diào)用的方法
*/
    if (freeOld) {
        cache_collect_free(oldBuckets, oldCapacity);
        cache_collect(false);
    }
}

再做一個(gè)驗(yàn)證查看老的緩存池是被釋放掉了還是在老的緩存池上做擴(kuò)容

2019-12-27 09:00:04.676836+0800 LGTest[41774:3837893] -[LGPerson by_eat5111]
(lldb) x tes
0x1000027c0: 99 27 00 00 01 80 1d 00 60 28 00 00 01 00 00 00  .'......`(......
0x1000027d0: f0 64 85 01 01 00 00 00 03 00 00 00 01 00 00 00  .d..............
(lldb) p (cache_t *)0x1000027d0
(cache_t *) $1 = 0x00000001000027d0
(lldb) p *$1
(cache_t) $2 = {
  _buckets = 0x00000001018564f0
  _mask = 3
  _occupied = 1
}
2019-12-27 09:00:36.586354+0800 LGTest[41774:3837893] -[BYTestCache_t by_run1]
2019-12-27 09:00:36.586639+0800 LGTest[41774:3837893] -[BYTestCache_t by_read]
2019-12-27 09:00:36.586748+0800 LGTest[41774:3837893] -[BYTestCache_t by_look]
(lldb) p *$1
(cache_t) $3 = {
  _buckets = 0x0000000101856540
  _mask = 7
  _occupied = 1
}
(lldb) 

由上面我們看到，當(dāng)擴(kuò)容后cache_t的地址依然沒變，從老的地址上取值依然能取到，但是容量卻變大了，說明老的緩存池未被釋放，擴(kuò)容是在老的緩存池上做的擴(kuò)容，并且擴(kuò)容后會(huì)把老方法廢棄掉，這是為啥呢？

方法存儲(chǔ)方式之哈希表

因?yàn)榉椒ㄊ蔷彺嬖赾ache_t里面，它的底層是通過散列表（哈希表）的數(shù)據(jù)結(jié)構(gòu)來實(shí)現(xiàn)的，用于緩存曾經(jīng)調(diào)用過的方法，可以提高方法的查找速度

散列/哈希表，想必大部分iOS開發(fā)這至少應(yīng)該聽過，而我們常用的NSDictionary其實(shí)就是一種散列表數(shù)據(jù)結(jié)構(gòu)。來看一下cache_t cache的定義

struct cache_t {
    struct bucket_t *_buckets;
    mask_t _mask;
    mask_t _occupied;
}

struct bucket_t *_buckets; —— 用來緩存方法的散列/哈希表
mask_t _mask; —— 這個(gè)值 = 散列表長(zhǎng)度 - 1
mask_t _occupied; —— 表示已經(jīng)緩存的方法的數(shù)量

上面介紹的_buckets散列表里面的存儲(chǔ)單元是bucket_t，來看看它包含了方法的什么信息

struct bucket_t {
private:
    cache_key_t _key;
    IMP _imp;
}

cache_key_t _key; —— 這個(gè)key實(shí)際上就是方法的SEL，也就是方法名
IMP _imp; —— 這個(gè)就是方法對(duì)應(yīng)的函數(shù)的內(nèi)存地址

但是散列表的運(yùn)作原理到底如何呢，這個(gè)屬于數(shù)據(jù)結(jié)構(gòu)問題，這里簡(jiǎn)要介紹一下。首先散列表本質(zhì)上就是一個(gè)數(shù)組

image.png

在往散列表里面添加成員的時(shí)候，首先需要借助key計(jì)算出一個(gè)index，也就是cache_hash函數(shù)，然后再將元素插入散列表的index位置

image.png

那么從散列表里面取值就顯而易見了，根據(jù)一個(gè)key，計(jì)算出index，然后到散列表對(duì)應(yīng)位置將值取出

image.png

這里的查詢方法的時(shí)候（也就是取值操作），時(shí)間復(fù)雜度為O(1), 對(duì)比我們一開始就從方法列表的遍歷查詢，它的時(shí)間復(fù)雜度為O(n)，因此通過緩存方法，可以極大的提高方法查詢的效率，從而提高了方法調(diào)用機(jī)制的效率。

根據(jù)key計(jì)算出index值的這個(gè)算法稱作散列算法，這個(gè)算法可以由你自己設(shè)計(jì)，總之目的就是盡可能減少不同的key得出相同index的情況出現(xiàn)，這種情況被稱作哈希碰撞，同時(shí)還要保證得出的index值在合理的范圍。index越大，意味著對(duì)應(yīng)的散列表的長(zhǎng)度越長(zhǎng)，這是需要占用實(shí)際物理空間的，而我們的內(nèi)存是有限的。散列表是一種通過犧牲一定空間，來換取時(shí)間效率的設(shè)計(jì)思想。

我們通過key計(jì)算出的index大小是隨機(jī)的，無順序的，因此在方法緩存的過程中，插入的順序也是無順序的

image.png

而且可以預(yù)見的是，散列表里面再實(shí)際使用中會(huì)有很多位置是空著的，比如散列表長(zhǎng)度為16，最終值存儲(chǔ)了10個(gè)方法，散列表長(zhǎng)度為64，最終可能只會(huì)存儲(chǔ)40個(gè)方法，有一部分空間終究是要被浪費(fèi)的。但是卻提高查找的效率。這既是所謂的空間換時(shí)間。
再介紹一下蘋果這里所采用的散列算法，其實(shí)很簡(jiǎn)單，如下
index = @selector(XXXX) & mask 根據(jù)&運(yùn)算的特點(diǎn)，可以得知最終index <= mask，而mask = 散列表長(zhǎng)度 - 1，也就是說 0 <= index <= 散列表長(zhǎng)度 - 1，這實(shí)際上覆蓋了散列表的索引范圍。而剛剛我們還提到過一個(gè)問題——哈希碰撞，也就是不同的key得到相同的index，該怎么處理呢？我們看一下源碼，在objc源碼里面搜索cache_t，可以發(fā)現(xiàn)一個(gè)跟查找相關(guān)的方法

//方法緩存
bucket_t * cache_t::find(cache_key_t k, id receiver)  //根據(jù)key值 k 進(jìn)行查找
{
    assert(k != 0);

    bucket_t *b = buckets();
    mask_t m = mask();
    mask_t begin = cache_hash(k, m);   //通過cache_hash函數(shù)【begin  = k & m】計(jì)算出key值 k 對(duì)應(yīng)的 index值 begin，用來記錄查詢起始索引
    mask_t i = begin; // begin 賦值給 i，用于切換索引
    do {
        if (b[i].key() == 0  ||  b[i].key() == k) { 
              //用這個(gè)i從散列表取值，如果取出來的bucket_t的 key = k，則查詢成功，返回該bucket_t，
              //如果key = 0，說明在索引i的位置上還沒有緩存過方法，同樣需要返回該bucket_t，用于中止緩存查詢。
            return &b[i];
        }
    } while ((i = cache_next(i, m)) != begin);
// 這一步其實(shí)相當(dāng)于 i = i-1,回到上面do循環(huán)里面，相當(dāng)于查找散列表上一個(gè)單元格里面的元素，再次進(jìn)行key值 k的比較，
//當(dāng)i=0時(shí)，也就i指向散列表最首個(gè)元素索引的時(shí)候重新將mask賦值給i，使其指向散列表最后一個(gè)元素，重新開始反向遍歷散列表，
//其實(shí)就相當(dāng)于繞圈，把散列表頭尾連起來，不就是一個(gè)圈嘛，從begin值開始，遞減索引值，當(dāng)走過一圈之后，必然會(huì)重新回到begin值，
//如果此時(shí)還沒有找到key對(duì)應(yīng)的bucket_t，或者是空的bucket_t，則循環(huán)結(jié)束，說明查找失敗，調(diào)用bad_cache方法。

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

*********************************** cache_hash(k, m);
static inline mask_t cache_hash(cache_key_t key, mask_t mask) 
{
    return (mask_t)(key & mask);
}

*********************************** cache_next(i, m)
static inline mask_t cache_next(mask_t i, mask_t mask) {
   // return (i-1) & mask;  // 非arm64
    return i ? i-1 : mask; // arm64
}

在cache_fill_nolock方法最后我們看到調(diào)用了cache_t::find函數(shù)，

   // Scan for the first unused slot and insert there.
    // There is guaranteed to be an empty slot because the 
    // minimum size is 4 and we resized at 3/4 full.
    bucket_t *bucket = cache->find(key, receiver);
    if (bucket->key() == 0) cache->incrementOccupied();
    bucket->set(key, imp);

上面源碼的最后一段以及它的注釋說明可以明白，當(dāng)通過cache->find返回的bucket->key() == 0，就說明該位置上是空的，沒有緩存過方法，是一個(gè)unused slot(未使用的槽口)，因此可以進(jìn)行插入操作bucket->set(key, imp);，也就是將方法緩存到這個(gè)位置上。

結(jié)論：

開辟方法不僅僅是在老緩存池基礎(chǔ)上進(jìn)行擴(kuò)容，開辟新的buckets，釋放老的buckets，因?yàn)樘O果是通過哈希表進(jìn)行緩存，并且散列算法是index = @selector(XXXX) & mask，擴(kuò)容后mask發(fā)生了變化，所以里面緩存方法的index也都要發(fā)生變化，為了提高緩存效率，創(chuàng)建了新的buckets，老的buckets就會(huì)被釋放掉

初始化緩存池方法：

void cache_t::setBucketsAndMask(struct bucket_t *newBuckets, mask_t newMask)
{
    // objc_msgSend uses mask and buckets with no locks.
    // It is safe for objc_msgSend to see new buckets but old mask.
    // (It will get a cache miss but not overrun the buckets' bounds).
    // It is unsafe for objc_msgSend to see old buckets and new mask.
    // Therefore we write new buckets, wait a lot, then write new mask.
    // objc_msgSend reads mask first, then buckets.

    // ensure other threads see buckets contents before buckets pointer
    mega_barrier();

    _buckets = newBuckets;
    
    // ensure other threads see new buckets before new mask
    mega_barrier();
    
    _mask = newMask;
    _occupied = 0;
}

總結(jié)：

1、實(shí)例方法是緩存在類中，類方法是在元類中
2、方法緩存邏輯是:
（1）第一次創(chuàng)建緩存池時(shí)候，緩存池的大小是4，但是最大容量數(shù)為3，并且以后擴(kuò)容的緩存池的最大容量數(shù)都是緩存池大小減一
（2）在緩存方法時(shí)候會(huì)判斷緩存新方法后的緩沖池里的方法數(shù)是否大于緩沖池大小的4/3，如果大于則需要擴(kuò)容
（3）擴(kuò)容后的緩存池大小是原來緩存池大小的2倍，并且擴(kuò)容后會(huì)將老緩存池里面緩存的方法全部清理掉