세대별 가비지 컬렉션

현실적인 메모리 용량을 고려할 때, 단순한 복사 방식 가비지 컬렉션의 효율성은 시스템이 컬렉션 시점마다 살아있는 모든 데이터를 복사해야 한다는 점에 의해 제한됩니다. 다양한 언어로 작성된 대부분의 프로그램에서 대부분의 객체는 매우 짧은 시간만 살아남고, 소수의 객체만이 훨씬 더 오래 살아남습니다. 언어와 프로그램에 따라 수치는 다르지만, 보통 새로 할당된 힙 객체의 80~98%가 수백만 개의 명령어가 실행되는 동안, 또는 1메가바이트가 추가로 할당되기 전에 소멸됩니다. 대다수의 객체는 훨씬 더 빨리, 수십 킬로바이트가 할당되는 동안 소멸하죠.

프로그램 실행을 측정할 때 실제 시간(wall clock time) 대신 힙 할당량을 사용하는 이유는 두 가지입니다. 첫째, 힙 할당량은 머신이나 구현 속도와 무관하게 프로그램이 실행되는 속도에 따라 적절히 변화하므로, 매번 하드웨어 속도를 언급할 필요가 없습니다. 둘째, 가비지 컬렉션 사이의 시간 간격이 주로 사용 가능한 메모리 양에 의해 결정되기 때문에 할당량으로 이야기하는 것이 적절합니다. 향후 컴파일러 기술이 발전하면 더 많은 “힙” 객체를 스택에 배치하여 힙 할당률을 줄일 수 있겠지만, 현재 최신 컴파일러들이 이런 종류의 수명 분석을 많이 하지 않기 때문에 실험적 연구에서는 아직 큰 문제가 되지 않습니다.

가비지 컬렉션이 수 킬로바이트 할당마다 일어날 정도로 빈번하더라도, 대부분의 객체는 컬렉션 전에 소멸하여 복사될 필요가 없습니다. 하지만 한 번 살아남아 복사된 객체들 중에서는 상당수가 여러 번의 컬렉션을 거쳐 살아남습니다. 이런 객체들은 매 컬렉션마다 반복해서 복사되고, 가비지 컬렉터는 대부분의 시간을 똑같은 오래된 객체들을 반복적으로 복사하는 데 소비합니다. 이것이 단순한 가비지 컬렉터의 주요 비효율성 원인입니다.

세대별 컬렉션은 객체를 나이에 따라 여러 영역으로 분리하고, 오래된 객체가 있는 영역은 젊은 객체가 있는 영역보다 덜 자주 수집함으로써 이런 반복적인 복사를 크게 줄입니다. 객체가 소수의 컬렉션을 살아남으면, 덜 자주 수집되는 영역으로 이동됩니다. 젊은 객체가 있는 영역은 매우 자주 수집되는데, 그곳의 대부분의 객체가 빠르게 소멸하여 공간을 확보하기 때문입니다. 살아남은 소수의 객체를 복사하는 비용은 크지 않죠. 이런 생존자들은 몇 번의 컬렉션 후에 더 오래된 상태로 승급되어 복사 비용을 낮게 유지합니다.

중단-수집(non-incremental) 방식의 가비지 컬렉션에서 세대별 가비지 컬렉션은 추가적인 이점이 있습니다. 대부분의 컬렉션이 짧은 시간만 소요된다는 것이죠. 가장 젊은 세대만 수집하는 것이 전체 가비지 컬렉션보다 훨씬 빠릅니다. 이는 방해가 되는 일시 정지의 빈도를 줄여주며, 실시간 데드라인이 없는 많은 프로그램에서는 이것만으로도 대화형 사용에 충분히 만족스럽습니다. 대부분의 일시 정지는 너무 짧아서(1초 미만) 사용자가 알아차리기 어렵고, 여러 세대를 수집하는 긴 일시 정지는 시스템이 사용되지 않을 때로 미루거나 프로그램의 비대화형 계산 집약적 단계에 숨길 수 있습니다. 세대별 기법은 더 비싼 점진적 기법의 대안으로 자주 사용되며, 전반적인 효율성도 개선합니다.

역사적 이유와 설명의 단순성을 위해, 우리는 세대별 복사 컬렉터에 초점을 맞출 것입니다. 복사 방식이나 마킹 방식의 선택은 본질적으로 세대별 컬렉션 문제와 직교합니다.

다양한 컬렉션 빈도를 가진 여러 서브힙

세미스페이스 구조를 기반으로 한 세대별 가비지 컬렉터를 생각해봅시다. 메모리는 대략적인 나이, 즉 세대가 다른 객체들을 담을 영역들로 나뉩니다. 각 세대의 메모리는 다시 세미스페이스로 나뉩니다. 그림 9에서는 두 개의 연령 그룹, 즉 New 세대와 Old 세대만 있는 간단한 세대별 구조를 보여줍니다. 객체는 New 세대에 할당되고, 현재 세미스페이스가 가득 차면 New 세대만 수집되어 살아있는 데이터를 다른 세미스페이스로 복사합니다.

객체가 오래된 것으로 간주될 만큼 충분히 오래 살아남으면, 다른 세미스페이스로 돌아가는 대신 New 세대에서 Old 세대로 복사될 수 있습니다. 이렇게 하면 단일 세대 컬렉션의 대상에서 제외되어 매 컬렉션마다 복사되지 않습니다. 이렇게 오래 사는 객체는 상대적으로 적기 때문에, Old 메모리는 New 메모리보다 훨씬 천천히 채워집니다. 결국 Old 메모리도 가득 차서 가비지 컬렉션이 필요하게 되겠죠.

세대의 수는 둘 이상일 수 있으며, 각각의 연속된 세대는 더 오래된 객체를 담고 훨씬 덜 자주 수집됩니다. Tektronix 4406 Smalltalk가 그런 세대 시스템으로, 8개의 세대 각각에 세미스페이스를 사용합니다.

이 구조가 작동하려면, 오래된 세대를 수집하지 않고도 젊은 세대를 수집할 수 있어야 합니다. 하지만 데이터의 생존 여부는 전역적 속성이므로, Old 메모리의 데이터도 고려해야 합니다. 예를 들어, Old 메모리에서 New 메모리로의 포인터가 있다면, 그 포인터는 컬렉션 시점에 발견되어 순회의 루트 중 하나로 사용되어야 합니다. 그렇지 않으면 살아있는 객체가 가비지 컬렉터에 의해 보존되지 않거나, 객체가 이동될 때 포인터가 적절히 업데이트되지 않을 수 있습니다. 어느 경우든 힙의 데이터 구조의 무결성과 일관성이 파괴됩니다.

