RPython의 가비지 컬렉션

소개

저희의 가비지 컬렉션 전략과 프레임워크에 대한 개요와 설명은 EU-report on this topic에서 확인할 수 있습니다. 오래되었지만 여전히 대체로 정확한 설명을 보려면 해당 파일을 참고하십시오. 이 문서는 저희가 프레임워크에서 작성한 특정 가비지 컬렉터들을 설명합니다.

현재 GC 프레임워크용으로 작성된 가비지 컬렉터

참고: 번역(translation)된 RPython 프로그램에 어떤 GC를 포함할지 선택하려면 translate.py의 --gc=NAME 옵션을 사용하십시오. 자세한 내용은 overview of command line options for translation을 참고하십시오.

다음 개요는 시간 순서대로 작성되어 있으므로, “최선의” GC(번역(translation) 시 기본값)는 아래 목록의 마지막 항목입니다.

Mark and Sweep

전통적인 Mark and Sweep 컬렉터입니다. 실험적이고 절반쯤 유지 관리되지 않는 기능도 많이 포함하고 있었습니다. 제거되었습니다.

세미스페이스 복사 수집기(Semispace copying collector)

크기가 같은 두 개의 아레나가 있으며, 그중 하나만 사용되어 새 객체로 채워집니다. 아레나가 가득 차면, 살아 있는 객체들은 체니(Cheney)의 알고리즘을 사용해 다른 아레나로 복사됩니다. 그런 다음 이전 아레나는 비워집니다. 자세한 내용은 rpython/memory/gc/semispace.py를 참고하십시오.

Unix에서는 arena 안으로 /dev/zero를 읽어 들임으로써 지우기를 수행하며, 이는 적어도 리눅스에서는 메모리 효율이 대단히 뛰어난 방식입니다. 즉, 커널이 예전 arena가 사용하던 RAM을 해제하고 이를 모두 필요할 때 할당되는(allocated-on-demand) 메모리로 대체할 수 있게 해줍니다.

각 세미스페이스(semispace)의 크기는 8MB에서 시작하지만, 살아있는 객체의 양이 늘어남에 따라 필요한 만큼 커집니다.

세대별 GC

이것은 2세대 GC입니다. 다음을 참조하십시오: rpython/memory/gc/generation.py.

이는 세미스페이스(Semispace) 복사 컬렉터의 서브클래스로 구현됩니다. 이는 현재 세미스페이스의 한 조각인 너서리(nursery)를 추가합니다. 그 크기는 CPU 레벨 2 캐시 크기의 절반으로 계산됩니다. 할당은 너서리를 채우며, 너서리가 가득 차면 수집이 이루어져 여전히 살아 있는 객체들은 현재 세미스페이스의 나머지 부분으로 옮겨집니다.

객체가 생성된 직후 소멸하는 경우가 매우 흔하다는 것이 이 아이디어의 요지입니다. 세대별 가비지 컬렉터는 이런 경우에 큰 도움이 되며, 특히 프로그램이 실제로 다루는 살아있는 객체의 양이 레벨 2 캐시에 들어맞을 때 그렇습니다. 게다가 세미스페이스가 훨씬 천천히 채워지므로, 전체 컬렉션이 덜 빈번하게 발생합니다.

하이브리드 GC

이는 3세대 가비지 컬렉터(GC)입니다.

이는 세대별(Generational) GC의 하위 클래스로 구현됩니다. Hybrid GC는 세미스페이스 내부에 있는 객체와 외부(“external”)에 있는 객체를 모두 처리할 수 있습니다. 외부 객체는 이동하지 않으며 마크-스윕(mark-and-sweep) 방식으로 수집됩니다. 큰 객체는 비용이 큰 이동을 피하기 위해 외부 객체로 할당됩니다. 충분히 오랫동안(세미스페이스 수집을 여러 차례 거칠 만큼) 살아남은 작은 객체 역시 더 이상 이동하지 않도록 외부 객체로 전환됩니다.

이는 객체를 세 세대로 구분하는 것과 결합되어 있습니다. 각 세대는 이전 세대보다 훨씬 드물게 수집됩니다. 세대의 구분은 단순히 nursery / semispace / external로 나누는 것보다 약간 더 복잡합니다. 소스 코드 rpython/memory/gc/hybrid.py 시작 부분의 다이어그램을 참조하십시오.

Mark & Compact GC

트렁크에서 제거되었습니다. 다음 문서는 역사적 목적으로만 제공됩니다.

