Garbage Collection

I wanna, I wanna,
I wanna, I wanna,
I wanna be trash.

The Whip, “Trash”

Lox는 프로그래머가 해결하고자 하는 문제와 무관한 세부 사항에 대해 신경 쓰지 않아도 되도록 하기 때문에 "고수준" 언어라고 말합니다. 사용자는 관리자가 되어 기계에 추상적인 목표를 제시하고, 하위 컴퓨터가 그 목표를 달성하는 방법을 알아내도록 합니다.

동적 메모리 할당은 자동화에 완벽한 후보입니다. 이는 작동하는 프로그램에 필수적이고, 수동으로 처리하기에는 지루하며, 오류가 발생하기 쉽습니다. 피할 수 없는 실수는 재앙을 초래하여 충돌, 메모리 손상 또는 보안 위반으로 이어질 수 있습니다. 이는 기계가 인간보다 뛰어난, 위험하지만 지루한 작업의 일종입니다.

이것이 Lox가 관리형 언어(managed language)인 이유입니다. 즉, 언어 구현체가 사용자를 대신하여 메모리 할당 및 해제를 관리합니다. 사용자가 동적 메모리가 필요한 작업을 수행하면 VM이 자동으로 메모리를 할당합니다. 프로그래머는 어떤 것도 할당 해제하는 것에 대해 걱정할 필요가 없습니다. 기계는 프로그램이 사용하는 모든 메모리가 필요한 한 유지되도록 보장합니다.

Lox는 컴퓨터가 무한한 양의 메모리를 가지고 있다는 환상을 제공합니다. 사용자들은 계속해서 할당하고 할당하며 이 모든 바이트가 어디에서 오는지 한 번도 생각할 필요가 없습니다. 물론, 컴퓨터는 아직 무한한 메모리를 가지고 있지 않습니다. 따라서 관리형 언어가 이 환상을 유지하는 방법은 프로그래머 몰래 프로그램이 더 이상 필요로 하지 않는 메모리를 회수하는 것입니다. 이 작업을 수행하는 구성 요소를 가비지 컬렉터(garbage collector)라고 부릅니다.

26 . 1접근성(Reachability)

이는 놀랍도록 어려운 질문을 제기합니다: VM은 어떤 메모리가 필요 없는 것인지 어떻게 알 수 있을까요? 메모리는 미래에 읽혀질 때만 필요하지만, 타임머신이 없는 한 구현체가 프로그램이 어떤 코드를 실행할지, 어떤 데이터를 사용할지 어떻게 알 수 있을까요? 스포일러 경고: VM은 미래로 여행할 수 없습니다. 대신, 언어는 보수적인(conservative) 근사를 합니다: 특정 메모리 조각이 미래에 읽힐 가능성이 있다면 여전히 사용 중인 것으로 간주합니다.

그것은 너무 보수적인 것 같습니다. 어떤 메모리라도 잠재적으로 읽힐 수 있지 않을까요? 사실, Lox와 같은 메모리 안전 언어에서는 그렇지 않습니다. 다음 예시를 보시죠:

var a = "first value";
a = "updated";
// GC here.
print a;

두 번째 줄에서 할당이 완료된 후 GC를 실행한다고 가정해 봅시다. 문자열 "first value"는 여전히 메모리에 있지만, 사용자 프로그램이 이 문자열에 접근할 방법은 전혀 없습니다. a가 재할당되자마자 프로그램은 해당 문자열에 대한 모든 참조를 잃었습니다. 우리는 이 메모리를 안전하게 해제할 수 있습니다. 어떤 값이 접근 가능한(reachable) 상태라는 것은 사용자 프로그램이 그 값을 참조할 수 있는 어떤 방법이 있다는 의미입니다. 그렇지 않다면, 이 예시의 "first value" 문자열처럼 접근 불가능한(unreachable) 상태입니다.

많은 값은 VM에 의해 직접 접근될 수 있습니다. 다음을 살펴보세요:

var global = "string";
{
  var local = "another";
  print global + local;
}

두 문자열이 연결된 직후, 하지만 print 문이 실행되기 전에 프로그램을 잠시 멈춥니다. VM은 전역 변수 테이블을 통해 global 항목을 찾아 "string"에 접근할 수 있습니다. 값 스택을 따라가서 지역 변수 local에 해당하는 슬롯을 찾아 "another"를 찾을 수 있습니다. 프로그램이 일시 중지된 시점에 이 임시 값이 VM 스택에 놓여 있으므로, 연결된 문자열 "stringanother"까지도 찾을 수 있습니다.

이러한 모든 값은 루트(roots)라고 불립니다. 루트는 VM이 다른 객체 내의 참조를 거치지 않고 직접 접근할 수 있는 모든 객체입니다. 대부분의 루트는 전역 변수이거나 스택에 있지만, 앞으로 보게 될 것처럼, VM이 찾을 수 있는 객체에 대한 참조를 저장하는 다른 곳들도 몇 군데 있습니다.

다른 값들은 다른 값 내부의 참조를 통해 찾을 수 있습니다. 클래스 인스턴스의 필드가 가장 명백한 경우이지만, 우리는 아직 필드를 가지고 있지 않습니다. 필드가 없더라도 우리의 VM은 간접 참조를 가지고 있습니다. 다음을 생각해 보세요:

fun makeClosure() {
  var a = "data";

  fun f() { print a; }
  return f;
}

{
  var closure = makeClosure();
  // GC here.
  closure();
}

표시된 줄에서 프로그램을 일시 중지하고 가비지 컬렉터를 실행한다고 가정해 봅시다. 컬렉터가 작업을 마치고 프로그램이 재개되면 클로저를 호출하고, 클로저는 "data"를 출력할 것입니다. 따라서 컬렉터는 해당 문자열을 해제해서는 안 됩니다. 하지만 프로그램을 일시 중지했을 때 스택은 다음과 같습니다:

"data" 문자열은 스택 어디에도 없습니다. 이미 스택에서 제거되어 클로저가 사용하는 닫힌 업밸류(upvalue)로 옮겨졌습니다. 클로저 자체는 스택에 있습니다. 하지만 문자열에 도달하려면 클로저와 그 업밸류 배열을 따라 추적해야 합니다. 사용자 프로그램이 그렇게 하는 것이 가능하므로, 이 모든 간접적으로 접근 가능한 객체들도 접근 가능한 것으로 간주됩니다.

이는 접근성(reachability)에 대한 귀납적 정의를 제공합니다:

• 모든 루트는 접근 가능합니다.

• 접근 가능한 객체에서 참조되는 모든 객체는 그 자체로 접근 가능합니다.

이것들은 여전히 "살아 있는(live)" 값이며 메모리에 유지되어야 합니다. 이 정의를 충족하지 않는 모든 값은 컬렉터가 회수할 수 있는 대상입니다. 이러한 재귀적인 규칙은 불필요한 메모리를 해제하기 위해 사용할 수 있는 재귀적 알고리즘을 암시합니다:

1. 루트에서 시작하여 객체 참조를 따라 탐색하여 접근 가능한 객체의 전체 집합을 찾습니다.

2. 그 집합에 없는 모든 객체를 해제합니다.

오늘날 사용되는 많은 다양한 가비지 컬렉션 알고리즘이 있지만, 모두 대략적으로 동일한 구조를 따릅니다. 일부는 단계를 번갈아 수행하거나 혼합할 수 있지만, 두 가지 기본 작업은 모두 존재합니다. 주로 각 단계를 어떻게 수행하는지에 따라 다릅니다.

26 . 2마크-스윕 가비지 컬렉션

최초의 관리형 언어는 Lisp였고, Fortran 바로 다음에 발명된 두 번째 "고수준" 언어였습니다. John McCarthy는 수동 메모리 관리나 참조 카운팅 사용을 고려했지만, 결국 가비지 컬렉션에 정착(그리고 용어를 만들었습니다)했습니다. 즉, 프로그램이 메모리가 부족해지면 돌아가서 사용하지 않는 저장 공간을 찾아 회수하는 방식입니다.

