簡介：本文主要從源碼的角度探究了Objective-C在runtime層的方法決議(Method resolveing)過程和方法緩存(Method cache)的實現(xiàn)。內(nèi)容包括：
1）從消息決議說起 2）緩存為誰而生 3）何為方法緩存 4）緩存和散列 5）十萬個為什么 6）緩存-性能優(yōu)化的萬金油？ 7）優(yōu)化永無止境
一、從消息決議說起
我們都知道，在Objective-C里調(diào)用一個方法是這樣的：
[object methodA];
這表示我們想去調(diào)用object的methodA。
但是在Objective-C里面調(diào)用一個方法到底意味著什么呢，是否和C++一樣，任何一個非虛方法都會被編譯成一個唯一的符號，在調(diào)用的時候去查找符號表，找到這個方法然后調(diào)用呢？
答案是否定的。在Objective-C里面調(diào)用一個方法的時候，runtime層會將這個調(diào)用翻譯成
objc_msgSend(id self, SEL op, ...)
而objc_msgSend具體又是如何分發(fā)的呢？ 我們來看下runtime層objc_msgSend的源碼。
在objc-msg-arm.s中，objc_msgSend的代碼如下：
（ps：Apple為了高度優(yōu)化objc_msgSend的性能，這個文件是匯編寫成的，不過即使我們不懂匯編，詳盡的注釋也可以讓我們一窺其真面目）
從源碼代碼中可以看到，objc_msgSend（就arm平臺而言）的消息分發(fā)分為以下幾個步驟：
*判斷receiver是否為nil，也就是objc_msgSend的第一個參數(shù)self，也就是要調(diào)用的那個方法所屬對象
- 從緩存里尋找，找到了則分發(fā)，否則
*利用objc-class.mm中_class_lookupMethodAndLoadCache3（為什么有個這么奇怪的方法。本文末尾會解釋）方法去尋找selector
*如果支持GC，忽略掉非GC環(huán)境的方法（retain等）
*從本class的method list尋找selector，如果找到，填充到緩存中，并返回selector，否則尋找父類的method list，并依次往上尋找，直到找到selector，填充到緩存中，并返回selector，否則調(diào)用_class_resolveMethod，如果可以動態(tài)resolve為一個selector，不緩存，方法返回，否則 轉(zhuǎn)發(fā)這個selector，否則 報錯，拋出異常
二、緩存為誰而生
從上面的分析中我們可以看到，當(dāng)一個方法在比較“上層”的類中，用比較“下層”（繼承關(guān)系上的上下層）對象去調(diào)用的時候，如果沒有緩存，那么整個查找鏈?zhǔn)窍喈?dāng)長的。就算方法是在這個類里面，當(dāng)方法比較多的時候，每次都查找也是費事費力的一件事情。
考慮下面的一個調(diào)用過程：
for ( int i = 0; i < 100000; ++i) {
MyClass myObject = myObjects[i];
[myObject methodA];
}
當(dāng)我們需要去調(diào)用一個方法數(shù)十萬次甚至更多地時候，查找方法的消耗會變的非常顯著。
就算我們平常的非大規(guī)模調(diào)用，除非一個方法只會調(diào)用一次，否則緩存都是有用的。在運行時，那么多對象，那么多方法調(diào)用，節(jié)省下來的時間也是非?？捎^的。
三、何為方法緩存
本著源碼面前，了無秘密的原則，我們看下源碼中的方法緩存到底是什么，在objc-cache.mm中，objc_cache的定義如下
struct objc_cache {
uintptr_t mask; / total = mask + 1 */
uintptr_t occupied;
cache_entry *buckets[1];
};
嗯，objc_cache的定義看起來很簡單包涵下面三個變量：
1）mask：可以認為是當(dāng)前能達到的最大index（從0開始的），所以緩存的size（total）是mask+1
2）occupied 被占用的槽位，因為緩存是以散列表的形式存在，所以會有空槽。而occupied表示當(dāng)前被占用的數(shù)目
3）buckets：用數(shù)據(jù)表示的hash表，cache_entry類型，每一個cache_entry代表一個方法緩存（buckets定義在objc_cache后邊 說明是一個可變長度的數(shù)組）
cache_entry的定義如下：
typedef struct {
SEL name; // same layout as struct old_method
void *unused;
IMP imp; // same layout as struct old_method
} cache_entry;
cache_entry定義也包含了三個字段，分別是：
1)、name，被緩存的方法名字
2)、unused，保留字段，還沒被使用。
3)、imp，方法實現(xiàn)
四、緩存和散列
緩存的存儲使用了散列，
為什么要用散列呢？ 因為散列檢索起來更快。我們來看下是方法緩存如何散列和檢索的：
// 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.
buckets = (cache_entry **)cache->buckets;
for (index = CACHE_HASH(sel, cache->mask);
buckets[index] != NULL;
index = (index+1) & cache->mask)
{
// empty
}
buckets[index] = entry;
這是往方法緩存里存放一個方法的代碼片段，我們可以看到sel被散列后找到一個空槽放在buckets中，而CACHE_HASH的定義如下：
define CACHE_HASH(sel, mask) (((uintptr_t)(sel)>>2) & (mask))
這段代碼就是利用了sel的指針地址和mask做了一下簡單計算得出的。
而從散列表取緩存則是利用匯編語言寫成的（是為了高度優(yōu)化objc_msgSend而使用匯編的）。我們看objc-msg-arm.mm 里面的CacheLookup方法：
.macro CacheLookup /* selReg, classReg, missLabel */
MOVE r9, 0, LSR #2 /* index = (sel >> 2) */ ldr a4, [1, #CACHE] /* cache = class->cache /
add a4, a4, #BUCKETS / buckets = &cache->buckets */
/* search the cache /
/ a1=receiver, a2 or a3=sel, r9=index, a4=buckets, 1=method */ 1: ldr ip, [a4, #NEGMASK] /* mask = cache->mask */ and r9, r9, ip /* index &= mask */ ldr1, [a4, r9, LSL #2] /* method = buckets[index] /
teq 1, #0 /* if (method == NULL) */ add r9, r9, #1 /* index++ */ beq2 / goto cacheMissLabel */
ldr ip, [1, #METHOD_NAME] /* load method->method_name */ teq0, ip /* if (method->method_name != sel) /
bne 1b / retry */
/* cache hit, 1 == method triplet address */ /* Return triplet in1 and imp in ip /
ldr ip, [$1, #METHOD_IMP] / imp = method->method_imp */
.endmacro
雖然是匯編，但是注釋太詳盡了，理解起來并不難，還是求hash，去buckets里找，找不到按照hash沖突的規(guī)則繼續(xù)向下，直到最后。
五、十萬個為什么
1）方法緩存在什么地方？
讓我們?nèi)シ搭惖亩x，在Objective-C 2.0中，Class的定義大概是這樣的（見objc-runtime.mm）
struct _class_t {
struct _class_t *isa;
struct _class_t *superclass;
void *cache;
void *vtable;
struct _class_ro_t ro;
};
我們看到在類的定義里有cache字段，沒錯，類的所有緩存都存在metaclass上，所以每個類都只有一份方法緩存，而不是每一個類的object都保存一份。
2）父類方法的緩存只存在父類么，還是子類也會緩存父類的方法？
在第一節(jié)對objc_msgSend的追溯中我們可以看到，即便是從父類取到的方法，也會存在類本身的方法緩存里。而當(dāng)用一個父類對象去調(diào)用那個方法的時候，也會在父類的metaclass里緩存一份
3）類的方法緩存大小有沒有限制？
要回答這個問題，我們需要再看一下源碼，在objc-cache.mm有一個變量定義如下：
/ When _class_slow_grow is non-zero, any given cache is actually grown
- only on the odd-numbered times it becomes full; on the even-numbered
- times, it is simply emptied and re-used. When this flag is zero,
- caches are grown every time. */
static const int _class_slow_grow = 1;
其實不用再看進一步的代碼片段，僅從注釋我們就可以看到問題的答案。注釋中說明，當(dāng)_class_slow_grow是非0值的時候，只有當(dāng)方法緩存第奇數(shù)次滿（使用的槽位超過3/4）的時候，方法緩存的大小才會增長（會清空緩存，否則hash值就不對了）；當(dāng)?shù)谂紨?shù)次滿的時候，方法緩存會被清空并重新利用。 如果_class_slow_grow值為0，那么每一次方法緩存滿的時候，其大小都會增長。
所以單就問題而言，答案是沒有限制，雖然這個值被設(shè)置為1，方法緩存的大小增速會慢一點，但是確實是沒有上限的。
3）為什么類的方法列表不直接做成散列表呢，做成list，還要單獨緩存，多費事？
這個問題嗎我覺得有以下三個原因：
①散列表沒有順序，Objective-C的方法列表是一個list，是有順序的；Objective-C在查找方法的時候會順著list依次查找，并且category的方法在原始方法list的前面，需要先被找到，如果直接用hash存方法，方法的順序就沒法保證。
②list的方法還保存了除selector和imp之外其他很多屬性
③散列表是有空槽的，會浪費空間
六、緩存 - 性能優(yōu)化的萬金油？
非也，就算有了有了Objective-C本身的方法緩存，我們還是有很多調(diào)用方法的優(yōu)化空間，對于這件事情，這篇文章講的非常詳細，大家可以自行移步觀摩
http://www.mulle-kybernetik.com/artikel/Optimization/opti-3-imp-deluxe.html（強烈推薦，雖然我們一般不會遇到需要這么強度優(yōu)化的地方，但是這種精神和思想是值得我們學(xué)習(xí)的）
七、優(yōu)化，永無止境
在文章末尾，我們再來回答一下第一節(jié)提出的問題：“為什么會有_class_lookupMethodAndLoadCache3這個方法？”
這個方法的實現(xiàn)如下所示：
/***********************************************************************
- _class_lookupMethodAndLoadCache.
- Method lookup for dispatchers ONLY. OTHER CODE SHOULD USE lookUpImp().
- This lookup avoids optimistic cache scan because the dispatcher
- already tried that.
**********************************************************************/
IMP _class_lookupMethodAndLoadCache3(id obj, SEL sel, Class cls)
{
return lookUpImpOrForward(cls, sel, obj,
YES/initialize/, NO/cache/, YES/resolver/);
}
如果單純看方法名，這個方法應(yīng)該會從緩存和方法列表中查找一個方法，但是如第一節(jié)所講，在調(diào)用這個方法之前，我們已經(jīng)是從緩存無法找到這個方法了，所以這個方法避免了再去掃描緩存查找方法的過程，而是直接從方法列表找起。從Apple代碼的注釋，我們也完全可以了解這一點。不顧一切地追求完美和性能，是一種品質(zhì)。
后記：
本文是Objective-C runtime源碼研究的第二篇，主要對Objective-C的方法決議和方法緩存做了剖析。runtime的源代碼可以在http://www.opensource.apple.com/tarballs/下載。如有錯誤，敬請指正。
