一被芳、前言，
在iOS消息機(jī)制過(guò)程中存在兩種查找imp 的方式樱拴，另外一種就是慢速查找柠衍，我們都知道快速就是走匯編流程，因?yàn)閰R編本身就計(jì)算機(jī)能識(shí)別的語(yǔ)言晶乔。所以并且上一篇文章已經(jīng)著重介紹了快速查找流程珍坊，本文我們著重介紹一下慢速查找流程。
我們?cè)陧?xiàng)目中創(chuàng)建一個(gè)類LGPerson 繼承自NSObject然后創(chuàng)建改類對(duì)象的示例方法正罢；
@interface LGPerson : NSObject
@property (nonatomic, copy) NSString *lgName;
@property (nonatomic, strong) NSString *nickName;
- (void)sayNB;
- (void)sayMaster;
- (void)say666;
- (void)sayHello;
@end
在main.m 文件中生成相應(yīng)的對(duì)象實(shí)現(xiàn)
LGPerson *person = [LGPerson alloc];
[person say666];
我們用斷點(diǎn)調(diào)試相關(guān)的say666 方法阵漏，然后進(jìn)入相應(yīng)的方法查找流程；
二，慢速查找
1履怯，斷定定位
首先我們跟著斷點(diǎn)調(diào)試進(jìn)入編譯流程川无，進(jìn)入XCode的 Debug > 下的 Debug WorkFlow 下的 Always show Disamessbly 界面如下
在此信息中我們能看你的的是我們創(chuàng)建的當(dāng)前對(duì)象 LGPerson 以及我們調(diào)用的方法 say666,我們?cè)俅?control + step into 進(jìn)入
此時(shí)我們能看到相應(yīng)的調(diào)試信息已經(jīng)跳轉(zhuǎn)的相應(yīng)位置是_objc_msgSend_uncached,我們順著再次進(jìn)入調(diào)試信息到：
通過(guò)調(diào)試方法我們最終定位到，慢速查找流程最終執(zhí)行的是lookUpImpOrForward 在objc-runtime-new.mm:的 弟 6099行虑乖；
當(dāng)然我們用快速查找流程的 CheckMiss 也可以進(jìn)入同樣的位置信息。定義如下晾虑；
.macro CheckMiss
// miss if bucket->sel == 0
.if $0 == GETIMP
cbz p9, LGetImpMiss
.elseif $0 == NORMAL
cbz p9, __objc_msgSend_uncached
.elseif $0 == LOOKUP
cbz p9, __objc_msgLookup_uncached
.else
.abort oops
.endif
.endmacro
我們使用的是NORMAL,所以執(zhí)行的是 __objc_msgSend_uncached 和上邊的查找流程一模一樣疹味；
2，源碼分析
順著代碼我們定位到相應(yīng)的方法里帜篇；
lookUpImpOrForward(nil, sel, cls, LOOKUP_RESOLVER);
進(jìn)入后代碼的實(shí)現(xiàn)如下：
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();
........................................
此處代碼很多糙捺，我們逐一的分析；
- 代碼段1
const IMP forward_imp = (IMP)_objc_msgForward_impcache;
IMP imp = nil;
Class curClass;
runtimeLock.assertUnlocked();
// Optimistic cache lookup
if (fastpath(behavior & LOOKUP_CACHE)) {
imp = cache_getImp(cls, sel);
if (imp) goto done_nolock;
}
首先定義了一個(gè)forward_imp 類型為 _objc_msgForward_impcache,吧imp 設(shè)置為nil; 然后開(kāi)始共緩存本類的緩存中取imp;因?yàn)槲覀冊(cè)谧瞿承┎僮鞯臅r(shí)候很有可能內(nèi)存已經(jīng)進(jìn)行緩存笙隙；所以優(yōu)先取自己的緩存列表洪灯；
代碼段2
checkIsKnownClass(cls);判斷當(dāng)前類是否是我們已知的類，因?yàn)橹挥邢到y(tǒng)熟悉竟痰，也就是我們創(chuàng)建的類對(duì)象宝磨，才能進(jìn)行相應(yīng)的屬性纹坐、列表，協(xié)議以及分類等方法的寫(xiě)入，從而才能進(jìn)行查找流程嗤瞎。代碼段3
if (slowpath(!cls->isRealized())) {
cls = realizeClassMaybeSwiftAndLeaveLocked(cls, runtimeLock);
// runtimeLock may have been dropped but is now locked again
}
進(jìn)入到最終的實(shí)現(xiàn)代碼定義如下
class_rw_t *rw;
Class supercls;
Class metacls;
if (!cls) return nil;
if (cls->isRealized()) return cls;
ASSERT(cls == remapClass(cls));
// fixme verify class is not in an un-dlopened part of the shared cache?
auto ro = (const class_ro_t *)cls->data();
auto isMeta = ro->flags & RO_META;
if (ro->flags & RO_FUTURE) {
// This was a future class. rw data is already allocated.
rw = cls->data();
ro = cls->data()->ro();
ASSERT(!isMeta);
cls->changeInfo(RW_REALIZED|RW_REALIZING, RW_FUTURE);
} else {
// Normal class. Allocate writeable class data.
rw = objc::zalloc<class_rw_t>();
rw->set_ro(ro);
rw->flags = RW_REALIZED|RW_REALIZING|isMeta;
cls->setData(rw);
}
supercls = realizeClassWithoutSwift(remapClass(cls->superclass), nil);
metacls = realizeClassWithoutSwift(remapClass(cls->ISA()), nil);
代碼只摘取了片段，次片段的主要作用是取出當(dāng)前類對(duì)象的data()數(shù)據(jù)山憨，和我們之前讀取的類的bits_t一樣拜轨，取出過(guò)后對(duì)相應(yīng)的ro,rw等賦值，確保類對(duì)象所有的數(shù)據(jù)結(jié)構(gòu)都存在并且不為空祥得；
最后兩句代碼也是非常的重要兔沃，起作用大致就是把相關(guān)的繼承鏈都實(shí)現(xiàn)，從而確保了isa走位圖的流通级及，
以及元類都存在乒疏；
也就是進(jìn)行相應(yīng)的初始化操作，確保我們所需與查找的流程以及環(huán)境的初始化
- 代碼段4
if (slowpath((behavior & LOOKUP_INITIALIZE) && !cls->isInitialized())) {
cls = initializeAndLeaveLocked(cls, inst, runtimeLock);
}
也就是系統(tǒng)調(diào)用的一些初始化方法创千，包括load 和initialize,這些方法都不需要我們自己手動(dòng)的調(diào)用缰雇，系統(tǒng)在創(chuàng)建的時(shí)候就已經(jīng)為我們調(diào)用了；
3追驴，imp的查找
所有的方法查找都是先從自己的緩存方法列表中查詢械哟，因?yàn)樽约河袑?shí)現(xiàn)了就沒(méi)必要查找父類方法了，這樣會(huì)節(jié)省時(shí)間和性能殿雪，從而節(jié)約資源
Method meth = getMethodNoSuper_nolock(curClass, sel);
if (meth) {
imp = meth->imp;
goto done;
}
從當(dāng)前類方法列表查找代碼如下
ALWAYS_INLINE static method_t *
search_method_list_inline(const method_list_t *mlist, SEL sel)
{
int methodListIsFixedUp = mlist->isFixedUp();
int methodListHasExpectedSize = mlist->entsize() == sizeof(method_t);
if (fastpath(methodListIsFixedUp && methodListHasExpectedSize)) {
return findMethodInSortedMethodList(sel, mlist);
} else {
// Linear search of unsorted method list
for (auto& meth : *mlist) {
if (meth.name == sel) return &meth;
}
}
#if DEBUG
// sanity-check negative results
if (mlist->isFixedUp()) {
for (auto& meth : *mlist) {
if (meth.name == sel) {
_objc_fatal("linear search worked when binary search did not");
}
}
}
#endif
return nil;
}
從代碼的源碼中我們就知道相關(guān)的查找算法是二分查找暇咆，
二分法原理
在用二分法進(jìn)行查找時(shí)，查找對(duì)象的數(shù)組必須是有序的，即各數(shù)組元素的次序是按其值的大小順序存儲(chǔ)的爸业。其基本思想是先確定待查數(shù)據(jù)的范圍（可用 [left,right] 區(qū)間表示）其骄，然后逐步縮小范圍直到找到或找不到該記錄為止。具體做法是：先取數(shù)組中間位置（mid=(left+right)/2）的數(shù)據(jù)元素與給定值比較扯旷。若相等拯爽，則查找成功；否則钧忽，若給定值比該數(shù)據(jù)元素的值刑号凇（或大），則給定值必在數(shù)組的前半部分[left,mid-1]（或后半部分[mid+1,right]）耸黑，然后在新的查找范圍內(nèi)進(jìn)行同樣的查找桃煎。如此反復(fù)進(jìn)行，直到找到數(shù)組元素值與給定值相等的元素或確定數(shù)組中沒(méi)有待查找的數(shù)據(jù)為止大刊。因此为迈，二分查找每查找一次，或成功缺菌，或使查找數(shù)組中元素的個(gè)數(shù)減少一半葫辐，當(dāng)查找數(shù)組中不再有數(shù)據(jù)元素時(shí)，查找失敗伴郁。
時(shí)間復(fù)雜度
1.最壞情況查找最后一個(gè)元素（或者第一個(gè)元素）Master定理T(n)=T(n/2)+O(1)所以T(n)=O(log2n)
2.最好情況查找中間元素O(1)查找的元素即為中間元素（奇數(shù)長(zhǎng)度數(shù)列的正中間另患，偶數(shù)長(zhǎng)度數(shù)列的中間靠左的元素）
空間復(fù)雜度
- S(n)=logn
有若干個(gè)數(shù)按由小到大的順序存放在一個(gè)一維數(shù)組中，輸入一個(gè)數(shù)x蛾绎，用二分查找法找出x是數(shù)組中第幾個(gè)數(shù)組元素的值昆箕。如果x不在數(shù)組中，則輸出“無(wú)此數(shù)租冠！”鹏倘。
（1）編程思路。
設(shè)有一數(shù)組a[n]顽爹，數(shù)組中的元素按值從小到大排列有序纤泵。用變量low、high和mid分別指示待查元素所在區(qū)間的下界镜粤、上界和中間位置捏题。初始時(shí)，low=0肉渴，high=n-1公荧。
1）令 mid = (low+ high) /2 。
2）比較給定值x與a[mid]值的大小
若a[mid] == x 同规，則查找成功循狰，結(jié)束查找窟社；
若a[mid]> x ，則表明給定值x只可能在區(qū)間low ~ mid-1內(nèi)绪钥，修改檢索范圍灿里。令high=mid-1，low值保持不變程腹；
若a[mid]< x 匣吊，則表明給定值x只可能在區(qū)間mid+1~high內(nèi)，修改檢索范圍寸潦。令low=mid+1缀去，high值保持不變。
3）比較當(dāng)前變量low和high的值甸祭，若low≤high，重復(fù)執(zhí)行第1）褥影、2）兩步池户，若low>high，表明數(shù)組中不存在待查找的元素凡怎，查找失敗校焦。
例如，設(shè)一有序的數(shù)組中有11個(gè)數(shù)據(jù)元素统倒，它們的值依次為{3寨典，8，15房匆，21耸成，35，54浴鸿，63井氢，79，82岳链，92花竞，97}，用二分查找在該數(shù)組中查找值為82和87的元素的過(guò)程如圖1所示掸哑。
這樣我們就能快速查找到我們相應(yīng)的方法了约急，通過(guò)方法編號(hào)去查找，快速有效苗分；
1 如果查找成功就進(jìn)行相應(yīng)的
log_and_fill_cache操作厌蔽，即cache_fill(cls, sel, imp, receiver);到cache->insert(cls, sel, imp, receiver);也就是我上一篇文章所提到的cache_t流程，寫(xiě)入自己的緩存摔癣，方便以后方法調(diào)用的時(shí)候查找躺枕，從而達(dá)到快速的目的服猪；2 如果查找失敗，則進(jìn)入父類的方法列表中查詢拐云；
if (slowpath((curClass = curClass->superclass) == nil)) {
// No implementation found, and method resolver didn't help.
// Use forwarding.
imp = forward_imp;
break;
}
此時(shí)我們能知道所有類對(duì)象和父類之間是一個(gè)雙向列表的關(guān)系罢猪；
curClass = cls;
curClass = curClass->superclass
如果查找成功就進(jìn)行相應(yīng)的 log_and_fill_cache操作，即 cache_fill(cls, sel, imp, receiver); 到cache->insert(cls, sel, imp, receiver); 如果查找失敗叉瘩，跳出循環(huán)膳帕；
4，遞歸查找
當(dāng)從我們創(chuàng)建的類對(duì)象的method_list 和父類method_list都沒(méi)找到相應(yīng)的方法實(shí)現(xiàn)是薇缅；我們就會(huì)進(jìn)入
imp = cache_getImp(curClass, sel);
cache_getImp(curClass, sel);;
全局搜索能發(fā)現(xiàn)我們的方法進(jìn)入
STATIC_ENTRY _cache_getImp
mov r9, r0
CacheLookup NORMAL, _cache_getImp
// cache hit, IMP in r12
mov r0, r12
bx lr // return imp
CacheLookup2 GETIMP, _cache_getImp
// cache miss, return nil
mov r0, #0
bx lr
END_ENTRY _cache_getImp
所有我們進(jìn)入了CacheLookup 然后又會(huì)進(jìn)入到 lookUpImpOrForward,所以此方法會(huì)來(lái)回的遞歸危彩，知道找到nil為止，
5泳桦、動(dòng)態(tài)方法解析汤徽；
以上4個(gè)步驟就是所有的查找流程，從創(chuàng)建的對(duì)象LGPerson 自身開(kāi)始灸撰，一直帶父類谒府，再到根類一直到NSObject如果都沒(méi)找到相應(yīng)的方法實(shí)現(xiàn)，那么就會(huì)進(jìn)入一下代碼浮毯，然后進(jìn)行一次動(dòng)態(tài)拯救的機(jī)會(huì)
if (slowpath(behavior & LOOKUP_RESOLVER)) {
behavior ^= LOOKUP_RESOLVER;
return resolveMethod_locked(inst, sel, cls, behavior);
}
我們斷點(diǎn)調(diào)試進(jìn)入會(huì)發(fā)現(xiàn)程序在執(zhí)行到這里之前是不會(huì)報(bào)錯(cuò)的
所以即使所有的類中都查找了沒(méi)找到我們調(diào)用的方法實(shí)現(xiàn)完疫，但是只要我們?cè)谶@之前進(jìn)行了次動(dòng)態(tài)方法解析，告訴系統(tǒng)我們會(huì)執(zhí)行相應(yīng)的操作债蓝，那么系統(tǒng)是不會(huì)存在報(bào)錯(cuò)問(wèn)題的壳鹤。
進(jìn)行動(dòng)態(tài)解析后系統(tǒng)又會(huì)繼續(xù)調(diào)用lookUpImpOrForward 從而檢測(cè)到該方法的實(shí)現(xiàn)
三，總結(jié)饰迹；
上一篇文章我們已經(jīng)詳細(xì)的介紹了快速的查找流程芳誓，此次是著重介紹方法機(jī)制的慢速查找，這樣就完整的介紹了在消息調(diào)用機(jī)制中的方法查找流程啊鸭，此次學(xué)習(xí)是個(gè)人的一個(gè)記錄和成長(zhǎng)兆沙，還請(qǐng)各位大神多多指教。