컬렉터가 젊은 세대로의 포인터를 찾을 수 있도록 보장하려면 점진적 컬렉터의 “쓰기 장벽(write barrier)”과 유사한 것이 필요합니다. 즉, 실행 중인 프로그램이 힙 객체에 포인터를 마음대로 저장할 수 없습니다. 각각의 잠재적 포인터 저장은 세대 간 포인터가 생성되는 경우를 대비해 추가적인 부기 작업을 동반해야 합니다. 일반적으로 컴파일러가 각 저장 명령과 함께 몇 개의 추가 명령어를 생성하여 필요한 쓰기 장벽 작업을 수행합니다.

쓰기 장벽은 각 저장 시점에 검사를 수행하거나, 단순히 더티 비트를 유지하고 컬렉션 시점에 더티 영역을 스캔할 수 있습니다. 중요한 점은 Old에서 New 메모리로의 모든 참조가 컬렉션 시점에 찾아져서 복사 순회의 루트로 사용되어야 한다는 것입니다.

이런 세대 간 포인터를 루트로 사용하면 젊은 세대의 도달 가능한 모든 객체가 실제로 컬렉터에 의해 도달되도록 보장합니다. 복사 컬렉터의 경우, 이동된 객체에 대한 모든 포인터가 적절히 업데이트되도록 보장하기도 합니다.

점진적 컬렉터에서처럼, 이런 쓰기 장벽의 사용은 진정한 생존성의 보수적 근사를 초래합니다. Old에서 New 메모리로의 모든 포인터가 루트로 사용되지만, 이 루트들이 모두 실제로 살아있는 것은 아닙니다. Old 메모리의 객체가 이미 소멸했을 수 있지만, 그 사실은 다음번 Old 메모리 컬렉션 전까지는 알 수 없습니다. 따라서 일부 가비지 객체가 (감지되지 않은) 부유 가비지인 객체로부터 참조되어 보존될 수 있습니다. 실제로는 이것이 문제가 되지 않는 것으로 보입니다.

새로운 객체에서 오래된 객체로의 모든 포인터를 추적하여 젊은 세대와 독립적으로 오래된 객체를 수집하는 것도 가능합니다. 하지만 이는 더 비용이 많이 드는데, 일반적으로 Old에서 New로의 포인터보다 New에서 Old로의 포인터가 훨씬 많기 때문입니다. 이런 유연성은 참조가 생성되는 방식의 결과입니다. 보통 이미 존재하는 다른 객체를 참조하는 새 객체를 생성하는 방식이죠. 때때로 새 객체에 대한 포인터가 오래된 객체에 설치되지만, 이는 훨씬 덜 일반적입니다. 이런 비대칭적 처리는 객체 생성 코드(Lisp의 자주 사용되는 cons 연산 같은)가 세대 간 포인터 기록을 건너뛸 수 있게 합니다. 객체를 초기화하지 않는 저장만 세대 간 참조를 확인하면 됩니다. 가장 젊은 세대의 객체를 초기화하는 쓰기는 더 젊은 세대로의 포인터를 생성할 수 없으니까요.

젊은-오래된 포인터가 기록되지 않더라도, 젊은 세대를 수집하지 않고 한 세대를 수집하는 것이 여전히 가능할 수 있습니다. 이 경우 젊은 세대의 모든 데이터를 가능한 루트로 간주하고 단순히 포인터를 스캔할 수 있습니다. 이런 스캔은 젊은 세대의 데이터 양에 비례하는 시간을 소비하지만, 각 세대는 보통 다음 세대보다 상당히 작고, 비용은 실제로 오래된 세대를 수집하는 비용에 비해 작을 수 있습니다. 젊은 세대의 데이터를 스캔하는 것이 두 세대를 모두 수집하는 것보다 나을 수 있는데, 스캔이 일반적으로 추적과 복사보다 빠르고 지역성도 더 좋기 때문입니다.

세대 간 포인터를 기록하는 비용은 일반적으로 프로그램 실행 속도에 비례합니다. 즉, 객체 생성 속도와 특별히 연관되어 있지 않습니다. 일부 프로그램의 경우, 힙으로의 각 잠재적 포인터 저장마다 여러 명령어를 실행해야 하므로 이것이 가비지 컬렉션의 주요 비용이 될 수 있습니다. 이는 프로그램 실행을 몇 퍼센트 느리게 만들 수 있습니다.

우리가 개요를 설명한 세대별 전략의 틀 안에서, 몇 가지 중요한 질문이 남아 있습니다:

• 승급 정책. 객체가 다음 세대로 승급되기 전에 한 세대에서 얼마나 오래 살아남아야 하는가?
• 힙 구조. 저장 공간을 세대 간, 그리고 세대 내에서 어떻게 나누고 사용해야 하는가? 결과적인 재사용 패턴이 가상 메모리 수준과 고속 캐시 메모리 수준에서 지역성에 어떤 영향을 미치는가?
• 컬렉션 스케줄링. 비점진적 컬렉터의 경우, 특히 대화형 애플리케이션에서 방해가 되는 일시 정지의 효과를 어떻게 피하거나 완화할 수 있는가? 신중한 “기회주의적” 스케줄링으로 효율성을 개선할 수 있는가? 이를 점진적 구조에 적용하여 부유 가비지를 줄일 수 있는가?
• 세대 간 참조. 오래된 세대를 수집하지 않고 젊은 세대를 수집할 수 있어야 하므로, 오래된 세대에서 수집 중인 세대로의 살아있는 포인터를 찾을 수 있어야 합니다. 이를 위한 최선의 방법은 무엇인가?

승급 정책

가장 단순한 승급 정책은 순회될 때마다 모든 살아있는 데이터를 다음 세대로 승급시키는 것입니다. 이는 구현이 쉽다는 장점이 있는데, 세대 내에서 다른 나이의 객체를 구별할 필요가 없기 때문입니다. 복사 컬렉터에서는 세미스페이스로 나누지 않고 세대에 단일 연속 영역을 사용할 수 있으며, 나이 정보를 담을 헤더 필드도 필요하지 않습니다.

첫 순회에서 모든 것을 세대 밖으로 승급시키는 추가적인 장점은 세대 내에서 오래 사는 객체의 축적을 피한다는 것입니다. 오래 사는 객체는 같은 시간 척도로 반복적으로 복사될 수 없는데, 빠르게 다음 오래된 세대로 승급되어 덜 자주 수집되기 때문입니다.

