증분 가비지 컬렉션

증분 가비지 컬렉션은 안 쓰는 메모리를 치우는 일을 잘게 나눠, 프로그램이 도는 사이사이에 조금씩 해 나갑니다. 한 번에 길게 멈추는 대신 짧게 여러 번 멈춥니다. 화면이 끊기면 안 되는 게임이 이 방식을 자주 씁니다. 대신 치우는 도중에 바뀌는 참조를 따로 챙기는 비용이 붙습니다.

상세

집 청소를 떠올려 봅니다. 주말에 하루를 통째로 비워 대청소를 하면 그날은 다른 일을 못 합니다. 매일 저녁 10분씩 한 구역만 치우면 하루도 비우지 않고 집이 유지됩니다.

증분 가비지 컬렉션은 incremental garbage collection 을 옮긴 말입니다. 「점진적 가비지 컬렉션」이라고도 부릅니다. 증분은 「조금씩 늘려 간다」는 뜻입니다. 수집 일을 조금씩 진척시킨다는 데서 온 이름입니다.

가비지 컬렉션과 멈춤

가비지 컬렉션은 프로그램이 더는 닿을 수 없는 객체를 찾아 그 메모리를 돌려받는 일입니다. 이 일을 맡은 런타임 부품이 컬렉터입니다.

컬렉터는 대개 두 단계로 일합니다. 먼저 표시 단계입니다. 프로그램이 지금 손에 쥔 변수들에서 출발해 참조를 따라가며 닿는 객체에 표시를 붙입니다. 이 출발점들을 루트 집합이라고 합니다.

다음은 돌려받기 단계입니다. 객체들이 놓이는 메모리 구역이 힙입니다. 컬렉터는 힙을 훑으며 표시가 없는 객체의 메모리를 돌려받습니다. 표시하고(mark) 쓸어 낸다(sweep)는 두 단계를 묶어 마크 앤 스윕이라고 부릅니다.

가장 단순한 컬렉터는 이 두 단계를 하는 동안 프로그램을 전부 세웁니다. 이 멈춤을 가비지 컬렉션 정지라고 합니다. 세상을 멈춘다는 뜻에서 스톱 더 월드(stop-the-world)라고도 부릅니다.

몰아서 치울 때 멈춤이 길어지는 까닭

표시 단계는 살아 있는 객체를 하나하나 다 방문해야 끝납니다. 살아 있는 객체가 많을수록 멈춤도 그만큼 길어집니다. 힙이 커지면 한 번의 멈춤이 프로그램이 견딜 수 있는 한도를 넘기 쉽습니다.

게임에서 이 한도는 프레임 예산입니다. 1초에 화면을 60장 그리려면 한 장에 쓸 수 있는 시간은 60분의 1초입니다. 수집 한 번이 이 시간을 넘기면 그 장이 늦게 나와 화면이 툭 끊겨 보입니다.

서버에서는 같은 일이 응답 시간으로 드러납니다. 멈춘 동안 도착한 요청은 전부 기다립니다. 평균은 멀쩡한데 일부 요청만 유난히 늦는 꼬리 지연이 생깁니다.

일을 조각으로 나누기

증분 방식은 표시 단계를 한 번에 끝내지 않습니다. 객체를 정해진 수만큼만 훑고 멈춘 뒤 프로그램에게 실행을 돌려줍니다. 프로그램이 조금 돌고 나면 컬렉터가 다시 와서 다음 조각을 훑습니다.

이렇게 하면 한 번의 멈춤 길이가 힙 크기가 아니라 조각 크기로 정해집니다. 조각을 작게 잡을수록 멈춤이 짧아집니다. 대신 조각 수가 늘어 전체 수집이 끝나기까지 더 오래 걸립니다.

sequenceDiagram
    participant 프로그램
    participant 컬렉터
    loop 표시가 끝날 때까지
        프로그램->>프로그램: 잠깐 돈다
        프로그램->>컬렉터: 실행을 넘긴다
        컬렉터->>컬렉터: 객체 몇 개를 표시한다
        컬렉터-->>프로그램: 실행을 돌려준다
    end
    컬렉터->>컬렉터: 표시 없는 객체를 돌려받는다

그림처럼 프로그램과 컬렉터가 번갈아 돕니다. 둘은 같은 스레드에서 차례를 주고받습니다. 한 차례의 컬렉터 몫이 짧으니 프로그램 쪽에서 보면 멈춤이 잘게 흩어집니다.

어디까지 훑었는지 기억하기

나눠서 하려면 멈춘 지점에서 다시 시작할 수 있어야 합니다. 그래서 객체마다 진행 상태를 색으로 붙입니다. 이 방법이 삼색 표시(tri-color marking)입니다.

