[Swift] Tail Call Optimization / TCO / 꼬리재귀

 

꼬리 재귀 최적화란?

꼬리 재귀 최적화는 컴파일러가 꼬리 호출(tail call), 즉 함수의 마지막 동작이 함수 호출인 경우, 새로운 스택 프레임을 생성하는 대신 현재의 스택 프레임을 재사용하여 함수를 호출하는 최적화 기법이다. 이 최적화를 통해 함수 호출에 따른 오버헤드를 줄이고, 스택 오버플로우의 위험을 감소시킨다.

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

print(sumPrefix(1000000, 0))

 

해당 재귀를 부르면 어떻게 될까 ? 

- 대부분의 정답은 어느정도 depth를 들어가다가 한계를 맞이하고 segmentfault를 띄울 것 이다. 라고 대답할 것이라 생각한다.

그런데 이 정답은 틀렸다.

왜냐하면 컴파일러 최적화 옵션을 킨다면 해당 함수는 아래 asm과 같이 반복문 형태로 변경된다.

이 함수는 주어진 숫자 n이 0이 될 때까지 자기 자신을 호출하면서 acc 매개변수에 n을 더해 가며 최종적으로 합계를 반환한다. 하지만 이 함수의 ARM 아키텍처용 어셈블리 코드를 살펴보면, 직접적인 함수 호출 대신에 점프 명령(b)을 사용하여 재귀 호출을 구현하고 있다. 이러한 변환은 특히 재귀 함수를 최적화하는 과정에서 발생할 수 있으며, 이를 "꼬리 재귀 최적화(tail recursion optimization)"라고 한다.

_$s4main9sumPrefixyS2i_SitF:
    .cfi_startproc
    cbz x0, LBB1_4        ; if n == 0, jump to LBB1_4
LBB1_1:
    subs x8, x0, #1       ; x8 = n - 1
    b.vs LBB1_5           ; branch if overflow
    adds x1, x1, x0       ; acc = acc + n
    b.vs LBB1_6           ; branch if overflow
    mov x0, x8            ; update n
    cbnz x8, LBB1_1       ; if x8 != 0, jump to LBB1_1
LBB1_4:
    mov x0, x1            ; return acc
    ret
LBB1_5:
    brk #0x1              ; breakpoint (error handling)
LBB1_6:
    brk #0x1              ; breakpoint (error handling)

 

컴파일러 최적화 옵션을 의도적으로 끄고 실행시킨 모습.

xcrun swiftc -Onone main.swift
chan@chanhihi swift_practise % ./main                        
zsh: segmentation fault  ./main

ASM

