RPython의 가비지 컬렉션

소개

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

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

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

다음 개요는 시간순으로 작성되었으므로, “가장 좋은” GC(변환 시 기본값으로 사용되는 GC)는 아래의 마지막 항목입니다.

마크 앤 스윕(Mark and Sweep)

고전적인 Mark and Sweep 컬렉터입니다. 실험적이고 반쯤 방치된 기능도 많이 포함하고 있었습니다. 제거되었습니다.

세미스페이스 복사 컬렉터

크기가 같은 아레나 두 개를 두되, 그중 한 아레나만 사용하면서 새 객체로 채워 나갑니다. 아레나가 가득 차면 Cheney 알고리즘을 사용하여 살아 있는 객체를 다른 아레나로 복사합니다. 그런 다음 이전 아레나를 비웁니다. rpython/memory/gc/semispace.py를 참고하십시오.

Unix에서는 /dev/zero를 아레나(arena)로 읽어 들이는 방식으로 초기화를 수행하며, 이 방식은 적어도 Linux에서는 메모리 효율이 매우 뛰어납니다. 커널이 이전 아레나가 사용하던 RAM을 해제하고, 그 전부를 요청 시 할당되는(allocated-on-demand) 메모리로 대체할 수 있게 해 주기 때문입니다.

각 세미스페이스(semispace)의 크기는 처음에 8MB이지만, 살아 있는 객체의 양이 늘어나면 필요에 따라 커집니다.

세대별 GC

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

이 컬렉터는 세미스페이스(Semispace) 복사 컬렉터의 서브클래스로 구현되어 있습니다. 이 컬렉터는 현재 세미스페이스(semispace)의 일부 영역인 너서리(nursery)를 추가합니다. 너서리의 크기는 CPU 레벨 2 캐시 크기의 절반으로 계산됩니다. 할당은 nursery를 채우며, nursery가 가득 차면 컬렉션이 수행되고 아직 살아 있는 객체는 현재 세미스페이스의 나머지 영역으로 옮겨집니다.

이 아이디어의 요지는 객체가 생성된 직후 곧 소멸하는 경우가 매우 흔하다는 것입니다. 세대별 GC는 이런 경우에 큰 도움이 되며, 특히 프로그램이 실제로 다루는 살아 있는 객체의 양이 L2 캐시에 들어갈 만큼일 때 더욱 그렇습니다. 게다가 세미스페이스가 훨씬 더 천천히 채워지므로 전체 컬렉션이 덜 자주 일어납니다.

하이브리드 GC

이것은 3세대 GC입니다.

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

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

Mark & Compact GC

트렁크에서 제거되었습니다. 다음 문서는 기록 보존 목적으로만 제공됩니다.

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

세미스페이스 GC와 달리, 컬렉션을 수행하려면 데이터를 여러 차례 순회해야 합니다. 이 때문에 컬렉션이 상당히 느려집니다. 향후 개선 방안으로는 이 문제를 완화하기 위해 Mark & Compact에 너서리(nursery)를 추가하는 방법을 생각해 볼 수 있습니다.

컬렉션을 수행하는 동안 공간이 여전히 충분히 크다면 그 공간을 제자리에서 재사용합니다. 그렇지 않다면 더 큰 새 공간을 할당하고 객체들을 그곳으로 옮겨야 합니다. 다만 이 이동은 청크 단위로 이루어지며, 각 청크는 옮겨지는 즉시 비워집니다(즉, OS에 반환됩니다). 이는 (OS의 관점에서 보면) 컬렉션 때문에 전체 메모리 사용량이 일시적으로 크게 증가하는 일은 결코 없다는 뜻입니다.

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

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

Minimark GC

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

Hybrid GC와의 주요 차이점은 마크 앤 스윕(mark-and-sweep) 객체(“old stage”)를 malloc() 호출로 처리하지 않고 GC의 자체 할당자가 직접 처리한다는 점입니다. 그 덕분에 메이저 컬렉션 중에 오래된 세대의 객체를 가리키는 포인터 목록을 따로 저장하지 않고도 그 객체들을 모두 순회할 수 있다는 이점이 있습니다. 따라서 대략적으로 말하면, Minimark GC는 Hybrid GC에 비해 오래된 객체 하나당 메모리를 한 워드씩 절약합니다.

