# [[Cheney's Algorithm|Cheney's Algorithm]]

## 📌 Brief Summary
Cheney's Algorithm은 V8 자바스크립트 엔진의 마이너 가비지 컬렉터인 스캐빈저(Scavenger)에서 메모리를 관리하기 위해 사용하는 가비지 컬렉션 알고리즘입니다 [1, 2]. 이 알고리즘은 메모리의 '새로운 공간(New-space)'을 동일한 크기를 가진 'from-space'와 'to-space'라는 두 개의 반공간(Semi-space)으로 나누어 작동합니다 [1, 2]. 살아있는 객체만을 from-space에서 to-space로 복사하고 압축(compact)함으로써, 빠른 메모리 할당과 캐시 지역성 향상을 달성합니다 [1].

## 📖 Core Content
- **반공간(Semi-space) 구조 및 역할 교환**: 알고리즘은 할당 공간이 가득 찰 때 to-space와 from-space의 역할을 맞바꾸는 것으로 시작합니다 [1]. 이를 통해 모든 기존 객체는 from-space에 위치하게 되며, 이후 시스템은 살아있는 객체만을 찾아내어 to-space로 복사하거나 '오래된 공간(old-space)'으로 승격(promote)시킵니다 [1].
- **포인터를 활용한 너비 우선 탐색(BFS)**: 알고리즘은 내부적으로 to-space를 가리키는 두 개의 포인터를 유지합니다 [3]. 
  - `allocationPtr`: 다음 객체를 할당할 위치의 포인터입니다 [3].
  - `scanPtr`: 살아있는 포인터를 찾기 위해 스캔할 다음 객체의 포인터입니다 [3].
  - 이 두 포인터는 논리적으로 너비 우선 탐색(BFS) 대기열(Queue)의 맨 앞과 맨 뒤와 같은 역할을 합니다 [3].
- **객체 스캔 및 복사 과정**:
  1. 루트(roots)에서 도달할 수 있는 새로운 공간의 객체들을 복사하여 알고리즘을 초기화합니다 [4].
  2. `scanPtr`를 증가시켜 대기열에서 객체를 하나씩 꺼내고, 해당 객체의 내부 포인터들을 추적합니다 [4].
  3. 발견한 포인터가 아직 복사되지 않은 from-space의 객체를 가리킨다면, `allocationPtr`를 증가시켜 해당 객체를 to-space의 끝으로 복사하고 기존 객체의 첫 번째 워드(word)에 새 복사본을 가리키는 전달 주소(forwarding address)를 남깁니다 [4].
  4. 만약 포인터가 이미 복사된 from-space의 객체(전달 주소가 존재하는 객체)를 가리킨다면, 해당 포인터가 to-space의 새로운 복사본을 가리키도록 업데이트합니다 [4].
- **종료 조건 및 가비지 처리**: `scanPtr`가 `allocationPtr`에 도달하여 더 이상 처리할 객체가 남지 않게 되면 알고리즘은 종료됩니다 [5]. 이 시점에 from-space에 남아있는 모든 데이터는 가비지(쓰레기)로 간주되어 메모리가 해제되거나 다른 목적으로 재사용됩니다 [5].

## 🔗 Knowledge Connections
- **Related Topics:** Scavenge (Minor GC), Semi-space Design, [[Garbage Collection|Garbage Collection]]
- **Projects/Contexts:** [[V8 JavaScript Engine|V8 JavaScript Engine]]
- **Contradictions/Notes:** 과거의 V8 버전들은 동기식(synchronous) 구조의 기본 Cheney's algorithm을 사용했으나, V8 v6.2 이후부터는 다중 코어 환경의 이점을 활용하기 위해 Halstead semispace copying collector와 유사한 방식의 병렬 스캐빈저(Parallel Scavenger) 알고리즘으로 발전하여 사용되고 있습니다 [6].

---
*Last updated: 2026-04-19*