iOS objc_msgSend尾呼叫優化機制
本文基於Objective-C物件的訊息傳遞機制,詳細分析OC對 objc_msgSend 的尾呼叫優化方式。
1. 什麼是尾呼叫?
尾呼叫( TailCall):某個函式的最後一步僅僅只是呼叫了一個函式(可以是自身,可以是另一個函式)。 QiShare提醒:注意 “僅僅” 兩個字。
尾呼叫例子:
// 尾呼叫: - (NSInteger)funcA:(NSInteger)num { /* Some codes... */ if(num == 0) { return [self funcA:num];// 尾呼叫->自身 } if (num > 0) { return [self funcB:num];// 尾呼叫->函式funcB } return [self funcC:num];// 尾呼叫->函式funcC}
正例解釋:funcA 的最後一步僅僅呼叫了另一個函式。不論是呼叫funcA、funcB還是funcC 都屬於尾呼叫。(不論呼叫函式的位置在哪,只要最後一步僅僅呼叫一個函式就行。)
反例:不是尾呼叫的例子
// 不是尾呼叫1: - (NSInteger)funcA:(NSInteger)num { NSInteger num = [self funcB:(num)]; return num;// 不是尾呼叫->最後一步是返回一個值,而不是呼叫一個函式 }
反例解釋:不是尾呼叫。因為最後一步是返回一個值,而不是僅僅呼叫一個函式。
// 不是尾呼叫2: - (NSInteger)funcA:(NSInteger)num { return [self funcB:(num)] + 1;// 不是尾呼叫->原因:末尾有+1操作}
反例解釋:不是尾呼叫。因為最後一步不僅呼叫了函式還有 +1 操作。
2. OC的尾呼叫優化體現在哪裡?
小編準備了一個Demo:通過“斷點”和“當前記憶體情況”檢視有無尾呼叫優化。
場景一:無優化(因為追加了.0,不屬於尾呼叫)
無優化Demo效果圖:
這種場景下,每次函式呼叫一直在進棧,不斷申請棧空間,最後會棧溢位,最終導致崩潰。 空間複雜度O(n),時間複雜度O(n)。
圖解如下:
場景二:有尾呼叫優化
優化Demo效果圖:
這種場景下,每次函式呼叫一直在重用棧幀,不申請棧空間。空間複雜度O(1),時間複雜度O(n)。
圖解如下:
3. OC是如何實現尾呼叫優化的?
這次討論起因於《Effective Objective-C 2.0》的原文:
這項優化對 objc_msgSend非常關鍵,如果不這麼做的話,那麼每次呼叫Objective-C方法之前,都需要為呼叫objc_msgSend函式準備“棧幀”,大家在“棧蹤跡”(stack trace)中可以看到這種“棧幀”。此外,如果不優化,還會過早地發生“棧溢位”(stack overflow)現象。
作者對尾呼叫的描述十分精簡。在這裡,QiShare團隊對這段話進行了詳細的分析:
(1)尾呼叫優化的本質:很簡單,就是棧幀的複用。
(2)尾呼叫優化的條件有三點:
- 尾呼叫函式不需要訪問當前棧幀中的變數。(變數可以作為形參,但是不能作為實參)
- 尾呼叫返回後,函式沒有語句需要執行。(最後一步僅僅只能執行一個函式)
- 尾呼叫結果就是函式的返回值。(不能有別的“附加品”,最後一步僅僅只能是執行一個函式)
(3)函式呼叫的過程:函式呼叫會在記憶體中申請一塊“棧幀”,儲存呼叫的地址和內部變數等資訊。如果函式A內部呼叫函式B,那麼在函式A的棧幀上就會加上一個函式B的棧幀。如果函式B再呼叫了函式C,那麼函式A的棧幀上就會有序加上函式B和函式C的棧幀。如果C執行結束了,返回到函式B,C的棧幀才會消失。
(4)尾呼叫優化實現原理:當函式A的最後一步僅僅是呼叫另一個函式B時(或者呼叫自身函式A),這時,因為函式A的位置資訊和內部變數已經不會再用到了,直接把函式A的棧幀交給函式B使用。
尾呼叫優化關鍵圖解:
總結:
- 尾呼叫:某個函式的最後一步僅僅呼叫了一個函式(可以是自身,可以是另一個函式)。
- OC的尾呼叫優化的本質是:棧幀的複用
- 尾呼叫優化實現原理:當函式A的最後一步僅僅是呼叫另一個函式B時(或者呼叫自身函式A),這時,因為函式A的位置資訊和內部變數已經不會再用到了,直接把函式A的棧幀交給函式B使用。
PS:尾呼叫優化在Release模式下才會有,Debug模式下沒有。
原始碼地址: https://github.com/QiShare/QiRecursiveDemo.git