지역성 고려사항

가비지 컬렉션 전략은 메모리가 사용되고 재사용되는 방식에 큰 영향을 미치며, 당연히 참조의 지역성에도 상당한 영향을 줍니다.

지역성 효과의 종류

가비지 컬렉션의 지역성 효과는 대략 세 가지로 나눌 수 있습니다:

데이터 구조가 생성되고 조작되는 방식을 바꾸는 프로그래밍 스타일에 대한 효과
가비지 컬렉션 프로세스 자체의 직접적인 효과
가비지 컬렉션의 간접적인 효과, 특히 빈 메모리의 재할당 패턴과 살아있는 데이터의 클러스터링

첫 번째인 프로그래밍 스타일의 효과는 아직 잘 이해되지 않은 부분입니다. 효율적인 가비지 컬렉터가 있는 시스템에서는 프로그래머들이 당면한 작업에 적합한 프로그래밍 스타일을 채택하는 경향이 있는데, 주로 객체지향이나 함수형 접근법입니다. 새로 계산된 데이터를 담기 위해 새로운 데이터 객체가 동적으로 할당되고, 데이터가 더 이상 필요 없어지면 객체는 버려집니다. 이상적으로는 프로그래머가 가장 자연스러운 형태로 계산을 표현하며, 애플리케이션 레벨의 데이터가 언어 레벨의 데이터 객체로 상당히 직접적으로 매핑됩니다.

반면에 명시적 할당과 해제는 왜곡된 프로그래밍 스타일을 조장하는 경우가 많습니다. 프로그래머가 객체를 해제하고 다른 객체를 재할당하는 것이 너무 비싸다는 이유만으로, 언어 레벨 객체를 시간에 따라 개념적으로 다른 데이터를 표현하는 데 재사용하게 됩니다. 마찬가지로 비효율적인 가비지 컬렉션을 가진 시스템(많은 오래된 Lisp 구현체들처럼)에서는 프로그래머들이 비슷한 언어 레벨 객체 재사용에 의존하곤 합니다. 예를 들어 새로운 리스트 요소 할당을 피하기 위해 리스트 구조를 파괴적으로 변경하거나, 시간에 따라 여러 데이터 세트를 담는 데 사용되는 하나의 큰 배열을 할당하는 식입니다. 명시적 해제는 반대 방향의 왜곡도 초래합니다 - 하나의 개념적 데이터 객체를 여러 언어 레벨 객체로 매핑하는 것이죠. 프로그래머들은 명시적 해제를 단순화하기 위해 많은 추가 객체를 할당할 수 있습니다. 데이터 구조에 관심 있는 모듈은 데이터 구조를 복사하여, 언제 메모리를 회수할 수 있는지에 대한 로컬 결정을 내릴 수 있습니다. 이런 왜곡들은 가비지 컬렉션 시스템과 비-가비지 컬렉션 시스템의 지역성을 직접 비교하는 것을 극도로 어렵게 만듭니다. 이런 비교를 시도하는 전형적인 연구들은 가비지 컬렉션을 염두에 두지 않고 작성된 프로그램을 원래 형태와 명시적 해제를 가비지 컬렉션으로 대체한 형태로 비교합니다. 이는 왜곡된 프로그래밍 스타일의 효과를 암묵적으로 숨기는데, 가비지 컬렉션 버전의 프로그램이 왜곡을 그대로 물려받기 때문입니다.

두 번째 범주인 가비지 컬렉션 프로세스 자체의 지역성은 보통 즉시 떠오르는 것입니다. 때로는 상당히 중요하지만, 세 가지 중 가장 덜 중요할 수도 있습니다. 전체 가비지 컬렉션의 경우 모든 살아있는 데이터를 추적해야 하는데, 이는 기존 메모리 계층구조와 매우 나쁘게 상호작용할 수 있습니다. 대부분의 살아있는 객체는 추적 중에 단 한 번만 접근되므로 시간적 지역성, 즉 짧은 시간 동안 같은 데이터를 반복적으로 접근하는 경우가 거의 없습니다. 반면에 상당한 공간적 지역성은 있을 수 있습니다 - 짧은 시간 동안 여러 다른 인접한 메모리 영역(예: 같은 가상 메모리 페이지 내)을 접근하는 것이죠.