여기서 문제는 객체가 너무 빨리 승급될 수 있다는 것입니다. 컬렉션 직전에 할당된 단명 객체가 다음 세대로 승급되는데, 이들은 매우 젊고 거의 즉시 소멸할 가능성이 높습니다. 이는 오래된 세대가 더 빨리 채워져 더 자주 수집되게 만듭니다. 매우 단명한 객체의 문제는 객체의 승급을 단 한 번의 가비지 컬렉션 사이클만큼 지연시켜 완화할 수 있습니다. 이는 모든 객체가 오래된 세대로 승급될 때 대략 같은 나이(2배 이내)가 되도록 보장합니다. (점진적 세대별 컬렉터에서는 점진적 컬렉션 단계가 충분한 기간이라면 검은색으로 할당하는 것이 유사한 효과를 낼 수 있습니다.)

객체를 세대 내에 두 번의 컬렉션 사이클 이상 유지하는 것이 추가 복사 비용만큼 가치가 있는지는 불분명합니다. 대부분의 조건에서 연속적인 복사가 승급되는 데이터의 양을 크게 줄이지 않는 것으로 보이지만, 이는 애플리케이션의 특성에 크게 의존합니다. 승급 정책을 동적으로 변경하는 것도 바람직할 수 있습니다.

데이터를 세대에 여러 컬렉션 사이클 동안 유지하는 것의 바람직함은 오래된 세대의 수와 크기에도 영향을 받습니다. 일반적으로 세대가 매우 적으면(예: Ungar의 Generation Scavenging 시스템처럼 두 개), 오래된 세대가 채워지는 것을 피하기 위해 데이터를 더 오래 유지하는 것이 더 바람직합니다. 중간 세대가 있다면, 보통 더 빠르게 승급시키는 것이 낫습니다. 중간 세대에서 소멸하여 가장 오래된 세대로 승급되지 않을 가능성이 높기 때문입니다.

힙 구조

세대별 컬렉터는 다른 나이의 객체를 다르게 처리해야 합니다. 추적하는 동안 객체가 어느 세대에 속하는지 알아야 자손을 추적할지, 다른 세대로 승급시킬지 결정할 수 있습니다. 쓰기 장벽도 객체의 세대를 결정할 수 있어야 젊은 객체로의 포인터가 오래된 객체에 저장되는지 감지할 수 있습니다.

복사 컬렉터에서는 보통 다른 나이의 객체를 메모리의 다른 영역에 보관합니다. 많은 시스템에서 이들은 연속된 영역입니다. 따라서 간단한 주소 비교로 객체의 세대를 결정할 수 있습니다. 다른 시스템에서는 “영역”이 비연속적인 페이지 집합일 수 있습니다. 객체의 주소에서 페이지 번호 부분을 사용하여 그 페이지가 어느 세대에 속하는지 알려주는 테이블을 인덱싱할 수 있습니다.

비복사 컬렉터 같은 다른 시스템에서는 각 객체가 세대에 속하지만, 다른 세대의 객체들이 메모리에 섞여 있을 수 있습니다. 일반적으로 각 객체는 어느 세대에 속하는지 나타내는 헤더 필드를 가집니다.

복사 방식의 하위 영역

세대별 복사 컬렉터는 각 세대의 공간을 여러 영역으로 나눕니다. 예를 들어, 각 세대는 한 쌍의 세미스페이스로 구성되어 객체를 한 공간에서 다른 공간으로 복사하며 여러 컬렉션에 걸쳐 세대 내에 유지할 수 있습니다. 한 공간만 사용하면 객체를 즉시 다른 세대로 승급시켜야 하는데, 같은 세대 내에서 복사할 곳이 없기 때문입니다.

세미스페이스 메모리 사용의 지역성은 좋지 않습니다. 세대 메모리의 절반만 주어진 시간에 사용될 수 있지만, 두 공간 모두 두 컬렉션 사이클마다 전체가 접근됩니다. Lisp 머신 가비지 컬렉터는 세대당 단일 공간만 사용하여 이 문제를 피합니다. 객체를 한 세미스페이스에서 다른 곳으로 복사하여 승급시키는 대신, 세대의 가비지 컬렉션이 모든 객체를 다음 세대로 승급시킵니다. 이는 가장 오래된 세대를 제외하고는 세미스페이스 쌍이 필요 없게 합니다. 가장 오래된 세대는 복사할 곳이 없으니까요. 안타깝게도 이는 상대적으로 젊은 객체가 상대적으로 오래된 객체와 함께 승급될 수 있다는 단점이 있습니다. 컬렉션 직전에 할당된 객체는 승급되기 전에 소멸할 시간이 많지 않습니다. 이런 상대적으로 젊은 객체는 승급 직후 소멸할 가능성이 높아, 불필요하게 다음 세대의 공간을 차지하고 더 빨리 다시 수집되도록 만듭니다.

Ungar의 Young 세대(Generation Scavenging 컬렉터의)에서 이 문제에 대한 해결책은 두 개가 아닌 세 개의 공간을 사용하는 것입니다. 모든 객체가 처음에는 세 번째 공간에 할당됩니다. 이 세 번째 공간의 새로 생성된 객체는 다른 세미스페이스의 객체와 함께 한 세미스페이스로 복사됩니다. 세 번째 공간은 매 가비지 컬렉션 사이클마다 비워지므로 매번 즉시 재사용될 수 있습니다. 따라서 세대당 단일 공간 시스템과 유사한 지역성 특성을 가집니다. 이 세 번째 공간이 메모리 사용을 증가시킬 것 같지만, 객체를 여러 컬렉션 동안 세대에 유지하기 위해 세미스페이스가 여전히 필요하기 때문에 그렇지 않습니다. 생성 영역은 각 할당-컬렉션 사이클마다 전체가 사용되는 반면, 각 세미스페이스는 격 컬렉션 사이클마다 생존자를 담는 데 사용됩니다. 일반적으로 새 객체의 소수만이 첫 컬렉션조차 살아남으므로, 대부분의 경우 각 세미스페이스의 작은 부분만 실제로 사용되고, 전체 메모리 사용량은 더 낮습니다.

