하스켈 최적화

Johan Tibell의 ZuriHac 2015 발표: https://www.youtube.com/watch?v=_pDUq0nNjhI

 

그냥 동영상에 나오는 슬라이드 별로 요약한 것. 자세한 내용은 동영상 참조.

 

 

---

 

 

◎ 생성자의 헤더에 1워드, 필드에 1워드 소모

 

data Uno = Uno a -- 2워드

data Due = Due a b -- 3워드

 

예외: 필드 없는 생성자는 메모리 사용 X (Nothing, True 등)

 

 

---

 

 

◎ [1, 2] 의 메모리 표현

 

 

 

- 1박스 = 1워드

- 생성자마다 1워드의 오버헤드 (가비지 컬렉션 등에 이용)

 

 

---

 

◎ unboxed 타입 = 원시 기계 타입

 

- 관례에 의해 이름이 #로 끝난다

- 대부분 1워드를 소모 (예외: 32비트 기계에서 Double#)

- unboxed 타입의 값은 thunk일 수 없다

- 기본형들은 unboxed type을 이용해 정의

  data Int = I# Int#  -- Int boxed type

 

 

---

 

◎ unpacking

 

- 생성자의 내용물을 풀어헤쳐 다른 생성자의 필드로 집어넣는다

- 간접 참조를 한 단계 소거, 생성자 헤더를 하나 제거

- strict, monomorphic, 단일 생성자 필드만 unpack 가능

 

예: data Foo = Foo {-# UNPACK #-} !SomeType

 

 

 

 

 

 

 

---

 

 

◎ C와의 구조적 비교

 

 

data A = A !Int   struct A {     int *a; };

data A = A {-# UNPACK #-} !Int   struct A {     int a; };

 

 

 

---

 

◎ unpacking의 함정

 

non-strict 함수에 값을 전달하면 reboxing 필요 -> 퍼포먼스 오히려 저하

 

 

---

 

◎ f : ... -> T

 

T가 strict 필드만 있는 타입이면 f는 thunk를 포함할 수 없다

 

 

---

 

◎ 지침 1. 데이터 타입을 항상 strict로 만들 것

 

예제: Data.Map

 

data Map k a = Tip                      | Bin {-# UNPACK #-} !Size !k a                               !(Map k a) !(Map k a)

 

 

---

 

◎ 지침 2. 누적기(accumulator)에서 strict 자료형을 쓸 것

 

mean :: [Double] -> Double mean xs = s / n   where (s, n) = foldl' (\(s, n) x -> (s+x, n+1)) (0, 0) xs => 매번 할당 발생   ------------------------------------------------------------------   data StrictPair a b = SP !a !b  -- 한 번 쓰고 버릴 자료형   mean2 :: [Double] -> Double mean2 xs = s / n   where SP s n = foldl' (\(SP s n) x -> SP (s+x) (n+1)) (SP 0 0) xs

 

 

---

 

◎ 지침 3. 모나딕 코드에서 strict return을 사용할 것

 

return은 값을 lazy box로 감싸곤 한다.

 

return $ x + y  -- thunk를 만듦

 

우리가 원하는 것: return $! x + y

 

 

---

 

 

◎ 지침 4. 표현식을 lazy 자료형으로 감싸기 전에 강제 평가

 

safeDiv _ 0 = Nothing

safeDiv x y = Just $! x / y

 

 

---

 

 

◎ 모든 것을 인라인화?

 

아니다. 다만 GHC가 인라인화를 할 수 있게 만들어라.

 

 

---

 

 

◎ 실전: lazy한 base case에 주의

 

data Tree = Leaf           | Bin Key !Value !Tree !Tree   insert :: Key -> Value -> Tree insert k v Leaf = Bin k v Leaf Leaf  -- k 때문에 lazy insert k v (Bin k' v' l r)   | k < k'    = ...   | otherwise = ...

 

 

insert k! v Leaf = Bin k v Leaf Leaf 로 수정

 

GHC는 key를 unboxing하여 비교 비용을 줄인다

 

 

---

 

 

◎ 지침 5. 재귀 함수에 래퍼 사용

 

GHC는 재귀 함수를 인라인화하지 않는다

 

map :: (a -> b) -> [a] -> [b] map _ []     = [] map f (x:xs) = f x : map f x

 

재귀 함수를 인라인화하려면 비재귀적 래퍼 필요

 

map :: (a -> b) -> [a] -> [b] map f = go   where     go []     = []     go (x:xs) = f x : go xs

 

알려지지 않은 고차 함수 호출 -> 간접 호출 -> 비용 비쌈

 

 

---

 

 

◎ 지침 6. INLINABLE 사용

 

동영상 참조

 

 

---

 

 

◎ GHC Core

 

알 수 있는 것들

 

- 표현식이 언제 평가되는가?

- 이 함수 인자가 간접 참조되는가?

- 내 함수가 인라인화되었는가?

 

동영상 참조