¿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.