在談及面向?qū)ο缶幊痰臅r候巴帮，總是離不開 對象 與 類 溯泣。對象 是對客觀事物的抽象，類 是對 對象 的抽象榕茧。它們的關(guān)系是垃沦，對象 是 類 的實例，類 是 對象 的模板用押。

Object-C 是基于 類 的對象系統(tǒng)肢簿。類 作為對象的模板創(chuàng)建了類，對象的信息存儲在 類 中蜻拨。那么 類 的結(jié)構(gòu)是什么樣子呢池充？

// 類的實例 （即對象）
struct objc_object {
    isa_t isa;
}

// 類
struct objc_class : objc_object {
    // Class ISA;
    Class superclass;
    cache_t cache;             // formerly cache pointer and vtable
    class_data_bits_t bits;    // class_rw_t * plus custom rr/alloc flags
}

從源碼可以看出，objc_class 是繼承自 objc_object 的缎讼，也就是說 類 也是一個對象收夸。這也是萬物皆對象的由來。因其繼承自 objc_object 血崭，自然默認就含有了 objc_object 的成員 isa卧惜。

我們將類的結(jié)構(gòu)用圖表示如下：

類的結(jié)構(gòu)

isa : 其中 isa 在 看透 isa 中已做了詳細的解釋，感興趣的讀者可以看這篇文章：看透 isa

superclass : superclass 的類型 依然是Class夹纫， 指向了類的父類咽瓷。

cache : cache 是方法緩存列表，存儲了最近調(diào)用的方法舰讹。

bits : bits 的類型為 class_data_bits_t 茅姜，存儲了類中更詳細的信息。

1月匣、class_data_bits_t 結(jié)構(gòu)分析

struct class_data_bits_t {
    friend objc_class;

    // Values are the FAST_ flags above.
    uintptr_t bits;

public:

    class_rw_t* data() const {
        return (class_rw_t *)(bits & FAST_DATA_MASK);
    }
    void setData(class_rw_t *newData)
    {
        ASSERT(!data()  ||  (newData->flags & (RW_REALIZING | RW_FUTURE)));
        // Set during realization or construction only. No locking needed.
        // Use a store-release fence because there may be concurrent
        // readers of data and data's contents.
        uintptr_t newBits = (bits & ~FAST_DATA_MASK) | (uintptr_t)newData;
        atomic_thread_fence(memory_order_release);
        bits = newBits;
    }
}

在64位架構(gòu)CPU下钻洒，bits 的第3到第46字節(jié)存儲 class_rw_t 奋姿。class_rw_t 中存儲 flags 、witness航唆、firstSubclass、nextSiblingClass 以及 class_rw_ext_t院刁。

struct class_rw_ext_t {
    const class_ro_t *ro;
    method_array_t methods;
    property_array_t properties;
    protocol_array_t protocols;
    char *demangledName;
    uint32_t version;
};

class_rw_ext_t 中存儲著 class_ro_t 和 methods(方法列表)糯钙、properties(屬性列表)、protocols(協(xié)議列表)等信息退腥。

而 class_ro_t 中也存儲了 baseMethodList(方法列表)任岸、baseProperties(屬性列表)、baseProtocols(協(xié)議列表) 以及 實例變量狡刘、類的名稱享潜、大小 等等信息。

struct class_ro_t {
    uint32_t flags;
    uint32_t instanceStart;
    uint32_t instanceSize;
#ifdef __LP64__
    uint32_t reserved;
#endif

    const uint8_t * ivarLayout;
    
    const char * name;
    method_list_t * baseMethodList;
    protocol_list_t * baseProtocols;
    const ivar_list_t * ivars;

    const uint8_t * weakIvarLayout;
    property_list_t *baseProperties;
};

蘋果的工程師為什么要這樣設(shè)計一個類的結(jié)構(gòu)呢嗅蔬？

我們需要從類的編譯期開始了解：

