무한 리스트로 작성한 피보나치 수열
다음은 Haskell로 정의한 피보나치 수열인데, Haskell의 lazy evaluation을 이해하기 딱 좋다. 코드를 살펴보자.
fibs :: [Int]
fibs = 0 : 1 : zipWith (+) fibs (drop 1 fibs)fibs는 무한 리스트1로 정의되는 피보나치 수열이다.2 fibs의 0, 1 번째
원소는 이미 평가가 완료된 상태(fully evaluated)이며, 2 번째 이후의 원소는 아직
평가되지 않았다. 이 평가는 해당 값이 필요해지는 시점에 시작된다. 이처럼 값이
필요할 때까지 평가를 미루는 전략을 지연 평가(lazy evaluation)라고 한다.
지연 평가를 채택하면 필요한 시점에만 계산이 수행되며, 필요하지 않은 값은 평가되지 않는다. 이처럼 Haskell은 지연 평가 전략을 채택한 함수형 언어다. 반면, OCaml과 같이 즉시 평가(eager evaluation)을 기본으로 채택한 함수형 언어도 존재한다.
지연 평가 vs. 즉시 평가
지연 평가, 즉시 평가 각각 장단점이 있다. 지연 평가를 사용하면 프로그래머가 계산 순서를 명시적으로 관리할 필요가 없으며, 필요하지 않은 부분은 계산하지 않기 때문에 불필요한 연산을 줄이고 무한한 크기의 자료구조를 쉽게 추상화하여 다룰 수 있다.
다만, 지연 평가는 프로그래머 입장에서 성능을 예상하는게 조금은 난해할 수 있다는 단점이 있다. 메모리 사용 패턴을 제대로 이해해서 설계하지 못한다면 계산이 지연된 표현식들이 폭발적으로 쌓여서 메모리 점유 및 성능상 문제를 일으킨다.
이와 비교해서 즉시 평가는 프로그래머가 계산 순서를 명확히 이해하고 제어할 수 있으므로 최적화가 용이하고 성능에 깊이 개입할 수 있다는 장점이 있다.
비효율적인 메모리 사용으로 인한 성능 저하
n 번째 피보나치 수를 계산하는 함수를 작성해보자. 아까 작성한 피보나치 수열을 활용하면 다음과 같이 naive하게 구현할 수 있다.
fib :: Int -> Int
fib n = fibs !! n우리는 n 번째 값만 구하면 되지만, fibs의 정의상 1 부터 n-1 까지의 모든 원소를
적어도 한 번씩은 계산해야 한다. 다행히 우리가 정의한 피보나치 함수는 fibs
리스트를 활용하여 일종의 메모이제이션을 달성하기 때문에 \(\text{O}(n)\)의 시간
복잡도를 갖는다.
그러나, 구하고자 하는 표현식인 n 번째 피보나치 수가 최종적으로 평가 완료될 때까지 이들 중간값이 모두 살아있어야 하는 것은 아니다. 중간값들은 리스트의 원소이기도 하기 때문에 garbage collect되지 않고, 결국 \(\text{O}(n)\)의 공간 복잡도를 가진다. 따라서, n이 커지면 cache miss3의 영향으로 성능이 저하된다.
지연 평가로 인한 성능 저하
다음과 같은 코드를 생각해볼 수 있다.
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, b4가 지연 평가되기 때문이다. 아직 평가되지 않은 표현식이 매우 깊은 트리5의 형태로 나타난다. 예를 들어, 다음과 같다.
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++로 작성한 동등한 알고리즘의 코드와 비교하여 메모리는 더 많이 쓰지만 계산 속도는 더 빨랐다. 벤치마크 결과를 다음 링크에서 확인할 수 있다. 벤치마크 결과
무한 리스트임을 보이자. (one-based index로) 첫 번째, 두 번째 원소의 값이 각각 0, 1임은 자명하다. n (n>1)번째 원소는
zipWith함수로부터 귀납적으로 정의된다.fibs가 0, 1, …이고,drop 1 fibs가 1, …인데,zipWith (+)함수는 이 둘을 0+1, 1+?, …와 같은 형태로 합친다. 따라서 최소한 세 번째 원소는 존재하며, 그 값은 0+1로 정의됨을 알 수 있다. 이처럼 모든 자연수 n에 대하여 n 번째 원소가 존재하면 n+1 번째 원소가 존재함을 보일 수 있다.↩︎fibs를 수열 \(a_n\)으로 두고 생각해보자. \(a_1 = 0, a_2 = 1\)임은 정의0 : 1 : (...)로부터 알 수 있다. \(a_n\:(n>2)\)부터는 귀납적으로 정의되는데, 수열 \(a'_n = a_{n+2}\)로 정의해보자. \(a'_n = a_n + a_{n+1}\)은 위 코드에서zipWith (+) fibs (drop 1 fibs)에 대응된다. \(a'_n\)의 정의로부터 \(a_{n+2} = a_n + a_{n+1}\)임이 도출되고, 이는 피보나치 수열의 점화식이다.↩︎연속된 메모리 공간에 순차적으로 쓰기를 한다고 가정하면 캐시 용량 초과로 인해 write miss와 eviction이 반복되며 병목이 발생한다. 다만, GHC가 컴파일한 코드가 런타임에 실제로 메모리를 연속적으로 할당한다는 보장은 없다. GHC가 내부적으로 연속된 쓰기를 어떻게 최적화하는지는 잘 모르겠다.↩︎
k는 지연 평가되지 않는다. 패턴 매칭 과정에서 값이 즉시 평가된다.↩︎
모든 표현식은 일종의 트리로 표현 가능하다.↩︎