적어도 부분적으로 Squeak의 가비지 컬렉터에서 영감을 받은 이것은, 컬렉션이 객체를 제자리에서(in-place) 압축하는 단일 아레나(single-arena) GC입니다. 이 GC의 핵심 목표는 가능한 한 많은 메모리를 절약하면서(Semispace보다 나쁘지 않도록 하면서)도, 컬렉션 도중 메모리 사용량이 두 배로 치솟는 정점 없이 그렇게 하는 것입니다.

Semispace GC와 달리, 수집(collection)은 데이터에 대해 여러 번의 패스를 거쳐야 합니다. 이 때문에 수집 속도가 상당히 느려집니다. 이 문제를 완화하기 위한 향후 개선책으로는 Mark & Compact에 너서리(nursery)를 추가하는 방안이 있을 수 있습니다.

컬렉션 중에는 공간이 여전히 충분히 크면 이를 제자리에서 재사용합니다. 그렇지 않다면 더 크고 새로운 공간을 할당하여 객체들을 그곳으로 옮겨야 합니다; 다만 이 이동은 청크 단위로 이루어지며, 청크는 이동이 끝나는 즉시 정리됩니다(즉, OS로 반환됩니다). 이는 (OS의 관점에서) 컬렉션이 전체 메모리 사용량에 상당한 일시적 증가를 결코 초래하지 않음을 의미합니다.

더 정확히 말하면, 공간(space)에 있는 바이트 수가 N*M을 초과할 때 컬렉션(collection)이 트리거됩니다. 여기서 N은 이전 컬렉션 이후 살아있는 바이트 수이고, M은 상수 계수로 기본값은 1.5입니다. 이는 프로그램의 총 메모리 사용량이 살아있는 객체 전체 크기의 1.5배를 결코 초과하지 않음을 보장합니다.

객체 자체는 상당히 조밀합니다: 힙(heap)에서 서로 인접하게 할당되며, 단 한 워드(32비트 플랫폼에서는 4바이트)의 GC 헤더로 구분되고, 워드 크기가 아닌 객체(예: 문자열)의 경우 최대 3바이트의 패딩이 뒤따를 수 있습니다. 수집(collection) 중에는 약간의 추가 메모리 사용이 발생합니다: 컬렉터가 일반 헤더에 임시 관계 정보를 저장할 수 있도록, 생존한 객체들의 헤더(의 절반)를 백업하기 위해 생존 객체마다 2바이트를 담는 배열이 필요합니다.

Minimark GC

이는 Hybrid GC의 아이디어를 단순화하고 다시 작성한 것입니다. 어린 객체에는 너서리(nursery)를, 오래된 객체에는 마크-앤-스윕(mark-and-sweep) 방식을 사용합니다. 이는 이동형 GC(moving GC)이지만, 객체는 한 번만(너서리에서 오래된 단계로) 이동할 수 있습니다.

Hybrid GC와의 주된 차이점은, mark-and-sweep 객체(“old stage”)가 malloc() 호출로 처리되는 대신 GC의 커스텀 할당자에 의해 직접 처리된다는 점입니다. 이점은, 이렇게 하면 major collection 동안 포인터 목록을 저장할 필요 없이 모든 old generation 객체를 순회할 수 있다는 것입니다. 따라서 대략적으로 보면, Hybrid GC와 비교했을 때 Minimark GC는 old 객체 하나당 메모리 1워드를 절약합니다.

가비지 컬렉션에 영향을 미치도록 조정할 수 있는 여러 환경 변수가 있습니다. (기본값은 대부분의 용도에 적합할 것입니다.)