GC에 영향을 주도록 조정할 수 있는 여러 환경 변수가 있습니다. (대부분의 용도에는 기본값으로 충분할 것입니다.)

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

  • 새로 malloc된 작은 객체는 너서리(nursery)에 할당됩니다(경우 1). nursery에 있는 모든 객체는 “젊은(young)” 객체입니다.
  • 큰 객체는 항상 시스템 malloc()이 직접 처리합니다. 하지만 새로 malloc된 큰 객체는 너서리(nursery)에 있지 않더라도 할당될 때에는 여전히 “젊은(young)” 객체입니다(경우 2).
  • 너서리(nursery)가 가득 차면 마이너 컬렉션을 수행합니다. 즉, (경우 1과 경우 2에 해당하는 객체 가운데) 어떤 “젊은(young)” 객체가 아직 살아 있는지 찾습니다. 그런 다음 “젊은(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) 단계입니다. 이 단계에서는 모든 객체를 순회한 다음(마크), 그중 일부를 해제합니다(스윕). 즉, 객체를 해제하려는 때는 모든 객체를 순회하는 동안뿐이며, 주소만 가지고 객체 하나를 해제하도록 요청하는 일은 결코 없습니다. 이 덕분에 obmalloc.c와 비교했을 때 구현을 어느 정도 단순화하고 메모리도 절약할 수 있습니다.
  • 모든 세대별 컬렉터와 마찬가지로, 이 GC에도 어떤 오래된 객체가 젊은 객체를 참조하고 있는지 기록하기 위한 쓰기 배리어(write barrier)가 필요합니다.
  • 또한 큰 배열은 따로 특별하게 처리하는 것이 유용하다는 사실을 알게 되었습니다. 큰 배열을 (시스템 malloc()으로) 할당할 때 그 앞에 적은 수의 바이트를 예약해 둡니다. 배열이 오래되면 이 여분의 바이트를 비트 집합으로 사용합니다. 각 비트는 배열의 항목 128개를 나타냅니다. 배열의 N번째 항목에서 어떤 젊은 객체로의 참조를 기록하기 위해 쓰기 배리어(write barrier)가 호출될 때마다 (N/128)번째 비트를 1로 설정합니다. 이렇게 하면 배열의 모든 항목 대신 128개 항목만 스캔하면 되므로 마이너 컬렉션(minor collection)의 속도를 상당히 높일 수 있습니다.
  • 늘 그렇듯이 약한 참조(weak reference)와 파이널라이저(finalizer)가 있는 객체에는 특별한 주의가 필요합니다. 약한 참조는 너서리(nursery)에 할당되며, 살아남으면 다른 모든 객체와 마찬가지로 old 단계로 이동합니다. 다른 점은 약한 참조가 담고 있는 참조가 객체를 따라가거나, 객체가 죽으면 NULL로 설정되어야 한다는 것입니다. 그리고 파이널라이저가 있는 객체는 충분히 드물다고 보고, 설계를 단순화하기 위해 처음부터 old 영역에 할당합니다. 특히 이러한 객체의 __del__ 메서드는 메이저 컬렉션(major collection) 직후에만 호출될 수 있습니다.
  • 객체는 단 한 번만 이동하므로, id()와 해시 함수 hash()를 구현하는 데 한 가지 요령을 사용할 수 있습니다. 객체가 nursery에 있지 않으면 더 이상 이동하지 않으므로, 그 객체의 id()와 해시 값 hash()는 객체의 주소를 정수로 캐스팅한 값입니다. 객체가 nursery에 있는 상태에서 그 객체의 id()나 해시 값 hash()를 요청하면, 오래된 단계에 위치 하나를 미리 예약하고 그 위치의 주소를 반환합니다. 객체가 다음 마이너 컬렉션에서 살아남으면 객체를 그 위치로 이동시키므로, 그 객체의 id()와 해시 값 hash()가 그대로 유지됩니다. 객체가 죽으면 미리 예약해 둔 위치는 해제된 가비지가 되어, 다음 메이저 컬렉션(major collection) 때 수거됩니다.

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