¿Swift implementa la optimización de llamadas de cola? ¿Y en caso de recursión mutua?

tail-call-optimization

Question

En particular si tengo el siguiente código:

func sum(n: Int, acc: Int) -> Int {
if n == 0 { return acc }
else { return sum(n - 1, acc + n) }
}

¿El compilador Swift lo optimizará a un bucle? ¿Y es así en un caso más interesante a continuación?

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) }
}

Answer 1

La mejor manera de verificar es examinar el código de lenguaje ensamblador generado por el compilador. Tomé el código de arriba y lo compilé con:

swift -O3 -S tco.swift >tco.asm

La parte relevante de la salida.

.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

No hay instrucciones de llamada en el código generado, solo saltos condicionales ( je / jne / jo / jno ). Esto sugiere claramente que Swift hace optimizaciones de llamadas de cola en ambos casos.

Además, las funciones isOdd / isEven son interesantes porque el compilador no solo parece realizar el TCO, sino que también incorpora la otra función en cada caso.

Answer 2

Sí, el compilador swift realiza la optimización de la llamada de cola en algunos casos:

func sum(n: Int, acc: Int) -> Int {
if n == 0 { return acc }
else { return sum(n - 1, acc: acc + 1) }
}

Como una función global, utilizará espacio de pila constante en el nivel de optimización "más rápido" ( -O ).

Si está dentro de una estructura, seguirá utilizando un espacio de pila constante. Sin embargo, dentro de una clase, el compilador no realiza tco porque el método podría ser anulado en tiempo de ejecución.

Clang también admite tco para Objective-C, pero a menudo el release llamadas ARC después de la llamada recursiva, lo que evita esta optimización, consulte este artículo de Jonathon Mah para obtener más detalles.

ARC también parece prevenir el TCO en Swift:

func sum(n: Int, acc: Int, s: String?) -> Int {
if n == 0 { return acc }
else { return sum(n - 1, acc + 1, s) }
}

No se realizó TCO en mis pruebas.