Wilson의 Opportunistic Garbage Collector는 이 구조의 변형을 사용하는데, 세대 내의 하위 영역을 객체를 한 세대에서 다른 세대로 승급시킬 시기를 결정하는 추가 목적으로 사용합니다. 객체는 연속된 컬렉션에서 한 세미스페이스에서 다른 곳으로 복사되는 대신, 각 사이클마다 세미스페이스에서 다음 세대로 승급됩니다. 사실상 이는 객체를 하위 영역으로 분리하여 승급 정책을 위한 나이를 인코딩하는 간단한 “버킷 브리게이드” 승급 메커니즘입니다. 객체 헤더의 나이 필드가 필요 없는데, 일부 시스템에서는 일부 객체에 헤더가 전혀 없을 수 있어 유리할 수 있습니다. 객체가 최소 한 번(최대 두 번)의 컬렉션 사이클을 살아남지 않고는 세대 밖으로 승급되지 않는다는 보장을 제공합니다. 이는 매우 단명한 데이터의 조기 승급을 피하기에 충분합니다.

여러 세대별 복사 컬렉션 시스템에서 가장 오래된 세대는 특별하게 취급됩니다. Lisp 머신 컬렉터에서는 대부분의 세대가 매 컬렉션 사이클마다 비워지고 내용이 다음 세대로 복사되기 때문에 이것이 필요합니다. 가장 오래된 세대(“동적 공간”)는 복사할 더 오래된 세대가 없으므로 한 쌍의 세미스페이스로 구조화되어 번갈아 사용됩니다. 추가 개선 사항은 “정적 공간”이라는 특별한 영역을 제공하는 것인데, 이는 정상 작동 중에는 전혀 가비지 컬렉션되지 않습니다. 이 영역은 매우 드물게 변경될 것으로 예상되는 시스템 데이터와 컴파일된 코드를 담습니다.

Ungar의 Generation Scavenging 시스템을 기반으로 한 일부 복사 컬렉터는 가장 오래된 세대를 단일 공간으로 구조화하고 마크-컴팩트 알고리즘을 사용하여 특별하게 취급합니다. 이런 시스템에서는 모든 세대가 일반적으로 정상 실행 중에 RAM에 상주하며, 단일 공간을 사용하면 가장 오래된 세대를 메모리 상주 상태로 유지하는 데 필요한 RAM이 줄어듭니다. 마크-컴팩트 알고리즘이 일반적인 복사 컬렉션보다 비싸지만, 페이징 없이 전체 컬렉션을 수행할 수 있는 능력이 가장 오래된 세대에는 가치가 있습니다. 비복사 기법도 같은 목적으로 사용될 수 있지만, 단편화 문제에 더 취약합니다.

비복사 방식의 세대

지금까지 세대별 컬렉션 논의에서 우리는 주로 복사 가비지 컬렉션 구조에 초점을 맞췄는데, 여기서 세대는 다른 나이의 객체를 담는 메모리의 “영역”으로 볼 수 있습니다. 하지만 다른 나이의 객체를 구별하고 다르게 취급할 수 있는 한 이것이 필수는 아닙니다. 점진적 컬렉션 알고리즘이 삼색 마킹의 추상화로 가장 잘 이해되듯이, 세대별 알고리즘은 다른 빈도로 가비지 컬렉션되는 객체 집합의 관점에서 가장 잘 이해됩니다. (이런 나이 집합 각각은 다시 추적 순회 목적으로 음영 처리된 집합과 음영 처리되지 않은 집합으로 나눌 수 있습니다.)

Xerox PARC PCR(Portable Common Runtime) 가비지 컬렉터는 세대별 마크-스윕 컬렉터로, 객체당 헤더 필드가 객체의 나이를 나타냅니다. 다른 세대의 객체가 같은 페이지에 할당될 수 있지만, 시스템은 지역성 이유로 이를 최소화하는 휴리스틱을 사용합니다. 젊은 데이터만 가비지 컬렉션할 때, PCR 컬렉터는 루트 집합을 스캔하고 나이 필드가 컬렉션 대상임을 나타내는 객체를 순회합니다. 이 추적은 일반적인 방식으로 전이적으로 계속되어 도달 가능한 모든 젊은 객체를 추적합니다. 세대별 쓰기 장벽은 가상 메모리 접근 보호 기법으로 유지되는 페이지별 더티 비트를 사용합니다. 설명하겠지만, 이전 컬렉션 이후 더럽혀진 오래된 세대의 페이지는 전체가 스캔되고, 젊은 세대로의 포인터가 발견되어 루트 집합의 일부로 사용됩니다.

논의

세대별 컬렉션에는 많은 변형이 가능하며, 다양한 트레이드오프를 조정하기 위해 하이브리드가 일반적입니다.

복사 컬렉터가 큰 객체를 다르게 관리하여 특별한 큰 객체 영역에 저장하고 실제로 복사하는 것을 피하는 것이 일반적입니다. 이는 본질적으로 작은 객체의 복사(저렴한 곳)와 큰 객체의 마크-스윕을 결합하여 복사의 더 큰 공간 및 시간 오버헤드를 피합니다. (일반적으로 큰 객체는 실제로 작은 복사 컬렉션된 프록시 객체로 표현되며, 이는 객체의 데이터 필드를 위한 실제 저장소로의 간접 포인터를 담습니다.)

포인터를 포함하지 않는 것으로 알려진 객체도 다른 객체와 분리될 수 있는데, 추적 프로세스 및/또는 일부 구조에서 세대 간 포인터를 추적하는 데 관련된 스캔을 최적화하기 위해서입니다. 복사 컬렉션된 프록시를 사용하는 경우 추적 중 참조 지역성도 개선될 수 있는데, 비포인터 객체의 실제 저장소는 전혀 접근할 필요가 없기 때문입니다.

ParcPlace Smalltalk-80 가비지 컬렉터는 젊은 세대의 중단-복사 컬렉션(최악의 경우 일시 정지가 크지 않음)과 오래된 데이터의 점진적 마크-스윕 컬렉션을 결합합니다.

세대 간 참조 추적

세대별 컬렉터는 오래된 세대에서 젊은 세대로의 포인터를 감지해야 하며, 일부 점진적 추적 알고리즘에서 사용되는 것과 유사한 쓰기 장벽이 필요합니다. 즉, 프로그램이 힙 객체에 포인터를 단순히 저장할 수 없습니다. 컴파일러 및/또는 하드웨어는 각 잠재적 저장이 검사 또는 기록 작업을 동반하도록 보장해야 하며, 젊은 세대로의 포인터가 생성되면 나중에 컬렉터가 찾을 수 있도록 해야 합니다. 일반적으로 컴파일러는 각 잠재적 저장 명령과 함께 추가 명령어를 생성하여 필요한 쓰기 장벽 작업을 수행합니다.

많은 시스템에서 이것이 세대별 가비지 컬렉션의 가장 큰 비용일 수 있습니다. 예를 들어, 최적화 컴파일러를 사용하는 현대 Lisp 시스템에서 포인터 저장은 일반적으로 전체 명령어 수의 약 1%를 차지합니다. 각 포인터 저장이 쓰기 장벽을 위해 20개의 명령어를 필요로 한다면, 성능이 약 20% 저하될 것입니다. 따라서 쓰기 장벽을 최적화하는 것이 전체 가비지 컬렉터 성능에 매우 중요하며, 상당히 빠른 쓰기 장벽이 개발되었습니다. 세대별 컬렉터의 전체 성능에서 핵심적인 역할을 하기 때문에, 쓰기 장벽을 상당히 자세히 논의하겠습니다.

다양한 쓰기 장벽 기법이 사용되었으며, 다른 하드웨어에서, 그리고 다른 언어 및 언어 구현 전략에 대해 다른 성능 트레이드오프를 가집니다.

일부 시스템은 쓰기 장벽을 사용하지 않고 “거의 세대별”인 컬렉션 전략을 사용하여 세대별 컬렉션의 이점 일부를 얻습니다. 오래된 데이터에서 젊은 데이터로의 포인터를 생성될 때 추적하는 대신, 컬렉션 시점에 오래된 데이터를 단순히 그런 포인터를 위해 스캔합니다. 이는 더 많은 스캔 작업이 필요하고 진정한 세대별 컬렉션보다 지역성이 나쁘지만, 도달 가능한 모든 데이터를 추적하는 것보다는 상당히 빠를 수 있습니다. (스캔은 일반적으로 추적보다 몇 배 빠르고 강한 공간적 참조 지역성을 가집니다.) Austin Kyoto Common Lisp의 “Stratified Garbage Collector”는 쓰기 장벽의 오버헤드를 피하기 위해 그런 구조를 사용합니다. Bartlett은 쓰기 장벽 명령어를 생성하지 않는 기성 컴파일러와 작동하도록 설계된 컬렉터에서 유사한 기법을 사용했습니다.

간접 테이블

Lisp 머신용 원래 세대별 컬렉터는 젊은 세대로의 포인터 검사를 가속화하기 위해 특수 하드웨어 및/또는 마이크로코드를 사용했으며, 발견된 포인터는 엔트리 테이블을 통해 (마이크로코드 루틴에 의해) 간접 참조되었습니다. 젊은 세대로의 직접 포인터는 허용되지 않고, 실제 포인터를 담는 테이블 엔트리로의 포인터만 허용되었습니다. 각 세대는 객체로의 실제 포인터를 담는 자체 엔트리 테이블을 가졌습니다. 뮤테이터가 저장 명령어를 실행하고 젊은 세대로의 포인터를 생성하려고 시도하면, 저장 명령어가 마이크로코드로 트랩되었습니다. 젊은 세대로의 포인터를 직접 생성하는 대신, 보이지 않는 전달 포인터가 생성되어 대신 저장되었습니다. Lisp 머신 하드웨어와 마이크로코드는 전달 포인터를 자동으로 감지하고 역참조하여 실행 중인 프로그램에 간접 참조를 보이지 않게 만들었습니다.

특정 세대를 가비지 컬렉션할 때, 다른 세대의 포인터를 실제로 찾아 업데이트하는 대신 엔트리 테이블을 추가 루트 집합으로 사용하기만 하면 되었습니다.

TI Explorer 시스템에서는 다소 다른 구조가 사용되었습니다. 세대당 들어오는 포인터 테이블 대신, 오래된 세대와 젊은 세대의 각 조합에 대해 별도의 나가는 포인터 테이블이 유지되었습니다. 예를 들어, 가장 오래된 세대는 각 젊은 세대에 대해 별도의 출구 테이블을 가지며, 각 세대로의 간접 참조된 포인터를 담았습니다. 이는 테이블 스캔을 더 정확하게 만들었습니다. 즉, 수집 중인 세대와 관련된 포인터만 스캔하고, 테이블 엔트리 자체를 가비지 컬렉션하는 것을 더 간단하게 만들었습니다.

안타깝게도 간접 테이블 구조는 빠르거나 효율적이지 않았습니다. 특히 전달된 포인터를 투명하게 역참조하는 지원이 없는 표준 하드웨어에서는 더욱 그랬습니다. Baker 스타일의 점진적 복사와 마찬가지로, 포인터를 간접 참조를 위해 검사해야 한다면 일반적인 포인터 작업의 비용이 크게 증가합니다. 최근의 세대별 컬렉터는 따라서 간접 참조를 피하고 어느 세대에서든 다른 세대로의 직접 포인터를 허용했습니다. 그런 포인터를 지역화하도록 요구하는 대신, 단순히 그런 포인터가 어디에 있는지 추적하여 컬렉션 시점에 찾을 수 있도록 합니다. 우리는 이런 구조를 포인터 기록 구조라고 부르는데, 단순히 포인터의 위치를 기록하기 때문입니다.

Ungar의 기억 집합

Ungar의 Generational Scavenging 컬렉터는 객체별 포인터 기록 구조를 사용하여 젊은 세대로의 포인터가 저장된 객체를 기록했습니다. 각 잠재적 포인터 저장에서 쓰기 장벽은 세대 간 포인터가 생성되는지 확인했습니다. 저장된 값이 실제로 포인터인지, 젊은 세대를 가리키는지, 오래된 세대의 객체에 저장되는지 확인하는 것이죠. 그렇다면 저장된 객체가 아직 없다면 그런 포인터를 담는 객체의 기억 집합에 추가되었습니다. 각 객체는 헤더에 이미 기억 집합에 있는지 나타내는 비트가 있어 중복 엔트리를 피할 수 있었습니다. 이는 컬렉션 시점의 스캔 비용을 저장된 객체의 수와 크기에 의존하게 만들며, 실제 저장 작업의 수가 아닙니다.

일반적인 경우, 이 구조는 Smalltalk 가상 머신에서 꽤 잘 작동했습니다. 안타깝게도 최악의 경우, 이 검사와 기록은 포인터 저장에서 수십 개의 명령어를 발생시켰고, 더 고성능 언어 구현에서는 상대적 비용이 훨씬 더 높았을 것입니다.

이 구조의 중요한 단점은 기억 집합의 객체가 다음 가비지 컬렉션에서 전체가 스캔되어야 한다는 것인데, 이는 두 가지 이유로 비쌀 수 있습니다. 일부 검사 비용이 반복되는데, 저장된 위치가 컬렉션 사이에 여러 번 저장되어 매번 검사되고, 저장된 객체가 컬렉션 시점에 다시 스캔되어야 하기 때문입니다. 더 나쁜 것은 매우 큰 객체가 정기적으로 저장되어 각 컬렉션에서 전체가 스캔되어야 할 수 있다는 것입니다. 후자는 일부 프로그램에서 Tektronix Smalltalk에서 실행될 때 대량의 스캔 작업, 심지어 스래싱을 유발하는 것으로 관찰되었습니다.

