Garbage Collection in Julia

Introduction

줄리아는 비이동성, 부분 동시성, 병렬, 세대 기반 및 대부분 정밀한 마크-스위프 수집기를 가지고 있습니다(사용자가 C에서 줄리아를 호출하고자 할 경우 보수적인 스택 스캐닝을 위한 인터페이스가 옵션으로 제공됩니다).

Allocation

줄리아는 두 가지 유형의 할당기를 사용하며, 할당 요청의 크기에 따라 어떤 할당기가 사용되는지가 결정됩니다. 2k 바이트 이하의 객체는 스레드별 자유 목록 풀 할당기를 통해 할당되며, 2k 바이트보다 큰 객체는 libc malloc을 통해 할당됩니다.

줄리아의 풀 할당자는 서로 다른 크기 클래스의 객체를 분할하여, 풀 할당자가 관리하는 메모리 페이지(64비트 플랫폼에서 4개의 운영 체제 페이지를 포함)는 동일한 크기 클래스의 객체만 포함하도록 합니다. 풀 할당자의 각 메모리 페이지는 스레드별 비잠금 리스트에 저장된 페이지 메타데이터와 쌍을 이룹니다. 페이지 메타데이터에는 페이지에 살아있는 객체가 있는지 여부, 무료 슬롯의 수, 해당 페이지에 포함된 무료 리스트의 첫 번째 및 마지막 객체에 대한 오프셋과 같은 정보가 포함됩니다. 이러한 메타데이터는 수집 단계를 최적화하는 데 사용됩니다: 예를 들어, 살아있는 객체가 전혀 없는 페이지는 스캔할 필요 없이 운영 체제에 반환될 수 있습니다.

객체가 없는 페이지는 운영 체제에 반환될 수 있지만, 그와 관련된 메타데이터는 영구적으로 할당되며 주어진 페이지보다 더 오래 지속될 수 있습니다. 위에서 언급한 바와 같이, 할당된 페이지의 메타데이터는 스레드별 비잠금 리스트에 저장됩니다. 그러나 자유 페이지의 메타데이터는 페이지가 매핑되었지만 한 번도 접근되지 않은 경우(page_pool_clean), 페이지가 지연 수거되었고 백그라운드 GC 스레드에 의해 조언을 기다리고 있는 경우(page_pool_lazily_freed), 또는 페이지가 조언된 경우(page_pool_freed)에 따라 세 개의 별도 비잠금 리스트에 저장될 수 있습니다.

줄리아의 풀 할당자는 "계층화된" 할당 규칙을 따릅니다. 풀 할당자를 위해 메모리 페이지를 요청할 때, 줄리아는:

page_pool_lazily_freed에서 페이지를 요청해 보세요. 이 페이지는 마지막 스톱-더-월드 단계에서 비어 있었지만, 아직 동시 스위퍼 GC 스레드에 의해 매핑되지 않은 페이지를 포함하고 있습니다.
page_pool_lazily_freed에서 페이지를 할당하는 데 실패하면, 이전 페이지 할당 요청에서 mmap된 페이지이지만 한 번도 접근되지 않은 페이지를 포함하는 page_pool_clean에서 페이지를 할당하려고 시도합니다.
pool_page_clean에서 페이지를 가져오는데 실패하고 page_pool_lazily_freed에서 페이지를 가져오는데 실패하면, 이미 동시 스위퍼 GC 스레드에 의해 조언된 페이지와 그 기본 가상 주소가 재활용될 수 있는 페이지를 포함하는 page_pool_freed에서 페이지를 가져오려고 시도합니다.
모든 위의 시도가 실패하면, 페이지 배치를 mmap하고, 자신을 위해 한 페이지를 할당한 다음, 나머지 페이지를 page_pool_clean에 삽입합니다.

계층 풀 할당 다이어그램

Marking and Generational Collection

줄리아의 마크 단계는 객체 그래프에 대한 병렬 반복 깊이 우선 탐색을 통해 구현됩니다. 줄리아의 수집기는 이동하지 않으므로 객체의 나이 정보를 객체가 위치한 메모리 영역만으로는 결정할 수 없으며, 객체 헤더나 사이드 테이블에 어떤 식으로든 인코딩되어야 합니다. 객체 헤더의 가장 낮은 두 비트는 각각 마크 단계에서 객체가 스캔될 때 설정되는 마크 비트와 세대 수집을 위한 나이 비트를 저장하는 데 사용됩니다.

