컴파일러가 기본적으로 하는 최적화를 알아보자

컴파일러는 실제 코드에 어떤 최적화를 할까?

사람이 작성한 코드는 컴퓨터 입장에서 그대로 실행하면 비효율적인 경우가 많습니다.

당장 여러 좋은 설계 원칙에서는 코드를 함수나 객체로 분리하라는 경우가 많은데 분리할수록 컴퓨터 입장에서는 함수를 찾고 호출해야 하기 때문에 분리되지 않은 것에 비해서는 비효율적입니다.

또, Clean Code에서 말하는 Magic Number를 쓰지 말고 명확히 변수로 분리하라는 원칙도 그렇습니다. 

// 구의 부피를 계산하는 프로그램: 효율적인 버전
fun calculate(radius: Double): Double {
    return 4.18666667 * radius * radius * radius
}

// 구의 부피를 계산하는 프로그램: 조금 비효율적이지만 읽기 쉬운 버전
fun calculate(radius: Double): Double {
    val coefficient = 4.0 / 3.0
    val pie = 3.14

    return  coefficient * pi * radius * radius * radius
}

아래의 조금 비효율적인 코드는 함수를 호출할 때 마다 4.186666667을 계산해야 하기 때문에 더 비효율적입니다.

하지만... 컴파일러가 어련히 알아서 이런걸 다 최적화해 주지 않을까요? 사실 현대 컴퓨터의 성능이 워낙 뛰어나서 저런 사소한 게 실제 성능에 영향을 미치기는 쉽지 않기도 하고, 점점 각종 말도 안 되게 복잡한 최적화 기법을 갖춘 현대 컴파일러를 믿고 요즘 개발자들은 (저를 포함해서) 저런 사소한 것들을 신경 쓰지는 않습니다.

그렇다면 실제로는 어떨까요? 현대의 복잡한 최적화 기법은 빼고, 대부분의 컴파일러 구현체가 하는 간단한 최적화 기법들을 공부해 봤습니다.

---

Constant Folding: 계산식은 미리 다 계산해 두기

위에서 예시를 들었던 구의 부피를 구하는 공식에서의 계산식은 역시나 컴파일러가 미리 계산을 해 둡니다.

fun calculate(radius: Double): Double {
    val coefficient = 4.0 / 3.0
    val pie = 3.14

    return  coefficient * pi * radius * radius * radius
}

코드가 요렇게 돼 있어도 컴파일 시점에는 미리 계산해서 나온 값으로 대체 시켜서 넣어 둡니다.

중요한 것은 컴파일 시점에서 항상 같은 값이여야만 Constant Folding이 적용된다는 겁니다. Kotlin의 경우 변수에 var, val 구분이 있어서 이게 간단한 편입니다.

하지만...

• 상수를 지원하지 않는 언어는 Constant Folding이 없을 수도 있고,
• 소스 코드 전체를 분석해 변하지 않는 부분만 Constant Folding을 적용할 수도 있습니다.
• 컴파일 과정이 없는 Interpreted 언어의 경우 Constant Folding이 불가능하지만,
• 일부 JIT Compiler 구현체에서는 구현하는 경우도 있습니다.

---

Common Subexpression Elimination (CSE): 계산 결과가 같으면 공통으로 사용하기

val x = a + b
val y = a + b

위의 예시에서 x, y는 같은 결과를 반환합니다. 이럴 경우 CSE를 적용한 컴파일러는 y 변수를 없애고 대신 x를 사용합니다.

누가 이런 바보같은 실수를 하겠냐 하겠지만 엄청 큰 코드 베이스에서 복잡한 계산식이 있는데 변수 이름도 다르면 충분히 있을 수 있는 상황입니다. 이 경우 사람 프로그래머는 탐지하기 힘들지만 컴파일러는 탐지해서 자동으로 최적화해 준다니 든든~합니다.

---

Loop Invariant Code Motion: Loop 안에 있는 변하지 않는 계산식은 Loop 밖으로 이동

for (i in 0 until n) {
    val x = a + b // 자동으로 밖으로 이동 됨
    arr[i] = x * i
}

위의 예시를 보시면 x의 값은 for-loop가 돌면서 변하지 않기 때문에 최적화가 없다면 불필요하게 Loop를 도는 횟수만큼 x가 계산됩니다. 이 경우 컴파일러는 변수의 Scope를 보고, 계산식이 Loop 밖의 Scope에 있는 변수들에만 좌우되고, 그 변수들을 Loop 안에서 변경하지 않는다면 밖으로 내보내서 컴파일을 진행합니다. (물론 이건 컴파일러마다 구현 방법이 다릅니다.)

여기서부터 간단한 거지만 제 생각보다 컴파일러가 최적화를 많이 놀랐습니다. 물론 같은 언어라고 해도 어떤 컴파일러를 쓰냐, 어떤 버전이냐에 따라 Loop Invariant Code Motion을 지원하지 않을 수도 있기 때문에 명시적으로 Loop 밖에 값을 이동시키는 게 훨씬 좋은 코딩 방법이라고 생각하긴 합니다.

---