當類被編譯的時候剑按，二進制類在磁盤中的表示如下：

首先是類對象本身，包含最常訪問的信息：指向元類（isa）澜术，超類（superclass）和方法緩存（cache）的指針艺蝴，它還具有指向包含更多數(shù)據(jù)的結(jié)構(gòu)體 class_ro_t 的指針，包含了類的名稱鸟废，方法猜敢，協(xié)議，實例變量等等 編譯期確定 的信息盒延。其中 ro 表示 read only 的意思缩擂。

當類第一次從磁盤加載到內(nèi)存時，它們總是以這樣的形式開始布局的添寺，但是一旦使用它們胯盯，就會發(fā)生改變：

當類被 Runtime 加載之后，類的結(jié)構(gòu)會發(fā)生一些變化计露，在了解這些變化之前陨闹，我們需要知道2個概念：

Clean Memory：加載后不會發(fā)生更改的內(nèi)存塊，class_ro_t 屬于 Clean Memory薄坏，因為它是只讀的趋厉。
Dirty Memory：運行時會發(fā)生更改的內(nèi)存塊，類結(jié)構(gòu)一旦被加載胶坠，就會變成 Dirty Memory君账，因為運行時會向它寫入新的數(shù)據(jù)。例如沈善，我們可以通過 Runtime 給類動態(tài)的添加方法乡数。

這里要明確椭蹄，Dirty Memory 比 Clean Memory 要昂貴得多。因為它需要更多的內(nèi)存信息净赴，并且只要進程正在運行绳矩，就必須保留它。另一方面玖翅， Clean Memory 可以進行移除翼馆，從而節(jié)省更多的內(nèi)存空間，因為如果你需要 Clean Memory 金度，系統(tǒng)可以從磁盤中重新加載应媚。

Dirty Memory 是這個類數(shù)據(jù) 被分成兩部分的原因。

對于我們來說猜极，越多的 Clean Memory 顯然是更好的中姜，因為它可以 節(jié)約更多的內(nèi)存。我們可以通過分離出永不更改的數(shù)據(jù)部分跟伏，將大多數(shù)類數(shù)據(jù)保留為 Clean Memory丢胚，應(yīng)該怎么做呢？

在介紹優(yōu)化方法之前受扳，我們先來看一下嗜桌，在類加載之后，類的結(jié)構(gòu)會變成如何呢辞色？

在類首次被使用的時候骨宠，runtime會為它分配額外的存儲容量，用于 讀取/寫入 數(shù)據(jù)的一個結(jié)構(gòu)體 class_rw_t相满。

在這個結(jié)構(gòu)體中层亿，存儲了只有在運行時才會生成的新信息。例如：所有的類都會鏈接成一個樹狀結(jié)構(gòu)立美，這是通過 firstSubclass 和 nextSiblingClass指針實現(xiàn)的匿又，這允許runtime遍歷當前使用的所有的類。但是為什么在這里還要有方法列表和屬性列表等信息呢建蹄？ 因為他們在運行時是可以更改的碌更。當 category 被加載的時候，它可以向類中添加新的方法洞慎。而且程序員也可以通過runtime API 動態(tài)的添加痛单。

class_ro_t 是只讀的，存放的是 編譯期間就確定 的字段信息劲腿；而class_rw_t 是在 runtime 時才創(chuàng)建的旭绒，它會先將 class_ro_t 的內(nèi)容拷貝一份，再將類的分類的屬性、方法挥吵、協(xié)議等信息添加進去重父，之所以要這么設(shè)計是因為 Objective-C 是動態(tài)語言，你可以在運行時更改它們方法忽匈，屬性等房午，并且分類可以在不改變類設(shè)計的前提下，將新方法添加到類中丹允。

因為 class_ro_t 是只讀的郭厌，所以我們需要在 class_rw_t 中追蹤這些東西。而這樣做嫌松，顯然是會占用相當多的內(nèi)存的沪曙。