페이지 마킹

Symbolics Lisp 머신용 Moon의 Ephemeral Garbage Collector는 다른 포인터 기록 구조를 사용했습니다. 세대 간 포인터가 저장된 객체를 기록하는 대신, 저장된 가상 메모리 페이지를 기록했습니다. 기록의 단위로 페이지를 사용하면 매우 큰 객체를 스캔하는 문제를 피할 수 있었지만, 작은 객체에 대한 희소 쓰기의 비용은 증가했는데, 전체 페이지가 여전히 스캔되기 때문입니다. Symbolics 하드웨어에서는 스캔 비용이 크지 않았는데, 세대 검사를 매우 빠르게 만드는 특별한 태그 지원이 있었고 페이지가 상당히 작았기 때문입니다. 쓰기 장벽의 대부분도 (각 포인터 쓰기를 동반하는 추가 명령어가 아닌) 하드웨어에서 직접 구현되어 각 포인터 저장의 시간 비용이 작았습니다. 이 시스템에서 젊은 세대로의 포인터에 대한 정보는 페이지별 테이블에 담깁니다. 이는 테이블이 암묵적으로 중복을 제거한다는 장점이 있습니다. 페이지가 여러 번 저장되어도 테이블의 같은 비트가 설정되지만, 페이지는 다음 가비지 컬렉션에서 한 번만 스캔됩니다. 이 중복 제거는 Ungar의 객체 헤더의 비트를 사용하여 기억 집합의 엔트리 고유성을 보장하는 것과 동등합니다. 가비지 컬렉션에서 기록된 항목을 스캔하는 데 필요한 시간은 따라서 저장된 페이지의 수와 페이지 크기에 비례하지만, 실제 저장 작업의 수에는 비례하지 않습니다.

안타깝게도 이 구조는 더 큰 페이지와 페이지 스캔이나 쓰기 검사를 위한 전용 하드웨어가 없는 표준 하드웨어에서 구현되면 상당히 느렸을 것입니다. 또한 처음부터 임의의 저장된 페이지를 스캔할 수 있는 능력이 필요했는데, 이는 모든 머신 워드에 타입 태그를 담는 추가 비트가 있는 Symbolics 머신보다 표준 하드웨어에서 더 복잡합니다.

최근에는 가상 메모리 더티 비트가 거친 쓰기 장벽으로 사용되었습니다. 기본 가상 메모리 시스템은 일반적으로 페이지가 마지막으로 디스크에 쓰여진 이후 더럽혀졌는지(어떤 방식으로든 변경되었는지) 나타내는 페이지당 비트를 유지합니다. 이 비트를 유지하기 위해 수행되는 작업의 대부분은 전용 메모리 하드웨어에서 수행되므로, 언어 구현자의 관점에서는 무료입니다. 안타깝게도 대부분의 운영 체제는 더티 비트를 검사하는 기능을 제공하지 않으므로 OS 커널 수정이 필요합니다. 대안으로, 가상 메모리 보호 기능을 사용하여 더티 비트를 시뮬레이션할 수 있는데, 페이지를 쓰기 보호하여 쓰기가 하드웨어에 의해 감지되고 트랩 핸들러를 호출하도록 합니다. 이 기법은 Xerox Portable Common Runtime 가비지 컬렉터에서 사용됩니다. 트랩 핸들러는 단순히 페이지가 마지막 가비지 컬렉션 이후 쓰여졌다고 기록하고, 페이지의 보호를 해제하여 프로그램 실행이 재개될 수 있도록 합니다. PCR 컬렉터에서는 다른 세대의 객체가 같은 페이지에 있을 수 있으므로, 더럽혀진 페이지가 컬렉션 시점에 스캔될 때 관련 없는 세대의 객체는 건너뜁니다. Appel, Ellis, Li 컬렉터와 마찬가지로, 가상 메모리 보호를 사용하면 엄격한 실시간 요구 사항을 충족하는 것이 불가능해지고 상당한 트랩 오버헤드가 발생할 수 있습니다. 쓰기 지역성이 좋지 않으면 스캔 비용도 상대적으로 높을 수 있습니다. 하지만 이런 종류의 쓰기 장벽은 쓰기 장벽 명령어를 생성하지 않는 비협조적인 컴파일러를 다룰 때 장점이 있습니다.

워드 마킹

표준 하드웨어에 Moon의 컬렉터를 적응시키면서, Sobalvarro는 워드 마킹 시스템을 사용하여 큰 페이지를 스캔하는 비용을 피했는데, 비트맵을 사용하여 실제로 포인터가 저장된 메모리의 특정 머신 워드를 기록했습니다. 이는 관련 포인터의 위치가 정확히 저장되었기 때문에 포인터를 위해 임의의 페이지를 스캔할 수 있는 능력이 필요 없게 했습니다.

Sobalvarro는 또한 쓰기 장벽을 더 간단하게 만들어 표준 하드웨어에 최적화했습니다. 대부분의 쓰기 장벽 검사가 제거되고 컬렉션 시점까지 연기되었습니다. 저장된 위치는 컬렉션 시점에 저장된 항목이 세대 간 포인터인지 확인하기 위해 검사됩니다. 이는 Moon이나 Ungar의 검사보다 덜 정확하고 컬렉션 시점에 더 많은 워드를 검사하게 만들 수 있지만, 암묵적 중복 제거가 먼저 수행되고 다른 검사는 저장된 워드당 한 번만 수행하면 된다는 이점도 있습니다.

Sobalvarro 구조의 단점은 합리적으로 큰 힙의 경우 비트 테이블이 상당히 크다는 것인데, 메모리 전체 크기의 약 3%입니다. 이 테이블을 스캔하는 것은 단순한 선형 비트 배열로 표현되면 상대적으로 비쌀 것입니다. 개별 비트를 저장하는 것도 일부 아키텍처에서 쓰기 장벽을 비싸게 만들 수 있는데, 워드 미만 쓰기 명령어가 느리거나 여러 다른 명령어를 사용하여 합성해야 하기 때문입니다. Sobalvarro의 해결책은 테이블의 희소(2단계) 표현을 사용하는 것이었습니다. 이는 추가적인 쓰기 장벽 비용을 발생시켰는데, 희소 배열에 대한 작업이 연속 배열에 대한 작업보다 상당히 느리기 때문입니다.

