기본 가비지 컬렉션 기법들

가비지 컬렉터의 기본적인 두 단계 동작 방식을 생각해보면, 다양한 변형들이 가능합니다. 첫 번째 단계인 살아있는 객체와 가비지를 구분하는 작업은 두 가지 방법으로 할 수 있습니다: 참조 카운팅(reference counting)이나 추적(tracing)입니다. 참조 카운팅 가비지 컬렉터는 각 객체를 가리키는 포인터의 개수를 세서, 이 카운트를 실제 살아있는지 판단하는 지역적 근사값으로 사용합니다. 반면 추적 컬렉터는 프로그램이 도달할 수 있는 포인터들을 실제로 따라가면서 살아있음을 더 직접적으로 판단합니다. 추적 컬렉션에는 여러 종류가 있습니다: 마크-스윕(mark-sweep), 마크-컴팩트(mark-compact), 복사(copying), 그리고 비복사 암시적 회수(non-copying implicit reclamation)입니다. 각각의 가비지 탐지 방식이 회수와 재사용 기법에 큰 영향을 미치기 때문에, 회수 방법들도 함께 소개하겠습니다.

참조 카운팅

참조 카운팅 시스템에서는 각 객체가 자신을 가리키는 참조(포인터)의 개수를 가지고 있습니다. 객체에 대한 참조가 생성될 때마다, 예를 들어 대입문으로 포인터가 한 곳에서 다른 곳으로 복사될 때, 가리켜진 객체의 카운트가 증가합니다. 기존 참조가 제거되면 카운트가 감소하죠. 객체의 카운트가 0이 되면 그 메모리를 회수할 수 있습니다. 왜냐하면 그 객체를 가리키는 포인터가 없다는 것은 실행 중인 프로그램이 그 객체에 도달할 수 없다는 의미니까요.

전형적인 참조 카운팅 시스템에서는 각 객체가 헤더 필드를 가지고 있는데, 여기에 객체를 설명하는 정보가 들어있고 참조 카운트를 위한 하위 필드도 포함됩니다. 다른 헤더 정보들처럼 참조 카운트는 보통 언어 레벨에서는 보이지 않습니다.

객체가 회수될 때는 그 객체의 포인터 필드들을 검사해서, 그 객체가 가리키던 다른 객체들의 참조 카운트도 감소시킵니다. 가비지 객체로부터의 참조는 살아있음을 판단하는데 포함되지 않으니까요. 따라서 하나의 객체를 회수하면 참조 카운트가 연쇄적으로 감소하면서 다른 많은 객체들도 함께 회수될 수 있습니다. 예를 들어, 큰 자료구조를 가리키던 유일한 포인터가 가비지가 되면, 그 구조 안의 모든 객체들의 참조 카운트가 대개 0이 되면서 모든 객체가 회수됩니다.

추상적인 2단계 가비지 컬렉션의 관점에서 보면, 참조 카운트를 조정하고 확인하는 작업이 첫 번째 단계를 구현하는 것이고, 참조 카운트가 0이 될 때 회수 단계가 일어납니다. 이 두 작업은 프로그램 실행과 섞여서 일어나는데, 포인터가 생성되거나 제거될 때마다 발생할 수 있기 때문입니다.

참조 카운팅의 한 가지 장점은 바로 이런 점진적(incremental) 특성입니다 - 가비지 컬렉션 작업(참조 카운트 업데이트)이 실행 중인 프로그램과 긴밀하게 섞여서 일어나죠. 완전히 점진적이고 실시간(real time)으로 만들기도 쉽습니다. 즉, 프로그램 실행 단위당 작고 제한된 양의 작업만 수행하도록 할 수 있습니다.

명백히, 일반적인 참조 카운트 조정은 본질적으로 점진적입니다. 프로그램이 실행하는 어떤 작업에 대해서도 몇 가지 연산 이상을 필요로 하지 않으니까요. 전체 자료구조의 연쇄적 회수는 나중으로 미룰 수 있고, 조금씩 처리할 수도 있습니다. 참조 카운트가 0이 되었지만 아직 처리되지 않은 해제된 객체들의 리스트를 유지하면 됩니다.

이런 점진적 컬렉션은 “실시간” 요구사항을 쉽게 만족시킬 수 있어서, 메모리 관리 작업이 실행 중인 프로그램을 아주 짧은 시간 이상 멈추지 않는다는 것을 보장합니다. 이는 응답 시간 보장이 중요한 애플리케이션을 지원할 수 있습니다. 점진적 컬렉션은 프로그램이 어떤 유의미한 시간 동안에도 상당한, 비록 눈에 띄게 줄어들긴 했지만, 작업량을 수행할 수 있도록 보장합니다.

참조 카운팅 시스템의 작은 문제 하나는 참조 카운트 자체가 공간을 차지한다는 점입니다. 어떤 시스템에서는 각 객체의 참조 카운트 필드에 머신 워드 전체를 사용해서, 시스템 전체에 실제로 존재할 수 있는 모든 포인터 개수를 표현할 수 있게 합니다. 다른 시스템들은 더 짧은 필드를 사용하면서 오버플로우에 대비합니다 - 참조 카운트가 필드 크기로 표현할 수 있는 최대값에 도달하면, 그 카운트를 최대값으로 고정하고 객체를 회수할 수 없게 합니다. 이런 객체들(과 거기서 도달 가능한 다른 객체들)은 다른 메커니즘으로 회수해야 하는데, 보통 가끔 실행되는 추적 컬렉터를 사용합니다. 아래에서 설명하겠지만, 이런 대비책 회수 전략은 어차피 보통 필요합니다.

참조 카운팅 가비지 컬렉터에는 두 가지 주요 문제가 있습니다. 항상 효과적(effective)이지 않고, 효율적(efficient)으로 만들기 어렵다는 점입니다.

순환 구조 문제

효과성 문제는 참조 카운팅이 순환(circular) 구조를 회수하지 못한다는 것입니다. 객체 그룹의 포인터들이 (방향성) 순환을 만들면, 루트 집합에서 그 객체들로 가는 경로가 없더라도 객체의 참조 카운트가 절대 0으로 줄어들지 않습니다.

고립된 두 객체 쌍을 생각해봅시다. 각각이 다른 객체를 가리키는 포인터를 가지고 있어서, 둘 다 참조 카운트가 1입니다. 하지만 루트에서 둘 중 어느 것으로도 가는 경로가 없기 때문에, 프로그램은 그것들에 절대 다시 도달할 수 없습니다.

개념적으로 말하면, 여기서 문제는 참조 카운팅이 실제로는 진짜 살아있음의 보수적 근사값(conservative approximation)만 판단한다는 점입니다. 객체가 어떤 변수나 다른 객체에게도 가리켜지지 않으면 명백히 가비지지만, 그 역은 종종 참이 아닙니다.

순환 구조가 매우 드물 것 같지만, 실제로는 그렇지 않습니다. 대부분의 자료구조가 비순환적이긴 하지만, 일반 프로그램들이 약간의 순환을 만드는 것은 드물지 않고, 몇몇 프로그램은 아주 많이 만듭니다. 예를 들어, 트리의 노드들이 특정 연산을 쉽게 하기 위해 부모로 가는 “역포인터”를 가질 수 있습니다. 더 복잡한 순환들은 때때로 더 단순한 자료구조들의 장점을 결합한 하이브리드 자료구조를 사용할 때나, 응용 도메인의 의미가 순환으로 가장 자연스럽게 표현될 때 생성됩니다.

따라서 참조 카운팅 가비지 컬렉터를 사용하는 시스템들은 보통 다른 종류의 가비지 컬렉터도 함께 포함합니다. 그래서 회수 불가능한 순환 가비지가 너무 많이 쌓이면, 다른 방법으로 회수할 수 있습니다.

참조 카운팅 시스템을 사용하는 많은 프로그래머들(Interlisp이나 초기 버전 Smalltalk 같은)은 순환 가비지 생성을 피하거나 골칫거리가 되기 전에 순환을 끊도록 프로그래밍 스타일을 수정해왔습니다. 이는 프로그램 구조에 부정적인 영향을 미치고, 많은 프로그램들이 여전히 다른 수단으로 회수해야 하는 순환 가비지를 축적하는 저장소 “누수”를 겪습니다. 이런 누수는 알고리즘의 실시간 특성을 해칠 수 있는데, 중요한 순간에 비실시간 컬렉터를 사용해야 할 수도 있기 때문입니다.

효율성 문제

참조 카운팅의 효율성 문제는 그 비용이 일반적으로 실행 중인 프로그램이 하는 작업량에 비례하며, 비례 상수가 꽤 크다는 점입니다. 한 가지 비용은 포인터가 생성되거나 제거될 때 참조 대상의 카운트를 조정해야 한다는 것입니다. 변수의 값이 한 포인터에서 다른 포인터로 바뀌면 두 객체의 카운트를 조정해야 합니다 - 한 객체의 참조 카운트는 증가시키고, 다른 객체의 것은 감소시킨 다음 0이 되었는지 확인해야 합니다.

단순한 참조 카운팅 방식에서는 수명이 짧은 스택 변수들이 많은 오버헤드를 발생시킬 수 있습니다. 예를 들어 인자가 전달될 때 새 포인터가 스택에 나타나고, 대부분의 프로시저 활성화는 (호출 그래프의 말단 근처에서) 호출된 직후 아주 빨리 반환되기 때문에 보통 거의 즉시 사라집니다. 이런 경우들에서 참조 카운트가 증가했다가 아주 빨리 원래 값으로 다시 감소합니다. 서로를 상쇄하는 이런 증가와 감소 대부분을 최적화해서 없애는 것이 바람직합니다.

지연된 참조 카운팅

이 비용의 많은 부분은 지역 변수를 특별히 처리해서 최적화할 수 있습니다. 항상 참조 카운트를 조정하고 카운트가 0이 된 객체를 회수하는 대신, 지역 변수로부터의 참조는 대부분의 시간 동안 이 부기 작업에 포함되지 않습니다. 보통 한 힙 객체에서 다른 힙 객체로의 포인터만 참조 카운트가 조정됩니다. 이는 스택의 포인터들이 계산에 포함되지 않고 생성되거나 제거될 수 있기 때문에 참조 카운트가 정확하지 않을 수 있다는 뜻입니다. 그 결과 카운트가 0으로 떨어진 객체가 실제로는 회수 가능하지 않을 수 있습니다. 가비지 컬렉션은 스택의 참조도 고려할 때만 수행될 수 있습니다.

가끔씩 스택을 스캔해서 힙 객체를 가리키는 포인터를 찾아 참조 카운트를 최신 상태로 만듭니다. 그러고 나서 참조 카운트가 여전히 0인 객체들을 안전하게 회수할 수 있습니다. 이 단계들 사이의 간격은 일반적으로 가비지가 자주 빨리 회수될 만큼 충분히 짧으면서도, (스택 참조를 위해) 주기적으로 카운트를 업데이트하는 비용이 높지 않을 만큼 충분히 길도록 선택됩니다.

이런 지연된 참조 카운팅(deferred reference counting)은 스택의 수명이 짧은 포인터들 대부분에 대한 참조 카운트 조정을 피해서, 참조 카운팅의 오버헤드를 크게 줄입니다. 하지만 한 힙 객체에서 다른 힙 객체로의 포인터가 생성되거나 제거될 때는 여전히 참조 카운트를 조정해야 합니다. 이 비용은 대부분의 시스템에서 여전히 실행 중인 프로그램이 하는 작업량에 대략 비례하지만, 비례 상수가 더 낮습니다.

참조 카운팅의 변형들

참조 카운팅의 또 다른 최적화는 아주 작은 카운트 필드를, 아마도 단일 비트만 사용해서 객체당 큰 필드가 필요 없게 하는 것입니다. 지연된 참조 카운팅이 스택의 포인터 카운트를 계속 표현할 필요를 피하기 때문에, 대부분의 객체에는 단일 비트로 충분합니다. 참조 카운트가 0이나 1이 아닌 소수의 객체들은 참조 카운팅 시스템으로 회수할 수 없지만, 대비책 추적 컬렉터가 잡아냅니다. 1비트 참조 카운트는 사용하지 않는 주소 비트가 있다면 헤더 필드 대신 객체를 가리키는 각 포인터에 표현할 수도 있습니다.

참조 카운팅 컬렉션에는 피하기 어려운 또 다른 비용이 있습니다. 객체의 카운트가 0이 되어 회수될 때, 실행 중인 프로그램이 재사용할 수 있게 하려면 약간의 부기 작업을 해야 합니다. 보통 이는 해제된 객체들을 재사용 가능한 객체들의 하나 이상의 “자유 리스트(free list)”에 연결하는 것을 포함하는데, 여기서 프로그램의 할당 요청이 만족됩니다. 또한 객체의 포인터 필드들을 검사해서 참조 대상들을 해제할 수 있어야 합니다.

이런 회수 작업이 객체당 수십 개의 명령어보다 적게 걸리도록 만들기 어렵고, 따라서 비용은 실행 중인 프로그램이 할당하는 객체 수에 비례합니다.

참조 카운팅 컬렉션의 이런 비용들이 순환 구조 회수 실패와 결합되어 최근 몇 년간 대부분의 구현자들에게 매력적이지 않게 만들었습니다. 다른 기법들이 보통 더 효율적이고 신뢰할 수 있습니다. 그래도 참조 카운팅은 장점이 있습니다. 즉각적인 회수는 전체 메모리 사용량과 참조 지역성에 이점이 있을 수 있습니다. 참조 카운팅 시스템은 힙 공간의 거의 전부가 살아있는 객체로 차 있을 때도 성능 저하가 거의 없이 작동할 수 있지만, 다른 컬렉터들은 더 높은 효율성을 위해 더 많은 공간을 희생합니다. 또한 종료 처리(finalisation)에도 유용할 수 있는데, 즉 객체가 죽을 때 (파일 닫기 같은) “정리” 작업을 수행하는 것입니다.

순환 구조를 회수하지 못하는 문제는 순환 자료구조 생성을 전혀 허용하지 않는 일부 언어들(예: 순수 함수형 언어)에서는 문제가 되지 않습니다. 비슷하게, 힙 객체 간 포인터를 부작용으로 바꾸는 상대적으로 높은 비용은 부작용이 적은 언어들에서는 문제가 되지 않습니다. 참조 카운트 자체가 일부 시스템에서는 가치 있을 수 있습니다. 예를 들어, 유일하게 참조되는 객체를 파괴적으로 수정할 수 있게 해서 함수형 언어 구현의 최적화를 지원할 수 있습니다. 분산 가비지 컬렉션은 전역 추적에 비해 가비지 컬렉션의 지역적 특성에서 이득을 볼 수 있습니다. 어떤 구성에서는 참조 카운팅 비용이 다른 노드의 객체를 가리키는 포인터에 대해서만 발생하고, 노드 내에서는 추적 컬렉션을 사용하며 노드 간 참조 카운트 변경을 계산합니다. 미래의 시스템들은 아마도 하이브리드 컬렉터에서 다른 기법들과 함께, 또는 CPU 비용을 낮추는 특화된 하드웨어로 보강되어 참조 카운팅의 다른 용도를 찾을 수도 있습니다.

참조 카운팅이 범용 프로그래밍 언어의 고성능 구현에서는 유행을 벗어났지만, 비순환 자료구조가 흔한 다른 응용 프로그램들에서는 꽤 일반적입니다. 대부분의 파일 시스템은 파일이나 디스크 블록을 관리하는데 참조 카운팅을 사용합니다. 단순함 때문에 단순 참조 카운팅은 간단한 인터프리터 언어나 그래픽 툴킷을 포함한 여러 소프트웨어 패키지에서 자주 사용됩니다. 순환 회수 영역의 약점에도 불구하고, 참조 카운팅은 순환이 발생할 수 있는 시스템에서도 흔합니다.

마크-스윕 컬렉션

마크-스윕 가비지 컬렉터는 앞서 설명한 추상적인 가비지 컬렉션 알고리즘을 구현하는 두 단계의 이름을 딴 것입니다:

1. 살아있는 객체를 가비지와 구분하기. 이는 추적으로 수행됩니다 - 루트 집합에서 시작해서 포인터 관계의 그래프를 실제로 순회합니다 - 보통 깊이 우선 또는 너비 우선 탐색으로. 도달한 객체들은 어떤 방식으로든 표시(mark)됩니다. 객체 내의 비트를 바꾸거나, 비트맵이나 다른 종류의 테이블에 기록할 수도 있습니다.

2. 가비지 회수하기. 살아있는 객체들이 가비지 객체들과 구분 가능하게 되면, 메모리를 훑어서(sweep) (철저히 검사해서) 표시되지 않은 (가비지) 객체들을 모두 찾아 그 공간을 회수합니다. 전통적으로 참조 카운팅과 마찬가지로, 이렇게 회수된 객체들은 할당 루틴이 접근할 수 있도록 하나 이상의 자유 리스트에 연결됩니다.

전통적인 마크-스윕 가비지 컬렉터에는 세 가지 주요 문제가 있습니다. 첫째, 가용 메모리의 단편화 없이 다양한 크기의 객체들을 다루기 어렵습니다. 회수되는 가비지 객체들이 살아있는 객체들과 섞여 있어서, 큰 객체를 할당하기 어려울 수 있습니다. 여러 작은 가비지 객체들이 큰 연속적인 공간을 만들지 못할 수 있습니다. 다양한 크기의 객체들을 위한 별도의 자유 리스트를 유지하고 인접한 자유 공간들을 병합함으로써 이를 어느 정도 완화할 수 있지만, 어려움은 남아있습니다. 시스템은 작은 데이터 객체를 생성하기 위해 필요에 따라 더 많은 메모리를 할당할지, 아니면 큰 연속적인 자유 메모리 덩어리들을 나눠서 영구적으로 단편화할 위험을 감수할지 선택해야 합니다. 이 단편화 문제는 마크-스윕에만 국한된 것이 아닙니다 - 참조 카운팅과 대부분의 명시적 힙 관리 방식에서도 발생합니다.

마크-스윕 컬렉션의 두 번째 문제는 컬렉션 비용이 살아있는 객체와 가비지 객체를 모두 포함한 힙 크기에 비례한다는 점입니다. 모든 살아있는 객체들을 표시해야 하고, 모든 가비지 객체들을 수집해야 해서, 효율성 개선 가능성에 근본적인 한계를 부과합니다.

세 번째 문제는 참조 지역성과 관련이 있습니다. 객체들이 절대 이동하지 않기 때문에, 살아있는 객체들은 컬렉션 후에도 제자리에 남아 자유 공간과 섞여있습니다. 그러면 새 객체들이 이 공간들에 할당됩니다. 결과적으로 매우 다른 나이의 객체들이 메모리에서 섞이게 됩니다. 이는 참조 지역성에 부정적인 영향을 미치고, 단순한 (세대별이 아닌) 마크-스윕 컬렉터는 대부분의 가상 메모리 응용 프로그램에 적합하지 않다고 종종 여겨집니다. 활성 객체들의 “작업 집합”이 많은 가상 메모리 페이지에 흩어져서, 그 페이지들이 주 메모리로 자주 스왑되고 나갈 수 있습니다. 이 문제가 많은 사람들이 생각한 것만큼 나쁘지 않을 수 있는데, 객체들이 종종 동시에 활성화되는 클러스터로 생성되기 때문입니다. 하지만 일반적인 경우에는 단편화와 지역성 문제를 피할 수 없고, 일부 프로그램에는 잠재적인 문제입니다.

이런 문제들이 충분히 영리한 구현 기법으로 극복 불가능하지 않을 수 있다는 점을 주목해야 합니다. 예를 들어, 표시 비트에 비트맵을 사용하면 32비트 정수 ALU 연산과 조건 분기로 32비트를 한 번에 확인할 수 있습니다. 살아있는 객체들이 명백히 종종 그러는 것처럼 메모리에서 클러스터로 생존하는 경향이 있다면, 이는 스윕 단계 비용의 비례 상수를 크게 줄일 수 있습니다. 힙 크기에 대한 이론적 선형 의존성이 처음 보기만큼 문제가 되지 않을 수 있습니다. 객체들의 클러스터 생존은 살아있는 객체들 사이에 공간을 재할당하는 지역성 문제도 완화할 수 있습니다. 메모리에서 객체들이 그룹으로 생존하거나 죽는 경향이 있다면, 다른 프로그램 단계에서 사용되는 객체들이 섞이는 것이 주요 고려사항이 아닐 수 있습니다.