事實證明奕污，class_rw_t 會占用比 class_ro_t 占用更多的內(nèi)存萎羔，在Apple的測試中，iPhone在系統(tǒng)中大約有 30MB 的 class_rw_t 結(jié)構(gòu)碳默。應(yīng)該如何優(yōu)化這些內(nèi)存呢贾陷？

通過測量實際設(shè)備上的使用情況，大約只有 10％ 的類實際會存在動態(tài)的更改行為（如動態(tài)添加方法嘱根，使用 Category 方法等）髓废。因此，蘋果的工程師 把這些動態(tài)的部分提取了出來單獨放在一個區(qū)域该抒，我們稱之為 class_rw_ext_t慌洪，這樣的設(shè)計使得 class_rw_t 的大小減少了一半， 所以凑保，結(jié)構(gòu)會變成這個樣子冈爹。

大約90%的類從來不需要這些擴展數(shù)據(jù)，經(jīng)過拆分欧引，可以把 90% 的類優(yōu)化為 Clean Memory频伤，在系統(tǒng)層面，蘋果測試了取得的效果是芝此，大約節(jié)省了 14MB 的內(nèi)存憋肖，使內(nèi)存可用于更有效的用途。

2. catch_t 分析

實例方法存儲在 類 中婚苹，類方法存儲在 元類 中岸更。在方法的查找流程中，我們可以根據(jù) isa 與 superclass 的指向一步步查找 響應(yīng)消息膊升。

cache_t 中存儲的是方法的緩存列表坐慰，之所以設(shè)計 方法緩存列表 存儲在類的結(jié)構(gòu)中，是為了更快的響應(yīng)消息的發(fā)送。因為在緩存中查找要比一步步通過 isa 和 superclass 查找要快得多结胀。

2.1 cache_t 結(jié)構(gòu)

?我們先看一下 cache_t 的結(jié)構(gòu)

#define CACHE_MASK_STORAGE_OUTLINED 1
#define CACHE_MASK_STORAGE_HIGH_16 2
#define CACHE_MASK_STORAGE_LOW_4 3
?
#if defined(__arm64__) && __LP64__
#define CACHE_MASK_STORAGE CACHE_MASK_STORAGE_HIGH_16
#elif defined(__arm64__) && !__LP64__
#define CACHE_MASK_STORAGE CACHE_MASK_STORAGE_LOW_4
#else
#define CACHE_MASK_STORAGE CACHE_MASK_STORAGE_OUTLINED
#endif
?
struct cache_t {
#if CACHE_MASK_STORAGE == CACHE_MASK_STORAGE_OUTLINED
    explicit_atomic<struct bucket_t *> _buckets; 
    explicit_atomic<mask_t> _mask;   
#elif CACHE_MASK_STORAGE == CACHE_MASK_STORAGE_HIGH_16
    explicit_atomic<uintptr_t> _maskAndBuckets;
    mask_t _mask_unused;
#elif CACHE_MASK_STORAGE == CACHE_MASK_STORAGE_LOW_4
    explicit_atomic<uintptr_t> _maskAndBuckets;
    mask_t _mask_unused;
#else
#error Unknown cache mask storage type.
#endif
    
#if __LP64__
    uint16_t _flags;
#endif
    uint16_t _occupied;  
?

explicit_atomic 是將普通指針轉(zhuǎn)換為原子指針的操作赞咙，為了線程安全。所以這里我們關(guān)注 _buckets 的類型 struct bucket_t

struct bucket_t {
private:
#if __arm64__
    explicit_atomic<uintptr_t> _imp;
    explicit_atomic<SEL> _sel;
#else
    explicit_atomic<SEL> _sel;
    explicit_atomic<uintptr_t> _imp;
#endif
?
    template <Atomicity, IMPEncoding>
    // 賦值 sel作為key imp作為value
    void set(SEL newSel, IMP newImp, Class cls);
};

盡管不同CPU架構(gòu)下的名稱以及存儲方式不同糟港，但作用都是一樣的攀操，我們可以將 cache_t 的結(jié)構(gòu)簡單理解如下的表現(xiàn)形式：
?[圖片上傳失敗...(image-abd7a5-1600351301148)]
其中：

• _buckets ：是一個散列表，用來存儲 緩存方法的 sel 和 imp秸抚。
• _mask ： 有2個作用速和，① 作為當前可存儲的最大容量；② 作為掩碼剥汤，取已緩存方法在 _buckets 中的下標颠放。（后面會講到）
• _occupied _buckets 中 已緩存的方法數(shù)量。
  ?
  cache_t 的基本工作結(jié)構(gòu)就是如上所示的吭敢，那么它具體是如何工作的呢碰凶？ 它是如何存儲的？ 存儲的最大容量是多少鹿驼？ 超出容量又如何處理呢?
  ?
  我們先做個小測試欲低，實際看一下 cache_t 中存儲的內(nèi)容。準備 Person 類 繼承自 NSObject 畜晰， 創(chuàng)建若干方法砾莱。
  ?

