Garbage Collection

OCaml은 Generational Hypothesis에 기반한 Generational Mark and Sweep Garbage Collection을 기반으로 메모리를 관리한다. 그래서 (특히 기본 정수의) 메모리 표현이 조금 특이한데 자세한 내용은 Memory Representation of Values와 Understanding the Garbage Collector를 참조하는 것이 가장 좋다. 여기서는 짧게 몇 가지만 언급하려고 한다.

힙의 종류

마이너 힙

가장 빠르다. 대부분의 메모리 블록은 제일 처음 마이너 힙에 할당되고 마이너 힙이 넘치는 순간 마이너 컬렉션이 수행되면서 살아남은 애들이 메이저 힙으로 프로모션 되는 방식이다. 마이너 힙은 Bump Pointer 방식으로 할당되기 때문에 빠르다. 그래서 마이너 힙이 클수록 작은 문제에서는 잘 동작할지도 모른다. 하지만 마이너 힙에서 살아남은 블록들이 메이저 힙으로 프로모션 될 때에는 이 블록들을 모두 복사하기 때문에 성능이 튈 수도 있다.

메이저 힙

복잡하거나 큰 데이터들은 대부분 처음부터 메이저 힙에 올라간다. 메이저 힙 컬렉션은 (1) 마킹 (2) 스윕 (3) 압축 세 페이즈가 있고, 성능을 위해서 각각을 조금씩 잘라서(slice) 동작하기 때문에 메모리 사용량이 항상 실제보다 조금 더 많을 수 밖에 없다. 문제에서 예상되는 입력이 커서 메이저 힙을 사용할 수 밖에 없는 경우 아예 처음부터 메이저 힙 크기를 크게 잡아서 메이저 컬렉션을 수행하지 않는 방향으로 하는 것이 빠를지도 모른다.

메모리 할당 방식

메모리 할당 방식은 세 가지가 있다. (1) Best Fit, (2) Next Fit, (3) First Fit.

Best Fit

두 가지 전략을 합친 할당 방식이다. 먼저, 작은 리스트나 튜플의 원소처럼, 대부분의 메이저 힙 할당이 작다는 관찰로부터 크기 별로 분류한 프리 리스트를 기반의 전략이 있다. 최대 16 워드 크기의 사이즈까지의 프리 리스트를 따로 구분해뒀다가 대부분의 할당에서 빠르게 제공한다.

두 번째 전략은, 더 큰 할당에 대해서 스플레이 트리라고 알려진 특별한 데이터 구조를 이용해서 프리 리스트를 구현한다. 이러한 검색 트리는 최근 접근 패턴에 알맞은 것으로, 가장 최근에 요청된 할당 사이즈에 가장 빠르게 접근할 수 있다는 의미이다.

크기 구분 프리 리스트에서 가능한 더 큰 사이즈가 없으면 작은 할당이 일어나고, 16 워드 이상의 큰 할당은 기본적으로 메인 프리 리스트에서 일어난다. 즉, 프리 리스트는 요청된 할당 크기만큼 큰 것 중 가장 작은 블록에 대해서 쿼리된다.

Best Fit은 OCaml 5 버전의 기본 할당 방식으로 할당 비용 (CPU) 과 힙 파편화 사이에서 적절한 트레이드 오프를 보여준다.

Next Fit

Next Fit은 가장 최근 할당 요청에 사용된 프리 리스트 블록에 대한 포인터를 유지하다가, 새로운 요청이 오면 이 포인터 다음 블록부터 프리 리스트의 끝까지, 그리고 끝까지 찾은 경우 다시 프리 리스트의 처음부터 그 블록 전까지 검색하는 전략이다.

보면 알겠지만 이 방법은 꽤 싼 할당 메커니즘인데, 같은 힙 청크를 다 쓸 때까지 할당 요청에 걸쳐 재사용할 수 있기 때문이다. 다시 말하면 CPU 캐시를 더 잘 사용하게 되어서 메모리 로컬리티가 좋다는 의미이다. 반면 가장 큰 단점은, 대부분의 할당이 작기 때문에, 프리 리스트의 시작 부분에 있는 커다란 블록이 심하게 파편화 된다는 것이다.

OCaml 4.11 버전의 기본 할당 방식으로, Best Fit은 이때 상대적으로 새롭게 추가된 전략이라서 아직 테스트가 덜 된 상황이었다.

First Fit

만약 프로그램이 아주 다양한 크기의 값을 할당하는 경우, 프리 리스트가 파편화될 수 있다. 어떤 할당 요청에 대해서 남아 있는 메모리 청크 중 아무것도 충분히 크지 못한 경우, GC는 프리 리스트에 여유 청크가 있는데도 불구하고 아주 비싼 압축을 강제로 수행해야 한다.

