원본: Write Haskell as fast as C: exploiting strictness, laziness and recursion
역주: 번역 시점에서 10년 된 글... 현재와는 다른 부분이 상당하다.
최근 메일링 리스트에서 Andrew Coppin이 긴 double 실수값 리스트의 평균을 계산하는 "깔끔하고 선언적인" 코드가 성능이 나쁘다고 불평했습니다.
import System.Environment
import Text.Printf
mean :: [Double] -> Double
mean xs = sum xs / fromIntegral (length xs)
main = do
[d] <- map read `fmap` getArgs
printf "%f\n" (mean [1 .. d])
위에 나온 그 코드는 실행하면 한동안 돌아가다가 결국 메모리 고갈을 일으킵니다.
$ ghc -O2 --make A.hs
$ time ./A 1e9
A: out of memory (requested 1048576 bytes)
./A 1e9 12.74s user 1.20s system 99% cpu 13.997 total
뭔가 결과를 얻는데 적어도 13초가 걸렸습니다.
Andrew는 이걸 GHC 하스켈은 예측할 수 없다는 예시로 (나중에 보겠지만 그렇진 않습니다) 들었지만 놓친 게 하나 있습니다. 이 작은 프로그램은 엄격함, 느긋함의 상호작용과 하스켈의 컴파일러 최적화 접근법을 상당히 드러냅니다.
이 글은 확실하게 빠른 코드를 짜는 법과 더 순진하면서도 확실히 빠른 코드를 짜는 법을 다룹니다. 특히 어떻게 최적화된 C와 겨룰만큼 근사한 코드를 재귀로 일반적이게 짜는지와, 어떻게 비슷한 성능을 고차 함수에서 이끌어내는지를 다룰 겁니다. 이 글에서 필자는 GHC 6.8.2를 -O2 플래그와 같이 썼습니다. 그리고 이걸 구현하는 더 나은 방법에 대해선 신경쓰지 않겠습니다. 우린 실제 반복문을 컴파일러가 어떻게 변환하는지 이해하는데 관심있습니다.
먼저, 왜 프로그램이 메모리 고갈을 일으키는지 알아봅시다. 명백히 힘들어보이는 점은 우리가 실수 10^9개를 담은 리스트를 요구하는 것입니다. 그건 매우, 매우 큽니다. 그건 그대로 할당하면 8 * 10^9 바이트를 차지하고, 약 7.5GB가 됩니다. 리스트 안에서도 리스트 노드와 그 포인터에 오버헤드가 있습니다. 그러므로 언어를 떠나서 우린 이 리스트를 수 기가의 메모리 없이는 한 번에 할당할 수 없습니다. 가능한 유일한 해결책은 리스트를 필요할 때마다 생성하는 겁니다. 엄격한 리스트 자료형을 써서 지금까지 이해한 걸 확인하겠습니다.
먼저 엄격한 리스트 자료형을 정의합니다. 이건 항상 리스트 머리와 꼬리를 완전히 평가합니다. 하스켈에선 엄격함은 자료 구조의 필드에 !를 붙이는 것으로 선언할 수 있습니다. 값을 어떻게 쓰는지 보고 추론하기도 합니다.
data List a = Empty
| Cons !a !(List a)
이건 새 자료형이므로 그에 맞는 새 함수도 필요할 겁니다.
length' :: List a -> Int
length' = go 0
where
go n Empty = n
go n (Cons _ xs) = go (n+1) xs
sum' :: Num a => List a -> a
sum' xs = go 0 xs
where
go n Empty = n
go n (Cons x xs) = go (n+x) xs
enumFromTo' :: (Num a, Ord a) => a -> a -> List a
enumFromTo' x y | x > y = Empty
| otherwise = go x
where
go x = Cons x (if x == y then Empty else go (x+1))
재귀적으로 처리하고 다시 싸매는 직관적인 형태를 썼습니다. 이건 잘 동작하는 간단한 함수형 관용구입니다.
이제 우린 리스트를 받아서 그 길이와 합을 구할 수 있습니다. mean 함수는 거의 같고, 타입만 느긋한 리스트에서 엄격한 리스트로 바꿨습니다.
mean :: List Double -> Double
mean xs = sum' xs / fromIntegral (length' xs)
테스트해보면 작은 수에서는 잘 동작하는 것을 확인할 수 있습니다.
$ time ./B 1000
500.5
./A 1000 0.00s user 0.00s system 0% cpu 0.004 total
하지만 수가 커질수록 메모리를 빠르게 고갈냅니다.
$ time ./B 1e9
Stack space overflow: current size 8388608 bytes.
Use `+RTS -Ksize' to increase it.
./A 1e9 0.02s user 0.02s system 79% cpu 0.050 tota
리스트를 합하는 단계조차 도달하지 못하는지 확인하기 위해, undefined만 반환하고 단지 받은 리스트 인자를 bang pattern(타입 명시와 비슷한 컴파일러에게 주는 엄격함에 관한 힌트)으로 평가만 하도록 바꾸겠습니다.
mean :: List Double -> Double
mean !xs = undefined
main = do
[d] <- map read `fmap` getArgs
printf "%f\n" (mean (enumFromTo' 1 d))
그리고 여전히 리스트를 할당하는 부분은 절망적입니다.
$ time ./A 1e9
Stack space overflow: current size 8388608 bytes.
Use `+RTS -Ksize' to increase it.
./A 1e9 0.01s user 0.04s system 93% cpu 0.054 total
엄격함은 해답이 되지 못했습니다.
그럼 왜 저 단순한 예제는 리스트 전체를 한번에 할당할까요? 느긋한 리스트면 그 원소를 할당하는 걸 피해야 하지 않을까요? 왜 예제가 동작하지 않는지 이해하려면
mean :: [Double] -> Double
mean xs = sum xs / fromIntegral (length xs)
함수가 실제 뭘 의미하는지 알아야 합니다. 코드를 살펴보기 위한 방법 하나는 GHC가 만든 최적화된 하스켈, 절차적 코드 바로 이전 번역을 보는 것입니다. 이 간략화된 하스켈은 “코어”라고 부르고 GHC가 원본 소스를 점진적으로 최적화하는 변환 최적화를 반복 적용해 얻은 최종 결과물입니다.
코어로 레지스터 레벨로 프로그램이 어떻게 동작할지 정할 수 있기에 C 수준의 성능을 원한다면 코어를 살펴보는 건 유용합니다. 코어엔 해석에 혼동을 주는 남은 최적화 과정이 전혀 없습니다. 코어는 완전 명백한 형태의 하스켈이기에 불확실성을 없애기 위해 코어를 쓰겠습니다. (일상적인 프로그래밍엔 간단한 느긋함과 엄격함의 개념으로도 충분합니다. 그러니 코어를 읽지 못하겠다고 당황하지 마세요!)
코어를 보기 위해 ghc -O2 -ddump-simpl이나 ghc-core 툴을 쓸 수 있습니다. mean의 코어 번역을 보면
$wlen :: [Double] -> Int# -> Int#
...
$wsum'1 :: [Double] -> Double# -> Double#
...
main = ...
shows (
let xs :: [Double]
xs = enumFromTo1 lvl3 d_a6h
in
case $wsum'1 xs 0.0 of {
_ -> case $wlen xs 0 of {
z -> case ww_s19a /## (int2Double# z) of {
i -> D# i
)
마치 조잡한 슈도 하스켈처럼 보입니다. 하지만 이건 명료한 의미를 가진 매우 간단한 요소들로 짜였습니다. 먼저 length와 sum이 특수화되었습니다. 임의 타입을 받는 부분이 구체적인 타입으로 바뀌었고 이 경우는 Double과 Int이 단순하고 원자적이기에 unlifted(혹은 unboxed)된 값으로 바뀌었습니다. 이게 좋은 점은 unlifted된 값은 레지스터에 저장할 수 있다는 것입니다.
또한 입력 리스트를 느긋하게 할당하는 것도 확인할 수 있습니다.
let xs :: [Double]
xs = enumFromTo1 lvl3 d_a6h
in ..
여기 나온 let은 느긋한 할당을 의미하는 기본 요소입니다. 만약 boxed 타입을 여기서 본다면 그게 힙에 할당되고 느긋하게 평가될 거라고 생각하면 됩니다. 기억할 것은 코어는 하스켈과 비슷하지만, 느긋한 바인딩을 위한 let과 평가를 위한 case밖에 존재하지 않습니다.
그건 좋습니다. 리스트를 쓰는 것 자체는 전혀 성능에 문제될 게 없다는 말입니다. 느긋한 할당으로 어떻게 메모리를 고갈나기 전에 어느 정도 연산을 할 수 있었는지도 설명이 됩니다. 리스트는 우리가 순회를 하면서야 할당될 겁니다.
하지만 모든 것이 완벽하진 않습니다. 다음 줄은
case $wsum'1 xs 0.0 of {
_ -> case $wlen xs 0 of {
z -> case ww_s19a /## (int2Double# z) of {
i -> D# i
여기서 case는 평가를 하는 기본 요소입니다. case는 받은 인자의 가장 바깥쪽 생성자를 즉시 평가합니다.
이런 식으로 컴파일러가 만들어 줄 연산의 순서를 알 수 있습니다. 처음의 느린 프로그램에선 먼저 리스트의 합을, 그 후에 리스트의 길이를 계산하고 나서야 합계를 길이로 나눕니다.
괜찮아 보입니다. 느긋한 리스트에서 실제 뭐가 일어날지 생각하기 전까진 말입니다. 처음의 let은 할당할 때 아무 일도 하지 않습니다. 하지만 처음 sum이 전체 리스트를 순회하면서 원소 합계를 구하기 시작합니다. 그러려면 반드시 그 큰 리스트를 전부 생성하고 평가해야 합니다.
그것 자체는 괜찮습니다. 가비지 컬렉터가 sum 뒤에서 돌아가면서 필요없는 노드를 해제할 것입니다. 하지만 여기엔 치명적인 결함이 있습니다. length가 여전히 리스트 머리를 잡고 있는 점입니다. 그래서 가비지 컬렉터가 리스트를 해제하지 못하고 전체 리스트를 내버려 두게 됩니다
그래서 sum은 거대한 리스트를 할당하고, 그 리스트는 length가 소비할 때까지 해제되지 않습니다. 이 해제 타이밍은 너무 늦습니다. 이건 우리가 본 증상과 정확히 일치합니다. 원래 글쓴이의 예측 불가능은 7G의 느긋한 리스트를 두 번 순회한다고 생각하면 완전히 예측 가능한 결과가 됩니다.
이건 엄격한 언어에서는 더 상황이 나빠진다는 걸 말해둡니다. 처음의 let이 평가를 시작할 것이고 아무것도 하지 못하게 됩니다.
이제 문제를 풀기 위한 정보를 충분히 모았습니다. 큰 리스트를 딱 한 번만 순회하도록 만들면 됩니다. 그럼 리스트를 유지할 필요가 없어집니다.
그럼 다음으로 할 것이자 지난 40년 간 보편적이었던 함수형 접근은 합계와 길이를 동시에 구하는 반복문을 짜는 것입니다.
mean :: [Double] -> Double
mean = go 0 0
where
go :: Double -> Int -> [Double] -> Double
go s l [] = s / fromIntegral l
go s l (x:xs) = go (s+x) (l+1) xs
평균을 구하는 데 쓸 길이와 합계를 함수 인자에 저장해 리스트의 끝에 도달하면 나누도록 했습니다. 이렇게 단일 순회로 바꿨습니다. 단순하고, 직관적입니다. 하스켈 해커라면 기본 도구로 가지는 접근법이 되어야 합니다.
리스트를 생성하는 즉시 순회하는 명료한 재귀 스타일로 작성하는 것으로 이제 상수 메모리 공간에서 동작하는 걸 확인할 수 있습니다. 이 코드는 아래와 같이 컴파일됩니다.
$wgo :: Double# -> Int# -> [Double] -> Double#
$wgo x y z =
case z of
[] -> /## x (int2Double# y);
x_a9X : xs_a9Y ->
case x_a9X of
D# y_aED -> $wgo (+## x y_aED) (+# y 1) xs_a9Y
$wgo가 리스트를 살펴보고, 빈 리스트인지 아닌지를 판단합니다. 비었다면 나눗셈 결과를 반환합니다. 아니라면 리스트의 머리를 살펴보고, 실수 값을 꺼낸 다음 나머지 리스트에 반복합니다. 작은 리스트에선
$ time ./B 1000
500.5
./B 1000 0.00s user 0.00s system 0% cpu 0.004 total
7 기가바이트 리스트에선
$ time ./B 1e9
500000000.067109
./B 1e9 68.92s user 0.19s system 99% cpu 1:09.57 total
예이! 결과를 계산했습니다! 느긋한 리스트가 우릴 퇴근시켜줍니다.
하지만 이게 끝일까요? GC와 메모리 통계를 보면 (프로그램을 +RTS -sstderr 인자를 줘서 실행하세요) 연산을 얼마나 했는지 볼 수 있습니다.
%GC time 1.4% (4.0% elapsed)
Alloc rate 2,474,068,932 bytes per MUT second
Productivity 98.6% of total user
이게 뭘 의미할까요? 먼저 가비지 컬렉션 시간은 전체 시간에서 아주 적은 비율(1.4%)을 차지하고, 이건 98.6% 시간동안 생산적인 연산을 했다는 의미가 됩니다. 이건 아주 좋습니다.
또 힙에 최대 24kB가 할당되었다는 것을 통해 프로그램이 상수 메모리 공간에서 실행된 걸 알 수 있습니다. 그리고 프로그램이 리스트 노드를 엄청난 속도로 쓰고 해제했습니다. 2GB/s라는 녹라운 속도로 말이죠. 다행히도 할당은 비용이 적습니다.
하지만 이 사실은 리스트 노드 할당을 피하고 메모리 버스를 꺼림으로써 훨씬 더 나아질 수 있단 걸 의미합니다. 우린 현재 값만 레지스터에 저장해 리스트 노드를 아예 할당하지 말아야 합니다. 메모리에서 벗어난다면 극적인 결과를 볼 것입니다.
이제 반복문이 리스트가 아니라 시작과 끝 값만 인자로 받도록 바꿔봅시다.
mean :: Double -> Double -> Double
mean n m = go 0 0 n
where
go :: Double -> Int -> Double -> Double
go s l x | x > m = s / fromIntegral l
| otherwise = go (s+x) (l+1) (x+1)
main = do
[d] <- map read `fmap` getArgs
printf "%f\n" (mean 1 d)
리스트의 최솟값과 최댓값을 함수 인자로 전달했습니다. 이제 여기엔 리스트가 일절 없습니다. 이건 융합 변환fusion transformation인데, 리스트를 생성하고, 소비하는 두 루프를 사용하는 대신 한 루프로 모든 연산을 처리하도록 합쳤습니다. 이건 리스트로 인한 메모리 트래픽을 없애줄 겁니다. 또 함수의 타입도 명시했는데, 그 결과 어떤 기계 타입을 쓸지 애매함이 사라집니다.
코어를 봅시다.
$wgo_s17J :: Double# -> Int# -> Double# -> Double#
$wgo_s17J x y z =
case >## z m of
False ->
$wgo_s17J
(+## x z)
(+# y 1)
(+## z 1.0);
True -> /## x (int2Double# y)
엄청 간단해졌습니다. 모든 인자는 unboxed 됐고, 반복문은 꼬리 재귀 형태고, 가비지 컬렉션이 일어나지 않는 걸 기대할 수 있고, 모든 리스트 인자는 레지스터에 들어갔고, 뛰어난 성능을 기대할 수 있습니다. >##과 +##은 실수를 비교·덧셈하는 GHC의 기본 연산입니다. +#은 정수 연산입니다.
먼저 GHC의 어셈블러로 컴파일해봅시다. (-O2 -fexcess-precision)
$ time ./C 1e9
500000000.067109
./C 1e9 3.75s user 0.00s system 99% cpu 3.764 total
훌륭합니다. 엄청난 속도입니다! 메모리 통계도 장밋빛 결과를 보여줍니다.
20,480 bytes maximum residency (1 sample(s))
%GC time 0.0% (0.0% elapsed)
Alloc rate 10,975 bytes per MUT second
Productivity 100.0% of total user
결국 이 프래그램은 상수 메모리 공간에서 돌아가고, 가비지 컬렉션을 전혀 하지 않으며, 초당 약간의 바이트 정도만 할당합니다. 재귀는 아침에 마시는 커피 한 잔입니다.
그리고 GHC에서 C 백엔드를 쓰면(-O2 -fexcess-precision -fvia-C -optc-O2), 한 층 더 빨라집니다.
$ time ./C 1e9
500000000.067109
./C 1e9 1.77s user 0.00s system 99% cpu 1.776 total
와우, 날아갑니다. GCC는 GHC가 만든 반복문을 더 최적화할 수 있었습니다.
C로 이 성능을 낼 수 있을지 알아봅시다. 함수 인자를 반복문 변수로 바꾸면 재귀 루프를 for 루프로 그대로 번역할 수 있습니다.
#include <stdio.h>
#include <stdlib.h>
int main(int argc, char **argv) {
double d = atof(argv[1]);
double n;
long long a; // 64 bit machine
double b;
// go_s17J :: Double# -> Int# -> Double# -> Double#
for (n = 1,
a = 0,
b = 0; n <= d; b+=n,
n++,
a++)
;
printf("%f\n", b / a);
return 0;
}
상당히 직설적이고, C는 깔끔하고 간결합니다. 함수 인자가 스택 공간(혹은 레지스터)을 함수형으로 재사용하면서 어떻게 C 코드에서 바뀌어가는지 알아보는 건 흥미롭습니다. 어쨌든 이 코드도 같은 코드를 나타낸 것입니다. 이제 C를 최적화 없이 컴파일합니다.
$ time ./a.out 1e9
500000000.067109
./a.out 1e9 4.72s user 0.00s system 99% cpu 4.723 total
좋습니다. 같은 결과를 얻었고 최적화된 하스켈은 최적화 안 한 C를 이겼습니다. -O 플래그로, gcc는 GHC에 가까워집니다.
$ time ./a.out 1e9
500000000.067109
./a.out 1e9 2.10s user 0.00s system 99% cpu 2.103 total
그리고 -O2로 코앞까지 다다릅니다.
$ time ./a.out 1e9
500000000.067109
./a.out 1e9 1.76s user 0.00s system 99% cpu 1.764 total
gcc -O2가 (거의?) gcc -O와 gcc -Onot보다 빠른 ghc -O2를 따돌리고 이겼습니다.
실제 어떤 코드가 나왔는지 생성한 어셈블리 파일을 (ghc -keep-tmp-files) 살펴볼 수 있습니다. GCC가 좀 더 나은 코드를 생성합니다.
.L6:
addsd %xmm1, %xmm2
incq %rax
addsd %xmm3, %xmm1
ucomisd %xmm1, %xmm0
jae .L6
.L8:
cvtsi2sdq %rax, %xmm0
movl $.LC2, %edi
movl $1, %eax
divsd %xmm0, %xmm2
잘 조여진 안쪽 루프와 최종 나눗셈을 봅시다. 반면에 GHC는 네이티브 백엔드로는
s1bn_info:
ucomisd 5(%rbx),%xmm6
ja .Lc1dz
movsd %xmm6,%xmm0
addsd .Ln1dB(%rip),%xmm0
leaq 1(%rsi),%rax
addsd %xmm6,%xmm5
movq %rax,%rsi
movsd %xmm0,%xmm6
jmp s1bn_info
.Lc1dz:
cvtsi2sdq %rsi,%xmm0
divsd %xmm0,%xmm5
안쪽 루프에 불필요한 것들이 -fasm이 느린 이유를 설명하고 있습니다. 이 네이티브 코드는 빠른 실수 연산에 더 개선이 필요합니다. 하지만 GHC C 백엔드로는
s1bn_info:
ucomisd 5(%rbx), %xmm6
ja .L10
addsd %xmm6, %xmm5
addq $1, %rsi
addsd .LC1(%rip), %xmm6
jmp s1bn_info
.L10:
cvtsi2sdq %rsi, %xmm7
divsd %xmm7, %xmm5
거의 GCC와 동일하고, 왜 성능이 좋은지 잘 설명합니다!
요지 1: C와도 견줄 정도로 예측 가능하며 빠른 하스켈을 짜려면 꼬리 재귀를 사용하고, 모든 타입이 Int, Word, Float, Double같은 간단한 기계 타입으로 추론되도록 합시다. 성능의 문은 두드리면 열립니다.
요지 2: 느긋함은 오버헤드가 있습니다. 비록 느긋함이 (리스트를 제어 구조로 쓸 수 있는 곳에서) 새로운 종류의 프로그램을 짜도록 해주지만 반복이 많은 내부 루프에선 메모리 트래픽이 커져 장애가 될 수 있습니다. 내부 루프에서 성능을 바란다면 느긋함에 기대지 마세요.
요지 3: 극도의 최적화를 위해, C 백엔드를 쓰는 걸 고려할 만 합니다. 좀 지나면 최신 네이티브 코드 생성기가 GHC에 추가되겠지만 그 때까진 C 백엔드도 멋진 무기입니다.
나중에 쓸 글에선 고차함수를 사용해서 어떻게 같은 성능을 낼 수 있는지 알아볼 겁니다.