    Person *p = [[Person alloc] init];
?
    [p instanceMethod1];
    [p instanceMethod2];
    [p instanceMethod3];
    [p instanceMethod4];
    [p instanceMethod5];
    [p instanceMethod6];
    [p instanceMethod7];
    [p instanceMethod8];

在instanceMethod1之前打斷點，通過lldb調(diào)試工具凄鼻，查看p的類的內(nèi)存結(jié)構(gòu)

(lldb) x/4gx p.class
0x100002488: 0x0000000100002460 0x0000000100334140
0x100002498: 0x0000000100680ff0 0x0005801000000007

前面類的結(jié)構(gòu)中腊瑟，我們已知類的內(nèi)存布局，是以 isa块蚌、superclass闰非、cache_t、class_data_bits_t 順序排布的匈子，其中 isa 與 superclass 分別占用8個字節(jié)河胎，所以 cache_t 的位置應(yīng)該是從類的首地址偏移16字節(jié)的位置，所以我們?nèi)?0x100002488 偏移 16字節(jié)虎敦，即 0x100002498 的地址游岳。這里注意類型的轉(zhuǎn)換。
?

(lldb) p (cache_t *)0x100002498
(cache_t *) $1 = 0x0000000100002498

取 cache_t 的值

(lldb) p (cache_t *)0x100002498
(cache_t *) $1 = 0x0000000100002498
(lldb) p *$1
(cache_t) $2 = {
  _buckets = {
    std::__1::atomic<bucket_t *> = 0x0000000100680ff0 {
      _sel = {
        std::__1::atomic<objc_selector *> = 0x00007fff75c3186
      }
      _imp = {
        std::__1::atomic<unsigned long> = 4047440
      }
    }
  }
  _mask = {
    std::__1::atomic<unsigned int> = 3
  }
  _flags = 32784
  _occupied = 1
}

?
其中 _buckets 中存儲 sel 的地址 和 編碼后的 imp其徙；_mask 為3胚迫，_occupied 為1（雖然 自定義的實例方法還沒有調(diào)用，但是 init方法已執(zhí)行唾那，所以此處為1）访锻，我們繼續(xù)增加調(diào)用方法的數(shù)量，觀察_mask 與_occupied 的取值，記錄如下期犬。
?
?

?
?
我們發(fā)現(xiàn)河哑，_mask 的值隨著方法的調(diào)用數(shù)量在增加，但是 _occupied 的值似乎增加到一定程度后會回到1的值龟虎，帶著這樣的疑問璃谨，我們看看 cache_t 是如何存儲的。
?

2.2 如何存鲤妥？

