fig 1. C++ 函數式編程
有一陣時間, 沒有去研究一個技術主題之後, 我又回到了 revursive 上, 這是在讀 SICP 之後才注意到的技術。
但是 revursive 實在太難, 我還沒能掌握這個思考方式。
甚至連 tail call (tail recursive) 都搞不清楚, 後來在閱讀了「C++ 函數式編程 (Functional Programming in C++: How to improve your C++ programs using functional techniques)」(fig 1) 之後, 才知道就是字面上的意思。
而只有 tail call 才能讓編譯器有機會轉成 loop, 避免使用 stack。
一般看到的文章都說編譯器會把 tail call 轉成 loop, 而不使用 stack 空間, 避免 stack 爆掉, 這是真的嗎?
要怎麼確認呢?
就像 inline function, 我要怎麼確認真的有 inline 呢?
如果編譯器沒有給出明確訊息, 似乎也只能看編譯器輸出的組合語言了。
我用了 sum.c 來測試, 這個程式就是把 arr[0] ~ arr[4] 印出來, 只是我用了 recursive function 印出, 而不是用 for loop。
這個程式符合 tail call, call 自己的那行程式是在程式的最尾端, 所以應該可以被編譯器最佳化為 loop 才是。但如果沒下什麼編譯選項的話, 是看不到這樣的結果的。
list 1. sum.c
1 #include <stdio.h>
2
3 void print(int *array, int len, int n)
4 {
5 if (n >= len)
6 {
7 return;
8 }
9 else
10 {
11 printf("n: %d, %d\n", n, array[n]);
12 return print(array, len, n+1);
13 }
14 }
15
16 int main(int argc, char *argv[])
17 {
18 int arr[] = {1,2,3,4,5,};
19 print(arr, 5, 0);
20 return 0;
21 }
而和 tail recursive calls 有關的編譯選項是 -foptimize-sibling-calls。
-foptimize-sibling-calls
Optimize sibling and tail recursive calls.
Enabled at levels -O2, -O3, -Os.
但是很奇怪, 如果使用 -foptimize-sibling-calls 反而不會輸出 Optimize tail recursive calls 的組合語言, 需要用 -Os 才會將 tail recursive calls 轉成 loop。
gcc -no-pie -m32 sum.c -g -Os -o sum.tc.opt
gcc -no-pie -m32 sum.c -g -foptimize-sibling-calls -o sum.no.tc.opt
list 2 L37, 在 print() 裡頭還是會 call print()
list 2. sum.no.tc.opt.txt
3
4 sum.no.tc.opt: file format elf32-i386
5
6
7
8 08049162 <print>:
9 8049162: 55 push %ebp
10 8049163: 89 e5 mov %esp,%ebp
11 8049165: 53 push %ebx
12 8049166: 83 ec 04 sub $0x4,%esp
13 8049169: e8 b4 00 00 00 call 8049222 <__x86.get_pc_thunk.ax>
14 804916e: 05 92 2e 00 00 add $0x2e92,%eax
15 8049173: 8b 55 10 mov 0x10(%ebp),%edx
16 8049176: 3b 55 0c cmp 0xc(%ebp),%edx
17 8049179: 7d 43 jge 80491be <print+0x5c>
18 804917b: 8b 55 10 mov 0x10(%ebp),%edx
19 804917e: 8d 0c 95 00 00 00 00 lea 0x0(,%edx,4),%ecx
20 8049185: 8b 55 08 mov 0x8(%ebp),%edx
21 8049188: 01 ca add %ecx,%edx
22 804918a: 8b 12 mov (%edx),%edx
23 804918c: 83 ec 04 sub $0x4,%esp
24 804918f: 52 push %edx
25 8049190: ff 75 10 pushl 0x10(%ebp)
26 8049193: 8d 90 08 e0 ff ff lea -0x1ff8(%eax),%edx
27 8049199: 52 push %edx
28 804919a: 89 c3 mov %eax,%ebx
29 804919c: e8 8f fe ff ff call 8049030 <printf@plt>
30 80491a1: 83 c4 10 add $0x10,%esp
31 80491a4: 8b 45 10 mov 0x10(%ebp),%eax
32 80491a7: 83 c0 01 add $0x1,%eax
33 80491aa: 83 ec 04 sub $0x4,%esp
34 80491ad: 50 push %eax
35 80491ae: ff 75 0c pushl 0xc(%ebp)
36 80491b1: ff 75 08 pushl 0x8(%ebp)
37 80491b4: e8 a9 ff ff ff call 8049162 <print>38 80491b9: 83 c4 10 add $0x10,%esp
39 80491bc: eb 01 jmp 80491bf <print+0x5d>
40 80491be: 90 nop
41 80491bf: 8b 5d fc mov -0x4(%ebp),%ebx
42 80491c2: c9 leave
43 80491c3: c3 ret
44
45 080491c4 <main>:
46 80491c4: 8d 4c 24 04 lea 0x4(%esp),%ecx
47 80491c8: 83 e4 f0 and $0xfffffff0,%esp
48 80491cb: ff 71 fc pushl -0x4(%ecx)
49 80491ce: 55 push %ebp
50 80491cf: 89 e5 mov %esp,%ebp
51 80491d1: 51 push %ecx
52 80491d2: 83 ec 24 sub $0x24,%esp
53 80491d5: e8 48 00 00 00 call 8049222 <__x86.get_pc_thunk.ax>
54 80491da: 05 26 2e 00 00 add $0x2e26,%eax
55 80491df: c7 45 e4 01 00 00 00 movl $0x1,-0x1c(%ebp)
56 80491e6: c7 45 e8 02 00 00 00 movl $0x2,-0x18(%ebp)
57 80491ed: c7 45 ec 03 00 00 00 movl $0x3,-0x14(%ebp)
58 80491f4: c7 45 f0 04 00 00 00 movl $0x4,-0x10(%ebp)
59 80491fb: c7 45 f4 05 00 00 00 movl $0x5,-0xc(%ebp)
60 8049202: 83 ec 04 sub $0x4,%esp
61 8049205: 6a 00 push $0x0
62 8049207: 6a 05 push $0x5
63 8049209: 8d 45 e4 lea -0x1c(%ebp),%eax
64 804920c: 50 push %eax
65 804920d: e8 50 ff ff ff call 8049162 <print>
66 8049212: 83 c4 10 add $0x10,%esp
67 8049215: b8 00 00 00 00 mov $0x0,%eax
68 804921a: 8b 4d fc mov -0x4(%ebp),%ecx
69 804921d: c9 leave
70 804921e: 8d 61 fc lea -0x4(%ecx),%esp
71 8049221: c3 ret
list 3 L65, 在 print() 是用 jmp 回到前面一個點 (L55), 就是 loop 的動作。
list 3. sum.tc.opt.txt
1
2 sum.tc.opt: file format elf32-i386
3
4
5
6 Disassembly of section .text:
7
8 08049050 <main>:
9 8049050: e8 9b 01 00 00 call 80491f0 <__x86.get_pc_thunk.ax>
10 8049055: 05 ab 2f 00 00 add $0x2fab,%eax
11 804905a: 8d 4c 24 04 lea 0x4(%esp),%ecx
12 804905e: 83 e4 f0 and $0xfffffff0,%esp
13 8049061: ff 71 fc pushl -0x4(%ecx)
14 8049064: 55 push %ebp
15 8049065: 89 e5 mov %esp,%ebp
16 8049067: 57 push %edi
17 8049068: 56 push %esi
18 8049069: 8d b0 14 e0 ff ff lea -0x1fec(%eax),%esi
19 804906f: 8d 45 d4 lea -0x2c(%ebp),%eax
20 8049072: 51 push %ecx
21 8049073: 8d 7d d4 lea -0x2c(%ebp),%edi
22 8049076: b9 05 00 00 00 mov $0x5,%ecx
23 804907b: 83 ec 30 sub $0x30,%esp
24 804907e: f3 a5 rep movsl %ds:(%esi),%es:(%edi)
25 8049080: 6a 00 push $0x0
26 8049082: 6a 05 push $0x5
27 8049084: 50 push %eax
28 8049085: e8 28 01 00 00 call 80491b2 <print>
29 804908a: 8d 65 f4 lea -0xc(%ebp),%esp
30 804908d: 31 c0 xor %eax,%eax
31 804908f: 59 pop %ecx
32 8049090: 5e pop %esi
33 8049091: 5f pop %edi
34 8049092: 5d pop %ebp
35 8049093: 8d 61 fc lea -0x4(%ecx),%esp
36 8049096: c3 ret
37 8049097: 66 90 xchg %ax,%ax
38 8049099: 66 90 xchg %ax,%ax
39 804909b: 66 90 xchg %ax,%ax
40 804909d: 66 90 xchg %ax,%ax
41 804909f: 90 nop
42
43
44 080491b2 <print>:
45 80491b2: 55 push %ebp
46 80491b3: 89 e5 mov %esp,%ebp
47 80491b5: 57 push %edi
48 80491b6: 56 push %esi
49 80491b7: 53 push %ebx
50 80491b8: e8 33 ff ff ff call 80490f0 <__x86.get_pc_thunk.bx>
51 80491bd: 81 c3 43 2e 00 00 add $0x2e43,%ebx
52 80491c3: 83 ec 0c sub $0xc,%esp
53 80491c6: 8b 75 10 mov 0x10(%ebp),%esi
54 80491c9: 8d bb 08 e0 ff ff lea -0x1ff8(%ebx),%edi
55 80491cf: 3b 75 0c cmp 0xc(%ebp),%esi56 80491d2: 7d 14 jge 80491e8 <print+0x36>
57 80491d4: 50 push %eax
58 80491d5: 8b 45 08 mov 0x8(%ebp),%eax
59 80491d8: ff 34 b0 pushl (%eax,%esi,4)
60 80491db: 56 push %esi
61 80491dc: 46 inc %esi
62 80491dd: 57 push %edi
63 80491de: e8 4d fe ff ff call 8049030 <printf@plt>
64 80491e3: 83 c4 10 add $0x10,%esp
65 80491e6: eb e7 jmp 80491cf <print+0x1d>66 80491e8: 8d 65 f4 lea -0xc(%ebp),%esp
67 80491eb: 5b pop %ebx
68 80491ec: 5e pop %esi
69 80491ed: 5f pop %edi
70 80491ee: 5d pop %ebp
71 80491ef: c3 ret
看到這樣的結果就安心了, 真的是像文章上說的一樣, 有做 tail recursive calls Optimization。
ref:
