In particular if I have the following code:
func sum(n: Int, acc: Int) -> Int {
if n == 0 { return acc }
else { return sum(n - 1, acc + n) }
}
Will Swift compiler optimize it to a loop? And does it so in a more interesting case below?
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) }
}
The best way to check is to examine the assembly language code generated by the compiler. I took the code above and compiled it with:
swift -O3 -S tco.swift >tco.asm
The relevant part of the output
.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
There are no call instructions in the generated code, only conditional jumps (je
/ jne
/ jo
/ jno
). This clearly suggests that Swift does do tail call optimizations in both cases.
In addition, the isOdd
/isEven
functions are interesting in that the compiler not only seems to perform TCO but also inlines the other function in each case.
Yes, the swift compiler performs tail call optimisation in some cases:
func sum(n: Int, acc: Int) -> Int {
if n == 0 { return acc }
else { return sum(n - 1, acc: acc + 1) }
}
As a global function, this will use constant stack space on the "Fastest" optimisation level (-O
).
If it is inside a struct it will still use constant stack space. Within a class however, the compiler does not perform tco because the method might be overridden at runtime.
Clang also supports tco for Objective-C but often ARC calls release
after the recursive call, thus preventing this optimisation, see this article by Jonathon Mah for more details.
ARC also seems to prevent TCO in Swift:
func sum(n: Int, acc: Int, s: String?) -> Int {
if n == 0 { return acc }
else { return sum(n - 1, acc + 1, s) }
}
No TCO was performed in my tests.