?
一旦消息得以成功發(fā)送(msgSend( ))佳吞，就會調(diào)用 cache_fill 開始加入緩存的流程
?

void cache_fill(Class cls, SEL sel, IMP imp, id receiver)
{
    runtimeLock.assertLocked();
?
#if !DEBUG_TASK_THREADS
    // Never cache before +initialize is done
    if (cls->isInitialized()) {
        cache_t *cache = getCache(cls);
#if CONFIG_USE_CACHE_LOCK
        mutex_locker_t lock(cacheUpdateLock);
#endif
        cache->insert(cls, sel, imp, receiver);
    }
#else
    _collecting_in_critical();
#endif
}

?
如果類已初始化完畢，就會進入 cache->insert 插入緩存
?

// 插入緩存信息
ALWAYS_INLINE
void cache_t::insert(Class cls, SEL sel, IMP imp, id receiver)
{
#if CONFIG_USE_CACHE_LOCK
    cacheUpdateLock.assertLocked();
#else
    runtimeLock.assertLocked();
#endif
?
    ASSERT(sel != 0 && cls->isInitialized());
    /** 
      1注： 下面這一部分為初始化的過程棉安，如果 occupied()為0,  并且buckets中無緩存內(nèi)容 底扳，
      則開辟 4 個存儲空間大小 為默認初始值。
   */
    mask_t newOccupied = occupied() + 1; // 即將要占用的數(shù) = 已占用數(shù)+ 1
    unsigned oldCapacity = capacity(), capacity = oldCapacity; // 獲取目前已占用數(shù)
    if (slowpath(isConstantEmptyCache())) {   // 如果緩存是空的
        if (!capacity) capacity = INIT_CACHE_SIZE;// 如果capacity 為0 初始化為4 
        reallocate(oldCapacity, capacity, /* freeOld */false); // 根據(jù)當前內(nèi)容分配空間
    }
?
    /** 
      2注： 以下為判斷空間是否足夠過程
      如果空間不足,  擴容到原空間大小的2倍值贡耽，并重新分配空間大小
      并釋放已存儲的緩存衷模，插入新緩存
   */
    //  arm64下 如果 newOccupied <= 容量的4分之3，存儲空間還足夠菇爪，不需額外處理
    else if (fastpath(newOccupied + CACHE_END_MARKER <= capacity / 4 * 3)) {
        // Cache is less than 3/4 full. Use it as-is.
    }
    // 如果超過 4分之3  
    else {
        // 擴容為原空間的 2倍大小  
        capacity = capacity ? capacity * 2 : INIT_CACHE_SIZE;
        if (capacity > MAX_CACHE_SIZE) { 
            capacity = MAX_CACHE_SIZE;  //  最大不能 超出 1<< 16
        }
        reallocate(oldCapacity, capacity, true); // 重新分配空間   存儲新的數(shù)據(jù)算芯，抹除已有緩存
    }
 
    /** 
      3注： 以下為插入緩存的過程
      遍歷 buckets()內(nèi)容柒昏，如果在緩存中找到了 傳入的方法凳宙，直接退出
      如果在緩存中沒有找到 傳入的方法 將_occupied ++;，并且將方法存入緩存
      如果遇到hash沖突职祷， cache_t查找下一個 直到回到begin 全部查找結(jié)束
    */
?
    // 獲取散列表
    bucket_t *b = buckets();
    // 獲取散列表大小 - 1
    mask_t m = capacity - 1;
    // 通過cache_hash函數(shù)【begin  = sel & m】計算出key值 k 對應(yīng)的 index值
    // begin氏涩，用來記錄查詢起始索引
    mask_t begin = cache_hash(sel, m);
    // begin 賦值給 i，用于切換索引
    mask_t i = begin;
?
    do {
        if (fastpath(b[i].sel() == 0)) {  // 如果沒有找到緩存的方法
            incrementOccupied(); //   _occupied ++;
            b[i].set<Atomic, Encoded>(sel, imp, cls); // 緩存實例方法
            return;
        }
        if (b[i].sel() == sel) {  // 如果找到需要緩存的方法有梆，什么都不做是尖，并退出循環(huán)
      
            return;
        }
    } while (fastpath((i = cache_next(i, m)) != begin));
// 當出現(xiàn)hash碰撞 cache_t查找下一個 直到回到begin 全部查找結(jié)束
?
    cache_t::bad_cache(receiver, (SEL)sel, cls);
}

