慢速查找前提

obj_msgsend消息發(fā)送在完成匯編緩存快速查找流程后，如果沒有找到，說明緩存沒有，那么就需要進(jìn)入到C/C++層進(jìn)入慢速查找lookUpImpOrForward流程。

消息查找過程與isa走位聯(lián)系

消息在查找過程中如果在自己類中沒有找到，那么就會去父類找，如果父類還是沒有找到就會找到其根源類，如同isa的走位圖一般。
我們可以通過下面案例演示，首先我們新建一個(gè)繼承自NSObject 的類SYPerson，再建一個(gè)繼承自SYPerson類的SYMan類，然后再建一個(gè)NSObject分類，如圖

類名

我們在SYMan中聲明兩個(gè)方法,同時(shí)在SYPerson和NSObject+SY中添加同樣的方法

- (void)sayHello;
+ (void)say666;

//實(shí)現(xiàn)

- (void)sayHello{
    NSLog(@"%s",__func__);
}

+ (void)say666{
    NSLog(@"%s",__func__);
}

//調(diào)用
SYMan *man = [SYMan alloc];

[man sayHello];

[SYMan say666];

• 首先，我們在SYMan中實(shí)現(xiàn)兩個(gè)方法，然后調(diào)用打印，毫無疑問直接打印如下

2020-09-22 21:22:41.968785+0800 KCObjc[28236:428912] -[SYMan sayHello]
2020-09-22 21:22:41.969886+0800 KCObjc[28236:428912] +[SYMan say666]

• 現(xiàn)在，我們將SYMan中方法的實(shí)現(xiàn)注釋，在其父類SYPerson中實(shí)現(xiàn)這兩個(gè)方法，那么我們執(zhí)行會打印什么呢？會不會崩潰呢？結(jié)果如下:

2020-09-22 21:25:35.352163+0800 KCObjc[28366:431785] -[SYPerson sayHello]
2020-09-22 21:25:35.352965+0800 KCObjc[28366:431785] +[SYPerson say666]

• 從上訴打印我們發(fā)現(xiàn)，在SYMan類中雖然沒有實(shí)現(xiàn)方法，但是我們在調(diào)用的時(shí)候并沒有崩潰，而是執(zhí)行了其父類SYPerson的方法實(shí)現(xiàn)，說明方法在自身沒有實(shí)現(xiàn)的時(shí)候如果其父類實(shí)現(xiàn)了，會找到父類進(jìn)行執(zhí)行。
• 最后我們將SYPerson的方法實(shí)現(xiàn)也注釋掉，，而是由分類NSObject+SY實(shí)現(xiàn)，那么會怎么樣了？我們執(zhí)行打印如下：

2020-09-22 21:29:27.085123+0800 KCObjc[28493:433778] -[NSObject(SY) sayHello]
2020-09-22 21:29:27.085790+0800 KCObjc[28493:433778] +[NSObject(SY) say666]

• 結(jié)果顯示雖然自身和父類都沒對方法進(jìn)行實(shí)現(xiàn)，但是其根源類NSObject中卻實(shí)現(xiàn)了調(diào)用的時(shí)候直接走了分類中的方法實(shí)現(xiàn)。

以上我們的主要目的就是為了驗(yàn)證方法消息在查找過程中會存在一個(gè)繼承鏈的關(guān)系，這在慢速查找
lookUpImpOrForward中是適用的。

通過源碼分析消息慢速查找

首先還是找到lookUpImpOrForward的實(shí)現(xiàn)源碼進(jìn)行分析

