러스트에 보수적 가비지 컬렉션을 통합한 Alloy의 설계와 구현을 소개한다. 기존 소멸자 재사용을 가능케 하는 파이널라이저 안전성 분석, 파이널라이저 생략, 조기 파이널라이저 방지 등 핵심 기법과 성능 평가를 다룬다.
October, 2025
Abstract 러스트(Rust)는 비-GC(가비지 컬렉션) 언어이지만, GC가 없다는 사실은 공유 소유권이 필요한 자료구조를 표현할 때 난해함과 비효율(혹은 둘 다)을 초래한다. 본 논문에서는 러스트를 위한 새로운 GC 설계 및 구현 Alloy를 탐구한다. Alloy는 기존 접근과 달리, 러스트의 소멸자(destructor)를 자동으로 GC 파이널라이저로 재사용할 수 있게 한다. 이는 기존 코드와의 통합성을 높이지만, 놀라운 건전성(safety) 및 성능상의 문제를 야기한다. Alloy는 핵심 문제들에 대해 다음의 새로운 해법을 제시한다: 파이널라이저 안전성 분석(finalizer safety analysis)은 파이널라이저로 자동 재사용하면 안 되는 불건전 소멸자를 거부한다; 파이널라이저 생략(finalizer elision)은 불필요한 파이널라이저를 최적화로 제거한다; 조기 파이널라이저 방지(premature finalizer prevention)는 파이널라이저가 증명 가능하게 안전할 때만 실행되도록 보장한다.
프로그래밍 언어를 분류하는 방식 중 하나는 GC(가비지 컬렉션) 사용 여부다. GC 언어는 암묵적 메모리 관리를 제공하고, 비-GC 언어는 명시적 메모리 관리(예: C의 malloc/free)를 요구한다. 러스트는 어파인(affine) 타입[25, p. 5]과 소유권(ownership)을 사용하므로 이 분류에 깔끔히 들어맞지 않는다: GC 언어는 아니지만, 범위 기반의 암묵적 메모리 관리를 제공한다. 러스트 프로그램의 많은 부분은 GC 언어만큼 간결하지만, 소유권 모델은 다중 소유자가 필요한 자료구조(예: 이중 연결 리스트)에 대해 공유 소유권(shared ownership)을 표현하기에 경직되어 있다. 참조 카운팅 같은 우회책은 프로그래머의 부담을 늘리고, 실수 가능성을 키우며, 성능 비용이 따르는 경우가 많다.
이러한 문제를 피하려는 시도로, 현재 러스트에는 여러 GC 구현이 존재한다(예: [2, 11, 14, 32, 33]). 대부분은 사용자에게 보이는 타입 Gc<T>를 도입한다. 이는 타입 T의 값 v를 ‘GC 힙’으로 옮기며, Gc<T>는 GC 힙의 v를 가리키는 포인터를 감싼 래퍼다. 사용자는 Gc<T>를 복제(clone)하고 역참조해 &T(타입 안전 포인터)로 얻을 수 있다. 프로그램의 루트(예: 스택의 변수)로부터 직접 또는 간접으로 v를 가리키는 Gc<T> 래퍼를 찾을 수 없게 되면, GC 힙 상 v의 메모리를 회수할 수 있다.
만족스러운 러스트용 GC의 설계·구현을 찾기는 어려웠고, 그 시도 횟수가 이를 암시한다. 우리는 두 가지 근본적인 도전을 식별한다: Gc<T>에 러스트스러운(idiomatic)이고 완결적인 API를 제공하는 법, 그리고 파이널라이저(값이 GC에 의해 수거되기 직전에 실행되는 코드)를 안전하고, 빠르고, 인체공학적으로 만드는 법이다.
struct GcNode { value: u8, nbr: Option<Gc<RefCell<GcNode>>>}
impl Drop for GcNode { fn drop(&mut self) { println!("drop {}", self.value); } }
fn main() {
let mut gc1 = Gc::new(RefCell::new(GcNode { value: 1, nbr: None } ));
gc1.borrow_mut().nbr = Some(gc1);
let gc2 = Gc::new(RefCell::new(GcNode { value: 2, nbr: None } ));
gc2.borrow_mut().nbr = Some(gc2);
gc1 = gc2;
force_gc();
println!("{} {}", gc1.borrow().value, gc1.borrow().nbr.unwrap().borrow().value);
}
리스팅 1. Alloy 예제: Gc<T>와 소멸자의 파이널라이저 재사용. 그래프를 모델링하는 타입 GcNode를 정의한다: 8비트 정수 값과 이웃 노드를 가리키는 널 가능 참조(표준 Option)를 저장한다(1행). 일반 러스트 소멸자를 추가하고, Alloy는 Gc<T> 안에서 GcNode가 쓰일 때 이를 파이널라이저로 사용한다(2행). main에서 첫 번째 GC된 노드를 만든다(5행). RefCell을 이용해 변경 가능하게 만들고(RefCell::borrow_mut은 러스트의 정적 규칙을 훼손하는 변경을 런타임에 점검) 자기 자신으로의 사이클을 만든다(6행). 두 번째 사이클 그래프를 만들고(7–8행) 곧바로 gc1 변수에 대입한다(9행): 이는 Gc<T>를 이동이 아닌 복사한다. 그 결과 첫 번째 사이클 그래프 GcNode{value: 1, ..}는 도달 불가능해지고, 강제 수집 후(10행) 해당 노드는 수집 가능하다. 그 파이널라이저가 후속 실행을 위해 예약되어 나중에 "drop 1"이 출력된다. 완료되면 GC 힙 메모리는 회수된다. 마지막 출력은 "2 2"이다(11행).
본 논문은 러스트를 위한 새로운 GC Alloy를 소개한다: 사용 예는 리스팅 1에 보인다. Alloy는 보수적(conservative) GC(도달 가능한 기계어 워드를 잠재적 포인터로 간주)를 사용하며, 이는 자연스럽게 API 도전을 해결한다. 그러나 파이널라이저 문제는 훨씬 복잡하다: 그 원인과 해결책이 논문의 대부분을 차지한다.
일반 러스트 코드에서는 소멸자(destructor: 값의 메모리가 러스트의 암묵적 관리로 회수되기 직전 실행되는 코드)를 광범위하게 사용한다. 파이널라이저와 소멸자가 동의어처럼 보일 수 있으나, 기존 러스트용 GC들은 소멸자를 파이널라이저로 재사용할 수 없다: 각 타입에 대해 파이널라이저를 수동으로 구현해야 한다. 불행히도 이것도 만만치 않다: T가 외부 라이브러리라면 Gc<T>를 위한 파이널라이저를 구현할 수 없고; 소멸자의 일부는 컴파일러가 자동 생성하지만, 수기 파이널라이저는 이를 수동으로 복제해야 하고; 사용자가 타입의 파이널라이저를 중복 실행하도록 실수할 수 있다. 요컨대 기존 러스트용 GC의 파이널라이저는 매력적이지 않다.
러스트용 GC만이 수기 파이널라이저를 요구하는 것은 아니다. 우리와 가까운 친척인 C++의 GC 제안에서는 소멸자의 파이널라이저 재사용이 해결 불가해 보이는 문제 탓에 배제되었다[8, p. 32]. 우리는 그 문제를 네 가지 범주로 나눈다: (1) 안전한 소멸자 중 일부는 안전한 파이널라이저가 아니다; (2) 파이널라이저가 조기에 실행될 수 있다; (3) 일시 중지된 뮤테이터와 같은 스레드에서 파이널라이저를 실행하면 경쟁 조건과 교착이 발생할 수 있다; (4) 파이널라이저는 소멸자보다 현저히 느리다. 모두 전통적 GC 문제이며, 러스트에서는 더욱 악화된다. #2를 부분적으로 제외하면 기존 해법이 없다.
우리는 대부분의 러스트 소멸자를 만족스럽게 파이널라이저로 재사용할 수 있음을 보인다. 러스트의 독특한 정적 보장을 활용해 오래된 문제에 대한 새로운 해법을 제시한다. 즉 더 나은 러스트용 GC를 얻는 동시에, 미해결 GC 문제의 해법도 얻는다. 해결책은 다음과 같다: (1) 파이널라이저 안전성 분석은 소멸자가 파이널라이저로 사용될 때의 건전성을 정적으로 검증하고 불건전 사례를 거부한다; (2) 조기 파이널라이저 방지는 GC가 값이 죽기 전에 수거되도록 ‘속임’을 방지하는 펜스를 자동 삽입한다; (3) 파이널라이저는 별도 스레드에서 실행한다; (4) 파이널라이저 생략은 파이널라이저가 GC의 일을 중복할 때 이를 정적으로 제거한다.
Alloy 구현은 필연적으로 러스트에 묶이지만, 본 논문의 새 기법 대부분은 어파인 타입과 소유권이라는 일반 성질에 기대고 있다. 일반성을 증명 없이 주장하고 싶지는 않으나, 다른 소유권 기반 언어가 등장한다면 이 기법들이 일반화될 가능성이 높다.
Alloy는 아직 프로덕션 준비가 되지 않았으나, 성능은 충분히 합리적이다: 현재 Alloy가 사용하는 보수적 GC(BDWGC)가 다소 느림을 감안하고 통제했을 때, Alloy 성능은 참조 카운팅 대비 0.74×에서 최악 1.17×까지 변한다. Alloy는 다른 측면(예: 양질의 에러 메시지)에서도 충분히 다듬어져 있어, 관심 있는 이들에게 실질적 전진 경로를 제시하고, 러스트에 GC를 도입하는 것이 좋은 아이디어인지 평가할 수 있게 한다.
본 논문은 네 부분으로 나뉜다: GC와 러스트 배경(2절); Alloy의 기본 설계(3절); 소멸자/파이널라이저의 도전과 해법(4–7절); 평가(8절). 처음 세 부분은 GC와 러스트라는 상충해 보이는 두 영역을 가로지른다. 한 영역에 익숙한 독자가 다른 영역을 익히기에 충분하되 둘 다 지루하지 않도록 하려 노력했으며, 익숙한 부분은 건너뛰길 권한다.
러스트는 어파인 타입과 소유권으로 다음을 정적으로 보장한다: 하나의 값은 단일 소유자(예: 변수)를 갖는다; 소유자는 값을 다른 소유자에게 이동(move, 소유권 영구 이전)할 수 있다; 소유자가 스코프를 벗어나면 소멸자가 실행되고, 해당 메모리가 회수된다. 소유자는 다른 코드에 참조(reference)를 건넬 수 있으나, 다음 정적 제약을 따른다: 하나의 값에는 다수의 불변 참조(&) 또는 단 하나의 가변 참조(&mut)만 존재할 수 있다; 그리고 참조는 소유자보다 오래 살 수 없다. 이 규칙 덕분에 많은 러스트 프로그램은 GC 언어와 동등하게 간결하다. 이는 러스트용 GC 탐구가 지적 자극은 되되 실용 가치는 적을 수도 있음을 시사한다.
그러나 많은 프로그램이 어파인 타입과 소유권 제약에 들어맞지 않는 자료구조를 필요로 한다. 흔히 ‘순환(cyclic) 자료구조’라 부르나, 본 논문에서는 보다 추상적인 ‘공유 소유권’을 사용한다. 이는 순환 자료구조를 포함하되 그에 한정되지 않는다.
공유 소유권을 표현하는 일반적 방법은 표준 라이브러리의 참조 카운팅 타입 Rc<T>를 쓰는 것이다. 많은 자료구조에서 합리적 해법이지만, 어떤 형태의 공유 소유권은 강/약 카운트를 저글링해야 한다. 이는 프로그램을 복잡하게 만들고(리스팅 2 참조) 값의 수명이 과소/과대가 되는 문제를 유발한다.
struct RcNode { value: u8, nbr: Option<Weak<RefCell<RcNode>>> }
impl Drop for RcNode { fn drop(&mut self) { println!("drop {}", self.value); } }
fn main() {
let mut rc1 = Rc::new(RefCell::new(RcNode{value: 1, nbr: None}));
rc1.borrow_mut().nbr = Some(Rc::downgrade(&rc1));
let rc2 = Rc::new(RefCell::new(RcNode{value: 2, nbr: None}));
rc2.borrow_mut().nbr = Some(Rc::downgrade(&rc2));
rc1 = Rc::clone(&rc2);
println!("{} {}", rc1.borrow().value,
rc1.borrow().nbr.as_ref().unwrap().upgrade().unwrap().borrow().value);
}
리스팅 2. 리스팅 1을 표준 참조 카운팅 Rc<T>로 구현. 메모리 누수를 피하려면 노드 간 참조를 약(weak)으로 둔다(1행). 다시 두 개의 순환 그래프를 만들고(5–8행) Rc::downgrade로 약 참조를 만든다(6, 8행). Rc<T>는 복사 불가이므로 rc1과 rc2가 같은 순환 그래프를 가리키게 하려면 수동 clone이 필요하다(9행). 이웃 접근은 약 참조 업그레이드가 필요해 섬세하다(11행). Weak로 내렸다가(누수 방지) 다시 Rc로 올리는 과정(unwap 필요)은 리스팅 1 대비 큰 복잡도를 유발한다: 리스팅 1의 11행과 위 10–11행을 비교하라.
또 다른 해법은 값을 벡터에 저장하고 정수 인덱스로 접근하는 것이다. 이런 인덱스는 정상 참조보다 기계 포인터에 가깝다: 인덱스가 오래되거나, 댕글링하거나, 애초 유효하지 않을 수 있다. 프로그래머는 미사용 값 탐지, 압축(compaction) 등을 수동 처리해야 한다. 즉 프로그래머가 반(半)GC를 스스로 구현하게 된다. 변형으로 아레나(arenas)가 있는데, 값들을 점차 축적하다 한 번에 모두 해제한다: 값이 너무 일찍 해제되지는 않지만, 반대로 수명이 불필요하게 늘어나는 경향이 있다.
타입 기반 접근으로 GhostCell[35]은 브랜딩(branding)을 사용해, 특정 시점에 프로그램의 한 부분만이 공유 소유권 자료구조에 접근하도록 정적으로 보장한다. 이는 여러 소유자(예: 서로 다른 스레드)가 자료구조의 서로소 부분을 동시에 접근해야 하는 흔한 사용례를 배제한다.
간과되기 쉽지만, 일부 우회책(예: Rc<T>)은 안전하지 않은(unsafe) 러스트에 의존한다. 실용적으로 널리 쓰이는 코드(비록 기술적으로 unsafe라도)는 충분히 검증돼 실용적으로 신뢰 가능하다고 가정한다. 그러나 프로그래머가 unsafe로 구현한 ‘새’ 해법은 같은 신뢰 수준에 즉시 도달하기 어렵다.
모든 러스트 프로그램이 GC로 개선된다고 믿지는 않는다. 그러나 이미 존재하는 다양한 우회책과 새로운 우회책을 만드는 어려움은, GC로 이득을 볼 하위집합이 있음을 시사한다.
GC는 유서 깊은 분야로 낯설거나 직관적이지 않은 용어가 많다. 우리는 주로 Jones 등[19]의 용어를 사용하며, 주요 개념을 여기서 정의한다.
GC를 사용하는 프로그램은 뮤테이터(사용자 프로그램)와 콜렉터(GC 자체)로 나뉜다. 어느 시점이든 스레드는 뮤테이터로 실행 중이거나 콜렉터로 실행 중이다. 우리의 맥락에서는 모든 스레드가 적어도 때로는 콜렉터로 실행된다(후술할 이유로 어떤 스레드는 항상 콜렉터다). 추적과 회수는 컬렉션(collection) 단계 동안 수행된다. 우리의 컬렉션은 항상 스톱 더 월드(stop-the-world)로, 뮤테이터 코드를 실행 중인 모든 스레드를 일시 중지한 채 수집이 진행된다.
추적(tracing) GC는 메모리를 스캔해 루트에서 도달 가능한 값을 찾는다: 루트에서 도달 불가능한 값(사이클 포함)은 회수(reclaim)할 수 있다. 대비적으로 순수 참조 카운팅 GC는 메모리를 스캔하지 않으므로 사이클을 이루는 값을 해제할 수 없다. 점점 더 많은 GC 구현이 다수 기법을 혼합하지만[3], 단순화를 위해 달리 명시하지 않으면 한 가지 기법만 사용한다고 가정한다. 편의상 ‘GC’를 ‘추적 GC’의 약어로 쓴다; 다른 종류(예: 참조 카운팅)를 다룰 때는 명시한다.
Gc<T>로 할당된 메모리를 GC 힙이라 부른다. 하나의 GC 힙 상 값에 다수 포인터/래퍼가 붙을 수 있지만, 모호하지 않은 한, 우리는 ‘GC 값’이란 용어를 Gc<T>에 싸인 포인터와 해당 힙 상 값을 모두 지칭하는 데 쓴다.
‘Alloy’는 다음의 결합체를 뜻한다: 러스트 언어 확장; rustc 컴파일러 수정; 그리고 BDWGC를 수정된 rustc로 컴파일된 프로그램의 런타임에 통합한 것.
이 절에서는 Alloy의 기본 설계·구현을 개괄하고, 이후 절에서 심화 주제를 다룬다.
Alloy는 표준 라이브러리 Rc<T>의 API 모델을 따르는 Gc<T> 타입을 제공한다. Rc<T>는 Gc<T>와 개념적으로 유사하고, 러스트 코드에서 널리 쓰이며, 그 API가 러스트 프로그래머의 필요를 반영한다.
사용자가 Gc::new(v)를 호출하면 값 v는 GC 힙으로 이동한다. 반환된 Gc<T>는 v의 새 주소를 가리키는 포인터 래퍼다. 동일한 GC 값에 대해 여러(부분적으로 또는 완전히 중첩된) 참조가 동시에 활성일 수 있다. 러스트의 소유권 시스템을 훼손하지 않기 위해, Gc<T>를 역참조하면 기본 값에 대한 불변 참조(&)를 생성한다. 변경 필요 시 RefCell<T>나 Mutex<T> 같은 내부 가변성(interior mutability) 타입을 사용해야 한다.
Alloy가 명시적으로 지원하는 한 가지는, 러스트에서 참조를 생포인터(raw pointer)로 캐스팅하고 다시 되돌리는 능력이다. 이는 두 가지 주요 방식으로 일어난다. Gc<T>를 &T로 역참조한 뒤, 일반 참조와 마찬가지로 *const T로 변환할 수 있다. 또한 Gc<T>는 into_raw와 from_raw 같은 관용적 함수를 제공해 값↔포인터 변환을 더 고수준으로 감싼다. 참조를 생포인터로 변환하는 능력은 많은 곳(예: C FFI)에서 쓰인다. 우리는 러스트용 GC가 동일한 변환을 허용해야 한다고 믿지만, 이는 러스트가 생포인터를 정수 타입 usize로, 다시 그 반대로 바꾸는 것을 허용하기 때문에 중대한 영향을 낳는다[1].
포인터가 정수로 ‘위장’될 수 있음을 인정한다면, Alloy는 보수적 GC여야만 한다: 기계어 워드의 정수 값을 포인터로 해석했을 때 GC 블록 범위에 속하면, 그 블록을 도달 가능한 것으로 간주하고(전이적으로 스캔) 보존한다. 보수적 GC는 워드가 진짜 포인터인지, 우연히 유효 포인터와 같은 비트열인지 알 수 없으므로 라이브 집합을 과대평가한다. 일반적으로 위양성 비율은 매우 낮다(예: 자바 연구에서 라이브 집합의 0.01% 미만[28]).
보수적 GC는 언어 의미론 상 회색 지대에 위치한다: 많은 언어·컴파일러 내부 의미론에서 보수적 GC는 형식적으로 불건전하며, 또한 일부 언어(러스트 포함)는 포인터에 임의의 비트 조작을 허용해 가리키는 주소를 일시적으로 가린다. 그럼에도 보수적 GC는 널리 쓰인다. 대표적 웹 브라우저 둘도 이를 사용한다: 크롬은 Blink 렌더링 엔진에서[1], 사파리는 JavaScriptCore VM에서[26]. 2025년 현재도 보수적 GC의 대안은 미흡하다: 정밀(precise) GC를 위한 크로스 플랫폼 API가 없고, LLVM 같은 일부 컴파일러의 GC 지원[23]은 불완전하고 버그가 있다. 잠재적 건전성 우려에도 불구, 보수적 GC는 여전히 널리 쓰이는 기술이다.
보수적 GC 덕분에 Alloy는 러스트용 다른 대부분의 GC보다 인체공학적으로 유리한 점이 있다. 다수 구현에서 Gc<T>는 복제만 가능(cloneable)하다. 이런 타입은 복제에 임의의 사용자 코드를 실행해야 할 수 있다. 러스트는 잠재적 런타임 비용을 드러내기 위해 복제를 위한 직접 구문을 제공하지 않고 Rc::clone(&v) 호출을 요구한다. 반면, Alloy의 Gc<T>는 단지 포인터 래퍼이므로 복제 가능(cloneable)일 뿐 아니라 복사 가능(copyable)하다: 바이트 복사만으로 충분하며 임의의 사용자 코드 실행이 불필요하다. 대입(w = v)만으로 복사가 이뤄져, 명시적 clone 호출의 필요가 줄어든다[2]. 이는 단지 문법적 편의가 아니라 의미적 차이를 반영한다: Alloy에서 Gc<T> 복제는 흔히 참조 카운팅에 의존하는 다른 GC 대비 훨씬 싸고 단순하다.
다만 API에서 Rc<T> 대비 분명한 제약이 하나 있다. Rc<T>는 정의상 내부 데이터에 대한 참조 수를 알고 있어(get_mut/make_mut), 런타임에 단일 참조만 존재하면 가변 대여를 허용한다. 반면 Gc<T>는 내부 데이터에 대한 참조 수를 알 수 없다. 8절에서 보듯, 일부 러스트 프로그램은 이 API의 성능 상 이점에 크게 의존한다(일부 경우 ‘카피 온 라이트’를 ‘바로 라이트’로 바꿈).
Alloy의 가장 눈에 띄는 면은 표준 러스트 컴파일러 rustc의 포크와 확장이다. 우리는 rustc 1.79.0을 포크하여, 코어 컴파일러에 약 5,500 LoC를 추가/변경했고, 약 2,250 LoC의 테스트를 추가했다.
Alloy는 가장 널리 이식된 보수적 GC로 알려진 BDWGC[9]를 사용한다. 우리는 BDWGC의 GC_set_finalize_on_demand(1) API를 사용해 파이널라이저를 전용 스레드에서 실행한다.
BDWGC에도 약간의 수정을 가했다. 첫째, BDWGC의 병렬 콜렉터는 Alloy 성능을 악화시켜 비활성화했다. 왜 그런지는 불명확하다: 수집 중 잠금 경합이 크지만 원인을 특정하진 못했다. 둘째, BDWGC는 플랫폼 의존성 때문에 스레드 로컬에 저장된 포인터를 스캔할 수 없다. 다행히 rustc는 LLVM의 TLS 구현을 사용하며, 포인터는 ELF의 PT_TLS 섹션에 저장된다. 우리는 BDWGC가 매 수집마다 이 ELF 섹션을 스캔하도록 수정했다. 셋째, BDWGC는 스레드 생성을 동적으로 가로채 스택을 스캔하지만(부트스트랩 사유로) 우리의 맥락에서는 불가능했다. 우리는 Alloy에서 새 스레드를 BDWGC에 명시적으로 등록하도록 변경했다.
많은 GC 언어에서 ‘소멸자’와 ‘파이널라이저’는 값의 수명 종료 시 실행되는 코드라는 의미로 동의어다. 기존 러스트용 GC에서는 이 둘이 전혀 다른 계층의 코드(즉 본질적으로 상이)다. 반면 Alloy에서는 1차 근사로, 파이널라이저가 소멸자의 진부분집합이라고 볼 수 있다. 이 절에서는 차이를 분해하고, 소멸자를 파이널라이저로 사용할 때의 도전을 설명한다.
러스트에서 값이 드롭(drop: 소유자가 렉시컬 스코프를 벗어날 때)되면 소멸자가 자동 실행된다. 러스트의 소멸자는 C++의 RAII 스타일[30, §14.4]을 가능케 한다: 값이 드롭되면 그 값이 보유한 자원(파일 핸들, 힙 메모리 등)을 해제한다. 소멸자는 러스트 코드에서 빈번하게 사용된다(대략적인 감으로, 벤치마크 모음에서 소스 수준 타입의 약 15%가 소멸자를 가진다).
러스트 소멸자는 두 부분으로 구성되고 다음 순서로 실행된다: 사용자 정의 드롭 메서드(drop method)와 자동 삽입되는 드롭 글루(drop glue). 드롭 메서드는 선택 사항이며 Drop 트레이트의 drop 메서드를 구현해 제공한다. 드롭 글루는 포함된 타입(예: 구조체 필드)의 소멸자를 재귀적으로 호출한다. 흔히 소멸자를 드롭 메서드와 혼동하지만, 드롭 글루도 소멸자의 본질적 일부다. 우리는 소멸자를 드롭 메서드와 드롭 글루를 아우르는 용어로 사용한다.
러스트용 GC의 파이널라이저를 설계할 때 선택지는 여러 층위가 있다. 곧 보겠지만(§4.1), 파이널라이저는 여러 문제를 야기하므로, 한 가지 선택은 파이널라이저를 전면 금지하는 것이다. 그러나 그러면 소멸자가 있는 타입을 Gc<T>에 담을 수 없게 된다. 러스트가 항상 소멸자를 호출하는 것은 아니지만, 그런 상황은 ‘예외적’인 편이다. Gc<T>에서 소멸자를 호출하지 않으면 합리적 프로그래머의 기대를 완전히 배반한다. 때문에 Alloy를 포함해 사실상 모든 러스트용 GC는 어떤 형태로든 파이널라이저를 지원한다.
그러나 기존 GC는 소멸자와 파이널라이저를 별개 개념으로 사용자에게 강요한다. 전자는 Drop 트레이트를, 후자는 보통 Finalize 트레이트를 갖는다. 타입이 파이널라이즈되어야 한다면 사용자는 Finalize 구현을 제공해야 한다. 하지만 이는 문제를 낳는다: (1) 외부 라이브러리는 파이널라이저를 제공하지 않으므로, 각 소비자가 직접 구현해야 한다; (2) 러스트의 고아 규칙(orphan rule)[27, §6.12] 때문에 외부 라이브러리 타입에 대해 트레이트를 구현할 수 없다(즉 라이브러리 타입이 Gc<T>를 고려해 설계되지 않았다면 직접 GC할 수 없다); (3) 파이널라이저를 위해 드롭 글루를 자동 복제할 수 없다; (4) rustc가 Drop::drop 유사 호출을 금지하는 것을 재현할 수 없다.
프로그래머는 #1과 #2를 다양한 방식으로 우회할 수 있다. 예를 들어 외부 타입을 뉴타입(newtype)으로 감싸고[20, §19.3], 그에 파이널라이저를 구현한다. 번거롭지만 개념적으로 어렵진 않다.
#3에는 부분 해법이 있다. 예를 들어[14]는 Trace 매크로로 구조체 필드에 대해 파이널라이저 글루(드롭 글루의 파이널라이저판)를 생성한다. 그러나 이는 #2의 변형으로 부딪힌다: 외부 타입은 해당 트레이트를 구현하지 않으므로 재귀적 스캔이 불가하다.
#4는 현재 러스트로는 해결 불가다. 결코 호출될 수 없는 함수를 정의할 수는 없다 — 그런 함수가 무슨 쓸모인가? 부분 해법으로 finalize가 값을 소유권 취득하도록 할 수 있을 것 같지만, Drop::drop은 그렇게 하지 않는다. 그래야만 이후 드롭 글루가 실행될 수 있기 때문이다.
우리 목표는 Alloy가 소멸자를 파이널라이저로 쓰게 하는 것이다. 위에서 러스트 특유의 도전을 설명했지만, 비-러스트적 도전도 여럿 있다! 근본적으로 파이널라이저와 소멸자는 서로 다른, 때로 상충하는 속성을 지닌다. 이 차이와 문제의 최선의 안내서는 Boehm[6]이며, C++ 명세의 GC 지원 관련 후속 작업[8]이 이를 보완한다[3].
명백한 차이는 실행 시점이다. C++과 러스트는 소멸자의 실행 시점을 정확히 정의하지만[4], 파이널라이저는 불특정 시점에 실행된다. 보통 동등 소멸자보다 나중에 실행되지만, 프로그램이 특정 파이널라이저가 실행되기 전에 종료될 수도 있다[5]. 그러나 이와 뒤바뀌는 두 상황이 있다. 첫째, 스레드가 오류로 종료되고, 프로그램이 언와인딩을 사용하지 않거나, 스레드가 언와인딩 불가 ABI 경계를 넘어섰다면, 소멸자는 전혀 실행되지 않을 수 있지만 GC는 동등 파이널라이저를 자연스럽게 실행한다. 이는 문맥상 둘 다 합리적이므로 더 언급하지 않는다. 둘째이자 놀랍게도, 비-오류 상황에서도 파이널라이저가 동등 소멸자보다 ‘조기에’ 실행될 수 있다[6, §3.4].
덜 명백한 차이는 실행되는 스레드다. 소멸자는 값의 마지막 소유자와 같은 스레드에서 실행된다. 그러나 파이널라이저를 그 스레드에서 실행하면, 뮤테이터가 배타적 접근을 기대하는 자원을 파이널라이저가 접근해 경쟁/교착을 일으킬 수 있다[24][6, §3.3]. 일반 러스트 코드에서 이런 문제가 발생하면 프로그래머 실수로 명백하다. 소멸자의 실행 시점이 예측 가능하기 때문이다. 반면 파이널라이저는 실행 시점이 예측 불가능하므로, 같은 스레드에서 실행될 경우 공유 자원에 안전하게 접근할 방법이 없다. 유일한 해법은 파이널라이저를 비-뮤테이터 스레드에서 실행하는 것이다 — 하지만 모든 러스트 타입/소멸자가 다른 스레드에서 안전하게 실행 가능한 것은 아니다.
추가 차이로는 다음이 있다: 파이널라이저는 부분적/완전 ‘파이널라이즈’된 다른 GC 값을 참조할 수 있으며, 그 메모리는 재사용됐을 수도 있다; 파이널라이저는 전달된 참조를 복사해 어딘가 저장함으로써 객체를 부활(resurrection)시킬 수 있다.
시간이 흐르며 파이널라이저는 점점 의심받게 되었다. 예컨대 자바는 타입 단위 파이널라이저를 폐기(deprecate)했고, 결국 제거할 예정이다. 대신 의도적으로 덜 유연한 객체 단위 ‘클리너’를 도입해[13], 부활과 클래스 단위 파이널라이제이션 같은 문제를 API 수준에서 차단한다.
이 시점에서 독자에게 다음을 설득했길 바란다: 실용적 러스트용 GC는 가능할 때 기존 소멸자를 파이널라이저로 재사용해야 한다. 그러나 파이널라이저는, 기존 GC에서도, 여러 문제를 야기한다.
일부 문제는 근본적이다. 예를 들어, 파이널라이저는 마지막 사용 시점과 파이널라이제이션 사이에 지연(latency)을 불가피하게 도입한다.
일부 문제는 오래된 설계의 우발적 산물이다. 예컨대 자바의 클리너는 파이널라이저의 더 제한된 버전이라 볼 수 있다. 일반적 사용례 대부분을 허용하되 위험한 경우의 상당수를 설계로 금한다. 예를 들어, 클래스/구조체 단위 파이널라이제이션은 객체/값 단위로 쉽게 대체할 수 있고, 객체 접근에 간접화가 필요하도록 하면 부활을 차단할 수 있다. Alloy는 이런 문제와 해법에 대한 이해 향상의 수혜를 입는다: 객체 단위 파이널라이제이션은 자명하고(Gc::new_unfinalizable로 특정 값의 파이널라이즈를 끌 수 있음), 약간 더 수고하면 객체 부활도 처리 가능하다.
그러나 여전히 중간 영역의 문제가 남는다: 명백히 근본적이지는 않지만, 뚜렷한 해결책이 없다. 우리 맥락에서, 소멸자를 파이널라이저로 재사용하려면, 네 가지 문제가 지금껏 불가해 보였다[8, p. 32]: (1) 파이널라이저는 소멸자보다 터무니없이 느리다; (2) 조기 실행될 수 있다; (3) 뮤테이터와 같은 스레드에서 실행하면 경쟁/교착을 낳는다; (4) 안전한 소멸자 일부는 안전한 파이널라이저가 아니다.
다행히, Alloy가 확장한 러스트의 특이한 정적 보장을 이용해 이 문제들을 새롭고 만족스럽게 다룰 수 있다. 다음 절에서 위 순서로 문제를 다루되, #1·#2는 분리해, #3·#4는 함께 다룬다.
8절에서 보듯, 파이널라이저 실행 수와 GC 오버헤드는 상관이 있다(우리 실험에서 최악의 경우 3.35× 슬로우다운, 다만 명백한 아웃라이어). 이 절에서는 실행되는 파이널라이저 수를 줄이는 방법을 보여, 오버헤드를 줄인다.
파이널라이저의 성능 오버헤드에는 여러 요인이 있다: 소멸자는 즉시 실행되지만 파이널라이저는 큐 관리가 필요하다; 파이널라이저는 마지막 접근보다 한참 후 실행되어 캐시 미스가 늘기 쉽다; 파이널라이저는 값(및 그가 소유한 값들)의 수명을 늘릴 수 있다(메모리 사용량과 마킹 오버헤드 증가). 이런 요인의 대부분은 GC 일반의 본질이며, 성숙한 BDWGC를 사용해도 모두를 상쇄할 최적화가 누락됐다고 보지 않는다.
대신 Alloy는 가능할 때 파이널라이저를 ‘생략’해 아예 실행을 불필요하게 만든다. 그 이유는 다음과 같다: (1) BDWGC가 모든 할당을 책임지고, 직접 Gc<T>로 싸지 않은 할당도 필요시 GC한다; (2) 많은 러스트 소멸자는 BDWGC가 (지연되긴 하지만) 어차피 할 메모리 해제만 수행한다.
예컨대 표준 Box<T>는 힙에 공간을 할당하며, Box<T> 값이 드롭되면 힙 할당을 해제한다. 관찰 두 가지: 첫째, Box<T>의 드롭 메서드는 deallocate 호출뿐이다. 둘째, 관용적으로는 Box<T>가 ‘힙’, Gc<T>가 ‘GC 힙’을 쓴다고 하지만, Alloy에서는 모든 할당이 BDWGC를 통해 이뤄져 같은 힙에 저장된다.
따라서 Box<T>의 드롭 메서드는 파이널라이저로서 불필요하다. 기본 메모리는 어차피 BDWGC가 해제한다. 즉 Gc<Box<u8>> 같은 타입은 파이널라이저를 전혀 실행할 필요가 없고 정적으로 생략 가능하다. 그러나 Gc<Box<Rc<u8>>> 같은 타입은 생략할 수 없다. Rc<T>의 드롭 메서드가 참조 카운트를 감소해야 하기 때문이다. 이처럼 파이널라이저 생략 여부는 최상위 드롭 메서드뿐 아니라 전체 소멸자(드롭 글루 포함)를 고려해야 한다.
function NeedsFinalizer(T):
if Impls(T, Drop) and not Impls(T, DropMethodFinalizerElidable) then
return true;
for each field ∈ T do
if NeedsFinalizer(field) then
return true;
return false;
알고리즘 1. 파이널라이저 생략
impl<T> Gc<T> {
pub fn new(value: T) -> Self {
if needs_finalizer::<T>() { Gc<T>::new_with_finalizer(value) }
else { Gc<T>::new_without_finalizer(value) }
...
}
}
리스팅 3. Alloy 내부에서 파이널라이저를 생략하는 단순화된 모습. 새 컴파일러 인트린식 needs_finalizer는 타입에 파이널라이저가 필요한지 여부를 반환한다. Gc<T>는 이 인트린식을 사용해 해당 값을 파이널라이저 필요로 등록한다. 최적화가 켜진 빌드에서는 이 동적 분기가 정적으로 인라인되어 분기 없는 코드가 된다.
파이널라이저 생략은 어떤 타입의 소멸자가 파이널라이저를 필요로 하지 않는지 정적으로 판정하고 생략한다. 이는 보수적으로 수행되며, 드롭 글루를 올바르게 처리한다.
알고리즘 1에서 보이듯, Drop을 구현한 타입은 새 마커 트레이트 DropMethodFinalizerElidable(메서드 없는 마커)을 함께 구현하지 않는 한 파이널라이제이션이 필요하다. 이 트레이트로, 해당 타입을 Gc<T>에 담을 때 드롭 메서드를 호출할 필요가 없음을 프로그래머가 표지할 수 있다. 트레이트명에서 Drop을 강조한 이유는(‘소멸자’의 단순화가 아니다) 프로그래머가 로컬하게 추론할 수 있게 하기 위함이다(드롭 글루나 구체 타입 파라미터를 고려하지 않아도 됨). 만약 전이적으로 도달 가능한 필드 중 어떤 타입이 Drop을 구현했으나 DropMethodFinalizerElidable은 구현하지 않았다면, 최상위 타입은 여전히 파이널라이제를 필요로 한다.
러스트의 일반 소멸자나 Alloy의 파이널라이저는 수행이 보장되지 않지만, 소멸자나 파이널라이저가 결코 실행되지 않는 프로그램은 아마 쓸 수 없을 것이다(메모리 누수, 교착 등). 그러므로 DropMethodFinalizerElidable은 unsafe 트레이트로 만든다. 부적절 구현은 런타임에서 원치 않는 — 하지만 ‘잘못된’ 것은 아닌! — 동작을 유발할 가능성이 크기 때문이다.
Alloy는 표준 라이브러리에서 다음 타입들에 DropMethodFinalizerElidable을 구현한다: Box<T>, Vec<T>, RawVec<T>, VecDeque<T>, LinkedList<T>, BTreeMap<K, V>, BTreeSet<T>, HashMap<K, V>, HashSet<T>, RawTable<K, V>[6], BinaryHeap<T>. 다행히 이들 드롭 메서드는 해당 트레이트와 양립 가능할 뿐 아니라 러스트 코드에서 광범위하게 쓰인다. 덕분에 많은 파이널라이저를 생략할 수 있다.
리스팅 3은 알고리즘 1을 구현하기 위해 도입한 새 const 컴파일러 인트린식 needs_finalizer를 보여준다. 인트린식은 컴파일타임에 평가되어 결과가 Gc::new에 인라인되고, 관련 분기도 제거된다. 즉 — 컴파일러 최적화가 허용하는 한 — ‘이 타입에 파이널라이저가 필요한가?’ 점검은 런타임 오버헤드가 없다.
대부분은 파이널라이저가 동등 소멸자보다 항상 늦게 실행된다고 가정하지만, 때로는 그보다 먼저 실행될 수 있다[6, §3.4]. 이는 건전성을 훼손한다. 지금까지의 Alloy에서도 가능하다(리스팅 4). 이 절에서는 조기 파이널라이제이션을 방지하는 방법을 보인다.
조기 파이널라이제이션에는 두 가지 측면이 있다. 첫째, 언어 명세는 값이 파이널라이즈될 수 있는 ‘최초 시점’을 정의하지 않거나, 정확히 정의하지 않는 경우가 많다. 형식적으로 ‘조기’가 아닐 수 있지만, 언어 설계자들이 결과적 구현상의 놀라움(예: 자바의 사례[29])을 예상하지 못했다는 점은 분명하다. 둘째, 컴파일러 최적화 — 적어도 LLVM에서는 — GC 무지(‘GC unaware’)이므로, 스칼라 치환 같은 최적화가 프로그램에서 GC 값이 파이널라이즈 가능해 보이는 시점을 변경할 수 있다.
struct S { value: u8 }
impl Drop for S { fn drop(&mut self) { self.value = 0; } }
fn main() {
let root = Gc::new(Box::new(S{ value: 1 }));
let inner: &u8 = &**root.value;
force_gc();
println!("{}", *inner);
}
리스팅 4. 조기 파이널라이제이션 가능 사례. 새 구조체 S(1행), 값 래핑 정수를 0으로 설정하는 드롭 메서드(2행). main에서 S 인스턴스를 Box<T>에 담고, 다시 Gc<T>에 담는다(4행). 내부 정수에 대한 참조를 얻는다(5행). 이 시점에서 컴파일러는 Gc<T>가 더 이상 쓰이지 않음을 파악하고 root의 포인터(레지스터일 수도 있음)를 덮어쓸 수 있다. 이후 수집이 발생하면 파이널라이저가 S의 드롭 메서드를 실행해 프로그램이 기대와 달리 ‘1’이 아닌 ‘0’을 출력할 수 있다(7행).
우리 맥락에서는, Gc<T> 값의 (동적) 파이널라이저가 (정적) Gc<T> 소유자가 스코프를 벗기 전에 실행되면 조기로 정의한다. [7, 해결책 1]의 상위 제안을 빌려, Gc<T>에서 파생된 참조의 동적 수명이 Gc<T> 자체의 수명과 같거나 더 길도록 보장해야 한다.
해법은 Gc<T>의 드롭 메서드를 조정해, 해당 Gc<T>의 정적 수명 동안 GC 값이 살아있게(‘보이게’) 두는 것이다. 즉 Gc<T>가 스코프 내에 있는 동안, 보수적 GC가 해당 GC 값의 포인터를 항상 관찰할 수 있게 한다.
그러나 큰 문제가 있다: Gc<T>처럼 복사 가능한 타입은 소멸자를 가질 수 없다는 점이다. 근본적 도전은 복사된 각 값에 대해 소멸자가 호출되어, 공유되는 기본 값을 여러 번 소멸시킬 위험이 있다는 것이다. Alloy는 명시적으로 Gc<T> — 단, 다른 복사 가능한 타입은 아님 — 에 소멸자를 허용하되, 임의 복사 수에 직면해 놀라움을 야기하지 않도록 해당 소멸자는 멱등(idempotent)이어야 한다. 다행히 Gc<T>는 러스트 관점에서 드롭 글루가 없다: Gc<T>는 포인터 타입 필드 하나로 구성되며, 이런 타입은 소멸 관점에서 불투명하다.
따라서 Gc<T>의 드롭 메서드만 멱등이면 된다. 우리의 목적 — 파이널라이제이션을 억지 — 은 런타임 부작용이 필요치 않다. 이를 위해 펜스(fence)를 사용한다. 펜스에는 여러 종류가 있는데, 여기서는 컴파일러가 특정 구문 지점을 기준으로 재정렬하지 못하게 하고, CPU가 특정 주소를 기준으로 재정렬하지 못하게 하는 펜스가 필요하다. 우리는 BDWGC의 GC_reachable_here 매크로[7]의 플랫폼별 코드를 Gc<T>의 드롭 메서드에 복사해 필요한 효과를 얻었다.
우리가 추가한 Gc<T>의 드롭 메서드는 조기 파이널라이제이션을 완전히 방지한다. 또한 [7, 해결책 1]이 제시한 C++용 해결책의 성능 문제도 자연스럽게 해결한다. 거기서는 타입과 무관하게 모든 포인터를 스코프 전체 동안 살려 두어야 한다. 반면 우리의 해법은 정의상 Gc<T> 값만 살려 두며, 다른 타입의 값은 컴파일러가 마음껏 최적화할 수 있다. 다만 인공적 마이크로벤치에서 펜스 삽입이 눈에 띄는 오버헤드를 보았다.
그래서 간단한 최적화를 구현했다: Gc<T>에 파이널라이저가 있는 경우에만 펜스를 삽입한다. 직관적으로 그런 경우 드롭 메서드를 생성하지 않는 편이 좋아 보이나, rustc 내부에서 직접 그렇게 하기는 어렵다. 대신 그런 타입의 드롭 메서드 호출을 억제한다: 두 접근은 기능상 동등하나, 우리의 접근은 컴파일러 툴체인의 데드 코드 제거에 더 부담을 준다.
Alloy는 rustc의 MIR(중간 표현) 처리에 RemoveElidableDrops라는 새 패스를 추가한다. MIR은 rustc의 주된 IR로, 프로그램의 모든 함수로 구성되며 각 함수는 기본 블록들의 열이다. 단순화해 말해, 함수 호출과 드롭 메서드 호출은 기본 블록의 서로 다른 종류의 종결자(terminator)로 표현된다. 종결자는 피호출자와 후속 기본 블록을 참조한다.
remove_elidable_drops 패스는 프로그램의 MIR을 순회하며, 생략 가능한 파이널라이저를 참조하는 드롭 종결자를 찾아, 이를 후속 기본 블록으로의 goto 종결자로 치환한다. 부록의 알고리즘 4는 더 형식적인 버전을 제시한다.
이 절에서는 두 가지 상위 문제를 다룬다: 뮤테이터와 같은 스레드에서 파이널라이저를 실행하는 것은 경쟁/교착을 유발할 수 있다; 안전한 소멸자 중 일부는 안전한 파이널라이저가 아니다. 전자는 개념적으로 단순하다 — 파이널라이저는 별도 스레드에서 실행해야 한다 — 그러나 그렇게 해도 건전함이 유지되는지 보장해야 한다. 우리는 이를 후자의 특수 사례로 간주해 함께 다룬다.
파이널라이저 안전성 분석(FSA)을 도입해, 안전하지 않은(‘안전한 러스트’가 아닌 의미에서) 소멸자의 파이널라이저 사용을 금한다. 1차 근사로, FSA는 파이널라이저가 메모리 안전하고, 사이클 안전(이미 파이널라이즈된 객체에 접근하지 않음)하며, 스레드 안전함을 보장한다. 세 구성요소를 개별로 소개한 뒤, 이를 통합한다.
Gc<T>는 직접 또는 간접으로 일반 러스트 참조(&, &mut)를 저장할 수 있으며, 이 경우 러스트의 보로 체커 규칙을 따르고 참조 수명을 넘길 수 없다. 그러나 파이널라이저는 GC 값의 수명을 암묵적으로 연장하며, 저장된 참조도 그에 포함된다: 파이널라이저에서 참조 접근은 러스트의 대여 규칙을 훼손할 수 있다.
간단한 회피책은 Gc<T>가 직접/간접으로 참조를 저장하지 못하게 금지하는 것이다. 이는 큰 손실이 아닐 것 같다: Gc<T>에 참조를 저장하면 ‘GC다움’을 상당히 상실한다. 그러나 우리는 결과가 쓰기 어렵다는 걸 발견했다. 기존 코드를 점진적으로 Gc<T>로 이식 같은 간단 작업마저 고통스럽게 만든다.
중간 해법(그러나 불충분)은 파이널라이저가 필요한 타입만 참조 문제의 후보이므로, 그런 타입만 Gc<T>에 참조 저장을 금지하는 것이다. 예컨대 struct S{x: &u8}에 드롭 메서드가 없다면, 소멸자는 파이널라이저로 써도 안전하다. 드롭 비-측면이 &u8을 사용하지 않기 때문이다.
우리가 최종적으로 택한 FSA 규칙은 다음이다: 타입 T의 소멸자는, 드롭 메서드가 T의 필드(속성으로부터 도달 가능한 필드 포함)로부터 파생된 참조를 얻지 않는다면 파이널라이저로 사용할 수 있다. 러스트 용어로 말해, 소멸자 내의 프로젝션(구조체 필드, 벡터 인덱스 등)에서 참조를 생성하는 것을 금지한다. 드롭 메서드 내 비-프로젝션 참조는 정의상 안전하다. 스택 변수에 대한 참조는 드롭 메서드 동안만 존재하고, 전역 변수에 대한 참조는 프로그램 남은 기간 존재하기 때문이다.
이 규칙은 안전 집합을 과대포함한다. 예컨대 드롭 메서드가 새 값을 만들고 그 필드에 대한 참조(프로젝션)를 얻는다면, 그 참조는 드롭 메서드를 넘지 않더라도 FSA 하에서는 불가다. 이런 경우를 다루기 위해 규칙을 더 느슨하게 만드는 시도는 설명과 구현을 빠르게 복잡하게 만든다.
struct GcNode { value: u8, nbr: Option>> }
impl Drop for GcNode {
fn drop(&mut self) { self.value = 0; println!("{}", self.nbr.unwrap().borrow().value); }
}
fn main() {
let mut gc1 = Gc::new(RefCell::new(GcNode{value: 1, nbr: None}));
let gc2 = Gc::new(RefCell::new(GcNode{value: 2, nbr: None}));
gc1.borrow_mut().nbr = Some(gc2);
gc2.borrow_mut().nbr = Some(gc1);
}
리스팅 5. 사이클과 파이널라이제이션을 섞을 때의 문제 예. 리스팅 1과 본질적으로 다른 점은 드롭 메서드가 nbr 내부 필드 값을 출력한다는 점(3행). 강한 메모리 모델에서 이 프로그램은 아마 ‘2 0’ 또는 ‘1 0’을 출력할 것이다. 어느 쪽이 먼저 파이널라이즈되느냐에 따라 달라진다. ‘1 2’나 ‘2 1’ 같은 ‘그럴듯한’ 출력은 나오지 않는다: 먼저 실행된 파이널라이저가 다른 쪽이 그 파이널라이저에서 보게 될 상태를 바꿔버리기 때문이다. 이는 곧, 두 번째로 실행된 파이널라이저가 정의되지 않은 동작을 초래함을 의미한다.
GC의 주요 동기는 순환 자료구조 문제 해결이다. 그러나 파이널라이저가 사이클 구성원 간 공유 상태에 접근하면 불건전해질 수 있다. 리스팅 5는 두 GC 값이 사이클을 이루고 양쪽 파이널라이저가 서로를 참조할 때 발생하는 UB 예를 보인다. 어느 순서로 파이널라이저를 실행해도 최소 하나는 다른 쪽을 부분/완전 ‘파이널라이즈’된 상태로 본다.
우리가 아는 대부분의 언어/시스템은 사용자가 이런 문제에 빠지지 않거나(파이널라이저 사이클은 드묾[19, p. 229]) 빠지더라도 해결법을 안다고 가정한다(예: 파이널라이제이션이 필요한 부분과 필요 없는 부분으로 타입 분해[6, p. 11]). 완전 자동 해법은 없다. 일부 GC는 약 참조를 제공해 파이널라이저 사이클이 끊겼는지 감지하게 하지만, 결과 처리는 여전히 수동이다.
우리는 사용자가 소멸자를 파이널라이저로 사용할 때 사이클에서도 예기치 않은 동작이 없도록 정적 보장을 제공하고자 했다. 첫 시도는 Gc<T>가 직접/간접으로 Gc<T> 타입 필드를 가질 수 없게 하는 것이다. 이는 우리가 잡고 싶은 실수를 예방하지만 공유 소유권 자체를 금지한다! 그래서 우리는 타입의 소멸자가 직접/간접으로 Gc<T>에 접근하지 않음을 검사하기로 했다. 소멸자가 다른 GC 타입에 접근하지 않는 한, GC 타입이 공유 소유권을 표현하는 것을 허용한다.
검사를 쉽게 구현하려, 오토 트레이트(auto trait)[27, §11]를 도입한다. 오토 트레이트 A는 다음 중 하나가 아니면 타입 T에 자동 구현된다: T에 대한 A의 명시적 음수 구현(negative impl)이 있다; 또는 T가 A가 아닌 필드를 포함한다. 비공식적으로, 오토 트레이트의 음수 구현은 포함 타입을 ‘오염’시킨다고 말한다.
새 오토 트레이트 FinalizerSafe를 도입하고, 단일 음수 구현 impl<T> !FinalizerSafe for Gc<T>를 제공한다. 이는 전이적으로 도달 가능한 코드를 자연스럽게 처리해, FSA가 소멸자의 직접 필드 접근이 FinalizerSafe인지 여부만 검사하면 되게 한다.
impl Drop for GcNode {
fn drop(&mut self) { println!("drop {}", self.value.lock().unwrap()); }
}
fn main() {
let counter = Rc::new(Mutex::new(0));
{ let _ = Gc::new(GcNode { value: Rc::clone(&counter), nbr: None }); }
let r1 = counter.lock().unwrap();
force_gc();
assert_eq!(*r1, 0);
}
리스팅 6. 소멸자가 파이널라이저로 사용될 때 교착을 일으키는 예. 뮤테이터는 참조 카운팅된 뮤텍스를 만들고(6행), 이를 GcNode에 복사해 담은 뒤 즉시 스코프를 벗긴다(7행). 그다음 뮤테이터가 락을 획득하지만(8행), 해제하기 전에 GC가 발생해 GcNode의 파이널라이저가 실행된다(9행). 만약 파이널라이저가 뮤테이터와 같은 스레드에서 실행된다면, 파이널라이저는 락을 획득하지 못하고(2행) 교착에 빠진다.
뮤테이터와 같은 스레드에서 파이널라이저를 실행하면 공유 상태 접근 시 문제가 된다(§4.1, 리스팅 6). 가장 일반적 해법은 뮤테이터 코드를 결코 실행하지 않는 별도 파이널라이저 스레드에서 실행하는 것이다.
따라서 타입의 소멸자가 파이널라이저 스레드에서 실행해도 안전함을 보장해야 한다. 보수적 정의로는, T가 Send(타입을 한 스레드에서 다른 스레드로 영구 이동 가능)와 Sync(여러 스레드에서 동시 접근 가능)를 모두 구현하면 Gc<T> 사용은 안전하다. 그러나 Send와 Sync 모두를 요구하면 부담스럽다. 특히 Sync 구현 타입보다 Send 구현 타입이 많다.
겉보기에는 T가 Send만 구현하면 파이널라이저 스레드로 안전하게 보낼 수 있어 충분해 보인다. 하지만 이는 파이널라이저가 Arc 같은 메커니즘을 통해 비-GC 값과 공유된 상태를 간접 접근하는 것을 막지 못하며, 우리가 피하려는 문제를 유발할 수 있다.
FSA는 타입이 Send/Sync를 구현했는지 ‘무시’하고 소멸자 자체를 검사한다. FSA를 통과하려면: 소멸자가 스레드 로컬에 접근하지 않아야 하고; 프로젝션으로 접근하는 모든 타입이 Send와 Sync를 모두 구현해야 한다. 직관적으로, Send/Sync가 아닌 타입 T라도, 소멸자가 T의 Send+Sync ‘부분집합’만 접근한다면 안전한 파이널라이저를 가질 수 있다.
이 규칙은 FSA가 단순한 타입 시스템 확장이 아닌 추상 해석임을 분명히 보여준다[8]. 우리는 신중한 검토 끝에, 이는 작성 시점 러스트 의미론(rustc/LLVM 구현 포함)과 양립한다고 믿지만, 다른 언어/구현에서는 안전하지 않을 수 있다(예: 자바의 동기화 제거[31]). 러스트가 이런 점검을 의미론적으로 의도적으로 허용/금지해야 하는지는 열린 문제로 남긴다.
파이널라이저 스레드 구현은 꽤 단순하다. 예를 들어, 뮤테이터/파이널라이저 스레드 간 메모리를 명시적으로 동기화할 필요가 없다. BDWGC의 스톱 더 월드 수집 단계가 이미 모든 메모리를 동기화한다.
function FinalizerSafetyAnalysis(func):
for each basic_block ∈ func do
t ← basic_block.terminator;
if not IsGcConstructorCall(t) then
continue;
ty ← GetTyOfGcValue(t);
if isFinalizerUnchecked(ty) or not NeedsFinalizer(ty) then
continue;
for each drop_method ∈ GetDropGlue(ty) do
if not IsMIRAvailable(drop_method) then
EmitFinalizerUnsafeError();
CheckFunctionSafety(drop_method);
function CheckFunctionSafety(drop):
for each basic_block ∈ drop do
for each statement ∈ basic_block do
for each projection ∈ statement do
if not IsFinalizerSafe(projection.element) then
EmitFinalizerUnsafeError();
if IsFunctionCall(basic_block.terminator) then
CheckFunctionSafety(basic_block.terminator);
function IsFinalizerSafe(ty):
return Impls(ty, Send) and Impls(ty, Sync) and Impls(ty, FinalizerSafe);
알고리즘 2. 파이널라이저 안전성 분석
FSA는 앞서의 구성요소를 하나로 통합한다. 러스트 프로그램의 모든 함수를 순회하며 Gc<T>에 사용되는 타입의 소멸자를 분석한다. 알고리즘 2는 FSA의 정수(예: 컴파일 시간 단축을 위한 캐싱 생략)를 보여준다.
FSA는 추상 해석이므로 언제 실행할지 결정해야 한다. 본질적으로, 이전에 미검사였던 타입 T로 Gc<T>를 새로 생성하는 시점마다 FSA를 실행한다. Gc::new 생성자 외에도 From 같은 변환 트레이트로 Gc<T> 인스턴스를 생성할 수 있다. 우리는 그런 진입점에 rustc 전용 속성 rustc_fsa_entry_point를 주석 달았다: 이 속성이 달린 함수 호출은 FSA 점검을 유발한다.
FSA의 순진 구현은 비용이 크므로, Alloy는 여러 최적화를 사용한다. 앞서 암시했듯, FSA는 다양한 점검 결과를 캐시해 불필요한 중복 작업을 피한다. 또한 FinalizerSafe에 &T, &mut T에 대한 음수 구현을 확장한다. 타입 T가 FinalizerSafe, Send, Sync를 모두 구현한다면, 소멸자에 불안전 프로젝션이 없음을 알고 대부분의 FSA 점검을 완전히 생략할 수 있다(다만 스레드 로컬 접근 점검은 여전히 필요). 벤치마크 전반에서 FSA는 릴리즈 모드 컴파일 시간을 약 0.8–1.6% 늘린다.
알고리즘 2는 Alloy의 오류 메시지 접근도 담고 있다. ‘드롭 메서드가 FSA를 통과하지 못했다’는 막연한 메시지 대신, FSA 실패를 유발한 드롭 메서드의 필드나 코드 줄을 정확히 지목한다: EmitReferenceError는 타입 내 참조가 FSA를 위반하는 방식으로 사용될 때 보고하고(§7.1), EmitFinalizerUnsafeError는 드롭 메서드에 불안전 코드(예: Gc<T> 참조, 본문 미상의 함수 등)가 있을 때 보고한다. 리스팅 7은 Alloy가 보고하는 오류 예를 보인다: 드롭 메서드 내 실패 지점과 해당 타입 사용 지점을 함께 강조한다.
error: `RefCell::new(GcNode{value: 2, nbr: None})` cannot be safely finalized.
--> finalization_cycle.rs:11:21
|
7 | fn drop(&mut self) { self.value = 0; println!("{}", self.nbr.unwrap().borrow().value); }
| ^^^^^^^^
| a finalizer cannot safely dereference this
| because it might have already been finalized.
...
11 | let gc2 = Gc::new(RefCell::new(GcNode{value: 2, nbr: None}));
| ^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^
| has a drop method which cannot be safely finalized.
리스팅 7. 리스팅 5 예제에 대해 Alloy가 생성한 컴파일 오류. rustc의 일반 오류 메시지를 확장한다: FSA와 양립 불가 드롭 메서드 사용 지점(‘has a drop method’)과 드롭 메서드의 문제 표현식 위치(‘caused by the expression’)가 모두 강조된다.
FSA는 두 가지 ‘성가신’ 함수에 부딪힐 수 있다.
첫째, 일부 함수는(예: 트레이트 객체 사용, FFI) FSA 실행 시점에 본문이 없다: 이런 함수를 사용하면 FSA 점검은 실패한다. 흔한 부류는 러스트 인트린식(min_align_of 등)이다. 우리는 자주 쓰이는 인트린식을 감사하고 FSA 안전한 것들에 새 속성 rustc_fsa_safe_fn을 주석 달았다. 본문 미상의 다른 함수는 FSA 실패를 유발한다.
둘째, 대부분의 경우 FSA는 제네릭 타입이 구체 타입으로 치환(모노모픽)된 러스트 함수에 대해 실행된다. 그러나 때로는(예: 인트린식, 특정 주석) 아직 치환되지 않은 함수에 부딪힌다. FSA는 이런 함수에도 실행될 수 있으나, 모든 제네릭 타입이 FinalizerSafe, Send, Sync 트레이트를 내포한다고 암시되지 않으면 거부한다. 제네릭으로 타입화된 값의 메서드를 호출하는 경우, FSA는 본문 없는 메서드를 만나게 되어 — 앞의 경우처럼 — 실패한다.
공통 주제는 FSA의 건전성을 최우선으로 하며, 그 대가로 완전성을 포기한다는 점이다. 사용자가 FSA가 안전하다고 아는 코드에 대해 오류가 발생하면 좌절할 수 있다. 러스트에서 흔하듯, 우리는 안전하지 않은 탈출구를 제공한다. 사용자가 건전성을 해치지 않음을 스스로 증명할 수 있을 때 FSA 오류를 침묵시킬 수 있도록 한다. 타입 단위 접근을 실험했으나 너무 제약적이라 판단했고, 값 단위 탈출구 unsafe FinalizerUnchecked<T>를 제공한다. 이 타입으로 감싼 값은 FSA 전 지점에서 안전한 것으로 간주된다. 사용자가 이 탈출구를 사용할 일은 드물기를 바라지만, 러스트에서 흔하듯 정당한 관용구가 있는 경우 필요했다.
| 버전 | 설명 | #벤치마크 | |
|---|---|---|---|
| Binary Trees | Debian CLBG Rust#2 | 힙 할당 마이크로벤치 | 1 |
| Regex-Redux | Debian CLBG Rust#1 | 정규식 매칭 | 1 |
| Alacritty | v0.15.0-dev | 터미널 에뮬레이터 | 10 |
| fd | v9.0.0 | 유닉스 find 대체 | 7 |
| grmtools | v0.13.4 | 렉서/파서 라이브러리 | 4 |
| Ripgrep | v14.1.1 | 빠른 grep 대체 | 13 |
| som-rs-ast | git #35b780 | SOM AST VM | 26 |
| som-rs-bc | git #35b780 | SOM 바이트코드 VM | 26 |
표 1. 실험에 사용한 벤치마크(상)와 벤치마크 모음(하). 서로 다른 메모리 관리 전략(Alloy, Rc<T> 등)을 사용하도록 변경했다. Binary Trees와 Regex-Redux는 고전적 독립형 GC 벤치마크; 나머지는 각기 벤치마크 모음(예: Ripgrep은 13개 벤치마크)이다. 가운데는 다양한 ‘일반’ 러스트 프로그램; 아래는 SOM 언어의 세 구현 중 둘이다.
이 절에서는 방법론과 실험 결과를 설명한다.
러스트용 GC 벤치마크 모음은 존재하지 않는다. 설령 있었다 해도, 우리 목적에는 부적합할 수 있다. 실험 E GCvs에서는 기존 공유 소유권 접근들과 비교하고 싶다. 우리는 crates.io(사실상 표준 패키지 시스템)의 인기 상위 약 100개 러스트 라이브러리를 탐색해 적절 후보를 찾았다. 실제로는 참조 카운팅 사용 크레이트를 찾았다. 간결을 위해 이하에서는 ‘Rc<T>’가 Rc<T>와 스레드 안전 버전 Arc<T>를 모두 지칭한다고 가정한다.
| Gc<T> | Rc<T> | Weak<T> | |
|---|---|---|---|
| Alacritty | 107 | 9,450 | 1,970 |
| Binary Trees | 2 | 0 | 0 |
| fd | 7 | 421 | 1 |
| grmtools | 299 | 1,825 | 23 |
| Regex-Redux | 108 | 109 | 0 |
| Ripgrep | 104 | 249 | 4 |
| som-rs-ast | 206 | 35 | 0 |
| som-rs-bc | 464 | 39 | 0 |
표 2. 포팅 후 소스 코드에서 관련 타입이 참조되는 빈도. Rc<T>에 대해서는 약 참조 수(Weak)도 함께 보여준다: 이는 부분 포팅 정도와 약 참조 사용 정도의 프록시다. 순환 자료구조가 소스에 미치는 변화를 가늠할 수 있다.
표 1은 최종 모음을 보여준다: Binary Trees와 Regex-Redux를 제외하면 각 항목이 자체 벤치마크 모음이다. 전체로 보면(동일한 SOM 모음들을 하나로 치면) 62개, 따로 치면 88개 벤치마크다. 표 2는 포팅 후 관련 타입 사용 빈도, 표 3은 런타임 힙 데이터 분포를 보여준다. 다양한 메모리 패턴을 가진 벤치마크를 포함한다.
Binary Trees는 할당 집약적이고 단순해, 추가 공유 소유권 전략과 비교하기 용이하다: Rust-GC(사용자 수준 GC 라이브러리)[14], Arena<T>(비-GC 메모리 아레나)[10]. Alacritty, fd, Ripgrep은 잘 알려진 러스트 프로그램이며 각기 벤치마크 모음을 갖는다. grmtools는 오류 복구에서 Rc<T>를 광범위하게 사용하며, 실제 2.8만 LoC 자바 소스의 구문 오류를 삽입해 벤치마크했다.
SOM은 스몰토크 계열의 작지만 완전한 언어로, 구현이 다양하다. 우리는 그 중 두 개를 포함한다: som-rs-ast(프로그램을 AST로 표현), som-rs-bc(프로그램을 바이트코드로 표현). 둘 다 자바 SOM VM의 기존 러스트 포트이며 Rc<T>를 사용한다. 동일한 SOM core-lib 벤치마크를 사용한다(커밋 #afd5a6 기반).
모든 프로그램의 모든 부분을 포팅하진 못했다. 특히 어떤 프로그램은 Rc<T>의 make_mut/get_mut를 광범위 사용한다. 이는 런타임 단일 소유 시 내부 내용을 변경하도록 허용한다. 복사 가능한 Gc<T>에는 동등 기능이 없다(가질 수 없다). 일부는 대안으로 성공했으나, 어떤 것은 런타임에서 드물어(가치 없거나), 포팅이 너무 어렵다고 판단했다(프로그램의 너무 많은 부분이 해당 가정에 의존). 소수 사례에서 버그가 생겨 되돌렸다. 예: Alacritty의 UTF-8 지원에서 교착. 이런 버그를 만나면 해당 부분은 Rc<T>로 되돌렸다.
| 할당(개수) | GC 소유(%) | |
|---|---|---|
| Rc<T> | Box<T> | |
| Alacritty | 125 | 8,770 |
| Binary Trees | 0 | 3,222,201 |
| fd | 17,821 | 306,902 |
| grmtools | 2,283 | 19,859,431 |
| Regex-Redux | 45 | 3,132 |
| Ripgrep | 12,786 | 521,366 |
| som-rs-ast | 15 | 8,586,976 |
| som-rs-bc | 15 | 2,397,931 |
표 3. 런타임 힙 분포. ‘할당(개수)’ 열은 각 타입으로 할당된 값의 수를 보여준다(다른 타입도 할당되지만 여기서는 생략). ‘GC 소유’는 Gc<T> 값이 직접/간접 소유하는 값 비율을 보여준다. 예: Gc<Box<T>> 하나만 있는 프로그램은 ‘GC 소유’ 100%다. 박스가 Gc<T>에 의해 소유되기 때문이다. 후술하듯, Gc<T>가 다른 값을 소유하면 파급 효과가 있다.
우리는 최종 모음에 들어가지 않은 프로그램 10개를 포팅하려 시도했다. ‘체리 피킹’ 의혹을 피하기 위해 제외 사유를 간단히 보고한다. 모든 제외 벤치마크는 부록 표 4에 있다.
여러 프로그램(예: numbat, mini-moka, salsa)은 포팅 후 GC 벤치 관점에서 흥미롭지 않았다. 소스 상 참조 수가 많든 적든, 벤치마크가 할당하는 메모리가 너무 적어 전략 간 차이가 감지되지 않는다. 다시 말해, 평가 관점에서 ‘같은’ 프로그램이다.
두 프로그램(bevy, rust-analyzer)은 포팅 후 올바르게 실행되지 않았다. 둘 다 Rc<T>의 make_mut/get_mut를 광범위 사용했고, 이를 되돌리면 벤치마크가 흥미롭지 않았다.
RustPython도 포팅했으나, 파이썬 수준 소멸자 구현을 성실히 반영하지 못했다. 본질적으로 RustPython의 기본 구성에서 객체 표현이 FSA와 양립하지 않는다. 따라서 파이널라이저 스레드에서 파이썬 __del__을 실행할 수 없다. 기술적으로 파이썬 의미론과 양립하지만, 우리 포트가 덜한 일을 하게 되어 오도라 판단했다.
우리 실험은 Alloy와 ‘일반’ 러스트의 비교로 볼 수 있다. 다행히 Alloy는 ‘일반’ 러스트의 진상위 집합이다: 사용자가 명시적으로 GC를 택한 경우에만 Alloy가 ‘러스트용 GC’가 된다. 동일한 컴파일러/표준 라이브러리를 사용해 결과의 교란 요인을 제거한다. 우리는 로깅 없는 바이너리와 로깅 포함 바이너리 둘을 컴파일한다. 후자만 콜렉터 관련 지표 보고에 사용한다.
도전 하나는 전략마다 서로 다른 할당자 사용 가능성이다. 특히 Alloy는 BDWGC를 써야 하지만 Rc<T>는 jemalloc 같은 현대 할당자를 사용할 수 있다. BDWGC는 1980년대 뿌리를 둔 만큼 현대 할당자 대비 성능 차가 있다: Rc<T>만 사용하는 벤치마크에서 jemalloc 대비 BDWGC 고유 오버헤드는 2–26% 수준이었다(부록 표 6). 이는 상당하고 가변적인 교란 요인이다. 다행히 BDWGC는 ‘전통’ 할당자로써 사용할 수 있어, 요청 시 할당/해제를 수행(보수적 GC 없음)할 수 있다. 주 실험에서는 모든 벤치마크의 할당자를 BDWGC로統一한다.
우리는 벤치마크 수명 동안의 메모리 사용을 이해하고자 한다. 그러나 ‘메모리 사용’을 포착하는 단일 지표는 없고, 합의된 지표 집합도 없다[5]. 우리는 두 지표를 사용한다: (1) 힙 풋프린트(heap footprint): heaptrack[34]이 모든 할당/해제 시점에 기록한 라이브 힙 메모리량; (2) RSS: 프로세스가 사용하는 실제 물리 메모리(메모리 맵 파일, 스택, 코드/텍스트 섹션 포함), 10Hz로 샘플링. 힙 풋프린트는 오버헤드가 크지만 더 자세한 뷰를 준다.
또 다른 교란 요인은 GC 힙의 초기/최대 크기다. 너무 작으면 빈번 재조정/스래싱, 너무 크면 비현실적으로 적은 수집. ‘작음/큼’은 벤치마크마다 다르며, 신중(혹은 경솔)한 선택은 성능 인식을 왜곡시킬 수 있다. BDWGC는 적응적 전략을 기본 사용해, 필요 인지 시 힙을 늘린다. 다른 전략/힙 크기가 차이를 만드는지 가늠하려, 세 가지 고정 힙 크기로 실행했다. 효과가 없거나 약간 가속하며, 영향은 대체로 10% 미만, 최대 28%였다(부록 표 9). 대체로 BDWGC의 기본 힙 크기 조절은 우리의 성능 인식을 크게 왜곡하지 않는다.
각 벤치마크를 30회 실행했다. 표준 time 유틸리티가 반환하는 경과 시간(wall-clock time)을 보고한다. SOM은 관례적 rebench 도구로 실행하지만, 일관성을 위해 time을 사용하도록 조정했다. 모든 벤치마크는 AMD EPYC 7773X 64코어 3.5GHz, 128GiB RAM, Debian 12(bookworm)에서 실행했다. 터보 부스트와 하이퍼스레딩은 끄고 진행했다.
달리 명시 없으면 모든 지표는 평균과 99% 신뢰구간을 보고한다. 개별 벤치마크에는 산술 평균, 모음에는 기하 평균을 사용한다.
시계열(샘플링) 메모리 지표를 플롯할 때, 동일 벤치마크의 구성에 따라 실행 속도가 다르다는 문제가 있다. 우리는 각 벤치마크의 데이터를 선형 보간으로 1000개의 등간격 지점으로 리샘플링한다. 1000은 플롯의 시각 해상도보다 충분히 높다. 정규화 후 원시 데이터가 아닌 각 그리드 포인트에서의 메모리 풋프린트 측정값의 산술 평균을 계산한다. 각 포인트에 대해 99% 신뢰구간을 기록하고, 평균 주변 음영으로 표시한다.
그림 1. Gc<T>와 Rc<T>의 벽시계 시간, 힙 풋프린트(라이브 세트 크기), RSS 비교. 기준선 1은 Rc<T>; 1보다 작을수록 Gc<T>가 더 좋음. 파란 수직선은 기하 평균 비율. 벽시계 시간은 유사하고, RSS도 어느 정도 유사하지만, 평균 힙 풋프린트는 자주 크게 다르다. 대체로 Gc<T>가 평균 힙 풋프린트를 증가시키는데, GC(특히 파이널라이제이션)가 값 수명을 연장하기 때문이다. 상대적으로 적게 할당하는 벤치마크(특히 표 3의 Ripgrep)는 이 효과를 과장할 수 있다. 의외로 힙 풋프린트와 RSS는 상관하지 않는다. RSS 샘플링 빈도가 낮고(특히 fd처럼 빠른 벤치마크에 영향), RSS에는 라이브 세트 외의 ‘헤드룸’이 포함되기 때문이다(나중에 OS로 반환될 수도 있음).
E GCvs의 주요 결과는 그림 1에 있다. 변동은 있으나, Alloy는 모음에서 벽시계 시간 기준 약 5% 오버헤드를 보인다. 메모리에 미치는 영향은 더 가변적이며, 예상대로 Alloy는 평균 힙 풋프린트가 더 크다(할당된 메모리가 더 오래 산다). 이 지표는 약간 주의가 필요하다: 상대적으로 작은 메모리를 할당하는 벤치마크(표 3)에서는 평균 힙 풋프린트의 상대 효과가 절대치보다 훨씬 나빠 보일 수 있다.
Binary Trees는 충분히 단순해 Arena<T>와 Rust-GC와의 비교에도 사용했다. 그림 2의 시계열 데이터가 특히 유익하다(완전한 시간은 부록 표 5). Alloy는 Arena<T>보다 약 3.5× 느리다. 후자의 시계열 데이터는 뚜렷한 단계들을 보인다: (상대적으로 긴) 할당 단계, (상대적으로 중간인) ‘작업’ 단계, (상대적으로 짧은) 해제 단계. 다시 말해, 이 뚜렷한 단계는 Binary Trees가 아레나에 완벽히 부합함을 보여준다. 다른 접근에서는 ‘작업’ 단계가 실행의 더 많은 비중을 차지하는데, 할당자 작업이 그 안에 포함되기 때문이다. Alloy는 Rc<T>보다 약 1.3× 빠르고, 둘의 메모리 프로파일은 유사하다. Alloy는 Rust-GC보다 약 3× 빠르고, 평균 힙 풋프린트는 약 4× 작다. Alloy가 사용자 수준 라이브러리가 아니고 Rc<T>에 부분 의존하지 않기 때문이다. 단일 벤치마크에 과해석은 경계하지만, 다양한 접근의 성능 상한/하한을 가늠케 한다.
그림 2. 다양한 GC 접근에 대한 시계열 데이터 일부: x축은 정규화된 시간, y축은 힙 풋프린트(라이브 메모리)이며 99% 신뢰구간은 음영으로 표시. Binary Trees는 Alloy가 Rc<T>와 비슷한 힙 풋프린트를 보이는 예; Rust-GC는 약 4× 크다. Binary Trees는 Arena<T>와 완벽한 궁합: 끝에서 한 번에 해제하며, Alloy보다 3× 빨라 ‘감속’ 구간이 전체(매우 짧은) 실행에서 유의미한 비중을 차지한다. Ripgrep Alternates는 Alloy의 메모리 누수처럼 보일 수 있지만, 실제로는 GC가 메모리 해제를 ‘늦게 눈치채음’의 결과이며, 파이널라이저 때문에 악화된다. 빈번한 고원(plateau)과 하강(dip)은 메모리가 해제되고 있음을 보여주지만, 기대보다 나중이다. 대비적으로 som-rs-bc JSON Small은 Rc<T>의 순환 객체로 인한 실제 누수를 보이며, Alloy의 풋프린트는 안정적이다.
그림 2의 시계열 데이터는 다른 요인 설명에 도움 된다. 예를 들어 som-rs-bc가 JSON Small에서 메모리를 누수한다(다른 일부에서도 그럴 듯). Rc<T>는 사이클 안의 값을 살려 두기 때문이다. Alloy는 사이클을 자연스럽게 처리해 누수하지 않는다.
Ripgrep의 시계열은 복잡한 힙 풋프린트를 보인다. 이는 누수를 암시할 수 있으나, 사실 GC에서 메모리 해제가 늦어지는 불가피한 결과다. 일반적으로 GC는 참조 카운팅보다 더 늦게 미사용 메모리를 인지하는데, 파이널라이저가 이를 더 악화한다. 놀랍게도, 파이널라이저는 할당 수명을 늘리거나 줄인다. 파이널라이저가 있는 GC 값은 파이널라이저 큐를 기다려 수명이 늘어나는 경향이 있다. 그러나 파이널라이저가 간접 소유 값을 free하면, 다음 수집까지 기다리지 않고 즉시 비라이브로 표시된다. 이것이 Ripgrep의 메모리 사용에서 무작위처럼 보이는 봉우리/골짜기를 설명한다.
그림 3. 파이널라이저 생략의 다양한 지표에 대한 효과. 좌상단 차트는 런타임 Gc<T> 값 중: 파이널라이저가 생략된 비율; 생략 불가 비율; 생략할 파이널라이저가 없는 비율을 보여준다. 표 3과 함께 보면 (a) 런타임 메모리 양상 (b) Gc<T>가 간접 소유하는 메모리 양을 가늠할 수 있다. 다른 플롯은 ‘생략 없음’을 기준으로 정규화(1보다 작으면 개선). 총 GC 정지 시간은 스톱 더 월드 총합; 사용자 시간은 모든 스레드(파이널라이저 스레드 포함) 시간을 포착. 대체로 파이널라이저를 더 생략할수록, 그리고 힙에서 Gc<T>가 소유한 비중이 클수록, 지표가 개선된다.
E Elision 결과는 그림 3에 있다. 일반적으로 상관관계가 뚜렷하다: 파이널라이저를 더 제거할수록, 그리고 힙에서 Gc<T> 소유 비중이 클수록 지표가 개선된다. 다만 주의점이 여럿 있다. 첫째, 모든 파이널라이저가 제거되면 BDWGC는 파이널라이저 스레드를 시작하지 않거나 그에 수반된 락킹을 호출하지 않는다. 시간 기반 지표를 과하게 유리하게 만든다. 둘째, 파이널라이저 수는 비용의 부분 대리자일 뿐이다. 일부 파이널라이저는 큰 간접 소유 그래프를 해제해 실행 시간이 길다. 셋째, 일부 벤치마크는 작업량이 변한다. grmtools는 크게 빨라져 오류 복구 알고리즘이 더 많은 일을 하게 되고, GC 정지 시간은 크게 개선되지만 벽시계 시간은 덜 변한다. 마지막으로, 파이널라이저가 간접 소유 할당을 GC보다 더 일찍 해제하게 만들 수 있기에, 이를 제거하면 간접 소유 값이 더 오래 살게 될 수 있다: Ripgrep의 평균 힙 풋프린트가 이를 드러낸다.
E PremOpt 결과는 그림 4에 있다. 우리는 Alloy의 세 구성을 만들었다. None은 펜스 없음(불건전)이지만 최선의 결과(불건전 코드 실행의 불확실성은 감안)를 근사한다. Naive는 가능한 모든 펜스를 삽입. Optimised는 필요 펜스만 삽입. 신뢰구간을 고려하면 통계적으로 유의미한 차이가 없다. 벤치마크 ‘잡음’이 의미 있는 차이를 가릴 가능성도 있으나, 차이가 있더라도 작을 것이다. 위안이라면, 어느 경우든 차이가 없다는 사실은 비-인공 벤치마크에서 조기 파이널라이저 방지 비용이 눈에 띄지 않음을 시사한다.
그림 4. 조기 파이널라이제이션 최적화의 효과(기준: None, 즉 펜스 없음). 회색 막대는 Naive(모든 펜스), 파란 막대는 Optimised(불필요 펜스 제거). 유감스럽게도 통계적으로 유의미한 효과가 없다.
우리의 모든 성능 판단은 방법론, 선택한 벤치마크 모음, 포팅 비율, 데이터 처리/표현 방식에 의존한다. 예컨대 우리는 외부 라이브러리를 Gc<T>로 포팅하지 않아, 다수 벤치마크가 다양한 할당 전략을 혼용한다. 설령 전부 포팅했더라도, 예를 들면 ‘파이널라이저 생략이 언제나 정확히 우리 실험의 배수만큼 개선된다’고 말할 수는 없다. 타당하고 비-병리적인 프로그램 중에도 범위를 벗어나는 결과가 있을 것이다.
모든 벤치마크에서 BDWGC를 할당자로 사용하면 ‘순수’ 할당자 성능을 교란 요인에서 제거할 수 있으나, 벤치마크의 성능 특성 일부를 바꾼다(예: 할당자에 소요되는 시간 비중; BDWGC의 적응적 힙 크기 전략). 현대 비-GC 할당자의 통찰을 활용한 현대 보수적 GC라면 결과가 다를(크게 다르지는 않을) 것이다. 현재 사용 가능한 ‘프로덕션급, 현대적, 범용 보수적 GC’는 없다. 대안이 등장하면 실험 재실행이 흥미로울 것이다.
우리가 수집한 RSS는 리눅스의 ‘재량’에 따른다: 기대만큼 자주 갱신되지 않으면, 피크/골저를 놓친 평탄화된 데이터를 보게 된다. 또한 시계열 데이터를 정규화 그리드에 보간하는 과정 자체가 평탄화할 수 있다. 우리는 많은 데이터를 수작업 검증해, 이 효과가 유의미하지 않음을 확인했다. 또한 30회 실행으로 피크/골저를 최소한 몇 번은 잡을 가능성을 높였다.
본 논문에서는 GC와 일반적 소멸자/파이널라이저에 대한 충분한 배경을 제공하려 노력했다. 이 절에서는 러스트용 GC 풍경을 넓게 조망한다. 이 분야는 빠르게 진화하므로, 개관은 불가피하게 불완전하다(우리가 아는 가장 최근 개관[16] 이후에도 여러 변화가 있었다). 또한 다른 곳에서 언급되지 않은 관련 비-러스트 GC 작업도 다룬다.
초기 러스트는 ‘관리 포인터’(@T 문법)로 GC 타입을 표현했다[16]. 코어 구현은 참조 카운팅이었고, 사이클 감지기는 여러 번 생겼다 사라졌다[17]. 관리 포인터 지원은 러스트 첫 안정 릴리스 약 1년 전 제거되었다[9]. 이는 ‘러스트 코어에 GC’의 종말은 아니었고, 코어 개발자가 문제 공간을 더 탐색했다[15, 21, 22]. 시간이 지나며 이런 노력은 줄었고, 러스트용 GC에 관심 있는 이들은 rustc 지원을 기대하기보다 사용자 수준 라이브러리로 모든 것을 해결하는 쪽으로 기울었다.
초기 사용자 수준 라이브러리 중 하나는 Bacon-Rajan-CC[12]다. 이는 Alloy의 Gc<T>와 유사 의도의 Cc<T>를 제공한다. 객체 수거 메커니즘은 다르다: 단순 참조 카운트를 두어 사이클 밖 객체는 결정적 파괴를 하고, 사용자가 수동으로 사이클 검출기를 호출해 Bacon/Rajan[4][10] 스타일의 trial deletion으로 미사용 사이클을 식별한다. 사이클 검출은 사용자가 타입의 필드를 순회하는 Trace 트레이트를 수동 구현해야 한다. 소멸자를 파이널라이저로 사용하며, §7.1의 참조 문제를 피하려면 Cc<T>의 타입 매개변수에 T:'static 수명 경계를 둔다. 단순화하면, 해당 타입의 참조는 프로그램 종료까지 유효해야 한다는 뜻으로, 매우 심한 제약이다. §7.2의 이미 파이널라이즈된 값 접근 문제와 달리 런타임에서만 감지해 안전한 패닉을 일으킨다.
아마 가장 알려진 러스트용 GC는 Rust-GC[14]다(§4 일부에서 다룸). Rust-GC의 Gc<T>는 Alloy와 유사한 API를 제공하나, 복사 가능이 아니어서 항상 Gc::clone 호출이 필요하다. Alloy처럼 포인터로의 변환을 허용하지만, 보수적 GC가 없으므로, 사용자는 파생 포인터의 전체 수명 동안 Gc<T> 래퍼가 살아있음을 보장해야 한다. Bacon-Rajan-CC와 유사하게, GC 값은 참조 카운팅을 두고, 가끔 추적 sweep으로 사이클을 식별하지만 Rust-GC는 자동으로 사이클을 검출한다(collect_cycles 같은 수동 호출 불필요). 드롭 메서드는 파이널라이저로 쓰지 않으며, 필요 시 Finalize 트레이트를 수동 구현해야 한다. 파이널라이저 글루는 제공되는 Trace 매크로로 대체로 자동 생성되지만, 완전히는 아니다(§4). Rust-GC는 이미 파이널라이즈된 값 접근을 런타임에서 동적으로 감지하고 패닉한다. Bacon-Rajan-CC와 달리, 콜렉터가 ‘스윕’ 단계인지 기록해, 스윕 중 Gc<T> 접근 시 패닉한다. 교차 스레드 수집/스윕이 이 검사를 회피할 수 있는지는 아직 검증하지 못했다.
참조 카운팅을 넘어서는 예로 Shifgrethor[2]가 있다. Root<'root>에서 Gc를 생성하도록 요구하며, 결과 Gc<'root, T>는 Root<'root>의 수명에 묶인다. 이는 루트를 정밀 식별하게 하지만, Gc<'root, T> 사용 시 명시적으로 Root<'root> 접근이 필요하다. Rust-GC와 달리, Shifgrethor는 사용자가 Finalize 트레이트를 수동 구현해야 하고, 더 제한적이다: 다른 GC 값을 접근할 수 없으며(§7.2 문제를 암묵 해결), GC 값과 같은 'root 수명을 갖지 않는 다른 타입 접근도 금지한다. 그 결과 겉보기엔 안전한 파이널라이저도 UnsafeFinalize를 구현해야 할 수 있다. 우리는 Shifgrethor를 ‘참조 카운팅 없이 정상 러스트에서 GC 루트 추적이 가능함’의 증거로 보지만, 참조가 포인터/usize로 변환되는 경우는 다루지 못한다.
루트 찾기 문제에 대한 다른 접근으로 GcArena[32]가 있다. GhostCell과 유사하게 브랜딩을 사용한다(§2). 사용자는 특별한 ‘루트’ 타입을 제공해, 루트는 그곳에만 저장할 수 있게 한다. 힙 변형은 브랜딩된 참조를 전달받는 함수 문맥에서만 가능하다. 그런 함수가 끝나면 GcArena는 GC 힙을 완전히 통제하고, 루트 타입만 스캔하면 됨을 안다. 이는 GC 참조 수명에 대한 정밀 보장을 낳는다. 그러나 아레나에서 코드가 너무 오래 실행되면, 많은 부분이 더 이상 쓰이지 않아도 자원 부족 상태에 빠지며 회복 수단이 없다. GcArena는 원래 Piccolo VM(Lua VM) 일부였다. 이런 VM은 자주 실행되는 메인 루프가 있어 GC 힙 참조를 내려놓기 쉬우나, 다른 GC 프로그램은 그렇지 않다.
Rust-GC를 개선하려는 시도로 Bronze[11]가 있다. 그러나 러스트용 GC를 의미 있게 개선하기가 어렵다는 걸 보여준다: 두 주요 진전은 모두 불건전해 충돌까지 야기해 비활성화되었다. 첫째, Bronze는 함수 진입에서 LLVM의 gc.root 인트린식을 사용해 스택 맵을 생성, 루트를 추적하려 했다. 이는 보수적 GC의 불가피한 위양성을 없앤다. 그러나 Bronze는 중첩 참조를 추적하지 못했다: 구조체 필드에 Gc<T>가 있으면 GC가 추적하지 못했다. 둘째, Bronze는 자바 같은 비-소유권 언어의 GC 의미론을 러스트에 부여하려 공유 변경을 허용해, 러스트의 보로 체커를 훼손했다.
크롬 렌더링 엔진 Blink는 보수적 GC Oilpan을 사용한다. 흥미롭게도 두 가지 종류의 파이널라이저가 있다. ‘풀 파이널라이저’는 Alloy와 유사하며, 파이널라이저 스레드에서 불특정 시점에 실행되지만, GC 값의 일부만 참조할 수 있다. 이를 보완해, ‘프리(pre) 파이널라이저’는 콜렉터가 객체를 미사용으로 인지하는 즉시 뮤테이터와 같은 스레드에서 실행되고, GC 값 전체에 접근할 수 있다. 프리 파이널라이저는 필요하지만 권장되지 않는다. 스톱 더 월드 단계를 암묵적으로 늘리기 때문이다. 이는 렌더링 엔진에선 지연(latency)이 근본 고려사항임을 반영한다. Alloy는 현재 저지연을 표방하지 않는다.
우리는 러스트용 GC의 새로운 설계를 소개했고, 러스트의 독특한 정적 보장을 활용해 고전적 파이널라이저 문제들까지 해결했다. 기존 러스트 코드와의 통합을 이전 GC들보다 쉽게 만들어, GC 혜택을 볼 러스트 코드의 부분적/전면적 마이그레이션에 실용 경로를 제시했다.
여전히 도전과 기회가 남아 있다. 예컨대 Alloy는 ‘전부 아니면 전무’ 비용이다. 한 군데서라도 Gc<T>를 쓰고 싶다면 GC 런타임 비용 등을 감수해야 한다. Alloy의 절대 속도는 BDWGC에 의해 제한된다고 믿는다. 반정밀(semi-precise) GC 또는 더 빠른 보수적 GC를 사용하면 절대 성능 인식이 달라질 것이다.
요약하자면, Alloy가 러스트용 GC의 궁극 설계라고 주장하지 않는다 — 예를 들어 보수적 GC의 비용 대비 이득에 대한 판단은 합리적 사람들 사이에서도 다를 수 있다 — 그러나 언어 설계와 rustc를 변경할 의지가 있다면 어디까지 가능한지를 보여준다.
부속 산출물[18]에는: 본 논문의 실험을 처음부터 실행(그림 생성 포함)하는 데 필요한 소스 코드와, 본 논문에 사용한 한 번의 실험 실행 데이터가 포함된다.
이 작업은 EPSRC 박사과정 장학금과 Shopify / 왕립공학학회 언어공학 리서치 체어의 지원을 받았다. Steve Klabnik, Andy Wingo에게 감사한다.
function RemoveElidableDrops(func):
for each basic_block ∈ func do
if IsDropTerminator(basic_block.terminator.kind) then
ty ← GetTypeOfDroppedValue(block.terminator);
if IsGcType(ty) then
if not RequiresFinalizer(ty) then
ReplaceTerminator(basic_block);
function ReplaceTerminator(basic_block):
drop_func ← GetDropFunc(basic_block.terminator);
last_block ← GetLastBasicBlock(drop_func);
block.terminator ← last_block.terminator;
알고리즘 3: 생략 가능한 드롭 제거
| 설명 | 제외 사유 | |
|---|---|---|
| bevy | 러스트의 ECS 게임 엔진 | 포팅 실패(§8.1.2) |
| dyon | 러스트 스크립팅 언어 | 포팅 실패(§8.1.2) |
| jiff | 러스트 날짜/시간 라이브러리 | 할당이 너무 적음 |
| mini-moka | 동시 인메모리 캐시 | 할당이 너무 적음 |
| numbat | 수학 검색 엔진 | 할당이 너무 적음 |
| rkyv | 제로 카피 역직렬화 | 벤치마크에서 Gc<T> 적용 범위 부족 |
| RustPython | 러스트의 파이썬 인터프리터 | del 의미론 후적용의 어려움(§8.1.2) |
| rust-analyzer | 러스트 언어 서버 | 포팅 실패(§8.1.2) |
| salsa | 증분 재계산 라이브러리 | 할당이 너무 적음 |
| WLambda | 러스트 스크립팅 언어 | 벤치마크에서 Gc<T> 적용 범위 부족 |
표 4. Alloy 포팅 시도 후 모음에서 제외된 러스트 프로그램들.
| 벽시계 시간(s) | |
|---|---|
| Gc<T> | |
| Alacritty | 0.41 [0.39, 0.45] |
| Binary Trees | 0.11 [0.11, 0.11] |
| fd | 0.33 [0.29, 0.38] |
| grmtools | 3.06 [3.00, 3.14] |
| Regex-Redux | 0.47 [0.47, 0.47] |
| Ripgrep | 1.61 [1.55, 1.69] |
| som-rs-ast | 0.92 [0.88, 0.95] |
| som-rs-bc | 0.28 [0.27, 0.29] |
표 5. E GCvs에서 서로 다른 메모리 관리 전략 비교의 벽시계 시간(초, 99% CI). 특정 전략을 지원하지 않는 벤치마크는 “–”.
| 벽시계 시간(s) | 비율 | |
|---|---|---|
| jemalloc | BDWGC | |
| Alacritty | 0.36 [0.33, 0.40] | 0.40 [0.38, 0.44] |
| Binary Trees | 0.12 [0.12, 0.12] | 0.15 [0.14, 0.15] |
| fd | 0.30 [0.25, 0.36] | 0.31 [0.26, 0.37] |
| grmtools | 3.09 [3.01, 3.17] | 3.24 [3.17, 3.31] |
| Regex-Redux | 0.45 [0.44, 0.45] | 0.45 [0.45, 0.46] |
| Ripgrep | 1.46 [1.40, 1.53] | 1.52 [1.45, 1.59] |
| som-rs-ast | 0.77 [0.74, 0.80] | 0.79 [0.76, 0.82] |
| som-rs-bc | 0.28 [0.27, 0.29] | 0.29 [0.28, 0.30] |
표 6. Rc<T>만 사용하는 코드(즉, GC 없음)에서 jemalloc과 BDWGC 할당자 비교. 비율은 BDWGC/ jemalloc 시간.
| 벽시계 시간(s) | |
|---|---|
| jemalloc | |
| Rc<T> | |
| Alacritty▶ | |
| Cur. Motion | 0.65 ±0.02 |
| Dense Cells | 2.16 ±0.03 |
| Light Cells | 0.37 ±0.01 |
| Scroll | 0.25 ±0.01 |
| Scroll (fullscreen) | 0.38 ±0.01 |
| Scroll Btm | 0.32 ±0.00 |
| Scroll Btm (small) | 0.32 ±0.01 |
| Scroll Top | 0.25 ±0.02 |
| Scroll Top (small) | 0.32 ±0.01 |
| Unicode | 0.23 ±0.02 |
| fd▶ | |
| Cmd Exec. | 1.29 ±0.01 |
| Cmd Exec. (large) | 1.24 ±0.01 |
| File Extension | 0.13 ±0.00 |
| File Type | 0.12 ±0.00 |
| No Pattern | 0.18 ±0.00 |
| Simple | 0.27 ±0.01 |
| Simple (-HI) | 0.12 ±0.00 |
| som-rs-ast▶ | |
| Bounce | 0.62 ±0.00 |
| BubbleSort | 0.56 ±0.01 |
| DeltaBlue | 0.77 ±0.00 |
| Dispatch | 0.59 ±0.01 |
| Fannkuch | 0.65 ±0.00 |
| Fibonacci | 0.83 ±0.00 |
| FieldLoop | 0.94 ±0.00 |
| GraphSearch | 0.31 ±0.00 |
| IntegerLoop | 0.52 ±0.01 |
| JsonSmall | 0.86 ±0.00 |
| List | 0.38 ±0.00 |
| Loop | 0.53 ±0.01 |
| Mandelbrot | 0.46 ±0.00 |
| NBody | 0.31 ±0.00 |
| PageRank | 0.31 ±0.00 |
| Permute | 0.67 ±0.00 |
| Queens | 0.77 ±0.01 |
| QuickSort | 0.98 ±0.00 |
| Recurse | 0.60 ±0.00 |
| Richards | 2.48 ±0.02 |
| Sieve | 0.67 ±0.00 |
| Storage | 0.56 ±0.00 |
| Sum | 0.52 ±0.01 |
| Towers | 0.31 ±0.00 |
| TreeSort | 0.32 ±0.00 |
| WhileLoop | 0.48 ±0.00 |
| grmtools▶ | |
| Eclipse | 3.48 ±0.03 |
| Hadoop | 2.86 ±0.01 |
| Jenkins | 2.90 ±0.00 |
| Spring | 2.43 ±0.00 |
| Ripgrep▶ | |
| Alternates | 1.18 ±0.01 |
| Alternates (-i) | 1.31 ±0.01 |
| Literal | 1.12 ±0.01 |
| Literal (-i) | 1.19 ±0.00 |
| Literal (default) | 1.08 ±0.01 |
| Literal (mmap) | 1.64 ±0.01 |
| Literal (mmap, -i) | 1.67 ±0.01 |
| Literal (regex) | 1.13 ±0.01 |
| UTF Greek | 3.29 ±0.01 |
| UTF Greek (-i) | 3.30 ±0.01 |
| UTF Word | 1.09 ±0.01 |
| UTF Word (alt.) | 1.11 ±0.01 |
| Word | 1.12 ±0.00 |
| som-rs-bc▶ | |
| Bounce | 0.25 ±0.00 |
| BubbleSort | 0.23 ±0.00 |
| DeltaBlue | 0.30 ±0.00 |
| Dispatch | 0.25 ±0.00 |
| Fannkuch | 0.25 ±0.00 |
| Fibonacci | 0.30 ±0.01 |
| FieldLoop | 0.49 ±0.00 |
| GraphSearch | 0.12 ±0.00 |
| IntegerLoop | 0.22 ±0.00 |
| JsonSmall | 0.37 ±0.00 |
| List | 0.18 ±0.00 |
| Loop | 0.23 ±0.00 |
| Mandelbrot | 0.20 ±0.00 |
| NBody | 0.11 ±0.00 |
| PageRank | 0.13 ±0.00 |
| Permute | 0.24 ±0.00 |
| Queens | 0.28 ±0.01 |
| QuickSort | 0.36 ±0.00 |
| Recurse | 0.25 ±0.00 |
| Richards | 0.92 ±0.00 |
| Sieve | 0.25 ±0.00 |
| Storage | 0.22 ±0.00 |
| Sum | 0.22 ±0.00 |
| Towers | 0.13 ±0.00 |
| TreeSort | 0.11 ±0.00 |
| WhileLoop | 0.22 ±0.00 |
표 7. E GCvs 각 벤치마크의 벽시계 시간(초). 30회 평균, 99% CI. 독립형인 Binary Trees와 Regex-Redux는 제외(표 5 참조).
| 사용자 시간(s) | |
|---|---|
| jemalloc | |
| Rc<T> | |
| Alacritty▶ | |
| Cur. Motion | 1.08 ±0.05 |
| Dense Cells | 6.66 ±0.13 |
| Light Cells | 0.34 ±0.03 |
| Scroll | 0.11 ±0.01 |
| Scroll (fullscreen) | 0.24 ±0.02 |
| Scroll Btm | 0.14 ±0.01 |
| Scroll Btm (small) | 0.14 ±0.01 |
| Scroll Top | 0.12 ±0.01 |
| Scroll Top (small) | 0.14 ±0.01 |
| Unicode | 0.10 ±0.01 |
| fd▶ | |
| Cmd Exec. | 1.05 ±0.01 |
| Cmd Exec. (large) | 1.02 ±0.01 |
| File Extension | 0.04 ±0.00 |
| File Type | 0.03 ±0.01 |
| No Pattern | 0.16 ±0.01 |
| Simple | 0.14 ±0.01 |
| Simple (-HI) | 0.03 ±0.01 |
| som-rs-ast▶ | |
| Bounce | 0.62 ±0.00 |
| BubbleSort | 0.56 ±0.00 |
| DeltaBlue | 0.77 ±0.00 |
| Dispatch | 0.59 ±0.01 |
| Fannkuch | 0.64 ±0.00 |
| Fibonacci | 0.82 ±0.00 |
| FieldLoop | 0.94 ±0.00 |
| GraphSearch | 0.30 ±0.00 |
| IntegerLoop | 0.52 ±0.01 |
| JsonSmall | 0.85 ±0.00 |
| List | 0.38 ±0.00 |
| Loop | 0.52 ±0.01 |
| Mandelbrot | 0.45 ±0.00 |
| NBody | 0.31 ±0.00 |
| PageRank | 0.30 ±0.00 |
| Permute | 0.66 ±0.00 |
| Queens | 0.77 ±0.00 |
| QuickSort | 0.98 ±0.00 |
| Recurse | 0.60 ±0.00 |
| Richards | 2.47 ±0.02 |
| Sieve | 0.66 ±0.00 |
| Storage | 0.55 ±0.00 |
| Sum | 0.52 ±0.00 |
| Towers | 0.31 ±0.00 |
| TreeSort | 0.31 ±0.00 |
| WhileLoop | 0.47 ±0.00 |
| grmtools▶ | |
| Eclipse | 3.32 ±0.03 |
| Hadoop | 2.77 ±0.01 |
| Jenkins | 2.74 ±0.01 |
| Spring | 2.35 ±0.01 |
| Ripgrep▶ | |
| Alternates | 0.42 ±0.02 |
| Alternates (-i) | 0.54 ±0.02 |
| Literal | 0.34 ±0.02 |
| Literal (-i) | 0.41 ±0.02 |
| Literal (default) | 0.30 ±0.02 |
| Literal (mmap) | 0.43 ±0.02 |
| Literal (mmap, -i) | 0.48 ±0.02 |
| Literal (regex) | 0.35 ±0.02 |
| UTF Greek | 2.55 ±0.02 |
| UTF Greek (-i) | 2.56 ±0.03 |
| UTF Word | 0.35 ±0.02 |
| UTF Word (alt.) | 0.33 ±0.02 |
| Word | 0.35 ±0.02 |
| som-rs-bc▶ | |
| Bounce | 0.25 ±0.00 |
| BubbleSort | 0.22 ±0.00 |
| DeltaBlue | 0.30 ±0.00 |
| Dispatch | 0.24 ±0.00 |
| Fannkuch | 0.24 ±0.00 |
| Fibonacci | 0.30 ±0.00 |
| FieldLoop | 0.48 ±0.00 |
| GraphSearch | 0.12 ±0.00 |
| IntegerLoop | 0.22 ±0.00 |
| JsonSmall | 0.36 ±0.00 |
| List | 0.17 ±0.00 |
| Loop | 0.22 ±0.00 |
| Mandelbrot | 0.19 ±0.00 |
| NBody | 0.11 ±0.00 |
| PageRank | 0.12 ±0.00 |
| Permute | 0.23 ±0.00 |
| Queens | 0.27 ±0.01 |
| QuickSort | 0.35 ±0.00 |
| Recurse | 0.25 ±0.00 |
| Richards | 0.92 ±0.00 |
| Sieve | 0.25 ±0.00 |
| Storage | 0.22 ±0.00 |
| Sum | 0.22 ±0.00 |
| Towers | 0.12 ±0.00 |
| TreeSort | 0.11 ±0.00 |
| WhileLoop | 0.21 ±0.00 |
표 8. E GCvs 각 벤치마크의 사용자 시간(초). 30회 평균, 99% CI.
| 힙 크기(MiB) | 상대 벽시계 시간 | 실패 벤치 | |
|---|---|---|---|
| Alacritty | 16 | 0.96 [0.91, 0.99] | |
| 32 | 0.98 [0.95, 1.02] | ||
| 64 | 0.94 [0.89, 0.98] | ||
| Binary Trees | 4 | 0.88 [0.82, 1.02] | |
| 8 | 0.90 [0.80, 1.01] | ||
| 16 | 0.87 [0.82, 0.94] | ||
| fd | 16 | 0.94 [0.90, 0.99] | |
| 32 | 0.94 [0.88, 0.98] | ||
| 64 | 0.94 [0.89, 1.00] | ||
| grmtools | 1024 | 1.01 [1.00, 1.02] | 2/4 (Eclipse, Jenkins) |
| 2048 | 1.00 [1.00, 1.01] | ||
| 4096 | 1.01 [1.00, 1.02] | ||
| Regex-Redux | 256 | 0.94 [0.92, 0.95] | |
| 512 | 0.93 [0.90, 0.94] | ||
| 1024 | 0.96 [0.92, 1.07] | ||
| Ripgrep | 32 | 0.96 [0.95, 0.96] | |
| 64 | 0.95 [0.94, 0.95] | ||
| 128 | 0.94 [0.93, 0.95] | ||
| som-rs-ast | 64 | 0.72 [0.71, 0.74] | 2/4 (Fannkuch, TreeSort) |
| 96 | 0.74 [0.73, 0.75] | 2/4 (Fannkuch, TreeSort) | |
| 128 | 0.75 [0.74, 0.76] | ||
| som-rs-bc | 32 | 0.79 [0.78, 0.80] | |
| 64 | 0.79 [0.77, 0.80] | ||
| 128 | 0.84 [0.83, 0.86] |
표 9. 힙 크기 고정의 효과(§8.1.3) — BDWGC 기본 적응 RSS 전략 대비 벽시계 시간 비율. 벤치메모리 관찰에 근거해 크기를 선택했으며, 일부 벤치는 작은 크기에서 실패. 대체로 성능 차이는 소폭이며, BDWGC의 적응 전략이 결과를 왜곡하지 않았다.
| 생략된 파이널라이저(%) | |
|---|---|
| Alacritty▶ | |
| Cur. Motion | 0.00 |
| Dense Cells | 0.00 |
| Light Cells | 0.00 |
| Scroll | 0.00 |
| Scroll Btm | 0.00 |
| Scroll Btm (small) | 0.00 |
| Scroll (fullscreen) | 0.00 |
| Scroll Top | 0.00 |
| Scroll Top (small) | 0.00 |
| Unicode | 0.00 |
| fd▶ | |
| Cmd Exec. | 8.93 |
| Cmd Exec. (large) | 9.09 |
| File Extension | 72.73 |
| File Type | 24.54 |
| No Pattern | 0.04 |
| Simple | 61.54 |
| Simple (-HI) | 61.54 |
| som-rs-ast▶ | |
| Bounce | 100.00 |
| BubbleSort | 100.00 |
| DeltaBlue | 100.00 |
| Dispatch | 100.00 |
| Fannkuch | 100.00 |
| Fibonacci | 100.00 |
| FieldLoop | 100.00 |
| GraphSearch | 99.99 |
| IntegerLoop | 100.00 |
| JsonSmall | 100.00 |
| List | 100.00 |
| Loop | 100.00 |
| Mandelbrot | 100.00 |
| NBody | 99.99 |
| PageRank | 99.99 |
| Permute | 100.00 |
| Queens | 100.00 |
| QuickSort | 100.00 |
| Recurse | 100.00 |
| Richards | 100.00 |
| Sieve | 100.00 |
| Storage | 100.00 |
| Sum | 100.00 |
| Towers | 99.99 |
| TreeSort | 99.99 |
| WhileLoop | 100.00 |
| grmtools▶ | |
| Eclipse | 11.79 |
| Hadoop | 32.99 |
| Jenkins | 26.74 |
| Spring | 37.25 |
| Ripgrep▶ | |
| Alternates | 79.04 |
| Alternates (-i) | 79.04 |
| Literal | 79.04 |
| Literal (-i) | 79.04 |
| Literal (mmap, -i) | 79.04 |
| Literal (default) | 79.04 |
| Literal (mmap) | 79.04 |
| Literal (regex) | 79.04 |
| UTF Greek | 79.04 |
| UTF Greek (-i) | 79.04 |
| UTF Word | 79.04 |
| UTF Word (alt.) | 79.04 |
| Word | 79.04 |
| som-rs-bc▶ | |
| Bounce | 72.50 |
| BubbleSort | 76.34 |
| DeltaBlue | 73.86 |
| Dispatch | 77.78 |
| Fannkuch | 72.74 |
| Fibonacci | 70.37 |
| FieldLoop | 83.33 |
| GraphSearch | 76.56 |
| IntegerLoop | 75.00 |
| JsonSmall | 71.85 |
| List | 79.41 |
| Loop | 74.82 |
| Mandelbrot | 70.93 |
| NBody | 86.17 |
| PageRank | 70.95 |
| Permute | 79.23 |
| Queens | 79.04 |
| QuickSort | 69.33 |
| Recurse | 82.61 |
| Richards | 71.17 |
| Sieve | 73.15 |
| Storage | 73.84 |
| Sum | 75.00 |
| Towers | 78.29 |
| TreeSort | 65.19 |
| WhileLoop | 74.98 |
표 10. 벤치마크별 Alloy가 생략할 수 있었던 파이널라이저 비율.
그림 5. 벤치마크별 파이널라이저 생략의 벽시계/사용자 시간 성능 비교. 막대는 최적화 적용 후 Alloy의 상대 성능(기준: 실선)을 나타낸다. 파란 수직선은 전체 기하 평균(음영은 CI). 사용자 시간이 벽시계보다 개선이 두드러지는 경우가 잦으며, 이는 생략으로 파이널라이저 스레드의 CPU 오버헤드가 줄기 때문.
| 벽시계 시간(s) | |
|---|---|
| 생략 전 | |
| Alacritty▶ | |
| Cur. Motion | 0.66 ±0.01 |
| Dense Cells | 2.17 ±0.03 |
| Light Cells | 0.39 ±0.01 |
| Scroll | 0.27 ±0.01 |
| Scroll (fullscreen) | 0.39 ±0.01 |
| Scroll Btm | 0.33 ±0.00 |
| Scroll Btm (small) | 0.33 ±0.00 |
| Scroll Top | 0.25 ±0.01 |
| Scroll Top (small) | 0.33 ±0.01 |
| Unicode | 0.26 ±0.02 |
| fd▶ | |
| Cmd Exec. | 1.29 ±0.02 |
| Cmd Exec. (large) | 1.25 ±0.01 |
| File Extension | 0.15 ±0.00 |
| File Type | 0.13 ±0.01 |
| No Pattern | 0.28 ±0.02 |
| Simple | 0.34 ±0.01 |
| Simple (-HI) | 0.14 ±0.01 |
| som-rs-ast▶ | |
| Bounce | 7.68 ±0.40 |
| BubbleSort | 5.27 ±0.29 |
| DeltaBlue | 7.84 ±0.19 |
| Dispatch | 6.52 ±0.46 |
| Fannkuch | 6.76 ±0.09 |
| Fibonacci | 22.16 ±1.87 |
| FieldLoop | 5.14 ±0.16 |
| GraphSearch | 2.82 ±0.06 |
| IntegerLoop | 5.88 ±0.11 |
| JsonSmall | 11.37 ±0.77 |
| List | 4.06 ±0.06 |
| Loop | 6.02 ±0.14 |
| Mandelbrot | 4.67 ±0.11 |
| NBody | 2.91 ±0.16 |
| PageRank | 2.44 ±0.05 |
| Permute | 6.69 ±0.35 |
| Queens | 9.07 ±0.34 |
| QuickSort | 10.86 ±0.66 |
| Recurse | 7.66 ±0.24 |
| Richards | 97.40 ±10.46 |
| Sieve | 7.06 ±0.13 |
| Storage | 5.06 ±0.10 |
| Sum | 5.91 ±0.12 |
| Towers | 3.20 ±0.14 |
| TreeSort | 4.65 ±0.32 |
| WhileLoop | 5.03 ±0.21 |
| grmtools▶ | |
| Eclipse | 5.09 ±0.05 |
| Hadoop | 4.49 ±0.03 |
| Jenkins | 4.45 ±0.02 |
| Spring | 4.11 ±0.03 |
| Ripgrep▶ | |
| Alternates | 1.44 ±0.03 |
| Alternates (-i) | 1.55 ±0.02 |
| Literal | 1.38 ±0.03 |
| Literal (-i) | 1.45 ±0.02 |
| Literal (default) | 1.38 ±0.02 |
| Literal (mmap) | 1.90 ±0.02 |
| Literal (mmap, -i) | 1.90 ±0.03 |
| Literal (regex) | 1.36 ±0.03 |
| UTF Greek | 3.53 ±0.01 |
| UTF Greek (-i) | 3.51 ±0.02 |
| UTF Word | 1.39 ±0.02 |
| UTF Word (alt.) | 1.36 ±0.02 |
| Word | 1.36 ±0.02 |
| som-rs-bc▶ | |
| Bounce | 3.03 ±0.04 |
| BubbleSort | 2.64 ±0.04 |
| DeltaBlue | 4.19 ±0.08 |
| Dispatch | 3.80 ±0.36 |
| Fannkuch | 2.86 ±0.23 |
| Fibonacci | 4.34 ±0.20 |
| FieldLoop | 2.45 ±0.16 |
| GraphSearch | 1.15 ±0.03 |
| IntegerLoop | 3.00 ±0.16 |
| JsonSmall | 4.96 ±0.80 |
| List | 2.69 ±0.09 |
| Loop | 3.07 ±0.18 |
| Mandelbrot | 2.21 ±0.15 |
| NBody | 1.23 ±0.06 |
| PageRank | 1.06 ±0.01 |
| Permute | 2.72 ±0.09 |
| Queens | 3.19 ±0.07 |
| QuickSort | 3.62 ±0.05 |
| Recurse | 4.27 ±1.91 |
| Richards | 15.51 ±0.89 |
| Sieve | 2.57 ±0.07 |
| Storage | 2.45 ±0.05 |
| Sum | 3.06 ±0.37 |
| Towers | 1.59 ±0.05 |
| TreeSort | 1.19 ±0.02 |
| WhileLoop | 3.26 ±0.08 |
표 11. E Elision 각 벤치마크의 벽시계 시간(초): 생략 전/후. 30회 평균, 99% CI.
| 사용자 시간(s) | |
|---|---|
| 생략 전 | |
| Alacritty▶ | |
| Cur. Motion | 1.08 ±0.06 |
| Dense Cells | 6.70 ±0.12 |
| Light Cells | 0.34 ±0.04 |
| Scroll | 0.12 ±0.01 |
| Scroll (fullscreen) | 0.27 ±0.03 |
| Scroll Btm | 0.15 ±0.01 |
| Scroll Btm (small) | 0.15 ±0.01 |
| Scroll Top | 0.12 ±0.01 |
| Scroll Top (small) | 0.15 ±0.01 |
| Unicode | 0.13 ±0.02 |
| fd▶ | |
| Cmd Exec. | 1.13 ±0.01 |
| Cmd Exec. (large) | 1.10 ±0.02 |
| File Extension | 0.05 ±0.01 |
| File Type | 0.04 ±0.00 |
| No Pattern | 0.27 ±0.02 |
| Simple | 0.19 ±0.01 |
| Simple (-HI) | 0.04 ±0.01 |
| som-rs-ast▶ | |
| Bounce | 11.15 ±0.41 |
| BubbleSort | 7.88 ±0.40 |
| DeltaBlue | 11.72 ±0.21 |
| Dispatch | 9.15 ±0.63 |
| Fannkuch | 9.60 ±0.12 |
| Fibonacci | 26.41 ±1.82 |
| FieldLoop | 6.42 ±0.17 |
| GraphSearch | 3.92 ±0.07 |
| IntegerLoop | 8.23 ±0.13 |
| JsonSmall | 16.08 ±0.75 |
| List | 5.79 ±0.09 |
| Loop | 8.51 ±0.17 |
| Mandelbrot | 6.62 ±0.12 |
| NBody | 3.98 ±0.15 |
| PageRank | 3.73 ±0.07 |
| Permute | 9.96 ±0.34 |
| Queens | 13.04 ±0.33 |
| QuickSort | 16.43 ±0.65 |
| Recurse | 11.18 ±0.28 |
| Richards | 109.49 ±10.34 |
| Sieve | 10.49 ±0.18 |
| Storage | 7.70 ±0.12 |
| Sum | 8.27 ±0.14 |
| Towers | 4.61 ±0.14 |
| TreeSort | 5.90 ±0.35 |
| WhileLoop | 6.74 ±0.20 |
| grmtools▶ | |
| Eclipse | 5.81 ±0.07 |
| Hadoop | 5.27 ±0.04 |
| Jenkins | 5.21 ±0.04 |
| Spring | 4.94 ±0.05 |
| Ripgrep▶ | |
| Alternates | 0.58 ±0.02 |
| Alternates (-i) | 0.72 ±0.02 |
| Literal | 0.53 ±0.02 |
| Literal (-i) | 0.59 ±0.02 |
| Literal (default) | 0.48 ±0.02 |
| Literal (mmap) | 0.63 ±0.02 |
| Literal (mmap, -i) | 0.65 ±0.02 |
| Literal (regex) | 0.52 ±0.02 |
| UTF Greek | 2.70 ±0.02 |
| UTF Greek (-i) | 2.71 ±0.03 |
| UTF Word | 0.53 ±0.02 |
| UTF Word (alt.) | 0.52 ±0.02 |
| Word | 0.51 ±0.02 |
| som-rs-bc▶ | |
| Bounce | 4.34 ±0.04 |
| BubbleSort | 3.76 ±0.05 |
| DeltaBlue | 5.76 ±0.11 |
| Dispatch | 4.91 ±0.35 |
| Fannkuch | 3.85 ±0.29 |
| Fibonacci | 6.15 ±0.17 |
| FieldLoop | 3.14 ±0.15 |
| GraphSearch | 1.54 ±0.03 |
| IntegerLoop | 3.94 ±0.15 |
| JsonSmall | 6.70 ±0.73 |
| List | 3.72 ±0.09 |
| Loop | 4.11 ±0.17 |
| Mandelbrot | 2.91 ±0.13 |
| NBody | 1.72 ±0.06 |
| PageRank | 1.51 ±0.02 |
| Permute | 3.84 ±0.09 |
| Queens | 4.53 ±0.07 |
| QuickSort | 5.28 ±0.09 |
| Recurse | 5.84 ±1.85 |
| Richards | 20.23 ±0.81 |
| Sieve | 3.76 ±0.12 |
| Storage | 3.23 ±0.05 |
| Sum | 4.03 ±0.36 |
| Towers | 2.20 ±0.05 |
| TreeSort | 1.71 ±0.03 |
| WhileLoop | 3.90 ±0.09 |
표 12. E Elision 각 벤치마크의 사용자 시간(초): 생략 전/후. 30회 평균, 99% CI.
| 평균 힙 풋프린트(MiB) | |
|---|---|
| 생략 전 | |
| Alacritty▶ | |
| Cur. Motion | 3.76 ±0.06 |
| Dense Cells | 3.74 ±0.06 |
| Light Cells | 3.76 ±0.08 |
| Scroll | 3.88 ±0.13 |
| Scroll (fullscreen) | 6.46 ±0.28 |
| Scroll Btm | 3.72 ±0.07 |
| Scroll Btm (small) | 3.75 ±0.05 |
| Scroll Top | 3.78 ±0.08 |
| Scroll Top (small) | 3.76 ±0.06 |
| Unicode | 3.73 ±0.15 |
| fd▶ | |
| execution | 17.18 ±0.33 |
| extension | 13.52 ±0.75 |
| hi | 15.14 ±0.36 |
| output | 17.54 ±0.65 |
| pattern | 37.79 ±5.22 |
| type | 15.80 ±0.40 |
| som-rs-ast▶ | |
| bounce | 309.85 ±43.90 |
| bubblesort | 334.97 ±6.55 |
| deltablue | 305.24 ±31.74 |
| dispatch | 345.26 ±18.67 |
| fannkuch | 412.43 ±5.54 |
| fibonacci | 382.32 ±22.98 |
| fieldloop | 326.47 ±8.38 |
| graphsearch | 100.82 ±4.86 |
| integerloop | 323.50 ±16.42 |
| jsonsmall | 257.67 ±34.84 |
| list | 236.78 ±5.27 |
| loop | 332.20 ±14.75 |
| mandelbrot | 276.68 ±4.14 |
| nbody | 151.00 ±2.63 |
| pagerank | 193.25 ±1.12 |
| permute | 284.84 ±43.08 |
| queens | 278.89 ±12.36 |
| quicksort | 515.72 ±20.82 |
| recurse | 429.81 ±12.37 |
| richards | 1187.31 ±98.12 |
| sieve | 355.11 ±17.79 |
| storage | 196.36 ±9.70 |
| sum | 320.61 ±11.55 |
| towers | 174.90 ±4.23 |
| treesort | 92.65 ±4.87 |
| whileloop | 272.66 ±10.05 |
| grmtools▶ | |
| Eclipse | 1993.86 ±9.04 |
| Hadoop | 1882.88 ±1.55 |
| Jenkins | 1876.35 ±14.92 |
| Spring | 1752.72 ±1.68 |
| Ripgrep▶ | |
| Alternates | 28.23 ±1.59 |
| Alternates (-i) | 29.52 ±1.66 |
| Literal | 25.14 ±1.52 |
| Literal (-i) | 26.69 ±1.56 |
| Literal (default) | 25.62 ±1.59 |
| Literal (mmap) | 26.91 ±1.78 |
| Literal (mmap, -i) | 28.72 ±1.66 |
| Literal (regex) | 25.87 ±2.01 |
| UTF Greek | 26.57 ±1.40 |
| UTF Greek (-i) | 26.85 ±1.54 |
| UTF Word | 28.03 ±1.57 |
| UTF Word (alt.) | 25.56 ±1.60 |
| Word | 29.35 ±2.05 |
| som-rs-bc▶ | |
| bounce | 138.59 ±5.18 |
| bubblesort | 121.69 ±6.72 |
| deltablue | 186.12 ±1.32 |
| dispatch | 168.63 ±7.00 |
| fannkuch | 139.94 ±5.95 |
| fibonacci | 205.88 ±10.08 |
| fieldloop | 98.52 ±4.07 |
| graphsearch | 45.81 ±1.21 |
| integerloop | 133.10 ±6.16 |
| jsonsmall | 164.80 ±5.83 |
| list | 106.38 ±7.84 |
| loop | 144.73 ±6.09 |
| mandelbrot | 90.31 ±4.84 |
| nbody | 58.61 ±1.77 |
| pagerank | 69.21 ±0.08 |
| permute | 126.65 ±5.94 |
| queens | 157.93 ±5.89 |
| quicksort | 183.42 ±4.54 |
| recurse | 169.34 ±7.22 |
| richards | 582.34 ±41.87 |
| sieve | 131.11 ±5.83 |
| storage | 71.95 ±2.32 |
| sum | 136.99 ±5.40 |
| towers | 71.09 ±3.09 |
| treesort | 57.12 ±2.12 |
| whileloop | 132.37 ±2.45 |
표 13. E Elision에서 파이널라이저 생략 전/후 평균 힙 풋프린트(MiB). heaptrack 리샘플링 추적의 30회 산술 평균, 99% CI(§8.1.4).