좀 더 자세히 설명하면 다음과 같습니다:

  • 새로 malloc된 작은 객체들은 nursery에 할당됩니다 (경우 1). nursery에 있는 모든 객체는 “young(젊은)” 상태입니다.
  • 큰 객체는 항상 시스템 malloc()에 의해 직접 처리됩니다. 하지만 새로 malloc된 큰 객체는 너서리에 있지 않더라도, 할당될 때(경우 2)는 여전히 “young” 상태입니다.
  • nursery가 가득 차면 마이너 컬렉션을 수행합니다. 즉, 어떤 “young” 객체가 (사례 1과 사례 2로부터) 아직 살아 있는지를 찾습니다. 그런 다음 “young” 플래그가 제거됩니다. 살아남은 사례 1 객체들은 old 단계로 옮겨집니다. 소멸하는 사례 2 객체들은 즉시 해제됩니다.
  • 올드 스테이지(old stage)는 오래된 (작은) 객체를 담고 있는 메모리 영역입니다. 이는 rpython/memory/gc/minimarkpage.py에서 처리됩니다. 이는 256KB 또는 512KB 크기의 “아레나(arena)”로 구성되며, 이는 다시 4KB 또는 8KB 크기의 “페이지(page)”로 세분됩니다. 각 페이지는 비어 있거나, 모두 같은 크기의 작은 객체를 담고 있을 수 있습니다. 또한 임의의 시점에 각 객체 위치는 할당되어 있거나 해제되어 있을 수 있습니다. 기본 설계는 CPython의 obmalloc.c에서 유래했습니다(이 역시 리눅스 시스템 malloc()과 동일한 소스에서 비롯되었습니다).
  • 새 객체는 마이너 컬렉션(minor collection)이 일어날 때마다 올드 스테이지(old stage)에 추가됩니다. 마이너 컬렉션 직후, 특정 임계값에 도달하면 메이저 컬렉션(major collection)을 실행합니다. 이는 마크 앤 스위프(mark-and-sweep) 단계입니다. 이 단계는 all 객체를 순회하며(마크), 그중 일부를 해제합니다(스위프). 이는 객체를 해제하려는 시점이 오직 모든 객체를 순회하는 동안뿐이라는 것을 의미합니다. 즉, 주소만 주어진 상태로 객체 해제를 요청하는 일은 결코 없습니다. 이를 통해 obmalloc.c와 비교했을 때 몇 가지 단순화와 메모리 절약이 가능합니다.
  • 모든 세대별 컬렉터가 그렇듯, 이 GC는 어떤 오래된 객체가 젊은 객체에 대한 참조를 갖는지 기록하기 위해 쓰기 배리어(write barrier)를 필요로 합니다.
  • 또한, 큰 배열의 경우를 특별히 처리하는 것이 유용하다는 사실을 알게 되었습니다. 큰 배열을 (시스템 malloc()으로) 할당할 때, 앞쪽에 적은 바이트를 미리 예약해 둡니다. 배열이 오래되면, 그 여분의 바이트를 비트 집합으로 사용합니다. 각 비트는 배열의 128개 항목을 나타냅니다. 배열의 N번째 항목에서 어떤 young 객체로의 참조를 기록하기 위해 쓰기 배리어(write barrier)가 호출될 때마다, 비트 번호 (N/128)을 1로 설정합니다. 이는 마이너 컬렉션(minor collection) 속도를 상당히 향상시킬 수 있는데, 그러면 배열의 모든 항목이 아니라 128개 항목만 스캔하면 되기 때문입니다.
  • 평소와 같이, 약한 참조(weak reference)와 소멸자(finalizer)가 있는 객체에 대해서는 특별한 주의가 필요합니다. 약한 참조는 너서리(nursery)에 할당되며, 살아남으면 다른 모든 객체와 마찬가지로 올드 스테이지(old stage)로 이동합니다. 차이점은 이들이 담고 있는 참조가 반드시 대상 객체를 따라가거나, 객체가 소멸하면 NULL로 설정되어야 한다는 점입니다. 그리고 소멸자가 있는 객체는 충분히 드물다고 간주되어, 설계를 단순화하기 위해 곧바로 올드(old)로 할당됩니다. 특히 이들의 __del__ 메서드는 메이저 컬렉션(major collection) 직후에만 호출될 수 있습니다.
  • 객체는 단 한 번만 이동하므로, 이를 이용해 id()와 hash()를 구현하는 트릭을 쓸 수 있습니다. 객체가 너서리(nursery)에 없다면 더 이상 이동하지 않으므로, 그 id()와 hash()는 정수로 캐스팅된 객체의 주소가 됩니다. 객체가 너서리에 있는 상태에서 id()나 hash()를 요청하면, 올드 스테이지(old stage)에 위치를 미리 예약해두고 그 위치의 주소를 반환합니다. 객체가 다음 마이너 컬렉션(minor collection)에서 살아남으면 그곳으로 이동시키므로, id()와 hash()가 보존됩니다. 객체가 죽으면 미리 예약해둔 위치는 빈 가비지가 되어, 다음 메이저 컬렉션(major collection) 때 수거됩니다.

이 GC의 정확한 이름은 minimark 또는 incminimark입니다. 후자는 메이저 컬렉션(major collection)을 점진적으로 수행하는 버전입니다(즉, 하나의 메이저 컬렉션이 특정 마이너 컬렉션 이후 한 번에 수행되는 대신, 여러 번의 마이너 컬렉션에 걸쳐 나뉘어 수행됩니다). 기본값은 incminimark이며, 이는 minimark의 긴 정지 시간을 피하는 이점을 얻으면서도 성능과 메모리 사용량에 미치는 영향은 매우 미미한 것으로 보이기 때문입니다.