Strength Reduction: 비싼 연산은 같은 값을 주는 다른 연산으로 대체하기

val x = y * 2  // y + y 로 대체
val z = y * 8  // y << 3 로 대체

컴퓨터는 대부분의 아키텍쳐에서 * 연산이 + 연산보다 비쌉니다. 마찬가지로 Bit 연산이 * 연산에 비래서는 훨씬 쌉니다. 이 경우 더 싼 연산으로 자동으로 대체시켜서 컴파일합니다.

 

🐜 더하기가 곱하기에 비해 싼 이유?

더하기는 CPU에서 구현할 때 (정확히는 ALU) 기본적인 Logic Gate만 사용해서 구현할 수 있는데, 곱하기는 그렇지 않기 때문에 훨씬 비쌉니다.

아래는 제가 처음 해당 내용을 이해했던 유튜브 동영상입니다.

 

🐜 그럼 곱하기를 다 비트 연산으로 대체하면 안 됨?

비트 연산은 비트를 옆으로 옮기는 게 끝이기 때문에 모든 컴퓨터 연산 중에 가장 싼 연산입니다. 컴퓨터는 이진수를 쓰기 때문에 자릿수가 1개 늘어나면 값은 2배로 됩니다. 즉, 2의 제곱수를 곱할 때만 비트 연산으로 대체할 수 있습니다. (일상생활에서 10진수를 쓰는 우리는 큰 숫자를 셀 때 흔히 "일... 십... 백... 천... 만..." 이런식으로 자리수를 가늠하는데, 생각해 보면 이건 10씩 곱하는 겁니다. 비슷하게 2진법에서는 자리수가 바뀔 때마다 2를 곱합니다.)

---

Scalar Replacement of Aggregates: 간단한 객체면 찢기

// 객체인데 간단한 연산만 한다면...
data class Point(val x: Int, val y: Int)
fun compute(): Int {
    val p = Point(3, 5)
    return p.x + p.y
}

// 그냥 찢어 버리면 메모리 절약 가능!
fun compute(): Int {
    val x = 3
    val y = 5
    return x + y
}

이건 딱 봐도 복잡합니다... 그래서 대부분의 컴파일러에서 꽤 엄격한 조건하에서만 일어납니다.

• 객체가 함수를 벗어나지 않고,
• 객체의 각 속성을 개별로 추적할 수 있고, (객체 자체를 다른 함수에 넘기거나 하지 않고)
• Passed by Reference나 배열에 저장되는 등 복잡한 방식으로 변형되지 않아야 합니다.

---

Dead Code Elimination: 프로그램에 영향을 주지 않는 코드는 제거

val x = 10
x + 5 // 변수에 할당하지 않았음...

위에 예시와 같이 실수로 코드에 영향을 전혀 주지 않지만 남아 있으면 계산은 해야 하는 코드들은 자동으로 지워 줍니다. 

요즘은 IDEA가 워낙 잘 되어 있어서 저런 경우는 IDEA가 탐지해 줍니다. 근데... 이 IDEA 탐지도 컴파일러가 IDEA에 제공하는 것이라는 거 알고 계셨나요? 즉, 컴파일러가 구리면 IDEA가 저런 거를 탐지 못 할 수도 있습니다. 반대로 IDEA가 탐지를 못 하면 (같은 컴파일러를 쓴다면) Dead Code Elimination도 일어나지 않습니다.

---

Loop Unrolling: 간단한 Loop면 그냥 찢어 버리기

// 정해진 만큼 (4번)만 도는 간단한 Loop...
for (i in 0 until 4) arr[i] = i * 2

// 그냥 찢어 버리는게 더 쌈...
arr[0] = 0
arr[1] = 2
arr[2] = 4
arr[3] = 6

컴파일러마다 어떤 조건에서 Loop Unrolling을 하는지는 너무 다릅니다. 보통은 아래 조건들에서 일어납니다.

• 컴파일 시에 정해진 횟수만큼만 돔
• 너무 많이 돌지 않음
• 도는 횟수는 매번 달라지지만 도는 횟수가 특정 인자에 의해 나눠짐 (이 경우 그 나눠지는 값만큼만 돌도록 부분적으로 Unrolling이 가능합니다.)

---

교훈: 컴파일러가 만능은 아니다

컴파일러에 대해 전혀 모를 때는 컴파일러를 내가 짠 이상한 코드를 알아서 다 최적화시켜 주는 마법의 상자 정도로 생각했던 거 같습니다. 하지만 점점 코딩을 하면서 내가 짠 코드가 생각보다 그대로 실행돼서 성능에 영향을 주거나, 컴파일러에 대해 공부하면서 컴파일러는 생각보다 정직하다는 것을 깨달았습니다.

효과적인 코드를 짜기 위해 컴파일러까지 뜯어보며 효율적인 코드를 고민할 필요는 없겠지만, 컴파일러가 하는 기본적인 최적화들을 보면서 컴파일러의 최소한의 능력치(?)에 대해 알게 돼 코드를 짤 때 더 효율적인 코드를 1번 더 고민할 거 같습니다.

---