수집을 시작할 때는 모든 객체가 흰색입니다. 루트 집합에서 바로 닿는 객체를 회색으로 바꿉니다. 회색 객체들은 「다음에 훑을 목록」 구실을 합니다.

조각 하나는 회색 객체를 몇 개 꺼내 그것이 가리키는 흰 객체를 회색으로 바꿉니다. 꺼낸 객체는 검은색으로 바꿉니다. 회색이 하나도 남지 않으면 표시가 끝납니다. 그때 흰색으로 남은 객체가 쓰레기입니다.

stateDiagram-v2
    [*] --> 흰색: 수집 시작
    흰색 --> 회색: 루트 집합이나 회색 객체에서 닿는다
    회색 --> 검은색: 이 객체가 가리키는 것을 다 훑는다
    흰색 --> [*]: 표시가 끝날 때 흰색이면 돌려받는다
    검은색 --> [*]: 표시가 끝나면 살아남는다

진행 상태가 객체의 색 안에 다 들어 있으니, 조각과 조각 사이에 따로 기억할 것이 없습니다. 다음 조각은 회색 목록에서 이어 꺼내기만 하면 됩니다.

조각 사이에 프로그램이 참조를 바꿀 때

몰아서 치울 때와 달리, 조각 사이에는 프로그램이 돕니다. 프로그램은 객체의 필드에 다른 객체를 넣거나 빼며 참조를 바꿉니다. 컬렉터가 모르는 사이에 바뀐 참조가 문제를 일으킵니다.

이미 다 훑은 검은 객체 A 가 있다고 합시다. 아직 안 훑은 회색 객체 C 는 흰 객체 B 를 가리키고 있습니다. 이때 프로그램이 B 를 A 의 필드에 넣습니다. 그리고 C 에서 B 로 가는 참조를 끊습니다.

flowchart TD
    R["루트 집합"] --> A["A · 검은색 · 다시 안 훑는다"]
    A -->|"프로그램이 새로 넣은 참조"| B["B · 흰색"]
    C["C · 회색"] -.->|"프로그램이 끊은 참조"| B

컬렉터는 검은 A 를 다시 훑지 않습니다. 회색 C 를 훑을 때는 B 로 가는 참조가 이미 사라졌습니다. B 는 A 를 거쳐 여전히 닿습니다. 그런데도 끝까지 흰색으로 남아 컬렉터가 그 메모리를 돌려받습니다. 프로그램이 아직 쓰는 객체를 치운 것이니 엉뚱한 값을 읽거나 프로그램이 죽습니다.

이 사고는 두 조건이 함께 갖춰질 때 생깁니다. 첫째, 검은 객체가 흰 객체를 가리키게 됩니다. 둘째, 회색 객체에서 그 흰 객체로 가는 길이 모두 끊깁니다. 둘 중 하나만 막아도 사고는 안 납니다.

쓰기 장벽

앞의 두 조건 중 하나를 막는 장치가 쓰기 장벽(write barrier)입니다. 쓰기 장벽은 프로그램이 객체의 필드에 참조를 쓸 때마다 끼어드는 짧은 코드입니다. 개발자가 쓰는 것이 아니라 컴파일러나 런타임이 참조를 쓰는 명령마다 넣어 둡니다.

아래는 a.next = b; 한 줄 대신 도는 코드를 자바 꼴로 적은 것입니다. 표시 단계가 진행 중이고 넣으려는 객체가 흰색이면 회색으로 바꿔 둡니다.

// a.next = b; 대신 도는 코드
void writeRef(Node a, Node b) {
  if (marking && b.color == WHITE) {
    b.color = GRAY;    // 회색 목록에 든다
    grayList.add(b);
  }
  a.next = b;          // 원래 하려던 쓰기
}

앞 그림에 이 코드를 대 보면, A 에 B 를 넣는 순간 B 가 회색이 됩니다. 회색은 다음 조각이 꺼내 훑습니다. 그래서 B 는 끝내 검은색이 되어 살아남습니다.

장벽을 거는 방법은 크게 둘입니다. 앞의 두 조건을 하나씩 맡습니다.

위 코드처럼 새로 들어오는 참조를 챙기는 방식이 증분 갱신(incremental update)입니다. 이름에 「증분」이 들어가지만, 수집 방식 전체가 아니라 장벽을 거는 한 방식의 이름입니다.

증분 갱신은 첫째 조건을 막습니다. 검은 객체가 흰 객체를 가리키는 일이 아예 없게 하는 것입니다. 이 규칙을 삼색 불변식이라고 합니다.

다른 하나는 덮어써져 사라지는 참조를 챙깁니다. 참조가 지워지기 직전에 그것이 가리키던 객체를 회색으로 바꿉니다. 앞 그림이라면 프로그램이 C 에서 B 로 가는 참조를 끊는 순간 B 가 회색이 됩니다.