cache->insert 函數(shù)大致做了 3件事

• 1. 初始化緩存空間

• 2. 判斷是否需要擴容，如果需要泥耀，以原始空間的2倍擴容饺汹，重新分配空間，釋放已有緩存信息

• 3. 根據(jù)散列表中是否已有該方法的緩存情況插入緩存

更為詳細的內(nèi)容為：

• 1. 初始化緩存空間

如果緩存空間還沒有初始化痰催，我們要對緩存空間進行初始化操作兜辞，默認開辟4個 bucket_t 大小的存儲空間 ( 4 來自于if (!capacity) capacity = INIT_CACHE_SIZE)

    INIT_CACHE_SIZE_LOG2 = 2,
    INIT_CACHE_SIZE      = (1 << INIT_CACHE_SIZE_LOG2),
    // 1 << 2  = 4

得到初始化所需空間大小的值后，然后調(diào)用 reallocate(oldCapacity, capacity, /* freeOld */false); 這里的freeOld 傳入的是 false夸溶，因為是剛初始化的空間逸吵，不存在已有的緩存，不需要清理缝裁。

ALWAYS_INLINE
void cache_t::reallocate(mask_t oldCapacity, mask_t newCapacity, bool freeOld)
{
    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);
    }
}

bucket_t *allocateBuckets(mask_t newCapacity)
{
    bucket_t *newBuckets = (bucket_t *)
        calloc(cache_t::bytesForCapacity(newCapacity), 1);

    bucket_t *end = cache_t::endMarker(newBuckets, newCapacity);

#if __arm__
    end->set<NotAtomic, Raw>((SEL)(uintptr_t)1, (IMP)(newBuckets - 1), nil);
#else
    end->set<NotAtomic, Raw>((SEL)(uintptr_t)1, (IMP)newBuckets, nil);
#endif
    
    if (PrintCaches) recordNewCache(newCapacity);

    return newBuckets;
}

reallocate函數(shù)中 通過 allocateBuckets函數(shù)的 calloc 向系統(tǒng)申請 newCapacity 大小的空間扫皱；
并且通過 setBucketsAndMask 設(shè)置 buckets 和 mask，其中 mask 更新為 新申請的總空間大小 - 1 （capacity - 1）；

初始化時的默認空間大小為 4（capacity） 韩脑，且如需擴容的時候 進行2倍 (capacity) 擴容氢妈，所以新空間大小一直為 4 的整數(shù)倍，如 4段多，8允懂，16，32...衩匣，那么 mask 的大小(capacity -1)的取值為 3蕾总，7，15琅捏，31...生百。

• 2. 判斷是否需要擴容，如需擴容柄延，按原容量2倍擴容蚀浆， 重新分配空間，釋放已有緩存信息 _occupied = 0

初始空間開辟完畢之后搜吧，在進行方法緩存的時候市俊，還需要判斷空間是否夠用，這很好理解滤奈，因為初始化時默認的空間大小為4摆昧。擴容是依據(jù)當前 空間大小（capacity） 以及 已占用數(shù)（occupied） 的情況進行擴容蜒程。

擴容的條件為：當前已占用的存儲數(shù)（occupied）是否超過當前開辟容量（capacity）的4分之3绅你。如果大于，則重新開辟為原容量（capacity）的2倍昭躺，進行擴容忌锯。且最大容量不能超過 MAX_CACHE_SIZE = 1<<16。

 capacity = capacity ? capacity * 2 : INIT_CACHE_SIZE;
 if (capacity > MAX_CACHE_SIZE) { 
       capacity = MAX_CACHE_SIZE;  //  最大不能 超出 1<< 16
 }