마크-컴팩트 컬렉션

마크-컴팩트(mark-compact) 컬렉터는 마크-스윕 컬렉터의 단편화와 할당 문제를 해결합니다. 마크-스윕처럼 표시 단계가 도달 가능한 객체들을 순회하고 표시합니다. 그런 다음 객체들이 압축(compact)되어, 대부분의 살아있는 객체들이 모든 살아있는 객체가 연속적이 될 때까지 이동합니다. 이는 나머지 메모리를 단일 연속 자유 공간으로 남깁니다. 이는 종종 메모리를 선형으로 스캔해서 살아있는 객체를 찾고 이전 객체에 인접하도록 “미끄러뜨려서(sliding)” 수행됩니다. 결국 모든 살아있는 객체들이 살아있는 이웃에 인접하도록 미끄러져 내려갑니다. 이는 힙 메모리의 한쪽 끝에 하나의 연속된 점유 영역을 남기고, 암묵적으로 모든 “구멍”을 다른 쪽 끝의 연속 영역으로 옮깁니다.

이 슬라이딩 압축에는 몇 가지 흥미로운 속성이 있습니다. 연속된 자유 영역은 단편화 문제를 제거해서 다양한 크기의 객체를 할당하는 것이 간단해집니다. 할당은 스택에 다양한 크기의 객체를 할당하는 방식과 비슷하게, 연속 메모리 영역으로의 포인터를 증가시키는 것으로 구현될 수 있습니다. 게다가 가비지 공간들이 단순히 “짜내져서” 메모리에서 객체들의 원래 순서를 방해하지 않습니다. 이는 지역성 문제를 완화할 수 있는데, 할당 순서가 보통 복사 가비지 컬렉터가 부과하는 임의의 순서보다 후속 접근 순서와 더 유사하기 때문입니다.

슬라이딩 압축으로 인한 지역성이 유리하긴 하지만, 컬렉션 프로세스 자체는 마크-스윕의 불행한 속성을 공유합니다. 즉 데이터에 대한 여러 번의 패스가 필요합니다. 초기 표시 단계 후에, 슬라이딩 컴팩터는 살아있는 객체들에 대해 두세 번 더 패스를 수행합니다. 한 번의 패스는 객체들이 이동할 새 위치를 계산하고, 후속 패스들은 객체들의 새 위치를 가리키도록 포인터를 업데이트하고 실제로 객체들을 이동시킵니다. 따라서 이 알고리즘들은 데이터의 큰 비율이 압축되도록 생존한다면 마크-스윕보다 상당히 느릴 수 있습니다.

대안적 접근법은 Daniel J. Edwards의 두 포인터 알고리즘(two-pointer algorithm)을 사용하는 것인데, 힙 공간의 양 끝에서 안쪽으로 스캔해서 압축 기회를 찾습니다. 한 포인터는 힙의 꼭대기에서 아래로 스캔해서 살아있는 객체를 찾고, 다른 포인터는 바닥에서 위로 스캔해서 그것들을 넣을 구멍을 찾습니다. 이 알고리즘의 많은 변형이 가능한데, 다양한 크기의 객체들을 보유하는 여러 영역을 다루고, 널리 분산된 영역의 객체들이 섞이는 것을 피하기 위해서입니다.

복사 가비지 컬렉션

마크-컴팩트처럼 (하지만 마크-스윕과 달리), 복사(copying) 가비지 컬렉션은 가비지를 실제로 “수집”하지 않습니다. 오히려 모든 살아있는 객체를 한 영역으로 옮기고, 나머지 힙은 가비지만 포함하고 있기 때문에 사용 가능한 것으로 알려집니다. 따라서 이런 시스템에서 “가비지 컬렉션”은 암시적일 뿐이고, 일부 연구자들은 그 프로세스에 그 용어를 적용하는 것을 피합니다.

복사 컬렉터는 표시-압축 컬렉터처럼 순회로 도달한 객체들을 연속 영역으로 옮깁니다. 표시-압축 컬렉터가 살아있는 데이터를 순회하는 별도의 표시 단계를 사용하는 반면, 복사 컬렉터는 데이터 순회와 복사 프로세스를 통합해서 대부분의 객체가 단 한 번만 순회되면 됩니다. 객체들은 순회에 의해 도달될 때 연속 목적지 영역으로 이동합니다. 필요한 작업은 살아있는 데이터의 양에 비례합니다 (모두 복사되어야 하므로).

스캐빈징(scavenging)이라는 용어가 복사 순회에 적용되는데, 가비지 속에서 가치 있는 객체들을 골라내서 가져가는 것으로 구성되기 때문입니다.

단순 복사 컬렉터: 반공간을 사용한 “정지-복사”

매우 일반적인 종류의 복사 가비지 컬렉터는 복사 순회를 위해 Cheney 알고리즘을 사용하는 반공간(semispace) 컬렉터입니다. 이 컬렉터를 이 논문의 참조 모델로 사용하겠습니다. 역사적 주석으로, 최초의 복사 컬렉터는 Lisp 1.5를 위한 Minsky의 컬렉터였습니다. 메모리의 한 영역에서 다른 영역으로 데이터를 복사하는 대신, 단일 힙 공간이 사용되었습니다. 살아있는 데이터가 디스크의 파일로 복사되고, 그런 다음 힙 공간의 연속 영역으로 다시 읽혀졌습니다. 현대 기계에서 이는 참을 수 없이 느릴 것인데, 파일 작업 - 모든 살아있는 객체를 쓰고 읽기 - 이 이제 메모리 작업보다 여러 배 느리기 때문입니다.

이 방식에서 힙에 할당된 공간은 두 개의 연속적인 반공간으로 세분됩니다. 정상적인 프로그램 실행 중에는 이 반공간들 중 하나만 사용됩니다. 메모리는 실행 중인 프로그램이 요구하는 대로 이 “현재” 반공간을 통해 선형적으로 위로 할당됩니다. 마크-컴팩트 컬렉터처럼, 큰 연속 자유 공간에서 할당할 수 있다는 것은 할당을 간단하고 빠르게 만들어서, 스택에 할당하는 것과 비슷합니다. 다양한 크기의 객체를 할당할 때 단편화 문제가 없습니다.