카드 마킹

페이지나 워드를 마킹하는 대안은 메모리를 개념적으로 카드라고 불리는 중간 크기 단위로 나누는 것입니다. 상대적으로 작은 카드를 사용하면 단일 저장 작업이 컬렉션 시점에 소량의 스캔만 유발할 수 있다는 장점이 있어, 평균적으로 페이지 마킹보다 비용이 작습니다. 카드가 극도로 작지 않은 한, 저장된 카드를 기록하는 데 사용되는 테이블은 워드 마킹의 해당 테이블보다 훨씬 작습니다. 대부분의 시스템에서 이는 테이블을 연속적인 선형 배열로 표현하는 것을 실현 가능하게 만들어 쓰기 장벽을 빠르게 유지합니다.

표준 하드웨어에서 카드 마킹을 사용하는 한 가지 문제는 카드가 객체의 시작 부분으로 시작하지 않더라도 포인터를 위해 스캔되어야 한다는 것입니다. Wilson의 Opportunistic Garbage Collector는 크로싱 맵을 유지하여 이를 해결하는데, 어느 카드가 객체의 스캔 불가능한 부분으로 시작하는지 기록합니다. 처음부터 스캔할 수 없는 카드의 경우, 맵을 사용하여 스캔 가능한 이전 카드를 찾고, 그 카드에서 객체 헤더를 찾아, 스캔할 카드의 객체 헤더를 찾을 때까지 객체별로 앞으로 건너뛸 수 있습니다. 이는 Appel, Ellis, Li가 점진적 복사 컬렉터에서 페이지별 스캔을 지원하기 위해 사용한 크로싱 맵의 개선입니다. Wilson의 구조에서 카드에 해당하는 비트는 카드가 젊은 세대로의 포인터를 포함하면 설정된 상태로 남습니다. 그런 카드는 다시 저장되지 않더라도 다음 가비지 컬렉션에서 다시 스캔되어야 합니다.

Ungar, Chambers, Holzle는 Self 언어용 가비지 컬렉터에서 이 카드 마킹 구조를 더욱 개선했습니다. 저장된 카드를 기록하기 위해 비트 테이블 대신 바이트 테이블을 사용합니다. 비트만 필요하지만 바이트가 사용되는데, 대부분의 아키텍처에서 바이트 저장이 빠르기 때문입니다. 이는 쓰기 장벽이 무조건 바이트 배열에 바이트를 저장하는 세 개의 명령어로만 구성되도록 합니다. 이는 바이트 배열이 비트 배열보다 8배 크기 때문에 스캔 비용의 증가를 초래하지만, 대부분의 시스템에서 쓰기 장벽 비용의 감소가 그만한 가치가 있습니다. Holzle는 쓰기 장벽의 기록 정확도를 완화하여 이를 더욱 개선했는데, Sun SPARC 프로세서에서 저장당 비용을 두 개의 명령어로 낮추면서 스캔 비용이 약간 증가했습니다. 카드 마킹은 저장 목록과 결합하여 젊은 세대로의 포인터를 담지만 다시 저장되지 않는 카드의 스캔을 줄일 수도 있습니다.

저장 목록

포인터 기록에 대한 가장 단순한 접근법은 단순히 각 저장된 주소를 어떤 종류의 목록에 기록하는 것입니다. 이는 연결 목록이거나, 선형 배열 스택에 항목을 푸시하는 것처럼 연속 위치에 저장되는 사전 할당된 배열일 수 있습니다.

Standard ML of New Jersey용 Appel의 매우 단순한(500줄의 C 코드) 세대별 컬렉터는 그런 목록을 사용하는데, 각 컬렉션에서 단순히 스캔되며 일반적인 ML 프로그램에서 좋은 성능을 보입니다.

하지만 단순한 저장 목록은 많은 언어 구현에서 단점이 있는데, 저장된 위치의 집합이 아닌 백(다중 집합)을 구현하기 때문입니다. 즉, 같은 위치가 자주 저장되면 목록에 여러 번 나타날 수 있고, 가비지 컬렉터는 컬렉션 시점에 각 엔트리를 검사해야 합니다. 따라서 컬렉션 시점 비용은 저장된 위치의 수가 아닌 포인터 저장의 수에 비례합니다. 이런 중복 제거의 부족은 포인터 저장이 매우 빈번하면 과도한 공간 사용으로 이어질 수도 있습니다. ML의 경우 부작용이 상대적으로 드물게 사용되므로 이것이 일반적으로 문제가 되지 않습니다.

Moss 등은 정적 저장 버퍼라는 특별한 종류의 목록에 제한된 수의 엔트리를 허용하고 이 버퍼가 가득 차면 특별한 루틴을 호출하는 저장 목록 기법의 변형을 고안했습니다. 특별한 루틴은 목록을 처리하여 빠른 해시 테이블을 사용하여 중복을 제거합니다. 이 기법은 공간 비용을 줄이고 모든 저장 목록 처리를 가비지 컬렉션 시점에 하는 것을 피하지만, 테이블 기반 구조와 같은 중복 제거 장점은 없습니다. 중복이 제거되지만, 이미 저장 목록에 넣은 후에만 그렇습니다. 각 포인터 저장은 저장 목록에 엔트리를 생성하며, 나중에 가져와서 검사되어야 합니다.

Hosking과 Hudson은 카드 마킹과 저장 목록의 최고 기능 일부를 결합했습니다. 포인터 저장은 일반적인 방식으로 카드 마킹 쓰기 장벽에 의해 기록되지만, 카드가 스캔될 때 젊은 세대로의 포인터를 포함하는 개별 위치가 기록됩니다. 이는 후속 컬렉션이 다시 저장되지 않으면 전체 카드를 다시 스캔하는 것을 피할 수 있게 합니다.

논의

세대별 컬렉터를 위한 쓰기 장벽 전략을 선택할 때, 시스템 구현의 다른 측면과의 상호작용을 고려하는 것이 중요합니다. 예를 들어, Xerox PARC “대부분-병렬” 컬렉터는 가상 메모리 기법을 사용하여 페이지별 더티 비트를 구현하는데, 부분적으로는 쓰기 장벽 구현에 협조하지 않을 수 있는 다양한 컴파일러와 작동하도록 설계되었기 때문입니다. 예를 들어, 기성 C 컴파일러는 각 포인터 저장과 함께 쓰기 장벽 명령어를 생성하지 않습니다. 다른 시스템, 특히 정적 타입 시스템 및/또는 타입 추론 기능이 있는 시스템에서는 컴파일러가 쓰기 장벽 비용을 상당히 줄일 수 있는데, 컴파일러가 정적으로 수행할 수 있는 쓰기 장벽 검사를 생략할 수 있기 때문입니다.