세 번째 범주의 효과가 아마도 가장 중요할 텐데, 그 중요성이 널리 인식되지 않고 있습니다. 메모리 재할당 전략은 메모리가 반복적으로 접근되는 방식에 지역성 특성을 부여하는데, 객체 자체가 빨리 죽어서 다시는 접근되지 않더라도 그렇습니다. 이것이 물론 세대별 가비지 컬렉션의 주요 이유 중 하나입니다 - 작은 메모리 영역(가장 젊은 세대)을 많은 단명 객체를 거기에 할당함으로써 반복적으로 재사용하는 것이죠. 이것이 또한 활성화 스택이 일반적으로 훌륭한 참조 지역성을 갖는 이유입니다 - 스택의 상단 근처에서 메모리가 매우 단명한 활성화 레코드를 할당함으로써 매우 자주 재사용됩니다. 세대별 가비지 컬렉터는 수명 분포가 대략 비슷하다는 사실을 활용하여 힙에 대략 스택과 같은 메모리 재사용 패턴을 부여하는 것으로 볼 수 있습니다.

앞서 지적했듯이, 단순한 비-세대별 가비지 컬렉터는 할당 속도가 높으면 지역성이 매우 나쁜데, 단순히 합리적인 시간 내에 너무 많은 메모리가 접근되기 때문입니다. Ungar가 지적했듯이, 새로운 데이터를 위한 메모리 공간을 만들기 위해 결과적인 가비지를 단순히 페이징 아웃하는 것은 고성능 시스템에서 일반적으로 받아들일 수 없는 비용일 것입니다. 세대별 가비지 컬렉터는 이 지역성 재앙의 범위를 관리 가능한 영역 - 가장 젊은 한두 세대 - 으로 제한합니다. 이를 통해 더 오래 살아남은 데이터에 대한 반복적인 접근의 “진짜” 지역성 특성이 더 오래된 세대에서 나타날 수 있습니다. 이 효과 때문에 가비지 컬렉션 시스템의 전반적인 지역성 특성은 비-가비지 컬렉션 시스템과 대략 비슷해 보입니다 - 가장 젊은 세대가 다른 언어에서 스택에 할당될 수 있는 힙 할당 데이터의 대부분을 걸러냅니다.

하지만 가비지 컬렉터와 명시적 힙 관리 모두에 관련된 설계 선택이 많기 때문에 직접 비교는 어렵습니다.

복사 가비지 컬렉션의 경우, 명백히 또 다른 간접적인 지역성 효과가 있습니다 - 메모리에서 데이터 객체를 이동시킴으로써 컬렉터가 프로그램 자체의 접근 지역성에 영향을 미칩니다 - 즉, 프로그램의 언어 레벨 데이터에 대한 논리적 참조와 특정 메모리 위치에 대한 결과적인 참조 사이의 매핑에 영향을 미칩니다.

이런 종류의 효과는 복사 컬렉션에만 국한되지 않습니다. 비-복사 컬렉터도 언어 레벨 객체를 사용 가능한 빈 메모리에 매핑하는 방법을 결정하는 데 상당한 자유도를 가집니다. 프로그램이 주어진 크기의 메모리 조각을 요청할 때, 할당자는 어떤 적절한 크기의 빈 메모리 조각이든 자유롭게 반환할 수 있습니다. 이 결정을 어떤 규칙이 지배해야 하는지는 불분명합니다. (이것은 명시적 힙 관리 시스템에서도 발생하지만, 거기서도 체계적으로 연구되지 않았습니다. 명시적 기법에 대한 대부분의 연구는 단편화와 CPU 비용을 연구했지만, 계층적 메모리에서의 캐싱에 대한 효과는 무시했습니다.)

서로 다른 지역성 효과의 중요성은 당연히 시스템이 사용하는 데이터의 상대적 크기와 그것이 실행되는 하드웨어의 주 메모리에 따라 달라집니다. 많은 시스템의 경우, 편집기, 브라우저, 컴파일러, 애플리케이션 코드와 데이터를 포함한 전체 시스템 힙이 주 메모리에 들어갑니다. 이런 시스템의 정상 모드는 프로그램이 일반적으로 전혀 페이징하지 않을 만큼 충분한 RAM을 갖는 것입니다. 하지만 다른 시스템에서는 가장 오래된 한두 세대가 일반적인 주 메모리에 들어가기에 너무 큰데, 시스템 자체가 크고 복잡한 소프트웨어를 포함하거나 애플리케이션 데이터나 코드가 매우 크기 때문입니다.