First Fit 할당 전략은 메모리 파편화를 줄이는데 (= 압축 횟수를 줄이는데) 초점을 맞춘 전략으로, 대신 메모리 할당 속도를 희생한다. 모든 할당은 프리 리스트를 처음부터 끝까지 스캔하면서 적절한 크기의 여유 청크를 찾는다.

부하가 있는 몇몇 리얼 타임 작업의 경우, 잦은 힙 압축을 줄이는 게 추가적인 할당을 희생하더라도 훨씬 더 좋을 수 있다.

요약

요약하면 다음과 같다.

• Best Fit: OCaml 5 버전의 디폴트 할당 방식. 작은 크기의 값에 대해서는 잘 동작할테고, 크기가 크면 좀 오버헤드가 있지만 적절한 성능이다.
• Next Fit: OCaml 4 버전의 디폴트 할당 방식. 가장 빠른 방식. 단 다양한 크기의 값에 대해서는 파편화가 심해져서 힙 압축이 자주 발생할 수 있기 때문에, 문제의 메모리 제한에 따라 힙 압축을 꺼버리는 것도 하나의 방법일 수 있다.
• First Fit: 문제 풀이에서는 쓸 일이 없는 방식이니 잊도록 하자.

결론은, 잘 모르겠으면 그냥 디폴트 할당 방식인 Best Fit을 쓰면 되고, 문제에 따라서는 Next Fit에 추가적인 GC 튜닝을 하면 효과를 볼 수 있을지도 모른다.

Gc 모듈

Gc 모듈을 이용하면 Gc를 들여다보거나 조절하는 것이 가능하다. 먼저 현재 Gc 상태를 나타내는 stat 타입이 있다. Gc를 튜닝하고 싶다면 먼저 Gc.stat ()을 호출해서 Gc 상태를 확인한 후에 파라미터를 튜닝하도록 하자.

type stat = {
  minor_words: float;  (* 프로그램 시작 후부터 마이너 힙에 할당된 워드의 수 *)
  promoted_words: float;  (* 프로그램 시작 후부터 마이너 힙에 할당되어 마이너 컬렉션에서 살아남아서 메이저 힙으로 옮겨간 워드의 수 *)
  major_words: float;  (* 프로그램 시작 후부터 메이저 힙에 할당된 수로, 프로모트된 마이너 힙의 워드까지도 포함한다. *)
  minor_collections: int;  (* 프로그램 시작 이래 마이너 컬렉션 횟수 *)
  major_collections: int;  (* 프로그램 시작 이래 메이저 컬렉션 사이클 완료 횟수 *)
  heap_words: int;  (* 메이저 힙의 전체 크기 (워드) *)
  heap_chunks: int;  (* 메이저 힙을 구성하는 연속된 메모리 조각의 개수 *)
  live_words: int;  (* 메이저 힙에 살아있는 데이터의 워드 수 *)
  live_blocks: int;  (* 메이저 힙에 살아있는 블록 수 *)
  free_words: int;  (* 프리 리스트에 있는 워드 수 *)
  free_blocks: int;  (* 프리 리스트에 있는 블록 수 *)
  largest_free: int;  (* 프리 리스트에 있는 가장 큰 블록의 크기 (워드) *)
  fragments: int;  (* 단편화로 인해서 낭비되는 워드의 수. 할당에 쓸 수 없는 것으로, 두 개의 살아있는 블록 사이에 있는 1 워드 짜리 프리 블록들의 개수이다. *)
  compactions: int;  (* 프로그램 시작 이후 힙 압축 횟수 *)
  top_heap_words: int;  (* 메이저 힙에서 도달 가능한 최대 사이즈 (워드) *)
  stack_size: int;  (* 현재 스택 크기 (워드) *)
}

그리고 Gc에 쓰이는 다양한 파라미터들을 튜닝하기 위한 control 타입이 있다.

type control = {
  mutable minor_heap_size: int;
  mutable major_heap_increment: int;
  mutable space_overhead: int;
  mutable verbose: int;
  mutable max_overhead: int;
  mutable stack_limit: int;
  mutable allocation_policy: int;

  window_size: int;
  custom_major_ratio: int;
  custom_minor_ratio: int;
  custom_minor_max_size: int;
}

현재 control 설정 값은 Gc.get ()을 호출해서 알아낼 수 있다. 이 값을 튜닝하려면 Gc.set { (Gc.get ()) with Gc.verbose = 0x00d }와 같이 호출할 수 있다. 이 중에서 우리가 관심을 갖고 지켜봐야 할 값은 다음과 같다.