또 다른 문제는 실시간 응답이 필요한지 여부입니다. 페이지 마킹과 카드 마킹 같은 테이블 기반 구조는 기록된 포인터를 실시간으로 점진적으로 스캔하기 어렵게 만들 수 있습니다. 저장 목록은 실시간으로 처리하기 더 쉽습니다. 사실, 쓰기 장벽을 위해 수행되는 작업은 점진적 업데이트 추적 기법을 위해 수행되는 작업과 유사할 수 있어, 두 쓰기 장벽을 결합하여 일부 비용을 최적화할 수 있습니다.

쓰기 장벽의 실제 비용은 다소 논쟁의 여지가 있습니다. 여러 연구가 인터프리터 시스템의 쓰기 장벽 오버헤드를 측정했는데, 최적화 컴파일러를 사용하는 고성능 시스템과 연관시키기 어렵습니다. 고성능 시스템의 측정을 가비지 컬렉터 비용에 대한 분석적 이해와 결합하여 잘 구현된 시스템에 대해 잘 구현된 컬렉터의 대략적인 비용을 추론하는 것이 더 합리적일 수 있습니다.

앞서 언급했듯이, 컴파일된 Lisp 시스템은 힙 객체로의 포인터 저장을 백 개의 명령어당 약 하나 실행하는 것으로 보입니다. 카드 마킹 쓰기 장벽은 그런 시스템을 약 4~5% 정도만 느리게 만들어야 하는데, 각 포인터 저장 시점에 2~3개의 명령어를 실행하고, 각 컬렉션에서 더 작은 카드 스캔 비용이 추가됩니다. 살아있는 데이터가 적거나 세대별 컬렉션에 유리한 수명 분포를 가진 많은 프로그램의 경우, 추적 및 회수 비용도 유사하게 낮을 것이고, 가비지 컬렉션 비용은 10% 미만이어야 합니다.

하지만 이 수치는 워크로드, 프로그래밍 언어의 타입 정보, 데이터 표현, 컴파일러가 사용하는 최적화에 따라 상당히 달라질 수 있으며, 종종 위쪽으로 달라집니다.

컴파일러가 더 빠른 코드를 생성하면, 쓰기 장벽 비용이 (더 작은) 전체 실행 시간의 더 큰 비율이 될 수 있습니다. 반면에 컴파일러는 일부 포인터 기록이 중복되거나 일부 동적 타입 값이 절대 포인터가 아니라고 추론하여 쓰기 장벽 비용을 줄일 수도 있습니다.

안타깝게도 기존의 명령형 정적 타입 시스템에서 쓰기 장벽의 비용은 잘 이해되지 않습니다. 정적 타입 시스템은 일반적으로 포인터와 비포인터 타입을 구별하여 컴파일러에 도움이 될 수 있지만, 타입 선언이 시스템의 다른 영역의 성능을 더욱 개선하여 가비지 컬렉터의 상대적 성능을 더 나쁘게 만들 수 있습니다. 반면에 기존의 정적 및 강타입 언어는 종종 힙 객체 할당 및 변경의 전체 비율이 낮아, 쓰기 장벽과 추적 비용을 전체 프로그램 실행 시간의 비율로 줄입니다.

프로그래밍 스타일도 쓰기 장벽 비용에 상당한 영향을 미칠 수 있습니다. 가비지 컬렉션과 함께 사용하도록 설계된 많은 언어에서 할당 루틴은 값을 인수로 받아 객체의 필드를 초기화하는 프리미티브입니다. 다른 언어에서는 프로그래머가 새 객체의 필드를 명시적으로 초기화해야 할 수 있습니다. 전자의 경우 언어 구현은 포인터 필드로의 초기화 쓰기에 대해 쓰기 장벽을 생략할 수 있지만, 후자의 경우 일반적으로 그럴 수 없습니다. 이것이 문제인지는 불분명합니다. 그런 언어의 프로그램은 일반적으로 힙 할당 비율이 낮고 객체의 포인터 필드가 더 적을 수 있습니다.

---

흥미로운 배경 이야기

1. Lisp 머신의 황금기와 특수 하드웨어

이 글에서 자주 언급되는 Symbolics와 TI Explorer 같은 “Lisp 머신”은 1970~80년대에 등장한 특수 목적 컴퓨터입니다. 이들은 Lisp 프로그램 실행에 최적화된 하드웨어를 가지고 있었는데, 예를 들어 모든 메모리 워드에 타입 태그를 담는 추가 비트가 있었고, 가비지 컬렉션을 위한 마이크로코드 지원도 있었습니다. 당시에는 이런 특수 하드웨어가 AI 연구에 필수적이라고 여겨졌지만, 1980년대 후반 범용 워크스테이션의 성능이 급격히 향상되면서 경제성을 잃고 역사 속으로 사라졌습니다. 하지만 이 시기에 개발된 많은 가비지 컬렉션 기법들은 현대 시스템에도 여전히 영향을 미치고 있습니다.

2. “세대 가설”의 발견

세대별 가비지 컬렉션의 핵심 아이디어인 “대부분의 객체는 젊어서 죽는다”는 관찰은 1980년대 초 여러 연구자들이 실제 프로그램의 메모리 사용 패턴을 분석하면서 발견했습니다. 이는 당시로서는 놀라운 발견이었는데, 언어와 프로그램이 다양함에도 불구하고 80~98%라는 일관된 비율이 나타났기 때문입니다. 이 발견은 가비지 컬렉션 연구의 패러다임을 바꿨고, David Ungar의 1984년 논문 “Generation Scavenging”이 이 아이디어를 체계화하여 큰 영향을 미쳤습니다.

3. 현대 JVM과 V8의 세대별 GC

이 글에서 설명하는 세대별 가비지 컬렉션 기법은 오늘날 Java의 HotSpot VM과 JavaScript의 V8 엔진 같은 주요 런타임에서 핵심 기술로 사용됩니다. 예를 들어 V8은 “Scavenger”라는 이름의 젊은 세대 컬렉터를 사용하는데, 이는 Ungar의 Generation Scavenging에서 직접 영감을 받았습니다. 흥미롭게도 이런 현대 시스템들은 여전히 이 글에서 논의된 카드 마킹, 쓰기 장벽 같은 기법들을 사용하고 있으며, 30년 이상 된 아이디어가 여전히 유효함을 보여줍니다.

---