擴容的空間計算完畢之后领炫，依然要重新調(diào)用 reallocate 函數(shù)重新分配存儲空間偶垮，只不過這一次
調(diào)用 reallocate(oldCapacity, capacity, /* freeOld */true); 這里的 freeOld 傳入的是 true。釋放已有的方法緩存帝洪。將已存儲的緩存依次置空似舵。

• 3. 插入緩存

所需空間已全部準備完畢，接下來就是存儲當前傳入的方法了碟狞。

    // 獲取散列表
    bucket_t *b = buckets();
    // 獲取散列表總長度 - 1 該值= mask的值
    mask_t m = capacity - 1;
   
    mask_t begin = cache_hash(sel, m);
   
    mask_t i = begin;

    do {
        if (fastpath(b[i].sel() == 0)) {  // 如果沒有找到緩存的方法
            incrementOccupied(); //  _occupied ++;
            b[i].set<Atomic, Encoded>(sel, imp, cls); // 緩存實例方法
            return;
        }
        if (b[i].sel() == sel) {  // 如果找到需要緩存的方法啄枕，什么都不做，并退出循環(huán)
            // The entry was added to the cache by some other thread
            // before we grabbed the cacheUpdateLock.
            return;
        }
    } while (fastpath((i = cache_next(i, m)) != begin));

這一步是在散列表的遍歷中進行的：

begin 作為 散列表 的初始查詢下標族沃，是經(jīng)過 sel & mask 計算而來的

static inline mask_t cache_hash(SEL sel, mask_t mask) 
{
    // 取 & 計算索引
    return (mask_t)(uintptr_t)sel & mask;
}

mask 值 始終為 capacity - 1频祝，之前我們提到他可能的值為3泌参，7，15常空，31...沽一，用二進制表示為 00000001，00000011漓糙，00000111铣缠，00001111，所以取任意值 & mask 必定小于等于mask昆禽，這一步 sel & mask 的操作確保了 begin 的值不會超過總?cè)萘?1蝗蛙，以確保遍歷的時候下標不會超出 capacity ，出現(xiàn)越界的情況醉鳖。
?
do ... while 循環(huán)的條件是 (i = cache_next(i, m) != begin 捡硅，判斷不等于初始下標值 begin 是為了將散列表中的數(shù)據(jù)全部遍歷結(jié)束，而cache_next( ) 是為了解決哈希沖突而進行的二次哈希盗棵。
?

static inline mask_t cache_next(mask_t i, mask_t mask) {
    return (i+1) & mask;
}

?
接著 根據(jù)下標值 遍歷查找 buckets( ) 壮韭，如果找到sel，說明方法已經(jīng)緩存纹因，直接return喷屋，退出遍歷。
?
如果直至遍歷結(jié)束依然沒有在緩存中找到該方法瞭恰，則將該方法存入 _bucket 屯曹，并更新已占用存儲數(shù)（occupied++）。
?
整個過程如下所示：
?

?
小結(jié)：方法的緩存是以散列表的形式進行存儲的寄疏，所以它是無序的是牢，當 當前緩存數(shù)量 超過 散列表 總存儲空間的四分之三時僵井，散列表的存儲空間以2倍的原始大小進行擴容陕截，并抹除已有緩存。存儲緩存時批什，是通過遍歷當前散列表的所有已存儲方法农曲，如果散列表中已有緩存，則不存儲并結(jié)束遍歷驻债，如果遍歷完畢依然沒有找到該方法乳规，則將該方法存入散列表垫竞。
?

Tip:
為什么在緩存容量達到總?cè)萘康?/4時進行擴容闪幽？