보면 알겠지만 마이너 힙을 조절할 수 있는 파라미터는 minor_heap_size 하나 뿐이고 나머지는 대부분 메이저 힙에 대한 파라미터이다. 그 외에 커스텀 할당과 관련된 파라미터도 있는데 이것은 문제 풀이의 범위를 벗어나기 때문에 여기서는 제외했다.

문제 풀이에서는 (1) 최대한 마이너 힙만을 쓰거나, (2) 메이저 컬렉션을 최대한 미루거나, 아니면 (3) 메이저 힙을 쓰되 파편화 신경쓰지 않고 할당 속도를 높이는게 중요하다. 따라서 가능한 세 가지 접근이 있다.

마이너 힙 늘리기

문제의 모든 할당이 충분히 작아서 마이너 힙을 키우면 될 것 같은 경우, 다음과 같이 세팅해볼 수 있다.

let () = Gc.set { (Gc.get ()) with Gc.minor_heap_size = 1_280_000 }

메이저 컬렉션 미루기

사실 메이저 힙에 메모리를 아예 할당하지 않는 것은 꽤 어렵다. 그것보다는, 어차피 문제 풀이에서는 테스트 셋만 통과하면 되니까, 메이저 힙 컬렉션을 아예 하지 않으면 추가적인 오버헤드가 없을 것이다. 하지만 이것은 더 예측하기 어려운데, 왜냐하면 메이저 힙 컬렉션을 안해버리면 거의 반드시 메모리 제한을 초과해버리기 때문이다.

따라서 가장 적당한 접근은 메이저 컬렉션을 최대한 미루는 것이다. 문제는 이것 역시 손쉽게 판단하기 어렵다는 것이다. 문제와 문제의 테스트 셋 특성에 따라서 메이저 힙의 공간 오버헤드를 얼마나 크게 가져갈 수 있을지가 다르다. 기본 값은 120 (살아있는 데이터의 120%) 인데, 문제마다 다양하게 실험해보고 적당한 값을 찾아야 한다.

let () = Gc.set { (Gc.get ()) with Gc.space_overhead = 1000 }

힙 압축 안하기

백준 채점용 컴파일러인 4.11.1에서는 이미 디폴트 할당 방식이 0 (Next Fit)이므로 할당 속도에는 문제가 없다. 힙 압축을 아예 꺼버리면 혹시나 발생할지 모를 힙 압축을 아예 하지 않을 수 있다.

let () = Gc.set { (Gc.get ()) with Gc.max_overhead = 1_000_001 }

예시

백준 11725번을 해시 테이블 + 정수 셋을 이용한 그래프로 풀면 3회 평균 297ms의 시간과 46MB 메모리가 나온다. 여기에 위의 Gc 정책을 각각 적용해보면 다음과 같다.

• 마이너 힙 늘리기: 286ms / 59MB
• 메이저 컬렉션 미루기 (1000%): 221ms / 49MB
• 메이저 컬렉션 미루기 (2000%): 204ms / 55MB
• 메이저 컬렉션 미루기 (2500%): 208ms / 53MB
• 메이저 컬렉션 미루기 (3000%): 233ms / 52MB
• 힙 압축 안하기: 309ms / 46MB
• 셋 다 적용: 250ms / 66MB

문제의 성격에 따라 당연히 다르겠지만 이 문제에서는 메이저 컬렉션만 미뤘을 때 (오버헤드 2000%) 가장 평균적인 속도가 빨랐다. 혹시 몰라서 마이너 힙 크기를 두 배 늘렸더니 메모리 사용량은 20MB 정도 늘어났지만 속도는 오히려 떨어졌기 때문에, 마이너 힙이 크다고 항상 좋은 것은 아닌 것 같다. 그리고 메이저 컬렉션을 미루기 위한 공간 오버헤드가 3000%을 넘어가니 유의미한 효과가 없었고, 10,000% 이상으로 주니 메모리 초과가 발생했다.

사실 정확한 측정을 하려면 수행 횟수를 최소 30번은 해야겠지만 그러긴 힘들어서 여기서는 3번의 수행만을 했기 때문에 오차 범위가 꽤 크다는 염두에 점을 두자. 그럼에도 불구하고 Gc를 튜닝하는 것이 문제 풀이 속도에 영향을 주는 것을 눈으로 확인할 수 있었기 때문에 문제에 맞게 이를 잘 활용하면 좋겠다. 그리고 무엇보다 문제와 채점 데이터의 성격에 따라서 작은 튜닝이 큰 영향을 줄 수 있기 때문에, 모든 문제에 맞는 은 총알은 없다는 것을 반드시 기억해야 한다.