그는 가장 처음이자 가장 단순한 가비지 컬렉션 알고리즘인 마크-앤-스윕(mark-and-sweep) 또는 단순히 마크-스윕(mark-sweep)을 설계했습니다. 이 알고리즘에 대한 설명은 Lisp 초기 논문의 세 단락에 불과합니다. 오래되고 단순함에도 불구하고, 이와 동일한 기본적인 알고리즘이 많은 현대 메모리 관리자의 기반이 됩니다. 컴퓨터 과학의 일부 분야는 시대를 초월하는 것 같습니다.

이름이 암시하듯이, 마크-스윕은 두 단계로 작동합니다:

• 마킹(Marking): 루트에서 시작하여 해당 루트가 참조하는 모든 객체를 순회하거나 추적합니다. 이것은 접근 가능한 모든 객체에 대한 고전적인 그래프 탐색입니다. 객체를 방문할 때마다 어떤 방식으로든 객체를 표시합니다. (구현에 따라 마크를 기록하는 방식은 다릅니다.)

• 스윕(Sweeping): 마크 단계가 완료되면, 힙의 모든 접근 가능한 객체가 표시됩니다. 이는 표시되지 않은 객체가 접근 불가능하며 회수될 준비가 되었다는 의미입니다. 우리는 표시되지 않은 모든 객체를 살펴보고 각각을 해제합니다.

대략 이런 모습입니다:

이것이 우리가 구현할 내용입니다. 특정 바이트를 회수할 때가 되었다고 결정할 때마다, 모든 것을 추적하여 접근 가능한 모든 객체를 표시하고, 표시되지 않은 것을 해제한 다음, 사용자 프로그램을 다시 시작할 것입니다.

26 . 2 . 1가비지 수집

이 챕터 전체는 이 하나의 함수를 구현하는 것에 관한 것입니다:

void* reallocate(void* pointer, size_t oldSize, size_t newSize);

void collectGarbage();

void freeObjects();

이 빈 껍데기부터 시작해서 전체 구현을 만들어 나갈 것입니다:

void collectGarbage() {
}

가장 먼저 물을 수 있는 질문은, 이 함수가 언제 호출되는가 하는 것입니다. 이 질문은 이 챕터 후반에 시간을 들여 다룰 미묘한 문제입니다. 지금은 이 문제를 잠시 제쳐두고, 그 과정에서 유용한 진단 도구를 만들 것입니다.

#define DEBUG_TRACE_EXECUTION

#define DEBUG_STRESS_GC

#define UINT8_COUNT (UINT8_MAX + 1)

가비지 컬렉터를 위한 선택적 "스트레스 테스트" 모드를 추가할 것입니다. 이 플래그가 정의되면, GC는 가능한 한 자주 실행됩니다. 이는 명백히 성능에 끔찍합니다. 하지만 GC가 적절한 순간에 트리거될 때만 발생하는 메모리 관리 버그를 찾아내는 데는 탁월합니다. 모든 순간이 GC를 트리거한다면, 그러한 버그를 발견할 가능성이 높습니다.