//傳入sel方法名，cls調(diào)用類名
IMP lookUpImpOrForward(id inst, SEL sel, Class cls, int behavior)
{
    
    const IMP forward_imp = (IMP)_objc_msgForward_impcache;
    IMP imp = nil;
    Class curClass;

    runtimeLock.assertUnlocked();

    // 再次判斷緩存中是否存在，之所以這里要再次判斷是因?yàn)榭赡芤驗(yàn)槎嗑€程等原因，之前緩存沒找到，但是后面緩存中又存在了，那么就直接通過緩存快速查找了，不需要進(jìn)入慢速查找。
    if (fastpath(behavior & LOOKUP_CACHE)) {
        imp = cache_getImp(cls, sel);
        if (imp) goto done_nolock;
    }


    runtimeLock.lock();
    //判斷當(dāng)前類是否已經(jīng)認(rèn)可，是已知類
    checkIsKnownClass(cls);

    if (slowpath(!cls->isRealized())) {
    // 遞歸找到類繼承鏈,做好去父類查找準(zhǔn)備
        cls = realizeClassMaybeSwiftAndLeaveLocked(cls, runtimeLock);
        
    }

    if (slowpath((behavior & LOOKUP_INITIALIZE) && !cls->isInitialized())) {        
    //遞歸初始所有類initialize
        cls = initializeAndLeaveLocked(cls, inst, runtimeLock);
    }

    runtimeLock.assertLocked();
    curClass = cls;
    //這是一個(gè)死循環(huán)，只有找到了就break
    for (unsigned attempts = unreasonableClassCount();;) {
        // 查找當(dāng)前類自己是否能找到方法，如果找到就不用去父類找了
        Method meth = getMethodNoSuper_nolock(curClass, sel);
        if (meth) {
            imp = meth->imp;
            goto done;
        }
        //這里將curClass賦值為其父類
        if (slowpath((curClass = curClass->superclass) == nil)) {
            imp = forward_imp;
            break;
        }

        // Halt if there is a cycle in the superclass chain.
        if (slowpath(--attempts == 0)) {
            _objc_fatal("Memory corruption in class list.");
        }

        // Superclass cache.
        //從父類去查找緩存  遞歸去父類緩存查找，父類沒找到就接著找父類的父類緩存      
        imp = cache_getImp(curClass, sel);// 這里實(shí)現(xiàn)了真正的lookUpImpOrForward遞歸
     
        if (slowpath(imp == forward_imp)) {
    
            break;
        }
        if (fastpath(imp)) {
            // Found the method in a superclass. Cache it in this class.
            goto done;
        }
    }
    //如果上訴都沒找到方法，那么進(jìn)入動(dòng)態(tài)方法決議
    if (slowpath(behavior & LOOKUP_RESOLVER)) {
        behavior ^= LOOKUP_RESOLVER;
        return resolveMethod_locked(inst, sel, cls, behavior);
    }

    
 done:
//找到了之后就加入到緩存，方便下次進(jìn)行快速查找
    log_and_fill_cache(cls, imp, sel, inst, curClass);
    runtimeLock.unlock();
 done_nolock:
// 不管什么方式都沒有找到，那么只有返回nil
    if (slowpath((behavior & LOOKUP_NIL) && imp == forward_imp)) {
        return nil;
    }
//返回查找到的imp
    return imp;
}

二分法查找方法

二分查找過程：
首先，假設(shè)表中元素是按升序排列，將表中間位置記錄的關(guān)鍵字與查找關(guān)鍵字比較，如果兩者相等，則查找成功；否則利用中間位置記錄將表分成前、后兩個(gè)子表，如果中間位置記錄的關(guān)鍵字大于查找關(guān)鍵字，則進(jìn)一步查找前一子表，否則進(jìn)一步查找后一子表。重復(fù)以上過程，直到找到滿足條件的記錄，使查找成功，或直到子表不存在為止，此時(shí)查找不成功。

在系統(tǒng)底層是通過二分法查找方法名對應(yīng)的IMP，在類初始化的時(shí)候method_list是以遞增方式存在， 二分法查找源碼如下：

findMethodInSortedMethodList(SEL key, const method_list_t *list)
{
    ASSERT(list);

    const method_t * const first = &list->first;
    const method_t *base = first;
    const method_t *probe;
    uintptr_t keyValue = (uintptr_t)key;
    uint32_t count;
    
    for (count = list->count; count != 0; count >>= 1) {
        //通過右移1位，找到中間位置
        probe = base + (count >> 1);
        
        uintptr_t probeValue = (uintptr_t)probe->name;
        
        if (keyValue == probeValue) {
            // `probe` is a match.
            // Rewind looking for the *first* occurrence of this value.
            // This is required for correct category overrides.
            // 判斷是否有重名方法，如分類中存在同名方法
            while (probe > first && keyValue == (uintptr_t)probe[-1].name) {
                probe--;
            }
            return (method_t *)probe;
        }
        
        if (keyValue > probeValue) {
            base = probe + 1;
            count--;
        }
    }
    
    return nil;
}