이쪽은 둘째 조건을 막습니다. A 가 B 를 가리키는 일은 그대로 두고, 끊길 길을 미리 살려 B 가 흰색으로 남지 않게 합니다. 그 결과 수집을 시작한 순간 닿던 객체는 모두 살아남습니다. 그래서 시작 시점 스냅샷(snapshot-at-the-beginning)이라고 부릅니다.

수집 속도를 할당 속도에 맞추기

프로그램은 조각 사이에도 새 객체를 계속 만듭니다. 컬렉터가 훑는 속도보다 프로그램이 객체를 만드는 속도가 빠르면 표시가 영영 안 끝납니다. 그 사이 힙이 바닥나면 결국 프로그램을 세워야 합니다. 남은 일은 한 번에 몰아서 끝냅니다.

그래서 많은 증분 컬렉터는 조각의 양을 메모리 할당에 묶습니다. 프로그램이 일정량을 새로 할당할 때마다 그 양에 비례해 표시도 일정량 하게 하는 식입니다. 할당을 많이 하는 프로그램일수록 수집 조각도 자주 돕니다.

게임처럼 화면 한 장마다 남는 시간이 정해진 프로그램은 다른 길도 씁니다. 한 장을 다 그린 뒤 예산이 남으면 그 남은 시간만큼만 수집 조각을 돌립니다.

증분 방식이 치르는 값

멈춤을 잘게 나눈 대신 다른 곳에서 값을 냅니다. 셋을 나란히 놓으면 이렇습니다.

셋 모두 전체 처리량 쪽으로 몰립니다. 컬렉터가 쓰는 시간을 다 더하면, 같은 일을 몰아서 할 때보다 대개 깁니다. 증분 방식은 이 합계를 내주고 한 번의 멈춤 길이를 사는 셈입니다.

동시 가비지 컬렉션과 가르기

멈춤을 줄이는 또 다른 길이 동시 가비지 컬렉션입니다. 이쪽은 컬렉터가 별도 스레드에서 프로그램과 같은 시각에 돕니다. 증분 방식이 한 스레드 안에서 차례를 주고받는 것과 다릅니다.

두 방식은 수집 도중에 프로그램이 참조를 바꾼다는 문제를 똑같이 안고 있습니다. 그래서 둘 다 삼색 표시와 쓰기 장벽을 씁니다. 실제 컬렉터는 두 방식을 섞어 쓰기도 합니다.

언제 쓰고 언제 안 쓰나

멈춤 한 번의 길이가 곧 품질인 프로그램이 증분 방식을 고릅니다. 프레임마다 시간이 정해진 게임, 사용자 입력에 바로 반응해야 하는 화면 프로그램, 브라우저의 자바스크립트 엔진이 그렇습니다. 코어가 하나뿐이라 컬렉터에게 따로 스레드를 줄 수 없는 임베디드 기기도 이 방식에 기댑니다.

반대로 밤새 도는 배치 작업처럼 끝나는 시각만 중요한 일은 몰아서 치우는 쪽을 고릅니다. 멈춤이 길어도 아무도 기다리지 않습니다. 쓰기 장벽 비용이 없으니 전체 일도 줄어듭니다.

관련 항목

증분 가비지 컬렉션이 속하는 상위 분류

가비지 컬렉션 · 추적 가비지 컬렉션 · 마크 앤 스윕 · 메모리 관리 · 런타임

증분 가비지 컬렉션을 이루는 구성 요소

삼색 표시 · 쓰기 장벽 · 읽기 장벽 · 루트 집합 · 힙 · 참조 · 메모리 할당

증분 가비지 컬렉션이 지키는 성질

삼색 불변식 · 도달 가능성 · 증분 갱신 · 시작 시점 스냅샷 · 뮤테이터

멈춤을 줄이려고 함께 겨루는 수집 방식

동시 가비지 컬렉션 · 세대별 가비지 컬렉션 · 실시간 가비지 컬렉션 · 복사 가비지 컬렉션 · 참조 카운팅 · 컴팩션

증분 가비지 컬렉션이 막으려는 장애

가비지 컬렉션 정지 · GC 스파이크 · 히칭 · 꼬리 지연 · 프레임 드롭

증분 가비지 컬렉션이 저울질하는 성능 지표

처리량 · 지연 · 응답 시간 · 프레임 예산 · 부동 쓰레기 · 메모리 사용량

증분 가비지 컬렉션을 품은 실행 환경

자바스크립트 엔진 · JVM · Go · Lua · 게임 엔진 · 게임 루프 · 임베디드

일을 잘게 나눠 비용을 흩는 다른 기법

분할 상환 비용 · 점진적 리해싱 · 협력적 멀티태스킹 · 타임 슬라이스