void* reallocate(void* pointer, size_t oldSize, size_t newSize) {

  if (newSize > oldSize) {
#ifdef DEBUG_STRESS_GC
    collectGarbage();
#endif
  }

  if (newSize == 0) {

메모리를 더 확보하기 위해 reallocate()를 호출할 때마다, 강제로 컬렉션을 실행합니다. 이 if 조건문은 reallocate()가 할당을 해제하거나 축소할 때도 호출되기 때문입니다. 이런 경우에는 GC를 트리거하고 싶지 않습니다. 특히 GC 자체가 메모리 해제를 위해 reallocate()를 호출할 것이기 때문입니다.

할당 직전에 컬렉션을 수행하는 것은 GC를 VM에 연결하는 고전적인 방법입니다. 이미 메모리 관리자를 호출하고 있으므로 코드를 연결하기 쉬운 지점입니다. 또한, 할당은 재사용할 수 있도록 해제된 메모리가 정말 필요한 유일한 시점입니다. 만약 할당을 사용하여 GC를 트리거하지 않는다면, 루프를 돌며 메모리를 할당할 수 있는 코드의 모든 가능한 지점에 컬렉터를 트리거할 방법이 있는지 확인해야 합니다. 그렇지 않으면 VM은 더 많은 메모리가 필요하지만 아무것도 수집하지 못하는 고갈 상태에 빠질 수 있습니다.

26 . 2 . 2디버그 로깅

진단에 대한 이야기로 넘어온 김에, 몇 가지를 더 추가해봅시다. 제가 가비지 컬렉터에서 발견한 실제 문제는 컬렉터가 불투명하다는 것입니다. 지금까지 우리는 GC 전혀 없이도 많은 Lox 프로그램을 잘 실행해 왔습니다. GC를 추가한 후에 그것이 유용한 일을 하고 있는지 어떻게 알 수 있을까요? 엄청난 양의 메모리를 사용하는 프로그램을 작성해야만 알 수 있을까요? 어떻게 디버그해야 할까요?

GC 내부 작동을 밝히는 쉬운 방법은 로깅을 추가하는 것입니다.

#define DEBUG_STRESS_GC

#define DEBUG_LOG_GC

#define UINT8_COUNT (UINT8_MAX + 1)

이것이 활성화되면 clox는 동적 메모리로 작업을 수행할 때 콘솔에 정보를 출력합니다.

두어 개의 include가 필요합니다.

#include "vm.h"

#ifdef DEBUG_LOG_GC
#include <stdio.h>
#include "debug.h"
#endif

void* reallocate(void* pointer, size_t oldSize, size_t newSize) {

아직 컬렉터는 없지만, 지금부터 로깅을 추가할 수 있습니다. 컬렉션이 시작될 때를 알고 싶을 것입니다.

void collectGarbage() {

#ifdef DEBUG_LOG_GC
  printf("-- gc begin\n");
#endif

}

결국 컬렉션 중에 다른 작업을 로깅할 것이므로, 작업이 끝났을 때도 알 수 있도록 할 것입니다.

  printf("-- gc begin\n");
#endif

#ifdef DEBUG_LOG_GC
  printf("-- gc end\n");
#endif

}

아직 컬렉터 코드는 없지만, 할당 및 해제 함수는 있으므로 지금 바로 계측할 수 있습니다.

  vm.objects = object;

#ifdef DEBUG_LOG_GC
  printf("%p allocate %zu for %d\n", (void*)object, size, type);
#endif

  return object;

그리고 객체 수명 주기의 끝에서:

static void freeObject(Obj* object) {

#ifdef DEBUG_LOG_GC
  printf("%p free type %d\n", (void*)object, object->type);
#endif

  switch (object->type) {

이 두 플래그를 사용하면 챕터의 나머지 부분을 진행하면서 우리가 진전을 이루고 있음을 확인할 수 있을 것입니다.

26 . 3루트(Root) 마킹하기

객체들은 어두운 밤하늘의 별처럼 힙 전체에 흩어져 있습니다. 한 객체에서 다른 객체로의 참조는 연결을 형성하며, 이러한 별자리들은 마크 단계가 탐색하는 그래프가 됩니다. 마킹은 루트에서 시작합니다.

#ifdef DEBUG_LOG_GC
  printf("-- gc begin\n");
#endif

  markRoots();

#ifdef DEBUG_LOG_GC

대부분의 루트는 VM 스택에 있는 지역 변수 또는 임시 변수이므로, 먼저 그 스택을 탐색하는 것으로 시작합니다.

static void markRoots() {
  for (Value* slot = vm.stack; slot < vm.stackTop; slot++) {
    markValue(*slot);
  }
}

Lox 값을 표시하려면, 이 새로운 함수를 사용합니다:

void* reallocate(void* pointer, size_t oldSize, size_t newSize);

void markValue(Value value);

void collectGarbage();

구현은 다음과 같습니다:

void markValue(Value value) {
  if (IS_OBJ(value)) markObject(AS_OBJ(value));
}

일부 Lox 값(숫자, 불리언, nil)은 Value 내에 직접 인라인으로 저장되며 힙 할당이 필요 없습니다. 가비지 컬렉터는 이들에 대해 전혀 걱정할 필요가 없으므로, 가장 먼저 하는 일은 그 값이 실제 힙 객체인지 확인하는 것입니다. 그렇다면 실제 작업은 이 함수에서 발생합니다:

void* reallocate(void* pointer, size_t oldSize, size_t newSize);

void markObject(Obj* object);

void markValue(Value value);

다음과 같이 정의됩니다:

void markObject(Obj* object) {
  if (object == NULL) return;
  object->isMarked = true;
}

markValue()에서 호출될 때는 NULL 검사가 불필요합니다. Obj 타입의 Lox Value는 항상 유효한 포인터를 가질 것입니다. 하지만 나중에 다른 코드에서 이 함수를 직접 호출할 것이며, 그 중 일부에서는 가리키는 객체가 선택 사항일 수 있습니다.

유효한 객체가 있다고 가정하면, 플래그를 설정하여 객체를 표시합니다. 이 새로운 필드는 모든 객체가 공유하는 Obj 헤더 구조체에 있습니다.

  ObjType type;

  bool isMarked;

  struct Obj* next;

새로운 객체는 아직 접근 가능한지 여부가 결정되지 않았으므로 표시되지 않은 상태로 생명(life)을 시작합니다.

  object->type = type;

  object->isMarked = false;

  object->next = vm.objects;

더 나아가기 전에 markObject()에 로깅을 추가해 봅시다.

void markObject(Obj* object) {
  if (object == NULL) return;

#ifdef DEBUG_LOG_GC
  printf("%p mark ", (void*)object);
  printValue(OBJ_VAL(object));
  printf("\n");
#endif

  object->isMarked = true;

이렇게 하면 마크 단계가 무엇을 하는지 볼 수 있습니다. 스택을 마킹하는 것은 지역 변수와 임시 변수를 처리합니다. 다른 주요 루트 소스는 전역 변수입니다.

    markValue(*slot);
  }

  markTable(&vm.globals);

}

이들은 VM이 소유한 해시 테이블에 존재하므로, 테이블의 모든 객체를 표시하기 위한 또 다른 헬퍼 함수를 선언할 것입니다.

ObjString* tableFindString(Table* table, const char* chars,
                           int length, uint32_t hash);

void markTable(Table* table);

#endif

그것은 여기 "table" 모듈에 구현되어 있습니다:

void markTable(Table* table) {
  for (int i = 0; i < table->capacity; i++) {
    Entry* entry = &table->entries[i];
    markObject((Obj*)entry->key);
    markValue(entry->value);
  }
}

꽤 간단합니다. 우리는 엔트리 배열을 순회합니다. 각 엔트리에 대해 그 값을 마크합니다. 또한 GC가 이 문자열들도 관리하므로 각 엔트리의 키 문자열도 마크합니다.

26 . 3 . 1덜 명백한 루트

이것들은 우리가 일반적으로 생각하는 루트들을 다룹니다. 즉, 사용자 프로그램이 볼 수 있는 변수에 저장되어 있어 명백하게 접근 가능한 값들입니다. 하지만 VM에는 직접 접근하는 값을 몰래 숨겨두는 몇 군데의 숨겨진 장소가 있습니다.

대부분의 함수 호출 상태는 값 스택에 존재하지만, VM은 별도의 CallFrame 스택을 유지합니다. 각 CallFrame은 호출되는 클로저에 대한 포인터를 포함합니다. VM은 이 포인터들을 사용하여 상수와 업밸류에 접근하므로, 이 클로저들도 유지되어야 합니다.

  }

  for (int i = 0; i < vm.frameCount; i++) {
    markObject((Obj*)vm.frames[i].closure);
  }

  markTable(&vm.globals);

업밸류(upvalue) 이야기가 나왔으니 말인데, 열린 업밸류(open upvalue) 리스트는 VM이 직접 접근할 수 있는 또 다른 값 집합입니다.

  for (int i = 0; i < vm.frameCount; i++) {
    markObject((Obj*)vm.frames[i].closure);
  }

  for (ObjUpvalue* upvalue = vm.openUpvalues;
       upvalue != NULL;
       upvalue = upvalue->next) {
    markObject((Obj*)upvalue);
  }

  markTable(&vm.globals);

또한 컬렉션은 어떤 할당 중에든 시작될 수 있다는 점을 기억하십시오. 이러한 할당은 사용자 프로그램이 실행되는 동안에만 발생하는 것이 아닙니다. 컴파일러 자체도 리터럴과 상수 테이블을 위해 주기적으로 힙에서 메모리를 가져옵니다. 만약 컴파일 중 GC가 실행된다면, 컴파일러가 직접 접근하는 모든 값도 루트로 처리되어야 합니다.

컴파일러 모듈을 VM의 나머지 부분과 깔끔하게 분리하기 위해, 우리는 이 작업을 별도의 함수에서 수행할 것입니다.

  markTable(&vm.globals);

  markCompilerRoots();

}

다음과 같이 선언되어 있습니다:

ObjFunction* compile(const char* source);

void markCompilerRoots();

#endif

이는 "memory" 모듈에 include가 필요하다는 의미입니다.

#include <stdlib.h>

#include "compiler.h"

#include "memory.h"

그리고 정의는 "compiler" 모듈에 있습니다.

void markCompilerRoots() {
  Compiler* compiler = current;
  while (compiler != NULL) {
    markObject((Obj*)compiler->function);
    compiler = compiler->enclosing;
  }
}

다행히 컴파일러는 너무 많은 값을 붙잡고 있지 않습니다. 컴파일러가 사용하는 유일한 객체는 컴파일 중인 ObjFunction입니다. 함수 선언은 중첩될 수 있으므로, 컴파일러는 이들의 연결 리스트를 가지고 있으며 우리는 전체 리스트를 순회합니다.

"compiler" 모듈이 markObject()를 호출하므로, include도 필요합니다.

#include "compiler.h"

#include "memory.h"

#include "scanner.h"

이것들이 모든 루트입니다. 이 작업을 실행하고 나면, VM(런타임 및 컴파일러)이 다른 객체를 거치지 않고 접근할 수 있는 모든 객체는 마크 비트가 설정됩니다.

26 . 4객체 참조 추적하기

마킹 과정의 다음 단계는 객체 참조 그래프를 추적하여 간접적으로 접근 가능한 값을 찾는 것입니다. 아직 필드를 가진 인스턴스는 없으므로 참조를 포함하는 객체는 많지 않지만, 몇 개는 있습니다. 특히 ObjClosure는 자신이 닫는 ObjUpvalue 목록과 자신이 래핑하는 원시 ObjFunction에 대한 참조를 가지고 있습니다. ObjFunction은 차례로 함수의 본문에서 생성된 모든 리터럴에 대한 참조를 포함하는 상수 테이블을 가지고 있습니다. 이는 컬렉터가 탐색할 수 있는 상당히 복잡한 객체 웹을 구축하기에 충분합니다.

이제 탐색을 구현할 시간입니다. 너비 우선, 깊이 우선 또는 다른 순서로 갈 수 있습니다. 도달 가능한 모든 객체의 집합을 찾기만 하면 되므로, 방문 순서는 대부분 중요하지 않습니다.

26 . 4 . 1삼색 추상화(The tricolor abstraction)

컬렉터가 객체 그래프를 탐색할 때, 현재 위치를 잃거나 순환에 갇히지 않도록 해야 합니다. 이는 특히 마킹 작업을 사용자 프로그램 실행 조각들과 번갈아 수행하는 증분(incremental) GC와 같은 고급 구현에서 중요한 문제입니다. 컬렉터는 작업을 일시 중지한 다음 나중에 중단했던 지점에서 다시 시작할 수 있어야 합니다.

우리와 같은 부드러운 뇌를 가진 인간이 이 복잡한 과정을 이해하는 데 도움이 되도록, VM 해커들은 삼색 추상화(tricolor abstraction)라는 은유를 고안했습니다. 각 객체는 객체의 상태와 남은 작업을 추적하는 개념적인 "색상"을 가집니다.

• 흰색: 가비지 컬렉션 시작 시 모든 객체는 흰색입니다. 이 색상은 객체가 전혀 접근되거나 처리되지 않았음을 의미합니다.

• 회색: 마킹 중에 객체에 처음 도달하면 회색으로 어둡게 만듭니다. 이 색상은 객체 자체가 접근 가능하며 수집되어서는 안 된다는 것을 의미합니다. 그러나 우리는 아직 이 객체를 통해 무엇이 다른 객체를 참조하는지 추적하지 않았습니다. 그래프 알고리즘 용어로는 이것이 작업 목록(worklist)입니다. 즉, 우리가 알고 있지만 아직 처리하지 않은 객체들의 집합입니다.

• 검은색: 회색 객체를 가져와 그 객체가 참조하는 모든 객체를 표시하면, 그 회색 객체는 검은색으로 변합니다. 이 색상은 해당 객체에 대한 마크 단계 처리가 완료되었음을 의미합니다.

이 추상화의 관점에서, 마킹 프로세스는 이제 다음과 같습니다:

1. 모든 객체를 흰색으로 시작합니다.

2. 모든 루트를 찾아 회색으로 표시합니다.

3. 회색 객체가 남아있는 한 다음을 반복합니다:

   1. 회색 객체를 하나 선택합니다. 해당 객체가 참조하는 흰색 객체를 회색으로 바꿉니다.

   2. 원래의 회색 객체를 검은색으로 표시합니다.

저는 이것을 시각화하는 것이 도움이 된다고 생각합니다. 객체들 사이에 참조가 있는 웹이 있습니다. 처음에는 모두 작은 흰색 점입니다. 한쪽에는 VM에서 들어오는 가장자리가 있어 루트를 가리킵니다. 그 루트들은 회색으로 변합니다. 그런 다음 각 회색 객체의 형제 객체들은 회색으로 변하고, 객체 자체는 검은색으로 변합니다. 전체 효과는 그래프를 통과하는 회색 파동이 접근 가능한 검은색 객체들의 영역을 뒤에 남기는 것입니다. 접근 불가능한 객체들은 파동에 닿지 않아 흰색으로 남아 있습니다.

결국 끝에는, 도달한 검은색 객체들의 바다가 남고, 그 사이에 쓸어 담아 해제할 수 있는 흰색 객체들의 섬이 흩뿌려져 있습니다. 접근 불가능한 객체들이 해제되면, 남아 있는 객체들(모두 검은색)은 다음 가비지 컬렉션 주기를 위해 흰색으로 재설정됩니다.

26 . 4 . 2회색 객체를 위한 작업 목록

우리 구현에서 루트는 이미 표시되었습니다. 모두 회색입니다. 다음 단계는 그것들을 선택하고 참조를 따라 탐색하는 것입니다. 하지만 그것들을 쉽게 찾을 방법이 없습니다. 객체에 필드를 설정했지만 그것뿐입니다. 해당 필드가 설정된 객체를 찾기 위해 전체 객체 목록을 탐색하고 싶지는 않습니다.

대신, 모든 회색 객체를 추적하기 위해 별도의 작업 목록을 만들 것입니다. 객체가 회색으로 변하면, 마크 필드를 설정하는 것 외에도 작업 목록에 추가할 것입니다.

  object->isMarked = true;

  if (vm.grayCapacity < vm.grayCount + 1) {
    vm.grayCapacity = GROW_CAPACITY(vm.grayCapacity);
    vm.grayStack = (Obj**)realloc(vm.grayStack,
                                  sizeof(Obj*) * vm.grayCapacity);
  }

  vm.grayStack[vm.grayCount++] = object;

}