실행 중인 프로그램이 현재 반공간의 미사용 영역에 맞지 않는 할당을 요구하면, 프로그램이 중지되고 복사 가비지 컬렉터가 호출되어 공간을 회수합니다 (따라서 “정지-복사(stop-and-copy)”라는 용어). 모든 살아있는 데이터가 현재 반공간(fromspace)에서 다른 반공간(tospace)으로 복사됩니다. 복사가 완료되면 tospace 반공간이 “현재” 반공간이 되고, 프로그램 실행이 재개됩니다. 따라서 두 공간의 역할이 가비지 컬렉터가 호출될 때마다 바뀝니다.

아마도 가장 단순한 형태의 복사 순회는 Cheney 알고리즘입니다. 즉시 도달 가능한 객체들이 너비 우선 탐색을 위한 초기 큐를 형성합니다. “스캔” 포인터가 첫 번째 객체를 통해 위치별로 전진합니다. fromspace로의 포인터가 나타날 때마다, 참조된 객체가 큐의 끝으로 이동하고, 객체에 대한 포인터가 새 복사본을 가리키도록 업데이트됩니다. 그러면 자유 포인터가 전진하고 스캔이 계속됩니다. 이는 너비 우선 탐색을 위한 “노드 확장”을 수행해서, 그 노드의 모든 자손들에 도달하고 (복사하고) 합니다.

첫 번째 객체의 끝에서 멈추는 대신, 스캔 프로세스는 단순히 후속 객체들을 통해 계속되어, 그들의 자손을 찾고 그것들도 복사합니다. 큐의 시작부터의 연속 스캔은 연속된 노드들을 제거하고 그들의 모든 자손을 찾는 효과가 있습니다. 자손들은 큐의 끝으로 복사됩니다. 결국 스캔이 큐의 끝에 도달하는데, 이는 도달하고 (복사된) 모든 객체들도 자손을 위해 스캔되었다는 것을 의미합니다. 이는 더 이상 복사할 도달 가능한 객체가 없다는 것을 의미하며, 스캐빈징 프로세스가 끝났습니다.

실제로는 약간 더 복잡한 프로세스가 필요한데, 여러 경로로 도달한 객체들이 tospace로 여러 번 복사되지 않도록 하기 위해서입니다. 객체가 tospace로 이동될 때, 전달 포인터(forwarding pointer)가 객체의 오래된 버전에 설치됩니다. 전달 포인터는 오래된 객체가 더 이상 유효하지 않음을 나타내고 객체의 새 복사본을 어디서 찾을 수 있는지 표시합니다. 스캔 프로세스가 fromspace로의 포인터를 발견하면, 그것이 가리키는 객체에 전달 포인터가 있는지 확인합니다. 있다면 이미 tospace로 이동되었으므로, 그것에 의해 도달된 포인터는 단순히 새 위치를 가리키도록 업데이트됩니다. 이는 각 살아있는 객체가 정확히 한 번 이동되고, 그 객체에 대한 모든 포인터가 새 복사본을 가리키도록 업데이트되는 것을 보장합니다.

복사 컬렉션의 효율성

복사 가비지 컬렉터는 충분한 메모리가 사용 가능하다면 임의로 효율적으로 만들 수 있습니다. 각 컬렉션에서 수행되는 작업은 가비지 컬렉션 시점의 살아있는 데이터 양에 비례합니다. 프로그램 실행 중 어느 시점에서든 대략 같은 양의 데이터가 살아있다고 가정하면, 가비지 컬렉션 빈도를 줄이면 전체 가비지 컬렉션 노력이 줄어듭니다.

가비지 컬렉션 빈도를 줄이는 간단한 방법은 힙의 메모리 양을 늘리는 것입니다. 각 반공간이 더 크면, 프로그램이 그것을 채우기 전에 더 오래 실행됩니다. 이를 보는 다른 방법은 가비지 컬렉션 빈도를 줄임으로써 가비지 컬렉션 시점의 객체 평균 나이를 늘리고 있다는 것입니다. 가비지 컬렉션 전에 가비지가 된 객체들은 복사될 필요가 없어서, 객체가 절대 복사되지 않을 가능성이 증가합니다.

예를 들어, 프로그램 실행 중에 20메가바이트의 메모리가 할당되지만 어느 시점에서든 1메가바이트만 살아있다고 가정합시다. 두 개의 3메가바이트 반공간이 있다면, 가비지는 약 10번 수집됩니다. (컬렉션 후 현재 반공간이 3분의 1 차있으므로, 다음 컬렉션 전에 2메가바이트를 할당할 수 있습니다.) 이는 시스템이 할당하는 데이터의 약 절반을 복사한다는 의미입니다.

반면에 반공간 크기를 두 배로 늘리면, 각 컬렉션 후 5메가바이트의 자유 공간을 사용할 수 있습니다. 이는 가비지 컬렉션을 3분의 1만큼 자주, 즉 실행 중 약 3~4번 강제할 것입니다. 이는 간단하게 가비지 컬렉션 비용을 절반 이상 줄입니다. 당분간 가상 메모리 페이징 비용은 무시하고, 더 큰 힙 영역이 디스크로 페이징되지 않고 RAM에 캐시될 수 있다고 가정합니다. 그에 상응하는 큰 양의 RAM이 없다면 페이징 비용이 더 큰 힙 영역 사용을 비실용적으로 만들 수 있습니다.

비복사 암시적 컬렉션

최근 Wang과 Baker가 (독립적으로) 복사 방식의 효율성 장점 중 일부를 가진 새로운 종류의 비복사 컬렉터를 제안했습니다. 그들의 통찰은 복사 컬렉터에서 컬렉터의 “공간들”이 실제로는 집합의 특정 구현일 뿐이라는 것입니다. 추적 프로세스는 가비지 컬렉션 대상 집합에서 객체들을 제거하고, 추적이 완료되면 집합에 남아있는 모든 것이 가비지로 알려지므로 집합 전체를 회수할 수 있습니다. 유사한 성능 특성을 가진 집합의 다른 구현도 똑같이 잘 작동할 수 있습니다. 특히, 객체에 대한 포인터가 주어지면 그것이 어느 집합의 멤버인지 쉽게 판단할 수 있어야 하고, 복사 컬렉터에서 fromspace와 tospace 역할이 교환되는 것처럼 집합의 역할을 쉽게 바꿀 수 있어야 합니다. 복사 컬렉터에서 집합은 메모리 영역이지만, 비복사 컬렉터에서는 이전에 살아있는 객체를 보유했던 메모리 청크들의 어떤 종류의 집합이든 될 수 있습니다.

비복사 시스템은 각 객체에 두 개의 포인터 필드와 “색상(colour)” 필드를 추가합니다. 이 필드들은 응용 프로그래머에게 보이지 않으며, 저장소의 각 덩어리를 집합으로 기능하는 이중 연결 리스트로 연결하는 역할을 합니다. 색상 필드는 객체가 어느 집합에 속하는지 표시합니다.

