Использует ли Swift оптимизацию хвостового вызова? и во взаимном рекурсии?

В частности, если у меня есть следующий код:

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

Ответы

Ответ 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, но и строит другую функцию в каждом случае.

Ответ 2

Да, быстрый компилятор в некоторых случаях выполняет оптимизацию хвостового вызова:

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

В качестве глобальной функции это будет использовать постоянное пространство стека на уровне "Самый быстрый" (-O).

Если он внутри структуры, он все равно будет использовать постоянное пространство стека. Внутри класса, однако, компилятор не выполняет tco, потому что метод может быть переопределен во время выполнения.

Clang также поддерживает tco для Objective-C, но часто ARC вызывает release после рекурсивного вызова, тем самым предотвращая эту оптимизацию, см. в этой статье Джонатана Маха для более подробной информации.

ARC также, кажется, предотвращает TCO в Swift:

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

В моих тестах не было проведено TCO.