GCC & tail recursion
"Хвостова" рекурсія - це спеціальний вид рекурсії коли рекурсивний виклик це остання операція у функції. Оптимізація хвостової рекурсії - важлива властивість компіляторів і інтерпретаторів функціональних мов програмування (так як цикли у функціональному програмуванні відсутні, вони перетворюються на рекурсивні виклики). Фактично, така оптимізація це розгортання рекурсії у цикл.
До сьогоднішнього дня я не задумувався про оптимізацію хвостової рекурсії у імперативних мовах програмування, поки не знайшов ключик -foptimize-sibling-calls у gcc: "Optimize sibling and tail recursive calls.". Цей ключ автоматично включається з -O2, -O3 і -Os І воно дійсно працює!
$ cat test.c
#include
#include
int fact(int n)
{
return n == 1 ? 1 : n * fact(n - 1);
}
int main()
{
printf("%d\n", fact(10));
return EXIT_SUCCESS;
}
$ gcc ./test.c -O2 -o test
$ ./test
3628800
objdump -d дає нам такий код:
08048440 :
8048440: 55 push %ebp
8048441: b9 01 00 00 00 mov $0x1,%ecx
8048446: 89 e5 mov %esp,%ebp
8048448: 83 e4 f0 and $0xfffffff0,%esp
804844b: 83 ec 10 sub $0x10,%esp
804844e: b8 0a 00 00 00 mov $0xa,%eax
8048453: eb 05 jmp 804845a
8048455: 8d 76 00 lea 0x0(%esi),%esi
8048458: 89 d0 mov %edx,%eax
804845a: 8d 50 ff lea -0x1(%eax),%edx
804845d: 0f af c8 imul %eax,%ecx
8048460: 83 fa 01 cmp $0x1,%edx
8048463: 75 f3 jne 8048458
8048465: 89 4c 24 08 mov %ecx,0x8(%esp)
8048469: c7 44 24 04 50 85 04 movl $0x8048550,0x4(%esp)
8048470: 08
8048471: c7 04 24 01 00 00 00 movl $0x1,(%esp)
8048478: e8 af fe ff ff call 804832c
804847d: 31 c0 xor %eax,%eax
804847f: c9 leave
8048480: c3 ret
Рекурсивний виклик розгорнуто у цикл. При чому спочатку рекурсія розгорнута у цикл, а потім він за-inline-нений у main. При компілації з -O1 (або взагалі без оптимізації) маємо такий код:
0804842c :
804842c: 55 push %ebp
804842d: 89 e5 mov %esp,%ebp
804842f: 83 e4 f0 and $0xfffffff0,%esp
8048432: 83 ec 10 sub $0x10,%esp
8048435: c7 04 24 0a 00 00 00 movl $0xa,(%esp)
804843c: e8 c3 ff ff ff call 8048404
8048441: 89 44 24 08 mov %eax,0x8(%esp)
8048445: c7 44 24 04 20 85 04 movl $0x8048520,0x4(%esp)
804844c: 08
804844d: c7 04 24 01 00 00 00 movl $0x1,(%esp)
8048454: e8 d3 fe ff ff call 804832c
8048459: b8 00 00 00 00 mov $0x0,%eax
804845e: c9 leave
804845f: c3 ret
Ну і нарешті при компілації з -O2 -fno-inline маємо:
08048410 :
8048410: 55 push %ebp
8048411: b8 01 00 00 00 mov $0x1,%eax
8048416: 89 e5 mov %esp,%ebp
8048418: 8b 55 08 mov 0x8(%ebp),%edx
804841b: 83 fa 01 cmp $0x1,%edx
804841e: 75 0a jne 804842a
8048420: eb 13 jmp 8048435
8048422: 8d b6 00 00 00 00 lea 0x0(%esi),%esi
8048428: 89 ca mov %ecx,%edx
804842a: 8d 4a ff lea -0x1(%edx),%ecx
804842d: 0f af c2 imul %edx,%eax
8048430: 83 f9 01 cmp $0x1,%ecx
8048433: 75 f3 jne 8048428
8048435: 5d pop %ebp
8048436: c3 ret
8048437: 89 f6 mov %esi,%esi
8048439: 8d bc 27 00 00 00 00 lea 0x0(%edi,%eiz,1),%edi
08048440 :
8048440: 55 push %ebp
8048441: 89 e5 mov %esp,%ebp
8048443: 83 e4 f0 and $0xfffffff0,%esp
8048446: 83 ec 10 sub $0x10,%esp
8048449: c7 04 24 0a 00 00 00 movl $0xa,(%esp)
8048450: e8 bb ff ff ff call 8048410
8048455: c7 44 24 04 40 85 04 movl $0x8048540,0x4(%esp)
804845c: 08
804845d: c7 04 24 01 00 00 00 movl $0x1,(%esp)
8048464: 89 44 24 08 mov %eax,0x8(%esp)
8048468: e8 bf fe ff ff call 804832c
804846d: 31 c0 xor %eax,%eax
804846f: c9 leave
8048470: c3 ret
До сьогоднішнього дня я не задумувався про оптимізацію хвостової рекурсії у імперативних мовах програмування, поки не знайшов ключик -foptimize-sibling-calls у gcc: "Optimize sibling and tail recursive calls.". Цей ключ автоматично включається з -O2, -O3 і -Os І воно дійсно працює!
$ cat test.c
#include
#include
int fact(int n)
{
return n == 1 ? 1 : n * fact(n - 1);
}
int main()
{
printf("%d\n", fact(10));
return EXIT_SUCCESS;
}
$ gcc ./test.c -O2 -o test
$ ./test
3628800
objdump -d дає нам такий код:
08048440 :
8048440: 55 push %ebp
8048441: b9 01 00 00 00 mov $0x1,%ecx
8048446: 89 e5 mov %esp,%ebp
8048448: 83 e4 f0 and $0xfffffff0,%esp
804844b: 83 ec 10 sub $0x10,%esp
804844e: b8 0a 00 00 00 mov $0xa,%eax
8048453: eb 05 jmp 804845a
8048455: 8d 76 00 lea 0x0(%esi),%esi
8048458: 89 d0 mov %edx,%eax
804845a: 8d 50 ff lea -0x1(%eax),%edx
804845d: 0f af c8 imul %eax,%ecx
8048460: 83 fa 01 cmp $0x1,%edx
8048463: 75 f3 jne 8048458
8048465: 89 4c 24 08 mov %ecx,0x8(%esp)
8048469: c7 44 24 04 50 85 04 movl $0x8048550,0x4(%esp)
8048470: 08
8048471: c7 04 24 01 00 00 00 movl $0x1,(%esp)
8048478: e8 af fe ff ff call 804832c
804847d: 31 c0 xor %eax,%eax
804847f: c9 leave
8048480: c3 ret
Рекурсивний виклик розгорнуто у цикл. При чому спочатку рекурсія розгорнута у цикл, а потім він за-inline-нений у main. При компілації з -O1 (або взагалі без оптимізації) маємо такий код:
0804842c :
804842c: 55 push %ebp
804842d: 89 e5 mov %esp,%ebp
804842f: 83 e4 f0 and $0xfffffff0,%esp
8048432: 83 ec 10 sub $0x10,%esp
8048435: c7 04 24 0a 00 00 00 movl $0xa,(%esp)
804843c: e8 c3 ff ff ff call 8048404
8048441: 89 44 24 08 mov %eax,0x8(%esp)
8048445: c7 44 24 04 20 85 04 movl $0x8048520,0x4(%esp)
804844c: 08
804844d: c7 04 24 01 00 00 00 movl $0x1,(%esp)
8048454: e8 d3 fe ff ff call 804832c
8048459: b8 00 00 00 00 mov $0x0,%eax
804845e: c9 leave
804845f: c3 ret
Ну і нарешті при компілації з -O2 -fno-inline маємо:
08048410 :
8048410: 55 push %ebp
8048411: b8 01 00 00 00 mov $0x1,%eax
8048416: 89 e5 mov %esp,%ebp
8048418: 8b 55 08 mov 0x8(%ebp),%edx
804841b: 83 fa 01 cmp $0x1,%edx
804841e: 75 0a jne 804842a
8048420: eb 13 jmp 8048435
8048422: 8d b6 00 00 00 00 lea 0x0(%esi),%esi
8048428: 89 ca mov %ecx,%edx
804842a: 8d 4a ff lea -0x1(%edx),%ecx
804842d: 0f af c2 imul %edx,%eax
8048430: 83 f9 01 cmp $0x1,%ecx
8048433: 75 f3 jne 8048428
8048435: 5d pop %ebp
8048436: c3 ret
8048437: 89 f6 mov %esi,%esi
8048439: 8d bc 27 00 00 00 00 lea 0x0(%edi,%eiz,1),%edi
08048440 :
8048440: 55 push %ebp
8048441: 89 e5 mov %esp,%ebp
8048443: 83 e4 f0 and $0xfffffff0,%esp
8048446: 83 ec 10 sub $0x10,%esp
8048449: c7 04 24 0a 00 00 00 movl $0xa,(%esp)
8048450: e8 bb ff ff ff call 8048410
8048455: c7 44 24 04 40 85 04 movl $0x8048540,0x4(%esp)
804845c: 08
804845d: c7 04 24 01 00 00 00 movl $0x1,(%esp)
8048464: 89 44 24 08 mov %eax,0x8(%esp)
8048468: e8 bf fe ff ff call 804832c
804846d: 31 c0 xor %eax,%eax
804846f: c9 leave
8048470: c3 ret