복사 컬렉터에서는 따라서 효과적으로 메모리 상주하는 세대와 가상 메모리 캐싱에 진정으로 의존해야 할 만큼 큰 세대 사이에 이진 구분이 있습니다. 전자의 경우(전체 시스템을 포함할 수 있음), 할당과 컬렉션의 지역성은 가상 메모리 성능과 본질적으로 무관합니다 - 공간 비용은 모든 것을 RAM에 유지하는 고정 비용입니다. 반면 후자의 경우, 가상 메모리 수준의 지역성이 결정적일 수 있습니다.

비-이동 컬렉터에서는 상황이 다소 다릅니다 - 가장 젊은 세대의 공간 비용도 단편화 정도와 다양한 세대의 데이터가 메모리에서 어떻게 섞여 있는지에 따라 달라집니다. 이러한 문제의 정도는 잘 이해되지 않았지만, 널리 믿어지는 것보다 덜 심각할 수 있습니다.

할당의 지역성과 단명 객체

위에서 언급했듯이, 할당 패턴은 종종 단순 컬렉터에서 지역성에 가장 중요한 영향을 미칩니다. 세대별 복사 컬렉터에서는 이 효과가 가상 메모리 관점에서 크게 줄어듭니다 - 가장 젊은 한두 세대를 구성하는 페이지들이 너무 자주 재사용되어 단순히 RAM에 머물러 있고 효과적으로 고정 공간 비용을 발생시킵니다. 반면에 전체 가장 젊은 세대의 빈번한 재사용은 메모리 계층구조의 다음 작은 레벨 - 고속 CPU 캐시 - 에 해로운 영향을 미칠 수 있습니다. 메모리 재사용 주기가 훨씬 작아졌지만, 주기가 캐시에 맞지 않으면 캐시는 단순 컬렉터에서 주 메모리가 겪는 것과 거의 같은 방식으로 추가 미스를 겪게 됩니다. 하지만 이러한 미스의 효과는 가상 메모리만큼 극적이지 않은데, 캐시 대 주 메모리 속도의 비율이 주 메모리 대 디스크 속도의 비율만큼 크지 않기 때문입니다. 또한 적어도 복사 컬렉션에서는 재할당 패턴이 매우 강하게 순차적이어서 단순한 프리페칭 전략이나 심지어 큰 블록 크기의 사용만으로도 미스를 상당히 줄일 수 있습니다. 현재 프로세서에서는 할당 속도가 상대적으로 높을 때조차 비용이 전체 실행 시간의 몇 퍼센트를 넘지 않는 것으로 보입니다. 하지만 더 빠른 프로세서는 캐시-메모리 대역폭이 프로세서 속도에 맞춰 확장되지 않거나 공유 버스 멀티프로세서에서처럼 버스 대역폭이 프리미엄인 경우 이 효과로 더 많이 고통받을 수 있습니다.

Zorn은 상대적으로 큰 캐시가 세대별 가비지 컬렉션 시스템에 상당히 효과적일 수 있음을 보였습니다. Wilson은 캐시와 가장 젊은 세대의 상대적 크기가 특히 중요하며, 재할당으로 인한 접근 패턴의 특이성 때문에 캐시 교체 정책의 세부 사항도 중요할 수 있음을 보였습니다.