이 컬렉터의 작동은 간단하고 복사 컬렉터의 작동과 동형입니다. 따라서 Wang은 이를 “가짜 복사(fake copying)” 컬렉터라고 부릅니다. 자유 공간의 청크들은 초기에 연결되어 이중 연결 리스트를 형성하고, 할당된 객체를 보유하는 청크들은 다른 리스트로 연결됩니다.

자유 리스트가 소진되면, 컬렉터는 살아있는 객체들을 순회해서 할당된 집합 (fromset이라고 부를 수 있음)에서 다른 집합 (toset)으로 “이동”시킵니다. 이는 객체를 이중 연결된 fromset 리스트에서 연결 해제하고, 색상 필드를 토글하고, toset의 이중 연결 리스트에 연결함으로써 구현됩니다.

복사 컬렉터에서처럼, 공간 회수는 암시적입니다. 도달 가능한 모든 객체들이 순회되어 fromset에서 toset으로 이동되면, fromset은 가비지만 포함하고 있는 것으로 알려집니다. 따라서 자유 리스트로 즉시 사용될 수 있습니다. (Baker의 방식은 그의 컬렉터가 점진적이기 때문에 실제로 약간 더 복잡합니다.) 컬렉션 비용은 살아있는 객체 수에 비례하고, 가비지 객체들은 모두 작은 상수 시간에 회수됩니다.

이 방식은 복사 컬렉터에서 사용되는 것과 유사한 방식으로 최적화될 수 있습니다 - 할당된 리스트와 자유 리스트가 연속적이고 할당 포인터로만 분리될 수 있어서 할당이 빠를 수 있습니다. 실제로 한 리스트에서 객체들을 연결 해제하고 다른 리스트에 연결하는 대신, 할당자는 단순히 리스트를 가리키고 할당된 세그먼트와 자유 세그먼트를 나누는 포인터를 전진시킬 수 있습니다. 비슷하게, Cheney 스타일 너비 우선 탐색은 포인터 쌍만으로 구현될 수 있고, 스캔된 리스트와 자유 리스트는 연속적일 수 있어서 스캔 포인터를 전진시키는 것이 그것들을 분리하는 포인터를 전진시키는 것만 필요합니다.

이 방식은 복사 컬렉터와 비교해서 장단점이 모두 있습니다. 단점으로는 객체당 상수가 아마도 약간 더 높고, 단편화 문제가 여전히 가능합니다. 장점으로는 큰 객체에 대한 추적 비용이 그렇게 높지 않습니다. 마크-스윕 컬렉터처럼 전체 객체를 복사할 필요가 없고, 포인터를 포함할 수 없다면 스캔할 필요도 없습니다. 아마도 많은 응용 프로그램에 더 중요한 것은, 이 방식이 객체 간의 실제 언어 레벨 포인터를 변경할 필요가 없어서 컴파일러에 더 적은 제약을 부과한다는 점입니다. 나중에 설명하겠지만, 이는 병렬 및 실시간 점진적 컬렉터에 특히 중요합니다.

이 기법의 공간 비용은 보통 대략 복사 컬렉터의 것과 비슷합니다. 객체당 두 개의 포인터 필드가 필요하지만, 추적되는 살아있는 객체들은 fromspace와 tospace 버전 모두를 위한 공간이 필요하지 않습니다. 대부분의 경우 이는 공간 비용을 복사 컬렉터보다 작게 만드는 것으로 보이지만, 일부 경우 단편화 비용 (데이터를 압축할 수 없기 때문)이 그런 절감을 넘어설 수 있습니다.

기본 추적 기법들 중 선택하기

교과서에서 가비지 컬렉션 알고리즘을 다룰 때 종종 점근적 복잡도를 강조하지만, 모든 기본 알고리즘들은 대략 비슷한 비용을 가지는데, 특히 가비지 컬렉션을 전체 자유 저장소 관리 방식의 일부로 볼 때 그렇습니다. 할당과 가비지 컬렉션은 기본 메모리 재사용 동전의 양면이고, 어떤 알고리즘이든 할당 시점에 비용이 발생하는데, 단지 새 객체의 필드를 초기화하는 것만으로도 그렇습니다. “고성능” 가비지 컬렉션의 일반적인 기준은 객체를 가비지 컬렉팅하는 비용이 평균적으로 객체를 할당하는 비용과 비슷해야 한다는 것입니다.

따라서 효율적인 추적 컬렉션 방식은 세 가지 기본 비용 구성요소를 가집니다: (1) 각 컬렉션에서 필요한 초기 작업 (예: 루트 집합 스캔), (2) 할당 시 수행되는 작업 (할당량이나 할당된 객체 수에 비례), (3) 가비지 탐지 중 수행되는 작업 (예: 추적).

초기 작업은 보통 특정 프로그램에 대해 루트 집합 크기에 의해 상대적으로 고정됩니다. 할당 시 수행되는 작업은 일반적으로 할당된 객체 수에 비례하고, 거기에 크기에 비례한 초기화 비용이 더해집니다. 가비지 탐지 비용은 추적되어야 하는 살아있는 데이터 양에 비례합니다.

후자의 두 비용은 보통 비슷한데, 추적되는 살아있는 데이터 양이 보통 할당된 메모리 양의 상당한 비율이기 때문입니다. 따라서 비용이 할당량에 비례하는 알고리즘 (예: 마크-스윕)은 살아있는 데이터 추적량에 비례하는 것들 (예: 복사)과 경쟁력이 있을 수 있습니다.

예를 들어, 할당된 모든 데이터의 10퍼센트가 컬렉션에서 생존하고 90퍼센트는 절대 추적될 필요가 없다고 가정합시다. 어느 알고리즘이 더 효율적인지 결정할 때, 점근적 복잡도는 관련 상수들보다 덜 중요합니다. 객체를 스윕하는 비용이 그것을 복사하는 비용의 10분의 1이라면, 마크-스윕 컬렉터는 복사 컬렉터와 거의 같은 비용이 듭니다. (마크-스윕 컬렉터의 스윕 비용이 할당자에게 청구되고, 객체를 초기화하는 비용에 비해 작다면, 스윕 단계가 그렇게 비싸지 않다는 것이 명백해집니다.) 현재 복사 컬렉터들이 현재 마크-스윕 컬렉터들보다 더 효율적인 것처럼 보이지만, 최신 구현들에서 차이는 크지 않습니다.

메모리가 예상되는 살아있는 데이터 양보다 훨씬 크지 않은 시스템에서는, 비이동 컬렉터가 복사 컬렉터보다 장점이 있는데 각 살아있는 객체의 두 버전 (“from”과 “to” 버전)을 위한 공간이 필요하지 않기 때문입니다. 공간이 매우 빠듯할 때는 참조 카운팅 컬렉터가 특히 매력적인데, 성능이 살아있는 데이터 대 전체 저장소 비율과 본질적으로 무관하기 때문입니다.