우리는 항목을 쉽게 넣고 뺄 수 있는 어떤 종류의 데이터 구조라도 사용할 수 있습니다. C 언어에서 동적 배열로 구현하기 가장 간단하기 때문에 스택을 선택했습니다. Lox에서 만든 다른 동적 배열과 거의 동일하게 작동하지만, 다만 자체 reallocate() 래퍼 함수가 아닌 시스템 realloc() 함수를 호출한다는 점에 유의하세요. 회색 스택 자체의 메모리는 가비지 컬렉터에 의해 관리되지 않습니다. GC 중에 회색 스택이 커지는 것이 GC가 재귀적으로 새로운 GC를 시작하도록 유발하는 것을 원치 않습니다. 그렇게 되면 시공 연속체에 구멍이 생길 수 있습니다.

우리는 이 메모리를 직접, 명시적으로 관리할 것입니다. VM이 회색 스택을 소유합니다.

  Obj* objects;

  int grayCount;
  int grayCapacity;
  Obj** grayStack;

} VM;

빈 상태로 시작합니다.

  vm.objects = NULL;

  vm.grayCount = 0;
  vm.grayCapacity = 0;
  vm.grayStack = NULL;

  initTable(&vm.globals);

그리고 VM이 종료될 때 이를 해제해야 합니다.

    object = next;
  }

  free(vm.grayStack);

}

우리는 이 배열에 대한 완전한 책임을 집니다. 여기에는 할당 실패도 포함됩니다. 만약 회색 스택을 생성하거나 확장할 수 없다면, 가비지 컬렉션을 완료할 수 없습니다. 이는 VM에 나쁜 소식이지만, 회색 스택은 일반적으로 상당히 작기 때문에 다행히 드문 경우입니다. 좀 더 우아하게 처리하는 것이 좋겠지만, 이 책의 코드를 간단하게 유지하기 위해 우리는 단순히 중단합니다.

    vm.grayStack = (Obj**)realloc(vm.grayStack,
                                  sizeof(Obj*) * vm.grayCapacity);

    if (vm.grayStack == NULL) exit(1);

  }

26 . 4 . 3회색 객체 처리하기

좋습니다. 이제 루트 마킹을 마쳤을 때, 우리는 여러 필드를 설정하고 처리할 객체들로 작업 목록을 채웠습니다. 다음 단계를 진행할 차례입니다.

  markRoots();

  traceReferences();

#ifdef DEBUG_LOG_GC

구현은 다음과 같습니다:

static void traceReferences() {
  while (vm.grayCount > 0) {
    Obj* object = vm.grayStack[--vm.grayCount];
    blackenObject(object);
  }
}

텍스트 알고리즘에 최대한 가깝습니다. 스택이 비워질 때까지 회색 객체를 계속 꺼내서 참조를 탐색한 다음 검은색으로 표시합니다. 객체의 참조를 탐색하면 회색으로 표시되어 스택에 추가되는 새로운 흰색 객체가 나타날 수 있습니다. 따라서 이 함수는 흰색 객체를 회색으로 바꾸고 회색 객체를 검은색으로 바꾸는 작업을 번갈아 수행하며 전체 파동을 점진적으로 앞으로 나아가게 합니다.

여기에 단일 객체의 참조를 탐색하는 코드가 있습니다:

static void blackenObject(Obj* object) {
  switch (object->type) {
    case OBJ_NATIVE:
    case OBJ_STRING:
      break;
  }
}

각 객체 종류는 다른 객체를 참조할 수 있는 다른 필드를 가지므로, 각 타입에 맞는 특정 코드 블록이 필요합니다. 문자열과 네이티브 함수 객체는 외부 참조를 포함하지 않으므로 탐색할 것이 없는 쉬운 것부터 시작합니다.

탐색된 객체 자체에 어떤 상태도 설정하지 않는다는 점에 유의하십시오. 객체의 상태에 "검은색"을 직접 인코딩하는 것은 없습니다. 검은색 객체는 isMarked 필드가 설정되어 있고 더 이상 회색 스택에 없는 모든 객체입니다.