여러 연구자들이 재할당될 영역의 가비지 데이터 페칭을 피하는 최적화를 제안했습니다. 이는 캐시-메모리 대역폭 요구사항을 거의 절반으로 줄일 수 있습니다. Koopman 등은 콤비네이터 리덕션 기반 함수형 프로그래밍 언어 구현에서 이를 처음 설명했고, 일부 기존 캐시 설계가 이 효과를 달성할 수 있음을 보였습니다. (핵심 기능은 서브-블록 배치와 결합된 쓰기-할당 정책의 사용입니다. 쓰기-할당은 블록이 먼저 읽지 않고 쓰여지면 캐시를 우회하여 단순히 주 메모리의 블록을 업데이트하는 대신 캐시 메모리 블록을 할당한다는 의미입니다. 이는 객체가 할당되어 쓰여질 때 곧바로 참조될 때 캐시에 있도록 보장합니다. 서브-블록 배치는 캐시 블록이 캐시에서 유효하거나 무효할 수 있는 여러 독립적인 라인으로 나뉜다는 의미입니다. 이를 통해 한 워드에 대한 쓰기가 블록의 나머지 부분의 페치를 트리거하는 것을 피할 수 있습니다. 따라서 객체는 프로세서를 멈추고 그들이 차지하는 저장소의 이전 내용을 페치하지 않고도 할당되고 초기화될 수 있습니다.) Tarditi와 Diwan은 세대별 가비지 컬렉션을 사용하는 더 기존의 언어 구현에서 같은 효과를 달성할 수 있음을 보이고, 높은 쓰기 속도를 지원하는 캐시-메모리 인터페이스의 가치를 입증했습니다.

이동 컬렉터와 비-이동 컬렉터 간의 지역성 차이는 고속 캐시 메모리 규모에서는 크지 않은 것으로 보입니다 - 컬렉터의 유형은 할당 속도와 가장 젊은 세대의 크기, 즉 일반적인 경우에 메모리가 얼마나 빨리 사용되고 회수되고 재사용되는지만큼 중요하지 않습니다. Zorn은 비-복사 컬렉터가 세미-스페이스를 사용하는 복사 컬렉터보다 더 나은 지역성을 가질 수 있음을 보이는데, 단순히 세대당 하나의 공간만 필요하기 때문입니다. Wilson은 Ungar의 특별한 생성 영역 사용 기법이 가상 메모리 수준에서와 마찬가지로 큰 캐시 수준에서도 비슷한 이점을 낼 수 있음을 보입니다. Wilson은 또한 힙에서의 변수 바인딩 환경과 활성화 레코드의 할당이 캐시에 맞지 않는 가장 젊은 세대로 인한 캐시 수준 지역성 문제를 크게 악화시킬 수 있음을 보입니다. 이는 고성능 프로세서에서 Standard ML of New Jersey의 시뮬레이션 연구에 의해 뒷받침됩니다. 이는 활성화 정보와 바인딩 환경이 컴파일 타임 분석을 사용하여 스택에 할당되거나 소프트웨어 스택 캐시에 할당되어야 함을 시사합니다. 소프트웨어 스택 캐시는 바인딩 환경이 일급 프로시저에 의해 캡처될 수 있고/있거나 활성화 체인이 일급 컨티뉴에이션으로 캡처될 수 있는 ML이나 Scheme 같은 언어에서 사용될 수 있습니다. 캐시는 환경과 컨티뉴에이션이 캡처될 수 있지만 대다수는 그렇지 않아 힙에 놓일 필요가 없다는 사실을 활용합니다.

추적 순회의 지역성

GC 추적 순회의 지역성은 독립적으로 연구하기 어렵지만, 몇 가지 명백한 특성이 있는 것으로 보입니다. 수집되는 세대의 대부분의 객체는 정확히 한 번 접근되는데, 대부분의 객체가 정확히 하나의 다른 객체에 의해 가리켜지기 때문입니다 - 일반적인 데이터 구조는 많은 수의 순환을 포함하지 않으며, 많은 순환은 순회 지역성에 거의 영향을 미치지 않을 만큼 충분히 작습니다.

이를 고려하면, 순회의 주요 특성은 모든 살아있는 데이터를 철저히 접근하지만 대부분 매우 짧게 접근한다는 것입니다. 시간적 참조 지역성, 즉 같은 데이터를 반복적으로 접근하는 것은 거의 없습니다. 대부분의 객체는 주어진 시간에 정확히 하나의 포인터에 의해 참조되므로 추적 순회에 의해 한 번만 도달됩니다. 활용할 수 있는 주요 지역성 특성은 메모리에서 데이터 구조 레이아웃의 공간적 지역성입니다 - 밀접하게 연결된 객체들이 메모리에서 서로 가까이 있으면, 한 객체를 접근하는 것이 순회되기 직전에 여러 다른 객체를 빠른 메모리로 가져올 수 있습니다.