這是一個選擇的適當值，因為在哈希表這種數(shù)據(jù)結(jié)構(gòu)里面感挥，其性能受裝載因子影響淌实，裝載因子可以用來表示空位率的大小冻辩，其公式為：裝載因子 = 已填入的容量 / 散列表的總?cè)萘俊?/code>

裝載因子越大猖腕，說明空閑的位置越少，沖突的可能性越多恨闪，散列表的性能會下降倘感。盡可能小的裝載因子可以提高散列表的性能，同時太小的值又容易觸發(fā)擴容條件咙咽，所以這里蘋果設(shè)計了這樣一個的適當?shù)闹怠?br> ?
?

STATIC_ENTRY _cache_getImp

    GetClassFromIsa_p16 p0
    CacheLookup GETIMP, _cache_getImp

LGetImpMiss:
    mov p0, #0
    ret

    END_ENTRY _cache_getImp

.macro CacheLookup
    
LLookupStart$1:

    // p1 = SEL, p16 = isa
    ldr p11, [x16, #CACHE]              // p11 = mask|buckets

#if CACHE_MASK_STORAGE == CACHE_MASK_STORAGE_HIGH_16
    and p10, p11, #0x0000ffffffffffff   // p10 = buckets
    and p12, p1, p11, LSR #48       // x12 = _cmd & mask
#elif CACHE_MASK_STORAGE == CACHE_MASK_STORAGE_LOW_4
    and p10, p11, #~0xf         // p10 = buckets
    and p11, p11, #0xf          // p11 = maskShift
    mov p12, #0xffff
    lsr p11, p12, p11               // p11 = mask = 0xffff >> p11
    and p12, p1, p11                // x12 = _cmd & mask
#else
#error Unsupported cache mask storage for ARM64.
#endif


    add p12, p10, p12, LSL #(1+PTRSHIFT)
                     // p12 = buckets + ((_cmd & mask) << (1+PTRSHIFT))

    ldp p17, p9, [x12]      // {imp, sel} = *bucket
1:  cmp p9, p1          // if (bucket->sel != _cmd)
    b.ne    2f          //     scan more
    CacheHit $0         // call or return imp
    
2:  // not hit: p12 = not-hit bucket
    CheckMiss $0            // miss if bucket->sel == 0
    cmp p12, p10        // wrap if bucket == buckets
    b.eq    3f
    ldp p17, p9, [x12, #-BUCKET_SIZE]!  // {imp, sel} = *--bucket
    b   1b          // loop

3:  // wrap: p12 = first bucket, w11 = mask
#if CACHE_MASK_STORAGE == CACHE_MASK_STORAGE_HIGH_16
    add p12, p12, p11, LSR #(48 - (1+PTRSHIFT))
                    // p12 = buckets + (mask << 1+PTRSHIFT)
#elif CACHE_MASK_STORAGE == CACHE_MASK_STORAGE_LOW_4
    add p12, p12, p11, LSL #(1+PTRSHIFT)
                    // p12 = buckets + (mask << 1+PTRSHIFT)
#else
#error Unsupported cache mask storage for ARM64.
#endif

    // Clone scanning loop to miss instead of hang when cache is corrupt.
    // The slow path may detect any corruption and halt later.

    ldp p17, p9, [x12]      // {imp, sel} = *bucket
1:  cmp p9, p1          // if (bucket->sel != _cmd)
    b.ne    2f          //     scan more
    CacheHit $0         // call or return imp
    
2:  // not hit: p12 = not-hit bucket
    CheckMiss $0            // miss if bucket->sel == 0
    cmp p12, p10        // wrap if bucket == buckets
    b.eq    3f
    ldp p17, p9, [x12, #-BUCKET_SIZE]!  // {imp, sel} = *--bucket
    b   1b          // loop

LLookupEnd$1:
LLookupRecover$1:
3:  // double wrap
    JumpMiss $0

.endmacro