iOS objc_msgSend尾調(diào)用優(yōu)化機(jī)制
本文基于Objective-C對(duì)象的消息傳遞機(jī)制，詳細(xì)分析OC對(duì) objc_msgSend 的尾調(diào)用優(yōu)化方式。
1. 什么是尾調(diào)用?
尾調(diào)用( TailCall)：某個(gè)函數(shù)的***一步僅僅只是調(diào)用了一個(gè)函數(shù)(可以是自身，可以是另一個(gè)函數(shù))。 QiShare提醒：注意 “僅僅” 兩個(gè)字。
尾調(diào)用例子：
- // 尾調(diào)用：
- - (NSInteger)funcA:(NSInteger)num {
- /* Some codes... */
- if(num == 0) { return [self funcA:num];// 尾調(diào)用->自身 }
- if (num > 0) { return [self funcB:num];// 尾調(diào)用->函數(shù)funcB }
- return [self funcC:num];// 尾調(diào)用->函數(shù)funcC}
正例解釋：funcA 的***一步僅僅調(diào)用了另一個(gè)函數(shù)。不論是調(diào)用funcA、funcB還是funcC 都屬于尾調(diào)用。(不論調(diào)用函數(shù)的位置在哪，只要***一步僅僅調(diào)用一個(gè)函數(shù)就行。)
反例：不是尾調(diào)用的例子
- // 不是尾調(diào)用1：
- - (NSInteger)funcA:(NSInteger)num {
- NSInteger num = [self funcB:(num)];
- return num;// 不是尾調(diào)用->***一步是返回一個(gè)值，而不是調(diào)用一個(gè)函數(shù)
- }
反例解釋：不是尾調(diào)用。因?yàn)?**一步是返回一個(gè)值，而不是僅僅調(diào)用一個(gè)函數(shù)。
- // 不是尾調(diào)用2：
- - (NSInteger)funcA:(NSInteger)num {
- return [self funcB:(num)] + 1;// 不是尾調(diào)用->原因：末尾有+1操作}
反例解釋：不是尾調(diào)用。因?yàn)?**一步不僅調(diào)用了函數(shù)還有 +1 操作。
2. OC的尾調(diào)用優(yōu)化體現(xiàn)在哪里?
小編準(zhǔn)備了一個(gè)Demo：通過“斷點(diǎn)”和“當(dāng)前內(nèi)存情況”查看有無尾調(diào)用優(yōu)化。
場景一：無優(yōu)化(因?yàn)樽芳恿?0，不屬于尾調(diào)用)
無優(yōu)化Demo效果圖：
這種場景下，每次函數(shù)調(diào)用一直在進(jìn)棧，不斷申請(qǐng)?？臻g，***會(huì)棧溢出，最終導(dǎo)致崩潰。 空間復(fù)雜度O(n)，時(shí)間復(fù)雜度O(n)。
圖解如下：
場景二：有尾調(diào)用優(yōu)化
優(yōu)化Demo效果圖：
這種場景下，每次函數(shù)調(diào)用一直在重用棧幀，不申請(qǐng)?？臻g?？臻g復(fù)雜度O(1)，時(shí)間復(fù)雜度O(n)。
圖解如下：
3. OC是如何實(shí)現(xiàn)尾調(diào)用優(yōu)化的?
這次討論起因于《Effective Objective-C 2.0》的原文：
| 如果某函數(shù)的***一項(xiàng)操作是調(diào)用另外一個(gè)函數(shù)，那么就可以運(yùn)用 “尾調(diào)用優(yōu)化”技術(shù)。編譯器會(huì)生成調(diào)轉(zhuǎn)至另一函數(shù)所需的指令碼，而且不會(huì)向調(diào)用堆棧中推入新的 “棧幀”(frame stack)。只有當(dāng)某函數(shù)的***一個(gè)操作僅僅是調(diào)用其他函數(shù)而 不會(huì)將其返回值另作他用時(shí)，才能執(zhí)行 “尾調(diào)用優(yōu)化”。
這項(xiàng)優(yōu)化對(duì) objc_msgSend非常關(guān)鍵，如果不這么做的話，那么每次調(diào)用Objective-C方法之前，都需要為調(diào)用objc_msgSend函數(shù)準(zhǔn)備“棧幀”，大家在“棧蹤跡”(stack trace)中可以看到這種“棧幀”。此外，如果不優(yōu)化，還會(huì)過早地發(fā)生“棧溢出”(stack overflow)現(xiàn)象。 |
作者對(duì)尾調(diào)用的描述十分精簡。在這里，QiShare團(tuán)隊(duì)對(duì)這段話進(jìn)行了詳細(xì)的分析：
(1)尾調(diào)用優(yōu)化的本質(zhì)：很簡單，就是棧幀的復(fù)用。
(2)尾調(diào)用優(yōu)化的條件有三點(diǎn)：
- 尾調(diào)用函數(shù)不需要訪問當(dāng)前棧幀中的變量。(變量可以作為形參，但是不能作為實(shí)參)
- 尾調(diào)用返回后，函數(shù)沒有語句需要執(zhí)行。(***一步僅僅只能執(zhí)行一個(gè)函數(shù))
- 尾調(diào)用結(jié)果就是函數(shù)的返回值。(不能有別的“附加品”，***一步僅僅只能是執(zhí)行一個(gè)函數(shù))
(3)函數(shù)調(diào)用的過程：函數(shù)調(diào)用會(huì)在內(nèi)存中申請(qǐng)一塊“棧幀”，保存調(diào)用的地址和內(nèi)部變量等信息。如果函數(shù)A內(nèi)部調(diào)用函數(shù)B，那么在函數(shù)A的棧幀上就會(huì)加上一個(gè)函數(shù)B的棧幀。如果函數(shù)B再調(diào)用了函數(shù)C，那么函數(shù)A的棧幀上就會(huì)有序加上函數(shù)B和函數(shù)C的棧幀。如果C運(yùn)行結(jié)束了，返回到函數(shù)B，C的棧幀才會(huì)消失。
(4)尾調(diào)用優(yōu)化實(shí)現(xiàn)原理：當(dāng)函數(shù)A的***一步僅僅是調(diào)用另一個(gè)函數(shù)B時(shí)(或者調(diào)用自身函數(shù)A)，這時(shí)，因?yàn)楹瘮?shù)A的位置信息和內(nèi)部變量已經(jīng)不會(huì)再用到了，直接把函數(shù)A的棧幀交給函數(shù)B使用。
尾調(diào)用優(yōu)化關(guān)鍵圖解：
總結(jié)：
- 尾調(diào)用：某個(gè)函數(shù)的***一步僅僅調(diào)用了一個(gè)函數(shù)(可以是自身，可以是另一個(gè)函數(shù))。
- OC的尾調(diào)用優(yōu)化的本質(zhì)是：棧幀的復(fù)用
- 尾調(diào)用優(yōu)化實(shí)現(xiàn)原理：當(dāng)函數(shù)A的***一步僅僅是調(diào)用另一個(gè)函數(shù)B時(shí)(或者調(diào)用自身函數(shù)A)，這時(shí)，因?yàn)楹瘮?shù)A的位置信息和內(nèi)部變量已經(jīng)不會(huì)再用到了，直接把函數(shù)A的棧幀交給函數(shù)B使用。
PS：尾調(diào)用優(yōu)化在Release模式下才會(huì)有，Debug模式下沒有。
源碼地址： https://github.com/QiShare/QiRecursiveDemo.git
【本文是51CTO專欄機(jī)構(gòu)360技術(shù)的原創(chuàng)文章，微信公眾號(hào)“360技術(shù)（ id: qihoo_tech）”】
