저수준 구현 이슈
지금까지 우리는 주로 가비지 컬렉터 설계의 기본 이슈들과 성능 트레이드오프를 살펴봤어요. 하지만 이런 주요 고려사항 외에도, 가비지 컬렉터 설계자는 시스템의 최종 성능과 다른 시스템 컴포넌트들과의 통합 용이성에 큰 영향을 미칠 수 있는 여러 설계 선택지들을 마주하게 됩니다. 이번 섹션에서는 이러한 저수준 구현 문제들을 좀 더 자세히 살펴볼게요.
포인터 태그와 객체 헤더
이 논문의 대부분에서 우리는 포인터에 작은 태그가 붙어있고, 포인터가 가리키는 객체들은 더 구체적인 타입 정보를 인코딩하는 헤더 필드를 가지고 있다고 가정했어요. 이 구체적인 타입 정보를 통해 객체의 레이아웃을 파악할 수 있고, 내장된 포인터 필드들의 위치도 알 수 있죠. 이건 Lisp이나 Smalltalk 같은 동적 타입 언어에서 가장 흔한 방식입니다. 이런 언어들에서는 객체들이 주로 두 가지 범주로 나뉘는데요: 머신 워드 내에 태그된 즉시값(immediate value)으로 저장될 수 있는 객체들과, 힙에 할당되어 포인터를 통해 참조되는 객체들이 그것이에요. 힙에 할당된 객체들은 다시 두 범주로 나뉘곤 합니다: 컬렉터가 포인터를 찾기 위해 검사해야 하는 태그된 값들(즉시값과 포인터)만 포함하는 것과, 가비지 컬렉터가 무시할 수 있는 비포인터 필드만 포함하는 것이죠.
또 다른 방법은 각 필드가 객체(작은 즉시값인 경우)나 포인터와 상세한 타입 정보를 모두 담는 거예요. 이 경우 일반적으로 필드가 두 워드가 필요한데요 - 하나는 원시 포인터나 원시 즉시값을 담을 만큼 충분히 길어야 하고, 다른 하나는 시스템의 모든 타입을 인코딩할 만큼 긴 비트 패턴을 담아야 해요. 보통 후자의 필드에도 전체 워드를 사용하는데, 로드와 스토어 연산의 정렬 제약 때문이에요. (많은 아키텍처에서 일반적인 로드와 스토어는 워드 경계에 정렬되어야 하고, 다른 아키텍처들에서는 정렬되지 않은 접근에 시간 패널티가 있거든요.) 공간 낭비가 있긴 하지만, 이 방식은 특히 넓은 버스를 가진 아키텍처에서 매력적일 수 있어요.
정적 타입 시스템을 가진 언어의 경우, 또 다른 가능성은 모든 객체가 헤더를 가지고 포인터 필드에는 태그가 없는 거예요. 이 방식은 즉시값이 포인터와 같은 필드에 저장될 수 없도록 보장하는 정적 타입 시스템이 필요한데요 - 만약 그럴 수 있다면, 둘을 구분하기 위한 태그가 필요하니까요. 객체의 어느 필드가 포인터를 포함할 수 있는지만 알아도 충분해요. 가리켜진 객체들이 자신의 구조를 디코딩할 헤더를 가지고 있다면 말이죠. 일부 동적 타입 시스템도 이런 표현을 사용하면서 워드 내의 즉시값을 피하는데요 - 심지어 짧은 정수도 헤더를 가진 객체로 표현되죠. (이 방식은 일반적으로 대부분의 정수 힙 할당을 최적화하기 위한 영리한 구현 전략이 필요해요.)
엄격한 정적 타입을 사용한다면, 헤더조차 생략할 수 있어요 - 포인터 필드를 찾고 포인터의 타입을 알면, 그것이 가리키는 객체의 타입은 자명하니까요. 추적 순회를 허용하려면, 루트 포인터들(예: 활성화 스택의 지역 변수)의 타입만 알면 돼요. 이건 나중에 설명할 몇 가지 방법으로 달성할 수 있어요. 거기서부터 참조 대상들의 타입을 결정할 수 있고, 따라서 그들의 참조 대상들의 포인터 필드도 알 수 있고, 이런 식으로 계속 이어지죠. 그래도 정적 타입을 가진 일부 시스템은 객체에 헤더를 달아요. 비용이 그리 크지 않고 구현의 일부 측면을 단순화하기 때문이죠. (예를 들어, 세대별 수집을 위해 페이지 마킹이나 카드 마킹을 사용한다면, 헤더가 있으면 페이지 스캔이 훨씬 간단해져요.)
태그와 포인터 스킴의 선택은 보통 가비지 컬렉션을 어느 정도 고려해서 이뤄지지만, 가장 중요한 건 일반적인 프로그램 연산의 효율성을 높이는 거예요. 태깅 스킴은 주로 타입 디스패칭, 산술 연산, 포인터 역참조를 최대한 빠르게 만들기 위해 선택되는데요. 어떤 스킴이 최선인지는 언어 시맨틱스와 가장 빈번한 연산들을 빠르게 만드는 전략에 크게 좌우돼요.
어떤 시스템에서는 개별 객체들이 헤더를 갖지 않고, 타입 정보가 특정 타입의 객체들을 별도의 페이지 세트로 분리함으로써 인코딩돼요. 이 “큰 페이지 묶음(big bag of pages)” 또는 BiBOP 기법은 타입을 페이지와 연관시키고, 할당자가 적절한 페이지에 객체를 할당하도록 제약해요. 타입 테스트는 포인터를 마스킹하고 시프트해서 페이지 번호를 도출하고, 테이블 조회로 그 페이지의 객체들에 대한 타입 디스크립터를 찾는 방식이에요. BiBOP 인코딩은 페이지당 하나의 태그로 많은 객체의 타입을 인코딩할 수 있게 해서 공간을 절약할 수 있어요.
전통적인 태깅 스킴의 또 다른 변형은 객체에 직접 헤더를 붙이지 않고 병렬 배열에 저장하는 거예요. 이 방식은 일반적인 프로그램 동작에 관련된 데이터와 컬렉터 및 할당자에만 관심 있는 데이터를 분리해서 참조 지역성(locality of reference) 측면에서 장점이 있을 수 있어요.
보수적 포인터 찾기
언어 구현의 다른 측면들을 고려하는 극단적인 경우는 보수적 포인터 찾기(conservative pointer-finding)인데요. 이건 런타임 타입 식별이나 가비지 컬렉션을 전혀 지원하지 않는 컴파일러들을 다루기 위한 전략이에요. (이 기법들은 주로 Boehm과 그의 동료들과 연관되어 있는데, 그들이 이를 높은 수준으로 발전시켰지만, 비슷한 기법이 교토 커먼 리스프(Kyoto Common Lisp) 시스템이나 다른 곳에서 더 일찍 사용된 것으로 보여요.) 이런 시스템에서 컬렉터는 포인터일 수도 있는 모든 것을 포인터로 취급해요 - 예를 들어, 힙의 객체 주소가 될 수 있는 적절히 정렬된 비트 패턴 같은 거죠. 컬렉터가 같은 비트 패턴을 가진 정수 같은 다른 값들을 포인터로 착각해서 불필요하게 객체를 유지할 수도 있지만, 이런 실수의 확률을 매우 낮게 만드는 여러 기법들을 사용할 수 있어요. 놀랍게도, 이 기법들은 충분히 효과적이어서 대부분의 C 프로그램들을 거의 또는 전혀 수정 없이 꽤 효율적으로 가비지 컬렉션할 수 있어요. 이렇게 하면 가비지 컬렉션을 염두에 두지 않고 작성된 프로그램들과, 일부가 협력적이지 않은 여러 언어로 작성된 프로그램들의 가비지 컬렉션이 단순해져요.
이런 컬렉터를 세대별로 만들려면 특별한 기법이 필요한데요. 세대 간 포인터를 감지하는 쓰기 배리어를 구현하는 데 컴파일러의 협력이 부족하기 때문이에요. 가상 메모리 더티 비트나 접근 보호 트랩을 사용해서 어느 페이지가 쓰여졌는지 감지할 수 있고, 그래서 수집 시점에 그것들을 스캔해서 더 어린 세대로의 포인터를 감지할 수 있어요.
보수적 포인터 찾기는 가비지 컬렉터에 추가 제약을 부과해요. 특히, 컬렉터가 객체를 이동시키고 포인터를 업데이트할 자유가 없어요. 비포인터가 포인터로 착각되어 잘못 업데이트될 수 있기 때문이죠. 이렇게 되면 정수나 문자열 같은 비포인터 데이터에 불가사의하고 예측 불가능한 변경이 일어날 수 있어요. 그래서 보수적 컬렉터들은 직관적인 복사 순회 알고리즘을 사용할 수 없어요.
보수적 포인터 찾기는 부분적으로만 협력적인 언어 구현들을 다루기 위해 다른 기법들과 결합될 수 있어요. 예를 들어, Bartlett와 Detlefs의 “대부분-복사(mostly-copying)” 컬렉터들은 힙의 객체 필드를 디코딩하기 위해 헤더를 사용하지만, 활성화 스택에서 포인터를 찾는 데는 보수적 기법에 의존해요. 이 방식은 대부분의 (하지만 전부는 아닌) 객체들을 재배치하고 압축하는 복사 기법을 지원해요. 스택에서 가리켜진다고 보수적으로 식별된 객체들은 제자리에 “고정”되어 이동할 수 없어요.
보수적 스택 스캐닝과 더 정확한 힙 추적의 선택은 종종 합리적인데요. 일반적으로 컴파일러를 수정해서 스택 프레임 형식을 디코딩 가능하게 만드는 것보다 언어에 객체 헤더를 추가하는 게 더 쉽기 때문이에요. 헤더는 힙 할당 루틴으로 객체에 추가할 수 있는데, 이건 종종 쉽게 변경하거나 대체할 수 있는 라이브러리 루틴일 뿐이거든요. 컴파일러들은 종종 디버깅 목적으로 레코드 레이아웃을 디코딩하기에 충분한 정보를 기록하는데, 그 정보를 캡처해서 힙 할당 객체들을 위한 런타임 타입 식별로 가공할 수 있어요.
보수적 포인터 찾기는 포인터를 정수로 캐스팅하고, 원래 포인터를 파괴하고, 정수 값에 임의의 산술 연산을 수행하는 능력 같은 언어 수준 기능들에 의해 무력화될 수 있어요. 원래 값이 복원되어 다시 포인터로 캐스팅되면, 참조된 객체가 더 이상 존재하지 않을 수 있어요 - 가비지 컬렉터가 정수 값이 포인터 값으로 봐도 객체를 “가리킨다”는 걸 알 수 없어서 객체를 회수했을 수도 있거든요. 다행히 대부분의 프로그램은 이런 연산 순서를 수행하지 않아요 - 포인터를 정수로 캐스팅할 수는 있지만, 원래 포인터가 여전히 존재할 가능성이 높고, 따라서 객체는 유지될 거예요.
컴파일러 최적화도 포인터에 비슷한 연산을 수행할 수 있는데, 이건 안타깝게도 프로그래머가 피하기 더 어려워요 - 컴파일러가 포인터 표현식에 대수적 변환을 사용해서 포인터를 감출 수도 있고, 포인터의 서브워드 부분들에 연산을 수행해서 포인터 상태에 일시적인 불일치를 만들 수도 있거든요. 대부분의 컴파일러가 이런 최적화를 자주 수행하지는 않지만, 발생하긴 하고, 일부 컴파일러는 정기적으로 해요. 대부분의 컴파일러에서는 이런 포인터 훼손 최적화를 피하기 위해 최고 수준의 최적화를 끄는 것으로 충분하지만, 이건 컴파일러마다 신뢰할 수 없고, 일반적으로 놓친 최적화 때문에 런타임 효율성에서 몇 퍼센트의 비용이 들어요. 대부분의 컴파일러가 가비지 컬렉터에 문제가 되는 최적화만 선택적으로 끄는 기능을 제공하지 않기 때문에, 일반적으로 여러 최적화, 즉 “고급” 최적화를 꺼야 해요. 이 문제를 피하기 위해, 가비지 컬렉터 설계자들은 컴파일러가 가비지 컬렉션이 가능하도록 보존할 수 있는 제약 세트를 제안했는데요. 이런 제약들은 기존 컴파일러에 큰 변경을 요구하지 않아요.
마찬가지로, C++ 프로그래머들이 올바른 가비지 컬렉션을 불가능하게 만드는 구조를 피하도록 하는 프로그래밍 가이드라인도 제안되었어요. 약간 제한된 C++의 부분집합으로 프로그래밍함으로써, 협력적인 컴파일러가 올바른 가비지 컬렉션을 지원할 수 있도록 보장할 수 있어요. 약간 더 제한된 (“안전한”) C++ 부분집합을 사용하면, 버그가 있는 프로그램조차 기본 메모리 추상화를 깨뜨리지 않고 진단하기 어려운 에러를 발생시키지 않도록 보장할 수 있어요.
일부 사람들은 보수적 포인터 찾기 기법이 “올바르지” 않은 것으로 알려져 있기 때문에 반대하는데요 - 예를 들어, 정수가 포인터로 착각되어 쓰레기가 유지될 수 있거든요. 최악의 경우, 이로 인해 상당한 쓰레기가 회수되지 않을 수 있고, 프로그램이 메모리를 단순히 소진해서 크래시할 수도 있어요. 보수적 포인터 찾기 옹호자들은 이런 일의 발생 확률을 매우 낮게 만들 수 있고, 이런 에러가 명시적 힙 관리에서 프로그래머의 실수로 인한 치명적 에러보다 훨씬 덜 일어날 가능성이 있다고 반박해요. 따라서 실제로 “올바르지 않은” 기법을 사용하는 게 프로그래머들이 더 올바르지 않은 프로그램을 작성하는 것보다 나을 수 있어요. 장기적으로, 보수적 포인터 찾기가 가비지 컬렉션을 널리 사용 가능하게 만들고, 일단 널리 사용되면 컴파일러 벤더들이 더 정확한 기법을 위한 어느 정도의 지원을 제공할 거라는 게 희망이에요.
언어 지원과 스마트 포인터
기존 시스템에 가비지 컬렉션을 추가하는 또 다른 접근법은 언어가 제공하는 확장 기능을 사용해서 언어 자체 내에서 가비지 컬렉션을 구현하는 거예요. 가장 흔한 형태는 가비지 컬렉터 제약을 보존하는 제한된 접근 함수 세트를 가진 특별한 가비지 컬렉션 데이터 타입 세트를 구현하는 거예요. 예를 들어, 참조 카운팅 데이터 타입을 구현하고, 대입을 수행하기 위해 접근자 함수(또는 매크로)를 사용할 수 있는데요 - 접근자 함수들은 실제 대입을 수행하는 것과 더불어 참조 카운트를 유지해요.
좀 더 우아한 접근법은 연산자 오버로딩 같은 확장 메커니즘을 사용해서 일반적인 프로그램 연산자들을 가비지 컬렉션 타입에 사용할 수 있게 하는 거예요. 컴파일러가 주어진 피연산자에 대해 적절한 사용자 정의 연산을 자동으로 선택하도록 하는 거죠. C++에서는 가비지 컬렉션 가능한 클래스와 함께 사용할 수 있는 “스마트 포인터” 클래스를 정의하는 게 일반적인데요. 포인터 조작 연산(예: *와 ->)과 컬렉션 가능한 객체에 대한 주소 가져오기 연산(&)에 대해 적절히 정의된 의미를 가지도록 해요. 안타깝게도, 이런 사용자 정의 포인터 타입들은 여러 이유로 내장 포인터 타입과 정확히 같은 방식으로 사용될 수 없어요. 한 가지 이유는 컴파일러가 내장 타입에 대해 자동으로 수행하는 모든 자동 강제 변환을 정의할 방법이 없기 때문이에요. 또 다른 문제는 모든 연산자가 이런 식으로 오버로드될 수 없다는 거예요. C++는 대부분을 제공하지만, 가비지 컬렉션을 언어에 우아하게 통합하는 데 필요한 확장성을 전부 제공하지는 않아요. (Ada에서는 오버로딩 시스템이 더 강력하고 내장 포인터 타입이 에뮬레이트해야 하는 미묘함이 덜해서 더 쉬운 것 같아요.) 또 다른 제한은 내장 클래스에 대한 연산을 재정의하는 게 불가능해서 언어의 기존 부분을 향상시키기 어렵다는 거예요 - 사용자 정의 타입만 우아하게 가비지 컬렉션될 수 있어요.
또 다른 제한은 가비지 컬렉션을 언어 내에서 효율적으로 구현하기 어렵다는 건데요. 특정 중요한 특수 케이스에 대해 컴파일하는 방법을 컴파일러에게 알려줄 수 없기 때문이에요. 예를 들어, C++나 Ada에서는 컴파일 시점에 힙에 할당되지 않은 것으로 알려진 객체에 대한 연산을 특화할 방법이 없어요. (C++ 용어로는, 연산자가 인수의 타입에 대해서만 특화될 수 있고, 인수의 스토리지 클래스에 대해서는 할 수 없어요.)
반영적(reflective) 시스템에 관한 최근 연구는 매우 강력하고 규칙적인 확장 메커니즘을 가진 언어들을 탐구했는데요. 기존 언어 기능의 효율적인 재구현을 허용하기 위해 일부 기저 구현을 노출하는 거예요. 대부분의 기존 반영적 언어들은 기본 언어의 일부로 가비지 컬렉션을 제공하지만, 작고 강력한 반영적 언어 내에서 가비지 컬렉션을 구현하는 걸 상상할 수 있어요. 그러나 모든 반영적 시스템에서처럼, 기본 언어 구현자의 선택을 제한하지 않기 위해 가장 중요한 저수준 이슈만 노출하는 게 중요한데요. 이건 활발한 연구 영역이에요.
컴파일러 협력과 최적화
모든 가비지 컬렉션 시스템에서 가비지 컬렉터와 시스템의 나머지 부분(인터프리터나 컴파일된 코드) 모두가 사용하는 규약 세트가 있어야 해요. 가비지 컬렉터가 객체와 포인터를 인식할 수 있도록 보장하기 위해서죠. 보수적 포인터 찾기 시스템에서는 컴파일러와 컬렉터 사이의 “계약”이 정말 약하긴 하지만, 여전히 존재해요 - 컴파일러가 컬렉터를 무력화할 수 있는 이상한 최적화를 피한다면 말이죠. 대부분의 시스템에서 컴파일러는 훨씬 더 협력적이어서, 컬렉터가 스택과 레지스터에서 포인터를 찾을 수 있도록 보장해요.
GC-언제나 vs. 안전점 수집
일반적으로, 컬렉터와 실행 중인 코드 사이의 계약은 우리가 gc-언제나(gc-anytime)와 안전점(safe-points) 전략이라고 부르는 두 가지 형태 중 하나를 취해요. gc-언제나 시스템에서는, 컴파일러가 실행 중인 코드가 어느 시점에든 중단될 수 있고 가비지 컬렉션을 수행하는 게 안전하도록 보장해요 - 현재 활성화된 모든 포인터 변수를 찾기 위한 정보가 제공되고, 그것들의 형식을 디코딩해서 도달 가능한 객체들을 찾을 수 있어요.
안전점 시스템에서는, 컴파일러가 프로그램 실행 중 특정 선택된 지점들에서만 가비지 컬렉션이 가능하도록 보장하고, 이 지점들이 꽤 자주 그리고 규칙적으로 발생하도록 해요. 많은 시스템에서 프로시저 호출과 역방향 분기가 안전점이 되도록 보장되는데요. 프로그램이 안전점에 도달하지 않고 무한히 루프(또는 재귀)할 수 없도록 보장하는 거예요 - 안전점들 사이의 가능한 최장 시간은 어떤 프로시저든 호출하지 않는 가장 긴 순방향 경로를 취하는 시간이에요. (필요하다면 중간 안전점을 도입해서 더 세밀한 반응성을 보장할 수 있어요.)
안전점 스킴의 장점은 컴파일러가 안전점들 사이의 안전하지 않은 영역 내에서 임의로 복잡한 최적화를 자유롭게 사용할 수 있고, 포인터 값을 찾고 역최적화하는 것을 가능하게 하는 데 필요한 정보를 기록할 의무가 없다는 거예요. (이건 특히 C 같은 고급 언어를 중간 언어로 사용할 때 중요한데, C 컴파일러가 포인터를 감추는 최적화를 사용하는 걸 막는 게 바람직하지 않거나 불가능할 때 그래요.) 안전점 스킴의 한 가지 단점은 경량 프로세스(스레드)의 구현 전략을 제한한다는 거예요. 같은 가비지 컬렉션 힙에서 여러 제어 스레드가 동시에 실행되고 있고, 한 스레드가 가비지 컬렉션을 강제하면, 컬렉션은 모든 스레드가 안전점에 도달하고 멈출 때까지 기다려야 해요.
이 스킴의 한 구현은 안전점들 사이에서 하드웨어 인터럽트를 마스킹하는 거예요. 더 흔한 방법은 언제든 실제 저수준 인터럽트를 처리할 수 있는 작은 루틴을 제공하는데, 그것에 대한 기본 정보를 기록하고, 플래그를 설정하고, 정상 실행을 재개하는 거예요. 컴파일된 코드는 각 안전점에서 플래그를 확인하고, 설정되어 있으면 고급 인터럽트 핸들러로 디스패치해요. 이렇게 하면 실제 머신 인터럽트에서 어느 정도 격리되고 약간 더 긴 지연 시간을 가진 높은 수준의 인터럽트 개념이 도입돼요.
안전점이든 gc-언제나 전략이든, 가비지 컬렉션을 위해 포인터를 식별할 수 있도록 보장하는 많은 가능한 규약이 있어요. 하지만 안전점 시스템에서는 컴파일러가 안전점들 사이에서 규약을 자유롭게 위반할 수 있어요.
분할된 레지스터 세트 vs. 변수 표현 기록
많은 시스템에서 컴파일러는 어느 레지스터를 어떤 종류의 값을 담는 데 사용할 수 있는지에 대한 간단한 규약을 준수해요. 예를 들어, T 시스템(Orbit 컴파일러 사용)에서는 일부 레지스터는 태그된 값에만 사용되고, 다른 것들은 원시 비포인터 값에만 사용돼요. 포인터는 일반적인 형식으로 가정되는데 - 객체 내의 알려진 오프셋에 대한 직접 포인터에 태그가 더해진 거예요. 따라서 헤더는 간단한 인덱스 로드 명령어로 가리켜진 객체에서 추출될 수 있어요.
다른 레지스터 세트 분할과 규약도 가능해요. 예를 들어, 원시 포인터를 담는 레지스터를 가질 수 있는데, 아마도 객체 내 어디든 가리키는 포인터일 수 있고, 컬렉터가 정렬 제약을 사용해서 그것들로부터 객체의 헤더를 도출할 수 있도록 하면 돼요. 비복사 컬렉터를 사용한다면, “추적되지 않은” 레지스터가 최적화된 포인터(대수적 변환으로 인해 실제로 객체 내를 가리키지 않을 수도 있는)를 담도록 허용할 수 있어요. 같은 객체에 대한 최적화되지 않은 포인터가 알려진 형식으로 “추적된” 레지스터에 있기만 하면 돼요.
분할된 레지스터 세트의 주요 문제는 컴파일러가 사용 가능한 레지스터 중 어디에든 프로그램 변수와 임시 변수를 할당할 자유를 줄인다는 거예요. 일부 코드 시퀀스는 여러 포인터 레지스터와 매우 적은 비포인터 레지스터를 필요로 할 수 있고, 다른 코드 시퀀스는 그 반대를 필요로 할 수 있어요. 이렇게 되면 더 많은 변수가 “유출”되어야 한다는 뜻인데요. 즉, 레지스터 대신 스택이나 힙에 할당되어야 하고, 코드가 더 느리게 실행될 거예요.
분할된 레지스터 세트의 대안은 컴파일러에게 레지스터 사용에 더 많은 자유를 주되, 가비지 컬렉터에게 더 많은 정보를 전달하도록 요구하는 거예요 - 즉, 포인터가 어디에 있고 그것들을 어떻게 적절히 해석할지 알려주는 거죠. 우리는 이 전략을 변수 표현 기록이라고 부르는데요. 컴파일러가 어느 레지스터(또는 스택 변수)가 포인터를 담고 있는지, 그리고 최적화로 포인터가 변환되었다면 객체의 주소를 어떻게 복구할지에 대한 결정을 기록해야 하기 때문이에요. 포인터 변수 표현이 다른 명령어 범위마다, 컴파일러는 주석을 생성해야 해요. 이 정보는 최적화된 코드를 디버깅하는 데 필요한 것과 비슷한데, 대부분의 최적화가 적은 오버헤드로 지원될 수 있어요. 하지만 이 추가 정보(기본적으로 실행 가능한 코드에 주석을 다는)를 위한 공간 요구사항은 무시할 수 없을 수 있고, 일부 경우에는 컴파일러의 코드 생성 전략을 약간 변경하는 게 바람직할 수 있어요.
가비지 컬렉션 자체의 최적화
가비지 컬렉터들이 컴파일러 및 그것의 최적화와의 관계로 제약받을 수 있는 반면, 컴파일러가 가비지 컬렉터를 효율적으로 만드는 데 도움을 줄 수도 있어요. 예를 들어, 최적화 컴파일러는 불필요하거나 중복된 읽기 또는 쓰기 배리어 연산을 최적화하거나, 힙 객체가 안전하게 스택에 할당될 수 있다는 걸 감지할 수 있어요.
대부분의 세대별 및 증분 알고리즘에서 쓰기 배리어는 포인터가 저장될 때만 필요하지만, 컴파일 시점에 값이 포인터인지 아닌지 명확하지 않을 수 있어요. 동적 타입 언어에서는 변수가 포인터 또는 비포인터 값을 가질 수 있고, 심지어 정적 타입 언어에서도 포인터 변수에 널 값이 할당될 수 있어요. 컴파일러는 데이터 흐름 분석을 수행해서 더 많은 비포인터 대입 연산에 대해 쓰기 배리어를 생략할 수 있게 해줄 수 있어요. 미래에는 Self 컴파일러에서 사용되는 것과 같은 고급 타입 흐름 분석이 읽기 및 쓰기 배리어 최적화에 더 큰 기회를 제공할 수 있어요.
컴파일러는 쓰기 배리어가 같은 포인터를 테스트하거나 같은 객체를 여러 번 마킹할 때 중복 검사나 마킹을 제거함으로써 도움을 줄 수도 있어요. (우리가 아는 한, 현재 어떤 컴파일러도 이걸 하지 않아요.) 하지만 이게 가능하려면, 최적화기가 특정 것들이 컴파일 시점에 명확하지 않은 방식으로 컬렉터에 의해 변경되지 않는다고 가정할 수 있어야 해요. 예를 들어, gc-언제나 컬렉터와 여러 제어 스레드가 있으면, 스레드가 언제든 선점될 수 있고, 스레드가 재개되기 전에 가비지 컬렉션이 발생할 수 있어요. 이런 시스템에서는 컬렉터가 연속된 두 명령어 사이에 호출될 수 있기 때문에 최적화 기회가 더 적어요. 하지만 안전점 시스템에서는, 최적화기가 가비지 컬렉션에 대해 원자적으로 실행되는 명령어 시퀀스에 걸쳐 더 많은 최적화를 수행할 수 있을 거예요.
여러 연구자들이 힙 할당 구조와 관련된 컴파일러 최적화를 조사했는데요. 잠재적인 앨리어싱을 감지하고, 프로그램의 특정 지점에서 쓰레기가 된다고 추론할 수 있을 때 힙 객체를 스택에 할당할 수 있도록 하기 위해서예요. Cha87은 전통적인 최적화와 가비지 컬렉션 사이의 상호작용, 그리고 가비지 컬렉션 지향 최적화가 안전한 때를 논의해요. 이런 주제들은 이 서베이의 범위를 넘어서고, 우리가 아는 한 실제 시스템이 이런 기법을 가비지 컬렉션 최적화에 사용하지는 않아요. 그래도 이런 기법들은 가비지 감지 작업의 대부분을 컴파일 시점으로 옮김으로써 가비지 컬렉터 성능에 중요한 개선을 가져올 수 있어요.
특정 제한된 형태의 수명 분석 - 지역 변수 바인딩 환경만을 위한 - 은 간단하지만 클로저를 가진 언어에서 대부분의 변수 바인딩을 힙에 할당할 필요를 피하는 데 효과적일 수 있어요.
자유 저장소 관리
비이동 컬렉터들은 해제된 공간이 메모리 전체에 분산되어 살아있는 객체들과 섞여 있다는 사실을 다뤄야 해요. 이를 다루는 전통적인 방법은 하나 이상의 자유 리스트를 사용하는 건데, 명시적으로 관리되는 힙을 위해 개발된 자유 저장소 관리 기법 중 어떤 것이든 적용할 수 있어요.
가장 간단한 스킴은 많은 초기 Lisp 인터프리터들에서 사용되었는데, 단 하나 크기의 힙 할당 객체만 지원하고, 단일 자유 리스트를 사용해서 해제된 항목들을 담는 거예요. 쓰레기가 감지되면(예: 스윕 단계 동안 또는 참조 카운트가 0이 될 때), 객체들은 단순히 리스트로 연결되는데, 일반 데이터 필드 중 하나를 사용해서 리스트 포인터를 담아요.
이 스킴을 여러 객체 크기를 지원하도록 일반화할 때, 두 가지 기본 선택이 가능해요: 각 객체 크기(또는 근사 객체 크기)에 대해 별도의 리스트를 유지하거나, 다양한 크기의 해제된 공간을 담는 단일 리스트를 유지하는 거예요. 다른 크기의 객체들에 대해 별도의 리스트를 가진 기법으로는 분리된 저장소(segregated storage)와 버디 시스템(buddy systems)이 있어요. 통합된 자유 리스트를 가진 시스템으로는 순차 적합(sequential fit) 방법과 비트맵 기법이 있어요. 중간 전략은 단일 데이터 구조를 사용하되, 자유 공간의 크기(및/또는 주소)로 정렬된 트리나 유사한 구조를 사용해서 검색 시간을 줄이는 거예요. 이런 시스템들과 여러 하이브리드는 이미 메모리 관리에 관한 문헌에 설명되어 있어서, 여기서는 설명하지 않을게요. 예외는 비트맵 메모리 관리인데, 여러 가비지 컬렉션에서 사용되었지만 보통 문헌에서 논의되지 않아요.
비트맵 메모리 관리는 단순히 메모리 단위(일반적으로 워드, 또는 객체가 항상 두 워드 경계에 정렬되면 워드 쌍)에 해당하는 비트맵을 유지하는데, 비트의 값은 그 단위가 사용 중인지 아닌지를 나타내요. 비트맵은 객체가 할당되거나 회수될 때 업데이트돼요. 비트맵을 스캔해서 자유 리스트를 구성하거나, 순차 적합 알고리즘에서 자유 리스트를 검색하는 것과 유사한 방식으로 할당 시점에 검색할 수 있어요.
힙 데이터의 압축 표현
힙 데이터의 표현은 종종 공간보다 속도에 최적화돼요. 예를 들어, 동적 타입 언어에서는 대부분의 객체의 대부분의 필드가 일반적으로 균일한 크기인데, 태그된 포인터를 담기에 충분히 커요. 포인터는 차례로 일반적으로 평탄한(비세그먼트화된) 주소 공간의 전체 크기 가상 주소로 표현돼요. 이 공간의 많은 부분이 어떤 의미에서는 “낭비”되는데요. 많은 비포인터 값이 더 적은 비트로 표현될 수 있고, 제한된 힙 크기와 참조 지역성 때문에 포인터가 일반적으로 매우 적은 정보를 포함하기 때문이에요.
적어도 두 가지 메커니즘이 데이터 구조의 규칙성을 활용해서 대부분의 경우 어느 정도 압축된 형태로 저장하고 조작될 때 필요에 따라 확장할 수 있도록 개발되었어요. 하나는 Lisp 콘스 셀 같은 리스트 셀에 특화된 cdr 코딩이라는 세밀한 메커니즘이에요. 다른 하나는 가상 메모리 페이지에서 작동하는 더 범용적인 메커니즘인 압축 페이징이에요. 두 메커니즘 모두 언어 수준에서는 보이지 않아요.
Cdr 코딩은 많은 초기 Lisp 시스템에서 사용되었는데, 랜덤 액세스 메모리가 매우 비쌌을 때였어요. 안타깝게도, CPU 시간 측면에서 꽤 비싼 경향이 있었는데요. 리스트의 변경 가능한 표현이 기본 리스트 연산을 복잡하게 만들기 때문이에요. CDR 같은 일반적인 연산은 순회하고 있는 리스트 셀이 어떤 종류인지 확인하기 위한 추가 명령어가 필요해요 - 일반 셀인가요, 아니면 압축된 셀인가요?
cdr 코딩 시스템에서 리스트의 압축된 표현은 실제로 원래 리스트의 항목들에 해당하는 항목들의 배열이에요. Cdr 코딩 시스템은 가비지 컬렉터와 함께 작동하는데, 가비지 컬렉터가 리스트를 선형화하고 연속된 항목들을 CAR 값(리스트 항목)을 담는 배열로 압축해요. CDR 값 - 리스트를 연결하는 포인터 - 은 생략돼요. 이게 작동하려면, CDR 값이 암묵적으로 메모리의 다음 항목에 대한 포인터라는 걸 말하는 비트를 어딘가에(예: CAR 값을 담는 필드의 태그에 특별한 추가 비트) 저장해야 해요. CDR 값에 대한 파괴적 업데이트는 필요에 따라 실제 콘스 셀을 생성하고, 배열의 선행 부분에서 참조를 전달해야 해요.
이 스킴은 Lisp 머신에서 발견되는 것과 같은 특수 하드웨어 및/또는 마이크로코드 루틴이 있을 때만 정말 가치가 있어요. 현재의 범용 프로세서에서는 얻을 수 있는 절약을 위한 시간이 거의 가치가 없어요. (Lisp 시스템의 데이터 중 대략 절반이 콘스 셀로 구성되어 있어서, 그것들을 두 워드에서 한 워드로 압축해도 기껏해야 약 25%만 절약할 수 있어요.)
더 최근에는, 압축 페이징이 일반 하드웨어에서 메모리 요구사항을 줄이는 수단으로 제안되었어요. 기본 아이디어는 메인 메모리의 일부를 압축된 형태로 페이지를 저장하는 데 할애해서, 하나의 메인 메모리 페이지가 여러 가상 메모리 페이지의 데이터를 담을 수 있도록 하는 거예요. 일반적인 가상 메모리 접근 보호 하드웨어를 사용해서 압축된 페이지에 대한 참조를 감지하고, 그것들을 압축 해제할 루틴으로 트랩해요. 일단 터치되면, 페이지는 잠시 동안 일반적인(압축되지 않은) 형태로 캐시되어, 프로그램이 그것을 조작할 수 있어요. 한동안 터치되지 않은 페이지는 재압축되고 접근 보호돼요. 압축 루틴은 CDR 필드를 압축하는 것에 국한되지 않아요 - 다른 포인터와 비포인터 데이터(예: 정수와 문자열, 또는 실행 가능한 코드)를 압축하도록 설계될 수 있어요.
사실상, 압축 페이징은 메모리 계층에 새로운 수준을 추가하는데, 비용 측면에서 일반적인 RAM과 디스크 사이에 위치해요. 이건 전체 RAM 요구사항을 줄일 뿐만 아니라 디스크 탐색 횟수를 줄여서 실제로 속도를 개선할 수 있어요. 간단하고 빠르지만 효과적인 압축 알고리즘을 사용하면, 힙 데이터는 일반적으로 2배에서 4배의 압축 비율을 가질 수 있는데 - 상대적으로 느린 프로세서에서도 디스크 탐색을 하는 데 걸리는 시간보다 훨씬 짧은 시간에요. 프로세서 속도 개선이 계속해서 디스크 속도 개선을 앞지르면서, 압축 페이징은 점점 더 매력적이 되고 있어요.
배경지식과 재미있는 히스토리
1. BiBOP와 Lisp 머신의 황금기
BiBOP(Big Bag of Pages) 기법은 1970-80년대 Lisp 머신 시대의 유산이에요. 당시 MIT와 Symbolics 같은 회사들은 Lisp을 위해 특별히 설계된 하드웨어를 만들었는데, 메모리가 지금보다 수백만 배 비쌌던 시절이라 모든 비트를 효율적으로 사용하는 게 생존의 문제였죠. 재미있게도, 이 기법들은 오늘날 모바일 기기나 임베디드 시스템처럼 메모리가 제한된 환경에서 다시 주목받고 있어요.
2. Hans Boehm의 보수적 GC - C에 가비지 컬렉션을 가져온 혁명
Hans Boehm이 개발한 보수적 가비지 컬렉터는 “가비지 컬렉션은 불가능하다”고 여겨졌던 C/C++ 언어에 GC를 가능하게 만든 획기적인 작업이었어요. 1988년에 처음 발표되었을 때 많은 사람들이 회의적이었지만, 지금은 Firefox, LLVM, 그리고 수많은 오픈소스 프로젝트에서 사용되고 있죠. Boehm 자신은 이를 “학계에서 가장 많이 인용되지 않은 널리 사용되는 소프트웨어”라고 농담했어요. 실제로 너무 잘 작동해서 사람들이 그냥 쓰고 논문은 잘 안 읽는다는 거죠!
3. 압축 페이징과 메모리 계층의 미래
압축 페이징은 컴퓨터 아키텍처의 흥미로운 트렌드를 보여줘요. CPU 속도는 무어의 법칙을 따라 빠르게 발전했지만, 디스크와 메모리 속도는 그에 훨씬 못 미쳐요. 1990년대에는 RAM 접근이 10ns, 디스크 탐색이 10ms 정도였는데, 그 차이가 백만 배였어요. 지금은 SSD가 나왔지만 여전히 수천 배 차이가 나죠. 그래서 CPU가 “쉬는 시간”에 데이터를 압축/해제하는 게 디스크를 기다리는 것보다 빠른 아이러니한 상황이 됐어요. 이건 마치 슈퍼마켓에서 줄을 서는 대신 집에서 요리하는 게 더 빠른 것과 비슷해요!