게다가, 실제 고성능 시스템들은 종종 다양한 객체 카테고리에 대한 절충을 조정하기 위해 하이브리드 기법을 사용합니다. 많은 고성능 복사 컬렉터들은 별도의 큰 객체 영역을 사용해서 공간 간에 큰 객체를 복사하는 것을 피합니다. 큰 객체들은 “옆에” 보관되고 보통 어떤 종류의 표시 순회와 자유 리스트 기법으로 제자리에서 관리됩니다. 다른 하이브리드들은 대부분의 시간 동안 비복사 기법을 사용할 수 있지만, 영구적인 단편화를 피하기 위해 때때로 복사 기법을 사용해서 일부 데이터를 압축합니다.

제자리 컬렉터를 지지하는 주요 논점은 포인터일 수도 아닐 수도 있는 데이터 값들에 대해 보수적(conservative)으로 만들 수 있다는 능력입니다. 이는 실행 시간에 모든 포인터를 명확히 식별하기 어렵거나 불가능하게 만들 수 있는 C 같은 언어나 기성 최적화 컴파일러에 사용할 수 있게 합니다. 비이동 컬렉터는 포인터처럼 보이는 것은 제자리에 남겨둘 수 있고, 그에 대한 (가능한) 포인터를 변경할 필요가 없기 때문에 보수적일 수 있습니다. 대조적으로, 복사 컬렉터는 값이 포인터인지 알아야 하고 - 객체를 이동시키고 포인터를 업데이트할지 결정해야 합니다.

비슷하게, 비이동 컬렉터의 선택은 다양한 언어로 작성되고 다양한 컴파일러로 컴파일된 모듈 간 인터페이스를 크게 단순화할 수 있습니다. 가비지 컬렉션을 염두에 두지 않고 작성되거나 컴파일된 외부 루틴들에 가비지 컬렉션 가능한 객체에 대한 포인터를 인자로 전달하는 것이 가능합니다. 이는 복사 컬렉터로는 실용적이지 않은데, 외부 루틴으로 “탈출한” 포인터들이 참조 대상이 이동할 때 찾아서 업데이트되어야 하기 때문입니다.

단순 추적 컬렉터의 문제들

복사 가비지 컬렉션의 점근적 복잡도가 훌륭하다는 것은 널리 알려져 있습니다 - 메모리가 매우 커지면 복사 비용이 0에 접근합니다. 트레드밀 컬렉션도 이 속성을 공유하지만, 메모리 회수와 재할당과 관련된 상수가 충분히 작다면 다른 컬렉터들도 비슷하게 효율적일 수 있습니다. 그런 경우 가비지 탐지가 주요 비용입니다.

불행히도, 실제로 단순 가비지 컬렉터에서 높은 효율성을 달성하기 어려운데, 많은 양의 메모리가 너무 비싸기 때문입니다. 가상 메모리가 사용되면, 할당과 회수 주기의 낮은 지역성이 일반적으로 과도한 페이징을 유발합니다. (힙의 모든 위치가 어떤 위치의 공간이 회수되고 재사용되기 전에 사용됩니다.) 최근 할당된 데이터를 페이징 아웃하는 것만으로도 고속 프로세서에게는 비싸고, 복사 컬렉션 자체로 인한 페이징은 엄청날 수 있는데, 모든 살아있는 데이터가 그 과정에서 접촉되어야 하기 때문입니다.

따라서 힙 영역을 사용 가능한 주 메모리보다 크게 만드는 것은 일반적으로 이익이 되지 않습니다. 주 메모리가 꾸준히 더 저렴해지더라도, 캐시 메모리 내의 지역성이 점점 더 중요해져서, 문제는 부분적으로 메모리 계층의 다른 레벨로 옮겨집니다.

일반적으로 단순 가비지 컬렉션의 잠재적 효율성을 달성할 수 없습니다. 컬렉션을 연기하거나 피하기 위해 메모리 크기를 늘리는 것은 증가된 페이징 시간이 장점을 부정하기 전까지만 갈 수 있습니다.

이 문제가 복사 컬렉터에만 국한되지 않는다는 것을 깨닫는 것이 중요합니다. 모든 효율적인 가비지 컬렉션 전략은 유사한 공간-시간 절충을 포함합니다 - 가비지 컬렉션이 연기되어 가비지 탐지 작업이 덜 자주 수행되고, 이는 공간이 빨리 회수되지 않는다는 의미입니다. 평균적으로 이는 회수되지 않은 가비지로 인해 낭비되는 메모리 양을 증가시킵니다.

지연된 참조 카운팅도 추적 컬렉션처럼 공간 대 시간을 교환합니다 - CPU 사이클을 참조 카운트 조정에 쓰는 것을 피하기 위해 지속적인 점진적 회수를 포기하면서, 가비지가 되어도 즉시 회수되지 않는 객체들을 위한 공간을 포기합니다. 메모리가 재사용되는 시간 규모에서, 결과적인 지역성 특성은 나중에 논의될 복사나 마크-스윕 종류의 세대별 컬렉터들과 기본적인 성능 절충 특성을 공유해야 합니다.

복사 컬렉터가 원래 지역성을 개선하기 위해 설계되었지만, 단순한 버전에서는 이 개선이 크지 않고, 실제로 지역성이 비압축 컬렉터보다 더 나쁠 수 있습니다. 이 시스템들은 오래 살아남은 데이터 객체에 대한 참조의 지역성을 개선할 수 있는데, 연속 영역으로 압축되었기 때문입니다. 하지만 이 효과는 보통 할당으로 인한 참조의 효과에 의해 압도됩니다. 컬렉션들 사이에 많은 양의 메모리가 접촉되고, 이것만으로도 가상 메모리 환경에 적합하지 않게 만듭니다.

주요 지역성 문제는 압축된 데이터의 지역성이나 가비지 컬렉션 프로세스 자체의 지역성에 있지 않습니다. 문제는 가비지 컬렉션 사용의 간접적인 결과입니다 - 공간이 회수되고 재사용될 때쯤이면 페이징 아웃되었을 가능성이 높은데, 단순히 그 사이에 너무 많은 다른 페이지들이 할당되었기 때문입니다. 압축은 도움이 되지만, 그 도움은 일반적으로 너무 작고, 너무 늦습니다. 단순 반공간 복사 컬렉터에서 지역성은 마크-스윕 컬렉터보다 나쁠 가능성이 높은데, 복사 컬렉터가 더 많은 전체 메모리를 사용하기 때문입니다 - 컬렉션들 사이에 메모리의 절반만 사용될 수 있습니다. 살아있는 데이터의 단편화는 두 공간의 정기적 재사용만큼 해롭지 않습니다.