Xerox PCR 시스템의 경험은 비-복사 컬렉터(압축 없이)에서도 메모리에서 객체의 초기 레이아웃에 유용한 지역성이 있음을 나타냅니다. 관련 객체들은 종종 거의 같은 시간에 생성되고/죽기 때문에 단순한 할당 전략이 메모리에서 유용한 클러스터링을 초래합니다. PCR 컬렉터는 데이터를 순회하기 전에 루트 세트를 정렬하여 이를 향상시키므로, 같은 영역으로의 루트 포인터가 거의 같은 시간에 순회됩니다. 이는 전체 가비지 컬렉션 중 페이징을 크게 줄이는 것으로 관찰되었습니다.

복사 컬렉터에서는 순회가 일반적으로 좋은 공간적 지역성을 갖는 것처럼 보이는데, 객체들이 일반적으로 처음 복사될 때 순회 순서에 따라 구성되고, 이후 순회에서 같은 순서로 순회되기 때문입니다. 물론 첫 번째 순회에서는 객체의 초기 할당 레이아웃과 순회 순서 간의 일치도 중요할 수 있습니다.

높은 공간적 지역성과 낮은 시간적 지역성 때문에, 추적 순회가 사용하는 메모리를 제한하여 추적 중에만 짧게 접근되는 대량의 데이터로 메모리 내용을 불필요하게 대체하는 것을 피하는 것이 바람직할 수 있습니다. 증분 추적은 추적 단계 중에 뮤테이터가 데이터를 접근할 수 있게 하여 가장 활성화된 데이터를 빠른 메모리에 유지함으로써 같은 이점의 일부를 낼 수 있습니다.

더 오래 살아남는 객체의 클러스터링

여러 연구가 복사 컬렉션의 지역성에 대한 간접적 효과 - 즉, 실행 중인 프로그램이 이후에 접근하는 데이터를 재구성하는 효과 - 를 다루었습니다.

정적 그룹화

Stamos와 Blau는 Smalltalk 시스템에서 오래 살아남는 시스템 데이터와 코드를 재구성하기 위해 서로 다른 복사 순회 알고리즘을 사용하는 효과를 연구했습니다. 이러한 알고리즘들은 프로그램 실행 중(즉, 가비지 컬렉션 시간에) 데이터를 재구성하지만, 가비지 컬렉션이 발생하는 시점에 객체들이 어떻게 연결되어 있는지에 따라 데이터를 재구성하기 때문에 정적 그룹화 알고리즘이라고 불립니다 - 클러스터링은 프로그램의 실제 데이터 객체 접근의 동적 패턴을 기반으로 하지 않습니다.

두 연구 모두 깊이 우선 재구성이 너비 우선 재구성보다 선호되지만 큰 차이는 아니라고 결론지었습니다. 데이터 구조의 토폴로지에는 유용한 지역성 정보가 있지만, 어떤 합리적인 순회든 데이터를 구성하는 데 괜찮은 일을 할 것입니다. 너비 우선과 깊이 우선 순회 모두 무작위 재구성보다 극적으로 우수합니다.

Wilson 등은 Lisp 시스템에 대해 비슷한 연구를 수행했고, 순회 알고리즘이 상당한 차이를 만들 수 있음을 보였습니다. 하지만 그 실험에서 가장 중요한 차이는 순회 알고리즘 자체 간의 차이가 아니라 큰 해시 테이블이 어떻게 처리되는지였습니다. 시스템 데이터는 종종 전역 네임스페이스나 패키지 같은 큰 변수 바인딩 환경을 구현하는 해시 테이블에 저장됩니다. 해시 테이블은 항목을 의사 무작위 순서로 저장하며, 이는 복사 컬렉터가 의사 무작위 방식으로 데이터 구조에 도달하고 복사하게 만들 수 있습니다. 이는 지역성을 크게 감소시키지만, 해시 테이블을 특별히 처리함으로써 쉽게 피할 수 있습니다. (한 기법은 항목이 만들어지는 순서를 기록하거나 다른 비-무작위 순서를 부여하도록 해시 테이블의 구조를 수정한 다음, 이 정보를 사용하여 항목 검사 순서를 정하도록 컬렉터를 수정하는 것입니다. 다른 기법은 해시 테이블을 순서가 있는 항목 배열로의 간접 인덱스로 만드는 것입니다. 이는 컬렉터를 수정하지 않고도 구현될 수 있어 사용자 정의 테이블 구조에 사용될 수 있다는 장점이 있습니다.)

