Haskell 토막글: Fibonacci 함수 구현 및 성능 개선

무한 리스트로 작성한 피보나치 수열

다음은 Haskell로 정의한 피보나치 수열인데, Haskell의 lazy evaluation을 이해하기 딱 좋다. 코드를 살펴보자.

fibs :: [Int]
fibs = 0 : 1 : zipWith (+) fibs (drop 1 fibs)

fibs는 무한 리스트¹로 정의되는 피보나치 수열이다.² fibs의 0, 1 번째 원소는 이미 평가가 완료된 상태(fully evaluated)이며, 2 번째 이후의 원소는 아직 평가되지 않았다. 이 평가(evaluation)는 해당 값이 필요해지는 시점에 시작된다. 이처럼 값이 필요할 때까지 미루는 전략을 지연 평가(lazy evaluation)라고 한다.

지연 평가를 채택하면 필요한 시점에만 계산이 수행되며, 필요하지 않은 값은 평가되지 않는다. 이처럼 Haskell은 지연 평가 전략을 채택한 함수형 언어다. 반면, 즉시 평가(eager evaluation)을 채택한 함수형 언어도 존재한다.

지연 평가 vs. 즉시 평가

지연 평가, 즉시 평가 각각 장단점이 있다. 지연 평가를 사용하면 프로그래머가 계산 순서를 명시적으로 관리할 필요가 없으며, 필요하지 않은 부분은 계산하지 않기 때문에 메모리 관리의 책임으로부터 자유로울 수 있다.

반면, 즉시 평가에서는 프로그래머가 성능에 깊이 개입할 수 있다. 지연 평가와 달리, 프로그래머가 계산 순서를 명확히 이해하고 제어할 수 있어서 성능 최적화가 쉽다.

정리하자면, 즉시 평가는 저수준(low-level) 문제에, 지연 평가는 고수준(high-level) 문제에 친화적이다.

비효율적인 메모리 사용으로 인한 성능 저하

n 번째 피보나치 수를 계산하는 함수를 작성해보자. 아까 작성한 피보나치 수열을 활용하면 다음과 같이 naive하게 구현할 수 있다.

fib :: Int -> Int
fib n = fibs !! n

우리는 n 번째 값만 구하면 되지만, fibs의 정의상 1 부터 n-1 까지의 모든 원소를 적어도 한 번씩은 계산해야 한다. 다행이 우리가 정의한 피보나치 함수는 fibs 리스트를 활용하여 일종의 메모이제이션을 달성하기 때문에 \(\text{O}(n)\)의 시간 복잡도를 갖는다.

그러나, 구하고자 하는 표현식(expression)인 n 번째 피보나치 수가 최종적으로 평가 완료될 때까지 이들 중간값이 모두 살아있어야 하는 것은 아니다. 중간값들은 리스트의 원소이기도 하기 때문에 garbage collect되지 않고, 결국 \(\text{O}(n)\)의 공간 복잡도를 가진다. 따라서, n이 커지면 cache miss의 영향으로 성능이 저하된다.

지연 평가로 인한 성능 저하

다음과 같은 코드를 생각해볼 수 있다.

fib :: Int -> Int
fib n = fib' n 0 1
  where
    fib' 0 a _ = a
    fib' k a b = fib' (k - 1) b (a + b)

앞선 예시와 다르게 필요한 중간값들이 모두 함수 인자로 제공되므로 수명이 다한 중간값들이 garbage collect되지 않는 문제는 피할 수 있을 것처럼 보인다.

그러나, 이번에도 n이 커지면 느려진다. 프로파일링 해보면 앞선 예시와 램 사용량, 실행시간 모두 비슷하게 나온다. 이번 예시 또한 \(\text{O}(n)\)의 공간 복잡도를 갖는 것은 아닐까?

원인은 함수의 인자인 a, b³가 지연 평가되기 때문이다. 아직 평가되지 않은 표현식이 매우 깊은 트리⁴의 형태로 나타난다. 예를 들어, 다음과 같다.

fib' 1000000 0 1 -->
fib' 999999 1 (0 + 1) -->
fib' 999998 (0 + 1) (1 + (0 + 1)) -->
fib' 999997 (1 + (0 + 1)) ((0 + 1) + (1 + (0 + 1))) -->
fib' 999996 ((0 + 1) + (1 + (0 + 1))) ((1 + (0 + 1)) + ((0 + 1) + (1 + (0 + 1)))) -->
...

결국 \(\text{O}(n)\)의 공간 복잡도를 갖는다. 언뜻 보면 \(\text{O}(2^n)\)처럼 보일 수 있는데, 각 중간 표현식들은 일종의 그래프와 같은 형태를 취하고 있어서 공통된 하위 표현식이 하나의 thunk와 같다. 예를 들어, fib' b (a + b)에서 첫 번째 인수의 b, 두 번째 인수의 b가 모두 같은 thunk다. 따라서 공통된 하위 표현식들은 계산이 완료된 값을 서로 공유한다.

엄격(Strict)한 인수 평가

다음과 같이 인수가 엄격(strict)하게 평가되도록 강제할 수 있다. Strict한 인수는 지연 평가되지 않고 즉시 평가된다.

fib :: Int -> Int
fib n = fib' n 0 1
  where
    fib' 0 !a !_ = a
    fib' !k !a !b = fib' (k - 1) b (a + b)

더이상 인수가 지연 평가되지 않고, 다음과 같이 즉시 평가된다.

fib' 1000000 0 1 -->
fib' 999999 1 1 -->
fib' 999998 1 2 -->
fib' 999997 2 3 -->
fib' 999996 3 5 -->
...

이번 예시는 메모리 사용량이 상수에 해당하며, C++로 작성한 동등한 알고리즘의 코드와 성능이 거의 동일하다. 벤치마크 결과를 다음 링크에서 확인할 수 있다. 벤치마크 결과