76

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) }
}
6
  • 2
    The stack's only so big. What happens when you run an infinitely recursive function? Does it crash?
    – Veedrac
    Commented Jun 3, 2014 at 19:49
  • @Veedrac: It's apple. It will be converted to a loop and gets back a deterministic result. Commented Jun 3, 2014 at 20:03
  • 5
    @Veedrac - that's a given. But a functional programmer doing infinite recursion would be like an imperative programmer doing a for loop without a test clause, e.g. for (int i = 0; ; i++) { println("%d", i); }.
    – Yawar
    Commented Jun 17, 2014 at 23:12
  • 6
    @Veedrac my point is a functional programmer is no more likely to do infinite recursion than an imperative programmer is to do an infinite loop.
    – Yawar
    Commented Jan 3, 2015 at 2:16
  • 3
    Regarding the standalone question "Does Swift implement tail call optimization?" The short answer is "Swift doesn’t guarantee tail call optimization, so don’t rely on it". However, if you are doing recursion, you might as well attempt TCO as the compiler may well assist ;)
    – arcseldon
    Commented Dec 6, 2015 at 14:01

2 Answers 2

83

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.

5
  • 4
    Oh, your word "clearly" makes me feel like a total dummy. But thanks for investigation- I'm sure it's pretty obvious if you know ASM.
    – skywinder
    Commented Jul 19, 2017 at 9:59
  • 2
    @skywinder - sorry about that. What I meant was that there are no call instructions in the generated code, only conditional jumps (je / jne / jo / jno)
    – Ferruccio
    Commented Jul 19, 2017 at 10:13
  • Much appreciated!
    – skywinder
    Commented Jul 19, 2017 at 11:11
  • 1
    You don't really have to know ASM to understand Ferruccio's analysis. An understanding of the basics of how stacks are used is sufficient. A call instruction is a subroutine/function/method call. Those push the return address (and any parameters) onto the stack. Jump instructions don't push anything onto the stack, and so they can't lead to potential stack overflows.
    – Duncan C
    Commented Dec 11, 2020 at 13:23
  • 1
    I don't think the best way is to check the assembly code, on the contrary. If the Swift spec doesn't guarantee TCO, then whether or not it happens is implementation detail, subject to change without notice. Your application may work today, to eventually be recompiled with a new compiler version, possibly breaking. Commented Jun 25, 2022 at 18:52
26

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.

4
  • Do you mean that the same TCO caveats Jonathon Mah describes for Obj-C apply to Swift compiler in the current (1.0) version?
    – Palimondo
    Commented Jun 17, 2014 at 13:55
  • @Palimondo Unfortunately, that's what it looks like to me.
    – Sebastian
    Commented Jun 17, 2014 at 22:08
  • 7
    I wouldn't say that ARC prevents TCO, but rather that since ARC has to add a release call before returning from a function, the recursive call is no longer in the tail position.
    – Ferruccio
    Commented Jul 20, 2014 at 13:46
  • @Sebastian, so from what I understand, TCO works for cases where no references are involved i.e. calling functions and methods on structs is fine but methods on classes get released and therefore are not optimized? Or are functions copied by reference and therefore subject to ARC? Commented Jan 28, 2023 at 6:00

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.