特别是如果我有以下代码:
func sum(n: Int, acc: Int) -> Int {
if n == 0 { return acc }
else { return sum(n - 1, acc + n) }
}
Swift编译器会把它优化成一个循环吗?在下面的一个更有趣的例子中也是如此吗?
func isOdd(n: Int) -> Bool {
if n == 0 { return false; }
else { return isEven(n - 1) }
}
func isEven(n: Int) -> Bool {
if n == 0 { return true }
else { return isOdd(n - 1) }
}
最好的检查方法是检查编译器生成的汇编语言代码。我将上面的代码编译为:
swift -O3 -S tco.swift >tco.asm
输出的相关部分
.globl __TF3tco3sumFTSiSi_Si
.align 4, 0x90
__TF3tco3sumFTSiSi_Si:
pushq %rbp
movq %rsp, %rbp
testq %rdi, %rdi
je LBB0_4
.align 4, 0x90
LBB0_1:
movq %rdi, %rax
decq %rax
jo LBB0_5
addq %rdi, %rsi
jo LBB0_5
testq %rax, %rax
movq %rax, %rdi
jne LBB0_1
LBB0_4:
movq %rsi, %rax
popq %rbp
retq
LBB0_5:
ud2
.globl __TF3tco5isOddFSiSb
.align 4, 0x90
__TF3tco5isOddFSiSb:
pushq %rbp
movq %rsp, %rbp
testq %rdi, %rdi
je LBB1_1
decq %rdi
jo LBB1_9
movb $1, %al
LBB1_5:
testq %rdi, %rdi
je LBB1_2
decq %rdi
jo LBB1_9
testq %rdi, %rdi
je LBB1_1
decq %rdi
jno LBB1_5
LBB1_9:
ud2
LBB1_1:
xorl %eax, %eax
LBB1_2:
popq %rbp
retq
.globl __TF3tco6isEvenFSiSb
.align 4, 0x90
__TF3tco6isEvenFSiSb:
pushq %rbp
movq %rsp, %rbp
movb $1, %al
LBB2_1:
testq %rdi, %rdi
je LBB2_5
decq %rdi
jo LBB2_7
testq %rdi, %rdi
je LBB2_4
decq %rdi
jno LBB2_1
LBB2_7:
ud2
LBB2_4:
xorl %eax, %eax
LBB2_5:
popq %rbp
retq
生成的代码中没有调用指令,只有条件跳转(je
/jne
/jo
/jno
)。这清楚地表明Swift在和情况下都做了尾部调用优化。
此外,isOdd
/isEven
函数很有趣,因为编译器不仅执行TCO,而且在每种情况下都内联其他函数。
是的,swift编译器在某些情况下执行尾部调用优化:
func sum(n: Int, acc: Int) -> Int {
if n == 0 { return acc }
else { return sum(n - 1, acc: acc + 1) }
}
作为一个全局函数,这将在"最快"优化级别(-O
)上使用恒定的堆栈空间。
如果它在结构体中,它仍然会使用常量堆栈空间。但是,在类中,编译器不会执行tco,因为该方法可能在运行时被重写。
Clang也支持Objective-C的tco,但是ARC经常在递归调用之后调用release
,从而阻止了这种优化,参见Jonathon Mah的文章了解更多细节。
ARC似乎也阻止了Swift中的TCO:
func sum(n: Int, acc: Int, s: String?) -> Int {
if n == 0 { return acc }
else { return sum(n - 1, acc + 1, s) }
}
在我的测试中没有执行TCO。