세대 수집은 스티키 비트를 통해 구현됩니다: 객체는 마크 비트가 설정되지 않은 경우에만 마크 스택으로 푸시되고 따라서 추적됩니다. 객체가 가장 오래된 세대에 도달하면, 이른바 "빠른 스위프" 동안 마크 비트가 재설정되지 않아 이러한 객체는 이후의 마크 단계에서 추적되지 않습니다. 그러나 "전체 스위프"는 모든 객체의 마크 비트를 재설정하여 이후의 마크 단계에서 모든 객체가 추적되도록 합니다. 객체는 생존하는 모든 스위프 단계에서 다음 세대로 승격됩니다. 변이자 측에서는 필드 쓰기가 쓰기 장벽을 통해 가로채져, 객체가 마지막 세대에 있고 필드에 쓰여지는 객체가 그렇지 않은 경우, 객체의 주소가 스레드별 기억 집합에 푸시됩니다. 이 기억 집합에 있는 객체는 이후의 마크 단계에서 추적됩니다.

Sweeping

Julia의 객체 풀 청소는 두 가지 범주로 나눌 수 있습니다: 풀 할당자가 관리하는 특정 페이지에 최소한 하나의 살아있는 객체가 포함되어 있다면, 해당 페이지의 죽은 객체를 통해 자유 목록이 연결되어야 합니다; 특정 페이지에 살아있는 객체가 전혀 포함되어 있지 않다면, 해당 페이지의 기본 물리적 메모리는 예를 들어 Linux에서 madvise 시스템 호출을 사용하여 운영 체제에 반환될 수 있습니다.

첫 번째 스위핑 카테고리는 작업 도용을 통해 병렬화됩니다. 두 번째 스위핑 카테고리의 경우, --gcthreads=X,1 플래그를 통해 동시 페이지 스위핑이 활성화되면, 우리는 뮤테이터 스레드와 동시에 백그라운드 스위퍼 스레드에서 madvise 시스템 호출을 수행합니다. 수집기의 세계 정지 단계 동안, 살아있는 객체가 없는 풀 할당 페이지는 처음에 pool_page_lazily_freed에 푸시됩니다. 그 후 백그라운드 스위핑 스레드가 깨어나고, pool_page_lazily_freed에서 페이지를 제거하고, madvise를 호출하며, 이를 pool_page_freed에 삽입하는 책임을 집니다. 위에서 설명한 바와 같이, pool_page_lazily_freed는 뮤테이터 스레드와도 공유됩니다. 이는 할당이 많은 다중 스레드 작업 부하에서 뮤테이터 스레드가 새로 mmap된 페이지에 접근하거나 madvised 페이지에 접근하는 것에서 오는 페이지 결함을 피하기 위해 종종 pool_page_lazily_freed의 페이지에서 직접 할당을 수행할 수 있음을 의미하며, 백그라운드 스위퍼 스레드는 일부 페이지가 이미 뮤테이터에 의해 청구되었기 때문에 줄어든 수의 페이지에 대해 madvise를 수행해야 합니다.

Heuristics

GC 휴리스틱은 가비지 수집 사이의 할당 간격 크기를 변경하여 GC를 조정합니다.

GC 휴리스틱은 수집 후 힙 크기가 얼마나 큰지를 측정하고, https://dl.acm.org/doi/10.1145/3563323에 설명된 알고리즘에 따라 다음 수집을 설정합니다. 요약하자면, 이는 힙 목표가 살아있는 힙과 제곱근 관계를 가져야 하며, GC가 객체를 해제하는 속도와 변조자가 할당하는 속도에 따라 조정되어야 한다고 주장합니다. 휴리스틱은 사용 중인 페이지 수와 malloc을 사용하는 객체 수를 세어 힙 크기를 측정합니다. 이전에는 살아있는 객체 수를 세어 힙 크기를 측정했지만, 이는 단편화를 고려하지 않아 잘못된 결정을 초래할 수 있었습니다. 또한 이는 스레드 로컬 정보(할당)를 사용하여 프로세스 전체에 대한 결정(언제 GC를 수행할지)을 내리는 것을 의미했습니다. 페이지를 측정하는 것은 결정이 전역적임을 의미합니다.

GC는 힙 크기가 허용된 최대 크기의 80%에 도달하면 전체 수집을 수행합니다.