d-0w0-b: [GCC神奇研究] GCC對遞迴的最佳化

我很喜歡functional programming的風格, 喜歡玩遞迴
但是一般會說在C裡面使用迴圈會比遞迴有效率
就讓我們來實驗一下GCC 對遞迴的處理吧！

為什麼說遞迴的成本會比迴圈高呢?

因為遞迴會一直做function call，這有不小的 overhaed
每次call function時, 都會複製參數.重新產生區域變數　疊到Stack上
這得付出一定的成本

一些functional language為了提升遞迴的效率，會幫你把遞迴轉換成迴圈以提升效率
以scheme為例，求N階層的function可以這樣寫：

(define (fac n)
  (if (<= n 0)
      1
      (* n fac((- n 1)))))

稍微解說一下，在scheme中 if 的結構是這樣的：
(if X a b)
如果X為 true , 則a, 否則 b
所以上面的程式碼寫成大家看得懂得python形式就是：

def fac(n):
  if n <= 0:
    return 1
  else:
    return fac(n-1)

然而scheme中有 "尾端遞迴"最佳化的機制，
只要把遞迴寫成尾端遞迴的形式，scheme就可以幫你把遞迴轉換程成迴圈形式以提高效率
像上面的求階層程式改程尾端遞迴的話就是這樣：

(define (fac n)
  (define (iter product i)
    (if (> i n)
        product
        (iter (* i product)
              (+ i 1))))
  (iter 1 1))

雖然可讀性稍微差了點，不過可以得到更好的效率

尾端遞迴的優化不在C的標準中，
但我們可以來看看大家最常使用的編譯器GCC(the GNU Compiler Collection)能為我們做什麼

一樣求階層的C程式：

/* fac_1.c */
int fac(int n){
    if(n <= 0)
        return 1;
    else
        return n * fac(n-1);
}

如果我們把他寫成尾端遞迴的形式：

/* fac_2.c */
int fac(int n, int product){
    if(n <= 0)
        return product;
    else
        return fac(n-1, product * n);
}

(在呼叫的時候要傳 fac(n, 1))

我們可以打這個指令讓GCC把C編譯成組合語言：

gcc fac_2.c -S -c

產生 fac_2.s 內容如下：

.file    "fac_2.c"
    .text
    .globl    fac
    .type    fac, @function
fac:
.LFB0:
    .cfi_startproc
    pushq    %rbp
    .cfi_def_cfa_offset 16
    .cfi_offset 6, -16
    movq    %rsp, %rbp
    .cfi_def_cfa_register 6
    subq    $16, %rsp
    movl    %edi, -4(%rbp)
    movl    %esi, -8(%rbp)
    cmpl    $0, -4(%rbp)
    jg    .L2
    movl    -8(%rbp), %eax
    jmp    .L3
.L2:
    movl    -8(%rbp), %eax
    imull    -4(%rbp), %eax
    movl    -4(%rbp), %edx
    subl    $1, %edx
    movl    %eax, %esi
    movl    %edx, %edi
    call    fac
.L3:
    leave
    .cfi_def_cfa 7, 8
    ret
    .cfi_endproc
.LFE0:
    .size    fac, .-fac
    .ident    "GCC: (Ubuntu/Linaro 4.6.3-1ubuntu5) 4.6.3"
    .section    .note.GNU-stack,"",@progbits

這個比較長就懶得解釋，產生出來的內容就是如我們預期的沒有做最佳化(我還沒下參數)
老老實實的做條件判斷然後選擇回傳 1 或是 n * fac(n-1)
也就是遞迴的做法-- 不斷地 call function 直到符合結束條件

接著我們來下最佳化參數 :
gcc fac_2.c -S -c -O2

產生的組合語言程式如下：

.file    "fac_2.c"
    .text
    .p2align 4,,15
    .globl    fac
    .type    fac, @function
fac:
.LFB0:
    .cfi_startproc
    testl    %edi, %edi
    movl    %esi, %eax
    jle    .L2
    .p2align 4,,10
    .p2align 3
.L4:
    imull    %edi, %eax
    subl    $1, %edi
    jne    .L4
.L2:
    rep
    ret
    .cfi_endproc
.LFE0:
    .size    fac, .-fac
    .ident    "GCC: (Ubuntu/Linaro 4.6.3-1ubuntu5) 4.6.3"
    .section    .note.GNU-stack,"",@progbits

很明顯的可以看出裡面沒有 call fac 這個呼叫自己的命令了

這次我來認真的翻譯組合語言吧，內容可以轉成下面的意思
eax, edi, esi都是暫存器名稱，我就寫成 a, d, s 大家可以當成變數看

int fac(int d, int s)
{int a;
    a = s;
    if(d <= 0) goto L2;
  
  L4:
    a = a * d;
    d = d -1;
    if(d != 0) goto L4;
    
  L2:
    return a;
}

這是一個迴圈型的程式，很神奇吧！

那如果是前一個沒有寫成尾端遞迴的程式呢？
我們來看一下 :
gcc fac_1.c -S -c -O2

得到的結果是：

.file    "fac_2.c"
    .text
    .p2align 4,,15
    .globl    fac
    .type    fac, @function
fac:
.LFB0:
    .cfi_startproc
    testl    %edi, %edi
    movl    %esi, %eax
    jle    .L2
    .p2align 4,,10
    .p2align 3
.L4:
    imull    %edi, %eax
    subl    $1, %edi
    jne    .L4
.L2:
    rep
    ret
    .cfi_endproc
.LFE0:
    .size    fac, .-fac
    .ident    "GCC: (Ubuntu/Linaro 4.6.3-1ubuntu5) 4.6.3"
    .section    .note.GNU-stack,"",@progbits