stp   x29, x30, [sp, #-16]!      ; 스택에 현재 프레임 포인터와 링크 레지스터를 저장하고 스택 포인터 갱신
mov   x29, sp                    ; 프레임 포인터를 스택 포인터로 설정
mov   w8, #16960                 ; w8에 16960 저장
movk  w8, #15, lsl #16           ; w8에 상위 16비트 설정하여 w8에 1000000 저장
mov   x0, x8                     ; x0에 w8(1000000) 복사
mov   x1, #0                     ; x1에 0 저장
bl    _$s4main9sumPrefixyS2i_SitF; sumPrefix 함수 호출
mov   w0, #0                     ; 반환 값으로 0 설정
ldp   x29, x30, [sp], #16        ; 프레임 포인터와 링크 레지스터 복원 및 스택 포인터 갱신
ret                              ; 함수 리턴

sub   sp, sp, #80                ; 스택에 80바이트 공간 확보
stp   x29, x30, [sp, #64]        ; 현재 프레임 포인터와 링크 레지스터 스택에 저장
add   x29, sp, #64               ; 프레임 포인터 업데이트
str   x0, [sp, #32]              ; x0(n)을 스택에 저장
stur  x1, [x29, #-24]            ; x1(acc)를 스택에 저장
subs  x8, x0, #0                 ; x0에서 0을 빼서 x8에 저장
cset  w8, ne                    ; x8이 0이 아니면 w8을 1로 설정
tbnz  w8, #0, LBB1_2             ; w8의 0번 비트가 1이면 LBB1_2로 점프
b     LBB1_1                     ; 그렇지 않으면 LBB1_1로 점프
LBB1_1:
ldur  x0, [x29, #-24]            ; x0에 저장된 acc 값을 불러옴
str   x0, [sp, #24]              ; x0(acc)를 스택에 저장
b     LBB1_5                     ; LBB1_5로 점프
LBB1_2:
ldr   x8, [sp, #32]              ; 스택에서 n 값을 x8에 불러옴
subs  x8, x8, #1                 ; x8에서 1 빼기
str   x8, [sp, #16]              ; 변경된 n을 스택에 저장
cset  w8, vs                    ; 오버플로우 발생 시 w8을 1로 설정
tbnz  w8, #0, LBB1_6             ; 오버플로우가 있으면 LBB1_6로 점프
b     LBB1_3                     ; 오버플로우가 없으면 LBB1_3으로 점프
LBB1_3:
ldur  x8, [x29, #-24]            ; acc 값을 x8에 불러옴
ldr   x9, [sp, #32]              ; n 값을 x9에 불러옴
adds  x8, x8, x9                 ; x8(acc)에 x9(n)를 더함
str   x8, [sp, #8]               ; 결과를 스택에 저장
cset  w8, vs                    ; 오버플로우 발생 시 w8을 1로 설정
tbnz  w8, #0, LBB1_7             ; 오버플로우가 있으면 LBB1_7로 점프
b     LBB1_4                     ; 오버플로우가 없으면 LBB1_4로 점프
LBB1_4:
ldr   x1, [sp, #8]               ; 변경된 acc 값을 x1에 불러옴
ldr   x0, [sp, #16]              ; 변경된 n 값을 x0에 불러옴
bl    _$s4main9sumPrefixyS2i_SitF; 재귀 호출
str   x0, [sp, #24]              ; 결과를 스택에 저장
b     LBB1_5                     ; LBB1_5로 점프
LBB1_5:
ldr   x0, [sp, #24]              ; 최종 결과 값을 x0에 불러옴
ldp   x29, x30, [sp, #64]        ; 프레임 포인터와 링크 레지스터 복원
add   sp, sp, #80                ; 스택 포인터 복원
ret                              ; 함수 리턴
LBB1_6:
brk   #0x1                       ; 오버플로우 에러 처리
LBB1_7:
brk   #0x1                       ; 오버플로우 에러 처리

 

결론

- 꼬리 재귀함수를 사용하면 일반 재귀 함수의 단점을 보완할 수 있으므로 재귀를 쓰려면 고려하여 쓰도록 하자.

 

XCode에서 컴파일러 최적화 옵션을 키는법

compiler

1. Compilation Mode:
   • Debug - Incremental: 이 모드는 개발 중에 가장 흔히 사용. 'Incremental' 컴파일은 변경된 부분만 재컴파일하여 전체 컴파일 시간을 줄인다. 디버깅을 용이하게 하기 위해 최적화를 최소화하며, 개발 과정에서 빠른 피드백을 제공.
   • Whole Module: 이 모드는 프로젝트의 모든 파일을 하나의 모듈로 취급하여 컴파일. 이 방식은 개별 파일 간의 최적화를 가능하게 하여 더 효율적인 실행 파일을 생성할 수 있지만, 컴파일 시간은 길어질 수 있다. 주로 릴리즈 빌드에 사용.
2. Swift Compiler - Code Generation Options:
   • -onone: 최적화를 수행하지 않는 옵션. 이는 디버그 빌드에서 주로 사용되며, 디버깅을 용이하게 하기 위해 코드의 구조를 가능한 원래대로 유지.
   • -optimize for speed (-O): 이 옵션은 실행 시간을 최소화하기 위해 코드를 최적화. 컴파일러는 실행 속도를 높이기 위해 다양한 최적화 기술을 사용하여 코드를 변경. 보통 릴리즈 빌드에서 사용되며, 최종 애플리케이션의 성능을 향상시키는 데 초점을 둔다.
   • -optimize for size (-Osize): 이 옵션은 실행 파일의 크기를 최소화하기 위해 코드를 최적화. 주로 저장 공간이 제한적인 환경에서 유용하며, 약간의 실행 속도 저하를 감수하고 파일 크기를 줄인다.

응용

- iOS 개발자가 꼬리재귀 함수를 실제로 사용하게 되는 구조
- viewController에서 탭 컨트롤러가 있고 안에 내비게이션 컨트롤러가 있고 하는 이런 구조가 바로 트리 형태이므로, 최상단 뷰컨트롤러를 찾는 등 자주 쓰는 기능에서도 이런 꼬리 재귀 함수를 사용할 수 있다.

func searchTopViewController(viewController: UIViewController?) -> UIViewController? {
  guard let viewController = viewController else { return nil }
  switch viewController {
    case let viewController as UITabBarController:
      return searchTopViewController(viewController: viewController.selectedViewController)
    
    case let viewController as UINavigationController:
      return searchTopViewController(viewController: viewController.viewControllers.last)
    
    case let viewController where viewController.presentedViewController != nil:
      return searchTopViewController(viewController:viewController.presentedViewController)
      
    default:
      return viewController
  }
}

 

 

REF

Quick thoughts on Tail recursion in Swift