해시 테이블이 적절히 처리되면, 데이터 구조를 계층적으로 클러스터링하는 알고리즘을 사용하여 추가 지역성 이득을 얻을 수 있습니다. Symbolics Lisp Machine 시스템에 대해서도 D.L Andre의 석사 논문에서 비슷한 결과가 보고되었습니다. 그 실험들이 특별히 잘 통제되지는 않았지만, 결과는 놀랍도록 긍정적이었으며, 이는 크고 상업적인 시스템에 대해 얻어진 결과이기 때문에 특히 중요합니다.

동적 재구성

1980년에 White는 가비지 컬렉션이 오랜 기간 연기되지만 Baker의 읽기 배리어 증분 복사기가 지역성 효과를 위해 데이터를 복사할 수 있도록 활성화되는 시스템을 제안했습니다. 목표는 빈 공간을 회수하는 것이 아니라 단순히 활성 데이터를 클러스터링하여 빠른 메모리에 유지될 수 있도록 하는 것이었습니다. 이 방식의 한 가지 흥미로운 속성은 뮤테이터가 접근하는 순서대로 데이터를 재구성하며, 이후 접근 패턴이 비슷하다면 지역성을 크게 향상시켜야 한다는 것입니다.

이 방식은 원래 형태로는 비실용적이지만(메모리가 회수되지 않으면 가비지의 순수한 양이 일반적인 디스크의 쓰기 대역폭을 압도할 것이기 때문에), 같은 기본 아이디어가 Texas Instruments Explorer Lisp Machines의 가비지 컬렉터에 통합되었습니다. 이 컬렉터는 가비지 컬렉션 주기가 끝날 때까지 철저한 백그라운드 스캐빈징 수행을 피하여, 객체가 뮤테이터에 의해 먼저 도달되고 지역성을 향상시키는 순서로 복사될 가능성을 높입니다.

비슷한 접근법이 University of Manchester의 MUSHROOM 프로젝트에서 시뮬레이션에 사용되었습니다. 하지만 가비지 컬렉터에 의존하는 대신, 이 시스템은 캐시 미스에 의해 트리거됩니다. 따라서 프로그램과 가비지 컬렉터 간의 상호작용보다는 프로그램의 지역성 특성에 더 직접적으로 반응할 수 있습니다.

불행히도 이러한 방식들은 가치가 있으려면 특수화된 하드웨어에 의존합니다. Explorer 시스템은 Baker 스타일 읽기 배리어에 대한 Lisp 머신의 하드웨어 지원을 활용하고, MUSHROOM 시스템은 새로운 “객체지향” 아키텍처를 기반으로 합니다.

Wilson은 이러한 기법들을 적응형 프리페칭의 한 형태로 보고, 메모리가 계속 커짐에 따라 이러한 세밀한 재구성이 과도할 수 있다고 주장합니다. 더 큰 디스크 전송 단위 내에서 가상 메모리 페이지의 재구성이 일반 하드웨어에서 좋은 결과를 낼 수 있습니다. 이는 Smalltalk용 LOOM 객체지향 가상 메모리의 데이터에 의해 뒷받침되는데, 세밀한 캐싱 전략이 주로 메모리가 매우 작을 때 도움이 된다는 것을 보여줍니다. 메모리가 커질수록 최적의 캐싱 단위도 커지며, 페이지 단위 방식이 객체 단위 방식만큼 대략 잘 작동하는 경향이 있습니다. Wilson은 또한 세밀한 재구성으로 인한 개선이 주로 비교에 사용된 정적 그래프 알고리즘의 결함 - 특히 큰 해시 테이블의 처리 - 때문일 수 있다고 주장합니다. 하지만 Llames는 루트가 적절히 처리되고 좋은 백그라운드 스캐빈징 순회가 사용된 후에도 동적 재구성이 지역성을 크게 향상시킬 수 있다고 보고했습니다.

페이징과의 조정

