[iOS] 컴파일 최적화 feat 꼬리재귀

🛠 컴파일 최적화

⚙️ 컴파일 최적화란?

위키에서 말하는 컴파일 최적화의 정의를 찾아보았다.

컴파일러 최적화(optimizing compiler)는 컴파일러에서 출력되는 실행 프로그램의 효율성을 최적화하는 과정을 말한다. 일반적으로 프로그램의 실행 속도를 최대화하거나 프로그램이 차지하는 메모리의 양을 최소화하기 위해 많이 이용된다. 휴대용 컴퓨터가 성장함에 따라 프로그램에 의해 소비되는 전력을 최소화하는 것도 고려된다.

내가 이해하기로는 각 언어의 컴파일러 마다 어떤 경우일 때 최적화를 할 수 있다는 규칙이 있는 것 같다.

예를 들어 final 을 붙이는 것도 final 키워드를 붙이면 컴파일러가 상속되지 않는다는 것을 인지하고 static dispatch 로 바꿔주는 과정이 컴파일 최적화를 해주고 있는 것이다.

빠른 swift 코드 작성법 애플 공식 깃허브

⚙️ xcode 에서 컴파일 최적화 키기

xcode 에서 컴파일 최적화를 하려면 설정을 만져줘야 한다.

Optimization Level 의 Debug 와 Release 를 (기본적으로는 No Optimization[-Onone] 이다.) Optimize for Size[-Osize] 또는 Optimize for Speed[-O] 둘중에 하나로 설정 하면된다.
메모리공간 최적화를 우선으로 할건지 시간을 우선으로 할것인지를 고르는 것이다.

♻️ 재귀 함수 최적화

재귀 함수는 자기 자신을 호출하는 함수이다.
재귀 함수의 단점으로는 자기 자신을 계속 호출하기 때문에 스택에 함수가 계속 쌓여서 많이 재귀를 하게 되면 스텍 오버플로우가 일어날 수도 있다.

이런 단점을 최소화 하기 위해서 꼬리재귀 라는 형태로 재귀를 구현하면, 최적화를 해주는 컴파일러들이 존재한다.

🦋 꼬리 재귀란?

재귀 호출이 끝난 후 현재 함수에서 추가 연산을 요구하지 않도록 구현하는 재귀의 형태이다.

이를 이용하면 함수 호출이 반복되어 스택이 깊어지는 문제를 컴파일러가 선형으로 처리 하도록 알고리즘을 바꿔 스택을 재사용 한다.(더이상 값이 변할 여지가 없으므로 스택을 덮어쓸 수 있기 때문이라고 한다.)

꼬리재귀로 구현만 한다고 되는 것은 아니고, 컴파일러의 최적화에서 꼬리재귀에 대한 최적화를 지원하는지를 확인해야 한다.(xcode 는 지원한다.)

말이 좀 어려운데 코드를 보면 별거 아니다!

팩토리얼을 구해주는 함수를 재귀함수와 꼬리재귀함수로 표현해 보았다.

func 재귀함수(_ n: Int) -> Int {
    guard n > 0 else { return 0 }
    return n + 재귀함수(n - 1)
}

func 꼬리재귀함수(_ n: Int, _ acc: Int) -> Int {
    guard n > 0 else { return acc }
    return 꼬리재귀함수(n - 1, acc + n)
}

재귀함수는 return 부분에서 함수를 호출하면서 추가적인 연산이 들어간다.
꼬리재귀 함수를 return 에서는 스스로를 다시 호출하기만 한다.
꼬리 재귀는 이게 다다.

꼬리 재귀 형태로 재귀를 작성하고 위의 설정을 켜주면 이때 부터 컴파일러가 최적화를 해준다.

✅ 재귀와 꼬리재귀 성능 비교

재귀 함수를 호출해 주고 lldb 로 찍어보았다.

스택에 재귀함수가 쌓이고 있다. 500000번 재귀하고 있기 때문에, 스택에 5만개의 재귀함수가 쌓이게 될 것이다. StackOveflow 가 발생할 수 도 있다.

반면 꼬리재귀는 스택에 쌓이지 않게 된다. StackOveflow 를 막을 수 있다.

---

참고한 문서
빠른 swift 코드 작성법 애플 공식 깃허브