|
|
在上文《尾遞歸與Continuation》里，我們談到了尾遞歸的概念和示例，不過有些朋友對于尾遞歸的功效依然有所懷疑。因此現在，老趙再簡單講解一下尾遞歸的優化原理，希望能給大家以一定理性認識。
尾遞歸的循環優化
尾遞歸，即是遞歸調用放在方法末尾的遞歸方式，如經典的階乘：
int FactorialTailRecursion(int n, int acc)
{
if (n == 0) return acc;
return FactorialTailRecursion(n - 1, acc * n);
}
由于遞歸在方法的末尾，因此方法中的局部變量已經毫無用處，編譯器完全可以將其“復用”，并把尾遞歸優化為“循環”方式：
int FactorialLoopOptimized(int n, int acc)
{
while (true)
{
if (n == 0) return acc;
acc *= n;
n--;
}
}
不過，上文還提到了尾遞歸中的常用技巧Continuation。那么對于如下形式的Continuation，編譯器又該如何優化呢？
int FactorialContinuation(int n, Func<int, int> continuation)
{
if (n == 0) return continuation(1);
return FactorialContinuation(n - 1, r => continuation(n * r));
}
我們先用“人腦”來思考一下，這段代碼的執行方式是怎么樣的。我們每次使用n和contn調用FactorialContinuation時，都會構造一個新的contn - 1，并同n - 1傳入下一次FactorialContinuation調用中去。以此類推，直到n等于0時，就直接調用cont0并返回。至于每個Continuation的定義，我們可以歸納出如下結果：
Func<int, int> contn = r => r * n
因此：
Factorial(n)
= contn(contn - 1(...(cont2(cont1(cont0(1)))...))
= n * ((n – 1) * (...(2 * (1 * 1))...)) =
= n * (n - 1) * ... * 2 * 1
= n!
于是，我們可以根據這個“意圖”，將FactorialContinuation方法“優化”為如下形式：
int FactorialLoopOptimized2(int n, Func<int, int> continuation)
{
LinkedList<Func<int, int>> contList = new LinkedList<Func<int, int>>();
while (true)
{
if (n == 0) break;
int tempN = n;
Func<int, int> newCont = r => tempN * r;
contList.AddFirst(newCont);
n--;
continuation = newCont;
}
return contList.Aggregate(1, (acc, cont) => cont(acc));
}
我們構造了一個Continuation函數鏈表，隨著n遞減，每次都會把新的Continuation函數插入到鏈表頭，最后Aggregate方法會將第一個參數（累加器）依次運用到每個函數中去，得到最后結果并返回。只可惜，這個優化完全是我們“一廂情愿”而已，這么做的前提是“理解”了函數的意義，把方法的迭代調用“拆開”，而編譯器是無法（還是很難）幫我們優化到如斯地步的。那么編譯器對于此類問題又該如何解決呢？
之前，我們使用C#中的匿名方法特性來構造每個Continuation方法。如果我們使用自定義的封裝類，再將遞歸“優化”成循環，FactorialContinuation又會成為什么樣呢？如下：
private class Continuation
{
public Continuation(Func<int, int> cont, int n)
{
this.cont = cont;
this.n = n;
}
private Func<int, int> cont;
private int n;
public int Invoke(int r)
{
return this.cont(this.n * r);
}
}
public static int FactorialLoopOptimized3(int n, Func<int, int> continuation)
{
while (true)
{
if (n == 0) break;
continuation = new Continuation(continuation, n).Invoke;
n--;
}
return continuation(1);
}
其實這才是FactorialContinuation的“直譯”，也是編譯器能夠進行優化。不過朋友們應該也能夠看出，這只是一個Continuation對象套著另一個Continuation對象。如果形成了數萬個Continuation對象的嵌套，在最終調用最外層的Continuation時，每個內部的Continuation也會在調用時往同一個堆棧中不斷累加，最終還是會造成堆棧溢出。因此，如果使用了Continuation，還是無法簡單把遞歸優化成循環來避免堆棧溢出的。編譯器還必須進行其他方面的優化。
方法尾調用的優化
上一篇文章曾經談到：“與普通遞歸相比，由于尾遞歸的調用處于方法的最后，因此方法之前所積累下的各種狀態對于遞歸調用結果已經沒有任何意義，因此完全可以把本次方法中留在堆棧中的數據完全清除，把空間讓給最后的遞歸調用。這樣的優化便使得遞歸不會在調用堆棧上產生堆積，意味著即時是“無限”遞歸也不會讓堆棧溢出”。這其實才是尾遞歸的“正統”優化方式，那么我們先暫時忘記之前的“循環優化”，從最簡單的示例中查看這樣的優化是如何進行的。還是最簡單的“尾遞歸”階乘：
static int FactorialTailRecursion(int n, int acc)
{
if (n == 0) return acc;
return FactorialTailRecursion(n - 1, acc * n);
}
它的IL代碼是：
.method private hidebysig static int32 FactorialTailRecursion(int32 n, int32 acc) cil managed
{
.maxstack 8
L_0000: ldarg.0 // 加載第1個參數，即n
L_0001: brtrue.s L_0005 // 如果第一個參數不為0，則跳轉到L_0005
L_0003: ldarg.1 // 運行到此，說明第1個參數為0，則加載第2個參數，即acc
L_0004: ret // 返回（剛加載的第2個參數）
L_0005: ldarg.0 // 加載第1個參數，即n
L_0006: ldc.i4.1 // 加載數值1
L_0007: sub // 將兩者相減，即n - 1
L_0008: ldarg.1 // 加載第2個參數，即acc
L_0009: ldarg.0 // 加載第1個參數，即n
L_000a: mul // 將兩者相乘，即acc * n
// 把n - 1和acc * n作為參數遞歸調用
L_000b: call int32 TailRecursion.Recursion::FactorialTailRecursion(int32, int32)
L_0010: ret // 返回遞歸調用結果
}
在這個問題上，我們還需要觀察它的匯編代碼（為了不干擾文章內容，老趙會把獲取匯編代碼的做法單獨寫一篇文章，稍后發布），如下：
00ad00d0 push ebp
00ad00d1 mov ebp,esp
00ad00d3 push esi
00ad00d4 mov eax,edx
00ad00d6 test ecx,ecx
00ad00d8 jne 00ad00dd
00ad00da pop esi
00ad00db pop ebp
00ad00dc ret
00ad00dd lea edx,[ecx-1]
00ad00e0 imul ecx,eax
00ad00e3 mov esi,ecx
00ad00e5 test edx,edx
00ad00e7 jne 00ad00ed
00ad00e9 mov eax,esi
00ad00eb jmp 00ad00f9
00ad00ed lea ecx,[edx-1]
00ad00f0 imul edx,esi
00ad00f3 call dword ptr ds:[703068h] (地址703068h的值即為00ad00d0)
00ad00f9 pop esi
00ad00fa pop ebp
00ad00fb ret
上面的匯編代碼非常簡單，從中可以看出，每次遞歸調用都使用了最簡單的call指令，沒有經過任何有效的優化或調整。因此在不斷地遞歸調用之后，終究會出現堆棧溢出。這就是普通遞歸的缺陷。而對于尾遞歸來說，MSIL提供了額外的tail指令表示“尾調用”1，它只需簡單補充在IL指令call, callvirt, calli之前便可。因此我們使用ildasm.exe將IL代碼dump出來，并在call之前加上tail指令：
.method private hidebysig static int32 FactorialTailRecursion(int32 n, int32 acc) cil managed
{
.maxstack 8
L_0000: ldarg.0
L_0001: brtrue.s L_0005
L_0003: ldarg.1
L_0004: ret
L_0005: ldarg.0
L_0006: ldc.i4.1
L_0007: sub
L_0008: ldarg.1
L_0009: ldarg.0
L_000a: mul
L_000b: tail.
L_000c: call int32 TailRecursion.Recursion::FactorialTailRecursion(int32, int32)
L_0010: ret
}
使用ilasm.exe重新編譯之后運行，再重新察看FactorialTailRecursion的匯編代碼：
00a600d0 push ebp
00a600d1 mov ebp,esp
00a600d3 push edi
00a600d4 push esi
00a600d5 push ebx
00a600d6 mov eax,ecx
00a600d8 mov esi,edx
00a600da test eax,eax
00a600dc jne 00a600e5
00a600de mov eax,esi
00a600e0 pop ebx
00a600e1 pop esi
00a600e2 pop edi
00a600e3 pop ebp
00a600e4 ret
00a600e5 lea ecx,[eax-1]
00a600e8 imul eax,esi
00a600eb mov edx,eax
00a600ed mov eax,dword ptr ds:[813068h]
00a600f3 push 0
00a600f5 push 0
00a600f7 push 1
00a600f9 push eax
00a600fa cmp dword ptr [mscorwks!g_TrapReturningThreads (7204339c)],0
00a60101 je 00a6010c
00a60103 push ecx
00a60104 push edx
00a60105 call mscorwks!JIT_PollGC (71d5c9d3)
00a6010a pop edx
00a6010b pop ecx
00a6010c call mscorwks!JIT_TailCall (71b02890)
00a60111 int 3
在這里我實在無法完整講述上述匯編代碼的含義，不過從中可以看出它的確對于尾遞歸進行了特別的處理，而并非使用簡單的call指令進行調用。對此互聯網上的資源也不多，老趙只找到了Shri Borde的一篇文章，其中簡單描述了Whidbey V2（真早）中CLR對于這方面的處理，以及一些相關的考慮，從中似乎能夠看出一些苗頭來。
讓我們再回想之前的問題：Continuation無法通過簡單優化為循環來解決遞歸問題。但是通過觀察可以看出，Continuation.Invoke方法中的cont委托調用是最后一條命令，這說明它是一個“尾調用”——雖然不是“尾遞歸”，不過這已經滿足tail指令的要求了：只需和所在方法返回值相同（或兼容）即可。因此，對于Continuation來說，我們也需要進行尾遞歸的優化。您可以進行嘗試，現在無論遞歸多“深”，都不會使堆棧溢出了。
注1：與tail類似，IL指令jmp也能夠用于方法調用。這兩條指令都不會在調用棧上堆積數據。tail與jmp的不同之處在于，前者只需要返回值與所在方法相同或兼容即可，而后者需要簽名完全相同。您可以想象得到，對于“直接遞歸”來說，可以使用jmp進行調用，而普通的“尾調用”，則只能使用tail了。
NET技術：淺談尾遞歸的優化方式，轉載需保留來源！
鄭重聲明：本文版權歸原作者所有，轉載文章僅為傳播更多信息之目的，如作者信息標記有誤，請第一時間聯系我們修改或刪除，多謝。