여러 시스템이 페이징 성능을 향상시키기 위해 가비지 컬렉터를 가상 메모리 시스템과 조정했습니다.

Symbolics Lisp 머신은 아마도 가비지 컬렉션과 가상 메모리의 가장 포괄적인 조정을 가졌을 것입니다. Symbolics 할당자는 페이지가 더 이상 유용한 데이터를 포함하지 않을 때 가상 메모리 시스템에 알릴 수 있었고, 페이지가 처음 접근될 때 이전(가비지) 내용을 메모리로 페이징하지 않고 가상 메모리 페이지를 할당할 수 있었습니다.

가상 메모리 협력은 세대 간 포인터 기록 메커니즘에도 사용되었습니다. 더 젊은 세대로의 포인터를 담고 있는 페이지를 페이징 아웃하기 전에, 페이지가 스캔되고 세대 간 포인터가 발견되었습니다. 이를 통해 가비지 컬렉터가 더 젊은 세대로의 포인터를 스캔하기 위해 데이터를 페이징하는 것을 피할 수 있었습니다. 가상 메모리 매핑 기법은 큰 객체의 복사를 최적화하는 데도 사용되었습니다 - 큰 객체 내의 데이터를 실제로 복사하는 대신, 데이터를 담고 있는 페이지를 단순히 이전 가상 주소 범위에서 매핑 해제하고 새 범위로 매핑할 수 있었습니다.

최근에는 마이크로커널 운영체제가 실제로 커널을 수정하지 않고도 가상 메모리 정책을 수정할 수 있는 능력을 제공했습니다. 커널은 전체 페이징 정책을 커널 자체에 하드코딩하는 대신 프로세스의 페이징을 제어하기 위해 사용자 지정 루틴을 호출합니다. 예를 들어 Mach 시스템에서는 외부 페이저 프로세스를 사용하여 페이징 활동을 제어할 수 있습니다. 이 기능은 Symbolics 시스템에서 사용된 것과 유사한 방식으로 Standard ML of New Jersey의 페이징을 줄이는 데 사용되었습니다.

추가 배경지식

1. Baker의 증분 가비지 컬렉터 (1978)

Henry Baker가 제안한 실시간 가비지 컬렉션 알고리즘으로, “읽기 배리어(read barrier)”를 사용하여 프로그램 실행과 가비지 컬렉션을 동시에 수행합니다. 프로그램이 객체를 읽을 때마다 그 객체가 새 공간으로 복사되었는지 확인하고, 필요하면 복사합니다. 이는 긴 중단 시간 없이 메모리를 회수할 수 있게 해주었으며, 현대 실시간 시스템의 기초가 되었습니다. 오늘날 Go 언어의 가비지 컬렉터도 비슷한 동시성 원리를 사용합니다.

2. 세대별 가비지 컬렉션의 탄생

1980년대 초 David Ungar가 Berkeley Smalltalk에서 개발한 세대별 가비지 컬렉션은 “대부분의 객체는 젊어서 죽는다(most objects die young)”는 관찰에 기반합니다. 이 아이디어는 현대 거의 모든 주류 언어(Java의 HotSpot VM, .NET CLR, Python, JavaScript V8 엔진 등)의 가비지 컬렉터에 채택되었습니다. 젊은 세대를 자주 수집하고 오래된 세대를 드물게 수집함으로써 전체 성능을 크게 향상시켰습니다.

3. 현대 언어의 지역성 최적화 사례

Java의 G1GC와 ZGC: G1(Garbage First)은 힙을 여러 리전으로 나누고 가비지가 많은 리전을 우선 수집하여 지역성을 개선합니다. ZGC는 컬러드 포인터(colored pointers)를 사용해 읽기 배리어 오버헤드를 줄이면서도 동시 컬렉션을 수행합니다.
Rust의 소유권 시스템: 가비지 컬렉션 대신 컴파일 타임에 메모리 안전성을 보장하는 완전히 다른 접근법입니다. 스택 할당을 최대한 활용하여 자연스럽게 뛰어난 캐시 지역성을 얻습니다.
Go의 저지연 GC: Go 1.5 이후 동시 마크-스윕 컬렉터를 사용하며, 쓰기 배리어를 최적화하여 지연 시간을 밀리초 이하로 유지합니다.