|
|
在上文《尾遞歸與Continuation》里，我們談到了尾遞歸的概念和示例，不過(guò)有些朋友對(duì)于尾遞歸的功效依然有所懷疑。因此現(xiàn)在，老趙再簡(jiǎn)單講解一下尾遞歸的優(yōu)化原理，希望能給大家以一定理性認(rèn)識(shí)。
尾遞歸的循環(huán)優(yōu)化
尾遞歸，即是遞歸調(diào)用放在方法末尾的遞歸方式，如經(jīng)典的階乘：
int FactorialTailRecursion(int n, int acc)
{
if (n == 0) return acc;
return FactorialTailRecursion(n - 1, acc * n);
}
由于遞歸在方法的末尾，因此方法中的局部變量已經(jīng)毫無(wú)用處，編譯器完全可以將其“復(fù)用”，并把尾遞歸優(yōu)化為“循環(huán)”方式：
int FactorialLoopOptimized(int n, int acc)
{
while (true)
{
if (n == 0) return acc;
acc *= n;
n--;
}
}
不過(guò)，上文還提到了尾遞歸中的常用技巧Continuation。那么對(duì)于如下形式的Continuation，編譯器又該如何優(yōu)化呢？
int FactorialContinuation(int n, Func<int, int> continuation)
{
if (n == 0) return continuation(1);
return FactorialContinuation(n - 1, r => continuation(n * r));
}
我們先用“人腦”來(lái)思考一下，這段代碼的執(zhí)行方式是怎么樣的。我們每次使用n和contn調(diào)用FactorialContinuation時(shí)，都會(huì)構(gòu)造一個(gè)新的contn - 1，并同n - 1傳入下一次FactorialContinuation調(diào)用中去。以此類(lèi)推，直到n等于0時(shí)，就直接調(diào)用cont0并返回。至于每個(gè)Continuation的定義，我們可以歸納出如下結(jié)果：
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!
于是，我們可以根據(jù)這個(gè)“意圖”，將FactorialContinuation方法“優(yōu)化”為如下形式：
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));
}
我們構(gòu)造了一個(gè)Continuation函數(shù)鏈表，隨著n遞減，每次都會(huì)把新的Continuation函數(shù)插入到鏈表頭，最后Aggregate方法會(huì)將第一個(gè)參數(shù)（累加器）依次運(yùn)用到每個(gè)函數(shù)中去，得到最后結(jié)果并返回。只可惜，這個(gè)優(yōu)化完全是我們“一廂情愿”而已，這么做的前提是“理解”了函數(shù)的意義，把方法的迭代調(diào)用“拆開(kāi)”，而編譯器是無(wú)法（還是很難）幫我們優(yōu)化到如斯地步的。那么編譯器對(duì)于此類(lèi)問(wèn)題又該如何解決呢？
之前，我們使用C#中的匿名方法特性來(lái)構(gòu)造每個(gè)Continuation方法。如果我們使用自定義的封裝類(lèi)，再將遞歸“優(yōu)化”成循環(huán)，F(xiàn)actorialContinuation又會(huì)成為什么樣呢？如下：
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);
}
其實(shí)這才是FactorialContinuation的“直譯”，也是編譯器能夠進(jìn)行優(yōu)化。不過(guò)朋友們應(yīng)該也能夠看出，這只是一個(gè)Continuation對(duì)象套著另一個(gè)Continuation對(duì)象。如果形成了數(shù)萬(wàn)個(gè)Continuation對(duì)象的嵌套，在最終調(diào)用最外層的Continuation時(shí)，每個(gè)內(nèi)部的Continuation也會(huì)在調(diào)用時(shí)往同一個(gè)堆棧中不斷累加，最終還是會(huì)造成堆棧溢出。因此，如果使用了Continuation，還是無(wú)法簡(jiǎn)單把遞歸優(yōu)化成循環(huán)來(lái)避免堆棧溢出的。編譯器還必須進(jìn)行其他方面的優(yōu)化。
方法尾調(diào)用的優(yōu)化
上一篇文章曾經(jīng)談到：“與普通遞歸相比，由于尾遞歸的調(diào)用處于方法的最后，因此方法之前所積累下的各種狀態(tài)對(duì)于遞歸調(diào)用結(jié)果已經(jīng)沒(méi)有任何意義，因此完全可以把本次方法中留在堆棧中的數(shù)據(jù)完全清除，把空間讓給最后的遞歸調(diào)用。這樣的優(yōu)化便使得遞歸不會(huì)在調(diào)用堆棧上產(chǎn)生堆積，意味著即時(shí)是“無(wú)限”遞歸也不會(huì)讓堆棧溢出”。這其實(shí)才是尾遞歸的“正統(tǒng)”優(yōu)化方式，那么我們先暫時(shí)忘記之前的“循環(huán)優(yōu)化”，從最簡(jiǎn)單的示例中查看這樣的優(yōu)化是如何進(jìn)行的。還是最簡(jiǎn)單的“尾遞歸”階乘：
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個(gè)參數(shù)，即n
L_0001: brtrue.s L_0005 // 如果第一個(gè)參數(shù)不為0，則跳轉(zhuǎn)到L_0005
L_0003: ldarg.1 // 運(yùn)行到此，說(shuō)明第1個(gè)參數(shù)為0，則加載第2個(gè)參數(shù)，即acc
L_0004: ret // 返回（剛加載的第2個(gè)參數(shù)）
L_0005: ldarg.0 // 加載第1個(gè)參數(shù)，即n
L_0006: ldc.i4.1 // 加載數(shù)值1
L_0007: sub // 將兩者相減，即n - 1
L_0008: ldarg.1 // 加載第2個(gè)參數(shù)，即acc
L_0009: ldarg.0 // 加載第1個(gè)參數(shù)，即n
L_000a: mul // 將兩者相乘，即acc * n
// 把n - 1和acc * n作為參數(shù)遞歸調(diào)用
L_000b: call int32 TailRecursion.Recursion::FactorialTailRecursion(int32, int32)
L_0010: ret // 返回遞歸調(diào)用結(jié)果
}
在這個(gè)問(wèn)題上，我們還需要觀察它的匯編代碼（為了不干擾文章內(nèi)容，老趙會(huì)把獲取匯編代碼的做法單獨(dú)寫(xiě)一篇文章，稍后發(fā)布），如下：
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
上面的匯編代碼非常簡(jiǎn)單，從中可以看出，每次遞歸調(diào)用都使用了最簡(jiǎn)單的call指令，沒(méi)有經(jīng)過(guò)任何有效的優(yōu)化或調(diào)整。因此在不斷地遞歸調(diào)用之后，終究會(huì)出現(xiàn)堆棧溢出。這就是普通遞歸的缺陷。而對(duì)于尾遞歸來(lái)說(shuō)，MSIL提供了額外的tail指令表示“尾調(diào)用”1，它只需簡(jiǎn)單補(bǔ)充在IL指令call, callvirt, calli之前便可。因此我們使用ildasm.exe將IL代碼dump出來(lái)，并在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重新編譯之后運(yùn)行，再重新察看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
在這里我實(shí)在無(wú)法完整講述上述匯編代碼的含義，不過(guò)從中可以看出它的確對(duì)于尾遞歸進(jìn)行了特別的處理，而并非使用簡(jiǎn)單的call指令進(jìn)行調(diào)用。對(duì)此互聯(lián)網(wǎng)上的資源也不多，老趙只找到了Shri Borde的一篇文章，其中簡(jiǎn)單描述了Whidbey V2（真早）中CLR對(duì)于這方面的處理，以及一些相關(guān)的考慮，從中似乎能夠看出一些苗頭來(lái)。
讓我們?cè)倩叵胫暗膯?wèn)題：Continuation無(wú)法通過(guò)簡(jiǎn)單優(yōu)化為循環(huán)來(lái)解決遞歸問(wèn)題。但是通過(guò)觀察可以看出，Continuation.Invoke方法中的cont委托調(diào)用是最后一條命令，這說(shuō)明它是一個(gè)“尾調(diào)用”——雖然不是“尾遞歸”，不過(guò)這已經(jīng)滿(mǎn)足tail指令的要求了：只需和所在方法返回值相同（或兼容）即可。因此，對(duì)于Continuation來(lái)說(shuō)，我們也需要進(jìn)行尾遞歸的優(yōu)化。您可以進(jìn)行嘗試，現(xiàn)在無(wú)論遞歸多“深”，都不會(huì)使堆棧溢出了。
注1：與tail類(lèi)似，IL指令jmp也能夠用于方法調(diào)用。這兩條指令都不會(huì)在調(diào)用棧上堆積數(shù)據(jù)。tail與jmp的不同之處在于，前者只需要返回值與所在方法相同或兼容即可，而后者需要簽名完全相同。您可以想象得到，對(duì)于“直接遞歸”來(lái)說(shuō)，可以使用jmp進(jìn)行調(diào)用，而普通的“尾調(diào)用”，則只能使用tail了。
NET技術(shù)：淺談尾遞歸的優(yōu)化方式，轉(zhuǎn)載需保留來(lái)源！
鄭重聲明：本文版權(quán)歸原作者所有，轉(zhuǎn)載文章僅為傳播更多信息之目的，如作者信息標(biāo)記有誤，請(qǐng)第一時(shí)間聯(lián)系我們修改或刪除，多謝。