이제 다른 객체 타입들을 추가해 봅시다. 가장 간단한 것은 업밸류입니다.

  switch (object->type) {

    case OBJ_UPVALUE:
      markValue(((ObjUpvalue*)object)->closed);
      break;

    case OBJ_NATIVE:

업밸류가 닫힐 때, 닫힌 값에 대한 참조를 포함합니다. 해당 값이 더 이상 스택에 없으므로, 업밸류에서 해당 값으로의 참조를 추적해야 합니다.

다음은 함수입니다.

  switch (object->type) {

    case OBJ_FUNCTION: {
      ObjFunction* function = (ObjFunction*)object;
      markObject((Obj*)function->name);
      markArray(&function->chunk.constants);
      break;
    }

    case OBJ_UPVALUE:

각 함수는 함수의 이름을 포함하는 ObjString에 대한 참조를 가집니다. 더 중요한 것은, 함수는 함수 본문에서 생성된 모든 리터럴에 대한 참조로 가득 찬 상수 테이블을 가지고 있다는 것입니다. 이 헬퍼를 사용하여 이 모든 것들을 추적합니다:

static void markArray(ValueArray* array) {
  for (int i = 0; i < array->count; i++) {
    markValue(array->values[i]);
  }
}

지금 우리가 가지고 있는 마지막 객체 타입은 (다음 챕터에서 더 추가할 예정입니다) 클로저입니다.

  switch (object->type) {

    case OBJ_CLOSURE: {
      ObjClosure* closure = (ObjClosure*)object;
      markObject((Obj*)closure->function);
      for (int i = 0; i < closure->upvalueCount; i++) {
        markObject((Obj*)closure->upvalues[i]);
      }
      break;
    }

    case OBJ_FUNCTION: {

각 클로저는 자신이 래핑하는 순수 함수에 대한 참조뿐만 아니라, 자신이 캡처하는 업밸류에 대한 포인터 배열도 가집니다. 우리는 이 모든 것들을 추적합니다.

이것이 회색 객체를 처리하는 기본 메커니즘이지만, 두 가지 느슨한 끝을 정리해야 합니다. 첫째, 로깅입니다.

static void blackenObject(Obj* object) {

#ifdef DEBUG_LOG_GC
  printf("%p blacken ", (void*)object);
  printValue(OBJ_VAL(object));
  printf("\n");
#endif

  switch (object->type) {

이렇게 하면 객체 그래프를 통해 추적이 퍼져나가는 것을 볼 수 있습니다. 그런데 그래프라고 말한 것에 주목하세요. 객체 간의 참조는 방향성이 있지만, 그렇다고 해서 비순환적이라는 의미는 아닙니다! 객체 순환이 발생하는 것은 충분히 가능합니다. 그럴 경우, 컬렉터가 동일한 객체들을 계속해서 회색 스택에 다시 추가하여 무한 루프에 빠지지 않도록 해야 합니다.

해결책은 간단합니다.

  if (object == NULL) return;

  if (object->isMarked) return;

#ifdef DEBUG_LOG_GC

객체가 이미 마크되어 있다면, 다시 마크하지 않고 회색 스택에도 추가하지 않습니다. 이는 이미 회색인 객체가 중복으로 추가되지 않도록 하고, 검은색 객체가 실수로 다시 회색으로 변하는 것을 방지합니다. 즉, 파동이 흰색 객체만을 통해 계속 전진하도록 유지합니다.

26 . 5사용되지 않는 객체 스윕하기

traceReferences()의 루프가 종료되면, 우리는 손에 넣을 수 있는 모든 객체를 처리했습니다. 회색 스택은 비어 있고, 힙의 모든 객체는 검은색이거나 흰색입니다. 검은색 객체는 접근 가능하며, 우리는 그것들을 유지하고 싶습니다. 여전히 흰색인 객체는 추적에 의해 전혀 닿지 않았으므로 가비지입니다. 남은 것은 그것들을 회수하는 것뿐입니다.

  traceReferences();

  sweep();

#ifdef DEBUG_LOG_GC

모든 논리는 하나의 함수에 들어 있습니다.

static void sweep() {
  Obj* previous = NULL;
  Obj* object = vm.objects;
  while (object != NULL) {
    if (object->isMarked) {
      previous = object;
      object = object->next;
    } else {
      Obj* unreached = object;
      object = object->next;
      if (previous != NULL) {
        previous->next = object;
      } else {
        vm.objects = object;
      }

      freeObject(unreached);
    }
  }
}

코드가 많고 포인터 장난이 좀 많다는 것을 알지만, 일단 자세히 살펴보면 별것 아닙니다. 외부 while 루프는 힙에 있는 모든 객체의 연결 리스트를 순회하며 마크 비트를 확인합니다. 객체가 마크되어 있으면(검은색), 그대로 두고 지나갑니다. 마크되어 있지 않으면(흰색), 리스트에서 분리하고 이미 작성한 freeObject() 함수를 사용하여 해제합니다.

여기에 있는 대부분의 다른 코드는 단일 연결 리스트에서 노드를 제거하는 것이 번거롭다는 사실을 다룹니다. 우리는 다음 포인터를 연결 해제할 수 있도록 이전 노드를 계속 기억해야 하며, 첫 번째 노드를 해제하는 엣지 케이스도 처리해야 합니다. 하지만 그 외에는 아주 간단합니다. 즉, 비트가 설정되지 않은 연결 리스트의 모든 노드를 삭제하는 것입니다.

작은 추가 사항이 있습니다:

    if (object->isMarked) {

      object->isMarked = false;

      previous = object;

sweep()이 완료된 후, 남아 있는 유일한 객체는 마크 비트가 설정된 살아있는 검은색 객체입니다. 이것은 올바른 동작이지만, 다음 컬렉션 주기가 시작될 때 모든 객체가 흰색이어야 합니다. 따라서 검은색 객체에 도달할 때마다 다음 실행을 예상하여 지금 바로 비트를 지웁니다.

26 . 5 . 1약한 참조와 문자열 풀

이제 거의 수집을 마쳤습니다. VM에는 메모리에 대한 특이한 요구 사항을 가진 한 가지 부분이 남아 있습니다. clox에 문자열을 추가했을 때 VM이 모든 문자열을 인터닝(intern)하도록 만들었던 것을 기억할 것입니다. 이는 VM이 힙의 모든 문자열에 대한 포인터를 포함하는 해시 테이블을 가지고 있다는 것을 의미합니다. VM은 이를 사용하여 문자열의 중복을 제거합니다.

마크 단계에서 우리는 VM의 문자열 테이블을 의도적으로 루트의 소스로 취급하지 않았습니다. 만약 그랬다면, 어떤 문자열도 결코 수집되지 않았을 것입니다. 문자열 테이블은 계속해서 커질 것이고 운영 체제에 단 한 바이트의 메모리도 돌려주지 않을 것입니다. 이는 좋지 않습니다.

동시에, 만약 GC가 문자열을 해제하도록 허용한다면, VM의 문자열 테이블은 해제된 메모리에 대한 매달린 포인터(dangling pointer)로 남게 될 것입니다. 이는 훨씬 더 나쁠 것입니다.

문자열 테이블은 특별하며, 이를 위한 특별한 지원이 필요합니다. 특히, 특별한 종류의 참조가 필요합니다. 테이블은 문자열을 참조할 수 있어야 하지만, 그 연결은 접근성을 결정할 때 루트로 간주되어서는 안 됩니다. 이는 참조된 객체가 해제될 수 있음을 의미합니다. 이러한 일이 발생하면 매달린 참조도 수정되어야 합니다. 마치 마법처럼 스스로 지워지는 포인터와 같습니다. 이러한 특정 의미론 집합은 충분히 자주 발생하여 약한 참조(weak reference)라는 이름으로 불립니다.

우리는 마킹 중에 문자열 테이블을 탐색하지 않는다는 사실 덕분에 문자열 테이블의 독특한 동작 중 절반을 이미 암묵적으로 구현했습니다. 이는 문자열이 접근 가능한 상태를 강제하지 않는다는 것을 의미합니다. 남은 부분은 해제된 문자열에 대한 모든 매달린 포인터를 제거하는 것입니다.

접근 불가능한 문자열에 대한 참조를 제거하려면, 어떤 문자열이 접근 불가능한지 알아야 합니다. 마크 단계가 완료될 때까지는 이를 알 수 없습니다. 그러나 스윕 단계가 끝날 때까지 기다릴 수는 없습니다. 그때가 되면 객체(및 해당 마크 비트)는 더 이상 존재하지 않아 확인할 수 없기 때문입니다. 따라서 적절한 시점은 마킹 단계와 스윕 단계 사이입니다.

  traceReferences();

  tableRemoveWhite(&vm.strings);

  sweep();

곧 삭제될 문자열을 제거하는 로직은 "table" 모듈의 새로운 함수에 있습니다.

ObjString* tableFindString(Table* table, const char* chars,
                           int length, uint32_t hash);

void tableRemoveWhite(Table* table);

void markTable(Table* table);

구현은 다음과 같습니다:

void tableRemoveWhite(Table* table) {
  for (int i = 0; i < table->capacity; i++) {
    Entry* entry = &table->entries[i];
    if (entry->key != NULL && !entry->key->obj.isMarked) {
      tableDelete(table, entry->key);
    }
  }
}

테이블의 모든 엔트리를 순회합니다. 문자열 intern 테이블은 각 엔트리의 키만 사용합니다. 기본적으로 해시 맵이 아니라 해시 셋입니다. 만약 키 문자열 객체의 마크 비트가 설정되어 있지 않다면, 그것은 곧 쓸려 사라질 흰색 객체입니다. 우리는 먼저 해시 테이블에서 그것을 삭제하여 매달린 포인터를 볼 일이 없도록 합니다.

26 . 6언제 수집할 것인가

이제 우리는 완전히 작동하는 마크-스윕 가비지 컬렉터를 가졌습니다. 스트레스 테스트 플래그가 활성화되면 항상 호출되며, 로깅도 활성화되어 있으므로 컬렉터가 작동하여 메모리를 회수하는 것을 볼 수 있습니다. 하지만 스트레스 테스트 플래그가 꺼져 있으면 전혀 실행되지 않습니다. 이제 정상적인 프로그램 실행 중에 컬렉터를 언제 호출해야 할지 결정할 때입니다.

제가 아는 한, 이 질문은 문헌에서 제대로 답을 주지 못합니다. 가비지 컬렉터가 처음 발명되었을 때, 컴퓨터는 아주 작은 고정된 양의 메모리를 가지고 있었습니다. 초기 GC 논문 중 상당수는 몇 천 워드의 메모리(즉, 대부분의 메모리)를 따로 할당해두고 메모리가 부족해질 때마다 컬렉터를 호출한다고 가정했습니다. 간단했습니다.

현대 기계는 기가바이트의 물리적 RAM을 가지고 있으며, 운영 체제의 훨씬 더 큰 가상 메모리 추상화 뒤에 숨겨져 있고, 이 메모리는 모두 자신의 메모리 조각을 위해 싸우는 다른 많은 프로그램들과 공유됩니다. 운영 체제는 프로그램이 원하는 만큼 요청하도록 허용하고, 물리적 메모리가 가득 차면 디스크에서 페이지를 들락날락하게 합니다. 메모리가 정말로 "고갈"되는 일은 없고, 그저 점점 느려질 뿐입니다.

26 . 6 . 1지연 시간(Latency)과 처리량(Throughput)

이제 GC를 "해야만 할 때까지" 기다리는 것은 더 이상 말이 되지 않으므로, 더 미묘한 타이밍 전략이 필요합니다. 이를 더 정확하게 이해하기 위해, 메모리 관리자의 성능을 측정할 때 사용되는 두 가지 기본 숫자인 처리량(throughput)과 지연 시간(latency)을 소개할 때입니다.

모든 관리형 언어는 명시적인, 사용자 작성 할당 해제에 비해 성능 비용을 지불합니다. 실제로 메모리를 해제하는 데 걸리는 시간은 같지만, GC는 어떤 메모리를 해제할지 파악하는 데 사이클을 소비합니다. 이는 사용자 코드를 실행하고 유용한 작업을 수행하는 데 소비되지 않는 시간입니다. 우리 구현에서는 이것이 마크 단계 전체입니다. 정교한 가비지 컬렉터의 목표는 이러한 오버헤드를 최소화하는 것입니다.

이러한 비용을 더 잘 이해하는 데 사용할 수 있는 두 가지 주요 측정 항목이 있습니다:

• 처리량(Throughput)은 사용자 코드 실행 시간과 가비지 컬렉션 작업 시간의 전체 비율입니다. 예를 들어, clox 프로그램을 10초 동안 실행했고, 그 중 1초를 collectGarbage() 내부에서 보냈다고 가정해 봅시다. 이는 처리량이 90%라는 의미입니다. 즉, 시간의 90%는 프로그램을 실행하는 데, 10%는 GC 오버헤드에 사용되었습니다.

  처리량은 컬렉션 오버헤드의 총 비용을 추적하기 때문에 가장 근본적인 측정치입니다. 다른 모든 것이 동일하다면, 처리량을 최대화하고 싶을 것입니다. 이 챕터 전까지 clox는 GC가 전혀 없었으므로 100% 처리량을 가졌습니다. 이보다 더 나은 성능을 달성하기는 매우 어렵습니다. 물론, 이는 사용자 프로그램이 충분히 오래 실행될 경우 메모리 부족으로 인해 충돌할 수 있다는 사소한 단점이 있었습니다. GC의 목표는 그 "결함"을 수정하면서 가능한 한 처리량 손실을 최소화하는 것으로 볼 수 있습니다.

• 지연 시간(Latency)은 가비지 컬렉션이 진행되는 동안 사용자 프로그램이 완전히 일시 중지되는 가장 긴 연속적인 시간 조각입니다. 이는 컬렉터가 얼마나 "덩어리"로 작동하는지를 측정합니다. 지연 시간은 처리량과는 완전히 다른 측정 항목입니다.

  10초가 걸리는 clox 프로그램의 두 가지 실행을 생각해 봅시다. 첫 번째 실행에서는 GC가 한 번 작동하여 collectGarbage()에서 1초 동안 한 번의 거대한 컬렉션을 수행합니다. 두 번째 실행에서는 GC가 5번 호출되었고, 각각 1/5초씩 걸립니다. 컬렉션에 소요된 총 시간은 여전히 1초이므로, 두 경우 모두 처리량은 90%입니다. 하지만 두 번째 실행에서는 지연 시간이 1/5초에 불과하며, 첫 번째 실행보다 5배 적습니다.

비유를 좋아한다면, 여러분의 프로그램이 고객에게 갓 구운 빵을 파는 빵집이라고 상상해 보세요. 처리량은 하루 동안 고객에게 제공할 수 있는 따뜻하고 바삭한 바게트의 총 개수입니다. 지연 시간은 가장 운 없는 고객이 서빙되기 전에 줄을 서서 기다려야 하는 시간입니다.

가비지 컬렉터를 실행하는 것은 빵집을 일시적으로 닫고 모든 그릇을 정리하고, 더러운 것과 깨끗한 것을 분류한 다음, 사용한 그릇을 씻는 것과 같습니다. 이 비유에서 우리는 전담 식기세척기가 없으므로, 이 작업이 진행되는 동안에는 빵 굽기가 전혀 이루어지지 않습니다. 제빵사가 설거지를 하고 있습니다.

하루에 빵을 덜 파는 것도 나쁜 일이고, 특정 고객이 모든 설거지를 하는 동안 앉아서 기다리게 하는 것도 좋지 않습니다. 목표는 처리량을 최대화하고 지연 시간을 최소화하는 것이지만, 빵집 안에서도 공짜 점심은 없습니다. 가비지 컬렉터는 얼마나 많은 처리량을 희생하고 얼마나 많은 지연 시간을 허용할지 사이에서 다른 절충점을 만듭니다.

이러한 절충점을 만들 수 있다는 것은 유용합니다. 왜냐하면 사용자 프로그램마다 다른 요구 사항이 있기 때문입니다. 테라바이트의 데이터로부터 보고서를 생성하는 야간 배치 작업은 가능한 한 빨리 많은 작업을 완료해야 합니다. 처리량이 왕입니다. 반면에, 사용자 스마트폰에서 실행되는 앱은 사용자 입력에 항상 즉시 반응하여 화면 드래그가 버터처럼 부드럽게 느껴져야 합니다. GC가 힙을 어지럽히는 몇 초 동안 앱이 멈출 수는 없습니다.

가비지 컬렉터 개발자로서, 컬렉션 알고리즘 선택을 통해 처리량과 지연 시간 간의 절충점 일부를 제어할 수 있습니다. 하지만 단일 알고리즘 내에서도 컬렉터가 얼마나 자주 실행되는지에 대해 많은 제어권을 가집니다.

우리의 컬렉터는 스톱-더-월드 GC(stop-the-world GC)입니다. 이는 전체 가비지 컬렉션 프로세스가 완료될 때까지 사용자 프로그램이 일시 중지된다는 것을 의미합니다. 컬렉터를 실행하기 전에 오랫동안 기다린다면, 많은 수의 죽은 객체가 축적될 것입니다. 이는 컬렉터가 실행되는 동안 매우 긴 일시 중지를 유발하고, 따라서 높은 지연 시간을 초래합니다. 그러므로 분명히 우리는 컬렉터를 정말 자주 실행하고 싶습니다.

하지만 컬렉터가 실행될 때마다 살아있는 객체를 방문하는 데 시간을 보냅니다. 이는 유용한 일을 실제로 하지 않습니다 (잘못 삭제되지 않도록 보장하는 것 외에는). 살아있는 객체를 방문하는 시간은 메모리를 해제하지 않는 시간이며, 사용자 코드를 실행하지 않는 시간이기도 합니다. 만약 GC를 정말 자주 실행한다면, 사용자 프로그램은 VM이 수집할 새로운 가비지를 생성할 시간조차 없을 것입니다. VM은 동일한 살아있는 객체 집합을 계속해서 강박적으로 재방문하는 데 모든 시간을 보낼 것이고, 처리량은 저하될 것입니다. 그러므로 분명히 우리는 컬렉터를 아주 가끔 실행하고 싶습니다.

사실, 우리는 중간쯤 되는 것을 원하며, 컬렉터 실행 빈도는 지연 시간과 처리량 간의 절충점을 조절하는 주요 조절 장치 중 하나입니다.

26 . 6 . 2자기 조정 힙

우리는 GC가 지연 시간을 최소화하기에 충분히 자주 실행되면서도 적절한 처리량을 유지하기에 충분히 드물게 실행되기를 원합니다. 하지만 사용자 프로그램이 얼마나 많은 메모리를 필요로 하고 얼마나 자주 할당하는지 알 수 없을 때 이 두 가지 사이의 균형을 어떻게 찾을 수 있을까요? GC 튜닝 매개변수를 노출하여 사용자에게 문제를 떠넘길 수 있습니다. 많은 VM이 이렇게 합니다. 하지만 GC 개발자인 우리도 제대로 튜닝하는 방법을 모른다면, 대부분의 사용자도 모를 가능성이 높습니다. 그들은 합리적인 기본 동작을 받을 자격이 있습니다.

솔직히 말씀드리자면, 이것은 저의 전문 분야가 아닙니다. 저는 여러 전문 GC 해커들(이것만으로도 평생 직업을 만들 수 있습니다)과 이야기를 나누고 많은 문헌을 읽어봤지만, 제가 얻은 모든 답변은  . . . 모호했습니다. 제가 결국 선택한 전략은 일반적이고 꽤 간단하며 (바라건대!) 대부분의 용도에 충분할 것입니다.

이 아이디어는 컬렉터 빈도가 힙의 실제 크기에 따라 자동으로 조정된다는 것입니다. VM이 할당한 관리형 메모리의 총 바이트 수를 추적합니다. 특정 임계값을 넘어서면 GC를 트리거합니다. 그 후, 남아 있는 메모리 바이트 수, 즉 해제되지 않은 바이트 수를 기록합니다. 그런 다음 임계값을 그보다 큰 값으로 조정합니다.

결과적으로, 활성 메모리 양이 증가함에 따라, 늘어나는 활성 객체 더미를 다시 탐색하여 처리량을 희생하는 것을 피하기 위해 컬렉션을 덜 자주 수행합니다. 활성 메모리 양이 줄어들면, 너무 오래 기다려서 지연 시간을 너무 많이 잃지 않기 위해 컬렉션을 더 자주 수행합니다.

이 구현에는 VM에 두 개의 새로운 장부 관리 필드가 필요합니다.

  ObjUpvalue* openUpvalues;

  size_t bytesAllocated;
  size_t nextGC;

  Obj* objects;

첫 번째는 VM이 할당한 관리형 메모리의 총 바이트 수의 누계입니다. 두 번째는 다음 컬렉션을 트리거하는 임계값입니다. VM이 시작할 때 이를 초기화합니다.

  vm.objects = NULL;

  vm.bytesAllocated = 0;
  vm.nextGC = 1024 * 1024;

  vm.grayCount = 0;

여기서 시작 임계값은 임의적입니다. 우리가 다양한 동적 배열에 대해 선택했던 초기 용량과 비슷합니다. 목표는 처음 몇 번의 GC를 너무 빨리 트리거하지 않으면서도 너무 오래 기다리지 않는 것입니다. 만약 실제 Lox 프로그램이 있다면, 이를 프로파일링하여 튜닝할 수 있었을 것입니다. 하지만 장난감 프로그램밖에 없으므로 그냥 숫자를 선택했습니다.

메모리를 할당하거나 해제할 때마다 카운터를 해당 델타만큼 조정합니다.

void* reallocate(void* pointer, size_t oldSize, size_t newSize) {

  vm.bytesAllocated += newSize - oldSize;

  if (newSize > oldSize) {

총량이 한계를 넘어서면 컬렉터를 실행합니다.

    collectGarbage();
#endif

    if (vm.bytesAllocated > vm.nextGC) {
      collectGarbage();
    }

  }

이제, 마침내 우리 가비지 컬렉터는 숨겨진 진단 플래그가 활성화되지 않은 상태에서 사용자가 프로그램을 실행할 때 실제로 무언가를 합니다. 스윕 단계는 reallocate()를 호출하여 객체를 해제하고, 이는 bytesAllocated 값을 낮춥니다. 따라서 컬렉션이 완료된 후에는 얼마나 많은 활성 바이트가 남아 있는지 알 수 있습니다. 우리는 그 값을 기반으로 다음 GC의 임계값을 조정합니다.

  sweep();

  vm.nextGC = vm.bytesAllocated * GC_HEAP_GROW_FACTOR;

#ifdef DEBUG_LOG_GC

임계값은 힙 크기의 배수입니다. 이렇게 하면 프로그램이 사용하는 메모리 양이 증가함에 따라, 더 커진 활성 객체 집합을 다시 탐색하는 데 소요되는 총 시간을 제한하기 위해 임계값이 더 멀리 이동합니다. 이 챕터의 다른 숫자들과 마찬가지로, 스케일링 팩터는 기본적으로 임의적입니다.

#endif

#define GC_HEAP_GROW_FACTOR 2

void* reallocate(void* pointer, size_t oldSize, size_t newSize) {

실제 프로그램을 벤치마킹할 수 있다면 구현 시 이 값을 조정하고 싶을 것입니다. 지금은 적어도 가지고 있는 일부 통계들을 로깅할 수 있습니다. 컬렉션 전에 힙 크기를 캡처합니다.

  printf("-- gc begin\n");

  size_t before = vm.bytesAllocated;

#endif

그리고 마지막에 결과를 출력합니다.

  printf("-- gc end\n");

  printf("   collected %zu bytes (from %zu to %zu) next at %zu\n",
         before - vm.bytesAllocated, before, vm.bytesAllocated,
         vm.nextGC);

#endif

이렇게 하면 가비지 컬렉터가 실행되는 동안 얼마나 많은 작업을 수행했는지 확인할 수 있습니다.

26 . 7가비지 컬렉션 버그

이론적으로는 이제 모든 작업이 끝났습니다. GC가 있고, 주기적으로 작동하여 수집할 수 있는 것을 수집하고 나머지는 남겨둡니다. 이것이 일반적인 교과서였다면, 우리는 손의 먼지를 털어내고 우리가 만든 흠 없는 대리석 건축물의 부드러운 빛을 쬐었을 것입니다.

하지만 저는 여러분에게 프로그래밍 언어의 이론뿐만 아니라 때로는 고통스러운 현실도 가르치고자 합니다. 저는 썩은 통나무를 뒤집어 그 밑에 사는 끔찍한 벌레들을 보여줄 것입니다. 가비지 컬렉터 버그는 정말로 가장 역겨운 무척추동물 중 일부입니다.

컬렉터의 임무는 죽은 객체를 해제하고 살아있는 객체를 보존하는 것입니다. 양쪽 방향 모두에서 실수를 저지르기 쉽습니다. VM이 필요 없는 객체를 해제하지 못하면, 서서히 메모리 누수가 발생합니다. 사용 중인 객체를 해제하면, 사용자 프로그램이 유효하지 않은 메모리에 접근할 수 있습니다. 이러한 실패는 종종 즉시 충돌을 일으키지 않아서, 버그를 찾기 위해 시간을 거슬러 추적하기 어렵게 만듭니다.

이는 컬렉터가 언제 실행될지 알 수 없다는 사실 때문에 더욱 어려워집니다. 결국 메모리를 할당하는 모든 호출은 VM 내에서 컬렉션이 발생할 수 있는 지점입니다. 마치 의자 앉히기 놀이와 같습니다. 언제든지 GC가 음악을 멈출 수 있습니다. 우리가 유지하고 싶은 모든 힙 할당 객체는 스윕 단계가 게임에서 쫓아내기 전에 빠르게 의자를 찾아야 합니다. 즉, 루트로 표시되거나 다른 객체의 참조로 저장되어야 합니다.

GC 자체가 보지 못하는 객체를 VM이 나중에 어떻게 사용할 수 있을까요? VM은 어떻게 그것을 찾을 수 있을까요? 가장 일반적인 답변은 C 스택의 일부 지역 변수에 저장된 포인터를 통하는 것입니다. GC는 VM의 값 스택과 CallFrame 스택을 탐색하지만, C 스택은 GC에게 숨겨져 있습니다.

이전 챕터에서는 VM의 값 스택에 객체를 푸시하고, 약간의 작업을 한 다음, 다시 스택에서 팝하는 겉보기에는 무의미한 코드를 작성했습니다. 대부분의 경우, 저는 이것이 GC의 이점을 위한 것이라고 말했습니다. 이제 그 이유를 알 것입니다. 푸시와 팝 사이의 코드는 잠재적으로 메모리를 할당하여 GC를 트리거할 수 있습니다. 컬렉터의 마크 단계가 객체를 찾아 활성 상태로 유지할 수 있도록 객체가 값 스택에 있는지 확인해야 했습니다.

저는 clox 구현 전체를 챕터로 나누고 글을 쓰기 전에 작성했기 때문에, 이러한 모든 문제점을 찾고 대부분의 버그를 제거할 시간이 충분했습니다. 이 챕터 초반에 추가한 스트레스 테스트 코드와 꽤 괜찮은 테스트 스위트가 매우 도움이 되었습니다.

하지만 대부분만 수정했습니다. 몇 가지는 남겨두었습니다. 실제 상황에서 이런 버그를 만나는 것이 어떤 느낌인지 여러분에게 힌트를 주고 싶었기 때문입니다. 스트레스 테스트 플래그를 활성화하고 몇 가지 Lox 예제 프로그램을 실행해 보면, 아마도 몇 가지 버그를 발견할 수 있을 것입니다. 시도해 보고 스스로 고칠 수 있는지 확인해 보세요.

26 . 7 . 1상수 테이블에 추가하기

첫 번째 버그를 만날 가능성이 매우 높습니다. 각 청크가 소유하는 상수 테이블은 동적 배열입니다. 컴파일러가 현재 함수의 테이블에 새로운 상수를 추가할 때, 해당 배열이 늘어나야 할 수도 있습니다. 상수 자체도 문자열이나 중첩 함수와 같은 힙 할당 객체일 수 있습니다.

상수 테이블에 추가되는 새 객체는 addConstant()로 전달됩니다. 그 순간, 객체는 C 스택의 해당 함수의 매개변수에서만 찾을 수 있습니다. 해당 함수는 객체를 상수 테이블에 추가합니다. 만약 테이블이 충분한 용량을 가지고 있지 않아 늘어나야 한다면, reallocate()를 호출합니다. 그러면 GC가 트리거되고, GC는 새 상수 객체를 마킹하는 데 실패하여, 우리가 테이블에 추가할 기회를 갖기도 전에 객체를 스윕해 버립니다. 결국 충돌이 발생합니다.

이전 다른 곳에서 보셨듯이, 해결책은 상수를 임시로 스택에 푸시하는 것입니다.

int addConstant(Chunk* chunk, Value value) {

  push(value);

  writeValueArray(&chunk->constants, value);

상수 테이블에 객체가 포함되면 스택에서 팝합니다.

  writeValueArray(&chunk->constants, value);

  pop();

  return chunk->constants.count - 1;

GC가 루트를 마킹할 때, 컴파일러 체인을 따라가서 각 함수의 함수를 마킹하므로, 이제 새로운 상수는 접근 가능합니다. "chunk" 모듈에서 VM을 호출하려면 include가 필요합니다.

#include "memory.h"

#include "vm.h"

void initChunk(Chunk* chunk) {

26 . 7 . 2문자열 인터닝

여기 또 다른 비슷한 예시가 있습니다. clox에서는 모든 문자열이 인터닝되므로, 새로운 문자열을 생성할 때마다 그것을 intern 테이블에도 추가합니다. 이제 어떻게 될지 짐작이 가실 겁니다. 문자열이 새로 생성되었으므로, 어디에서도 접근 가능하지 않습니다. 그리고 문자열 풀의 크기를 조정하는 것은 컬렉션을 트리거할 수 있습니다. 다시 한번, 우리는 먼저 문자열을 스택에 임시로 저장합니다.

  string->chars = chars;
  string->hash = hash;

  push(OBJ_VAL(string));

  tableSet(&vm.strings, string, NIL_VAL);

그리고 테이블에 안전하게 안착한 후에는 스택에서 다시 팝합니다.

  tableSet(&vm.strings, string, NIL_VAL);

  pop();

  return string;
}

이렇게 하면 테이블 크기 조정 중에 문자열이 안전하게 유지됩니다. 일단 이 과정을 통과하면 allocateString()은 이를 호출자에게 반환하며, 호출자는 다음 힙 할당이 발생하기 전에 문자열이 계속 접근 가능한지 확인할 책임을 지게 됩니다.

26 . 7 . 3문자열 연결하기

마지막 예시입니다. 인터프리터에서 OP_ADD 명령어는 두 문자열을 연결하는 데 사용될 수 있습니다. 숫자와 마찬가지로 스택에서 두 피연산자를 팝하고, 결과를 계산한 다음, 새로운 값을 스택에 다시 푸시합니다. 숫자의 경우에는 완벽하게 안전합니다.

그러나 두 문자열을 연결하려면 힙에 새로운 문자 배열을 할당해야 하며, 이는 다시 GC를 트리거할 수 있습니다. 그 시점에 우리는 이미 피연산자 문자열을 스택에서 팝했기 때문에, 마크 단계에서 누락되어 쓸려 사라질 수 있습니다. 스택에서 즉시 팝하는 대신, 피크(peek)를 사용합니다.

static void concatenate() {

  ObjString* b = AS_STRING(peek(0));
  ObjString* a = AS_STRING(peek(1));

  int length = a->length + b->length;

이렇게 하면 결과 문자열을 생성하는 동안에도 피연산자들이 스택에 남아 있습니다. 작업이 완료되면 안전하게 피연산자를 팝하고 결과로 대체할 수 있습니다.

  ObjString* result = takeString(chars, length);

  pop();
  pop();

  push(OBJ_VAL(result));

이것들은 모두 꽤 쉬웠습니다. 특히 제가 수정할 곳을 알려주었기 때문입니다. 실제로는 찾는 것이 어려운 부분입니다. 여러분이 보는 것은 있어야 할 객체가 없다는 것뿐입니다. 다른 버그처럼 어떤 문제를 야기하는 코드를 찾는 것이 아닙니다. 문제를 방지하지 못하는 코드의 부재를 찾는 것이며, 이는 훨씬 더 어려운 탐색입니다.

하지만 적어도 지금은 안심해도 좋습니다. 제가 아는 한, clox의 모든 컬렉션 버그를 찾아냈고, 이제 작동하고 견고하며 자체 튜닝되는 마크-스윕 가비지 컬렉터를 갖게 되었습니다.