좋은 지역성을 갖는 유일한 방법은 정기적으로 재사용되는 영역을 보유할 만큼 메모리가 충분히 크다는 것을 보장하는 것입니다. 다른 접근법은 프리페칭 같은 최적화에 의존하는 것이지만, 이는 가상 메모리 레벨에서 실행 가능하지 않습니다 - 디스크는 RAM과 디스크 간의 엄청난 속도 차이 때문에 할당 속도를 따라갈 수 없습니다. 세대별(generational) 컬렉터는 더 작은 양의 메모리를 더 자주 재사용함으로써 이 문제를 다룹니다. 역사적 이유로, 복사 컬렉터만 세대별로 만들 수 있다고 널리 믿어지지만, 이는 사실이 아닙니다. 세대별 비복사 컬렉터는 구성하기 약간 더 어렵지만, 존재하고 꽤 실용적입니다.

마지막으로, 단순 추적 컬렉터의 작업의 시간적 분포도 대화형 프로그래밍 환경에서 문제가 됩니다. 갑자기 시스템이 응답하지 않게 되고 몇 초 동안 가비지 컬렉션을 하는 것은 사용자의 작업에 매우 방해가 될 수 있는데, 이런 시스템에서 흔한 일입니다. 큰 힙의 경우 일시 정지가 몇 초, 또는 많은 양의 데이터가 가상 메모리를 통해 분산되어 있다면 심지어 몇 분일 수 있습니다. 세대별 컬렉터는 대부분의 가비지 컬렉션이 메모리의 부분집합에서만 작동하기 때문에 이 문제를 완화합니다. 하지만 결국 더 큰 영역을 가비지 컬렉션해야 하고, 일시 정지가 상당히 더 길 수 있습니다. 실시간 응용 프로그램에는 이것이 받아들여지지 않을 수 있습니다.

가비지 컬렉션의 보수성

이상적인 가비지 컬렉터는 객체의 마지막 사용 직후에 모든 객체의 공간을 회수할 수 있을 것입니다. 물론 그런 객체는 실제로 구현 가능하지 않은데, 마지막 사용이 언제 발생하는지 일반적으로 판단할 수 없기 때문입니다. 실제 가비지 컬렉터들은 이 전지능의 보수적 근사값을 사용해서 이 행동의 합리적인 근사만 제공할 수 있습니다. 효율적인 가비지 컬렉터 설계의 기술은 가비지 탐지에 수행되는 작업을 크게 줄이는 작은 정도의 보수성을 도입하는 것입니다. 이 보수성 개념은 매우 일반적이며, 소위 “보수적” 가비지 컬렉터가 사용하는 특정 포인터 식별 기법과 혼동되어서는 안 됩니다. 모든 가비지 컬렉터는 하나 이상의 방식으로 보수적입니다.

대부분의 컬렉터가 하는 첫 번째 보수적 가정은 스택, 전역, 또는 레지스터의 모든 변수가 살아있다는 것인데, 비록 그 변수가 실제로는 다시 참조되지 않을 수도 있음에도 불구하고 그렇습니다. 컴파일러의 최적화와 가비지 컬렉터의 도달 가능성 그래프 관점 사이에 상호작용이 있을 수 있습니다. 컴파일러의 데이터 및 제어 흐름 분석이 죽은 값들을 탐지해서 완전히 최적화해서 제거할 수 있습니다. 컴파일러 최적화가 변수의 효과적인 생명주기를 연장해서 여분의 가비지가 유지되게 할 수도 있지만, 이는 실제로 보통 문제가 되지 않습니다.

추적 컬렉터는 컬렉션 주기 사이에 가비지가 수집되지 않도록 허용함으로써 주요 시간적 보수성 형태를 도입합니다. 참조 카운팅 컬렉터는 위상적으로 보수적인데, 포인터 관계 그래프에서 엣지를 공유하는 서로 다른 경로들을 구분하지 못합니다.

---

흥미로운 배경지식

1. 가비지 컬렉션의 탄생: John McCarthy와 Lisp

가비지 컬렉션은 1959년 John McCarthy가 Lisp을 개발하면서 처음 구현되었습니다. 당시 컴퓨터 메모리는 극도로 제한적이었고(IBM 704는 32KB 메모리를 가졌습니다), McCarthy는 프로그래머가 수동으로 메모리를 관리하지 않고도 재귀적 함수와 리스트 처리를 할 수 있는 방법을 찾고 있었습니다. 그가 고안한 마크-스윕 알고리즘은 오늘날까지도 많은 시스템의 기초가 되고 있습니다. 재미있는 사실은, McCarthy는 가비지 컬렉션을 일시적인 해결책으로 생각했고, 프로그래머들이 결국 더 나은 방법을 찾을 것이라 믿었다는 점입니다. 하지만 60년이 지난 지금도 가비지 컬렉션은 현대 프로그래밍 언어의 핵심 기능입니다.

2. “Stop the World”의 비극과 세대별 가비지 컬렉션

1980년대, 실시간 애플리케이션에서 가비지 컬렉션의 가장 큰 문제는 “stop-the-world” 일시 정지였습니다. 애니메이션 소프트웨어나 게임에서 갑자기 몇 초간 화면이 멈추는 것은 용납될 수 없었죠. 이 문제를 해결하기 위해 David Ungar와 연구팀이 1984년에 세대별(generational) 가비지 컬렉션을 제안했습니다. 핵심 통찰은 “대부분의 객체는 젊어서 죽는다(most objects die young)”는 경험적 관찰이었습니다. 전체 힙을 스캔하는 대신 젊은 객체들만 자주 수집하면, 일시 정지 시간을 몇 밀리초로 줄일 수 있었습니다. 이는 현대 Java, C#, JavaScript 엔진들이 모두 사용하는 표준 기법이 되었습니다.

3. 실전에서의 참조 카운팅: Python과 Objective-C의 선택

문서에서 참조 카운팅이 순환 참조를 처리하지 못한다고 설명하고 있지만, 흥미롭게도 Python과 (ARC 도입 전) Objective-C는 주 가비지 컬렉션 전략으로 참조 카운팅을 선택했습니다. Python은 이를 “보완하기 위해” 주기적으로 순환 참조를 탐지하는 별도의 순환 탐지기를 실행합니다. Objective-C의 경우, Apple은 프로그래머들에게 “강한 참조”와 “약한 참조”를 명시적으로 구분하도록 해서 순환을 피하게 했습니다. 참조 카운팅의 장점은 객체가 언제 정확히 해제되는지 예측 가능하다는 점이었는데, 이는 파일 핸들이나 네트워크 연결 같은 자원 관리에 중요했습니다. 현대 Rust 언어는 이 아이디어를 더 발전시켜, 컴파일 시점에 소유권을 추적해서 런타임 가비지 컬렉션 없이도 메모리 안전성을 달성했습니다.

---