Intro

python 최적화 스터디를 하이퍼커넥트 기술 블로그 포스팅을 리뷰하며 진행하고 있다. 이 포스팅은 그중 #1 상황에 따라 gc가 병목일 수 있다. 이런 경우 gc 발동 조건을 튜닝할 수 있다.를 리뷰한 포스팅이다.

what is GC?

garbage collection은 쉽게 생각하면 메모리 관리이다. 안 쓰는 객체(garbage)를 메모리에서 확인하여(collection) 삭제하는 방식으로 리소스를 관리한다.

GC를 사용하는 언어

• GC 사용 X: 대부분 컴파일 언어(Java, C# 제외)
• GC 사용 O: Java, C#, 스크립트 언어(Python, JavaScript)

C, C++ 등 대부분의 컴파일 언어에서는 동적 할당된 메모리, 쉽게 말하면 생성된 객체를 사용자가 직접 관리하도록 한다. C에서는 stdlib.h 헤더에 있는 malloc()과 free(), C++에서는 new와 delete로 사용자가 직접 메모리를 조작해야 한다.

python, javascript 등 스크립트 언어에서는 사용자가 직접 메모리 관리할 일이 많지 않다. 따라서 사용하지 않는 객체를 인터프리터가 판단하여 알아서 메모리 관리를 해 준다.

모든 컴파일 언어가 메모리 관리를 사용자에게 맡기지는 않는다. 이를테면 Java와 C#의 경우, 컴파일 단계에서 GC로 리소스 관리가 이루어진다.

GC 사용의 장단점

장점	단점
프로그래머가 관리할 필요가 없어진다.	어떤 메모리를 해제할지 결정하는 데 비용이 든다.
이미 해제된 메모리에 접근하는 버그를 방지한다.	쓰레기 수집이 일어나는 타이밍이나 점유 시간을 예측하기 어렵다.
이미 해제된 메모리를 다시 해제하는 버그를 방지한다.	할당된 메모리가 해제되는 시점을 알 수 없다.
더 이상 필요하지 않은 메모리가 해제되지 않는 버그를 방지한다.	쓰레기 수집으로 인한 일시적 정지는 실시간 시스템에 적합하지 않을 수 있다.

+ RAII(Resource Acquisition is Initialization) 스타일의 프로그래밍에서는 자원 해제 시점을 알 수 없다. 메모리 할당은 객체 초기화에서 이루어지지만, 메모리 해제 시점은 명확하게 나타나지 않기 때문이다. C 혹은 C++에서 변수 혹은 객체의 소멸은 사용자가 직접 정의한다.

GC 의 종류

한국어 위키피디아와 영어 위키피디아를 참고하여 정리했다.

포인터 추적 방식

접근 가능한 객체

변수가 가리키는 객체: 변수라 함은 콜 스택에 정의된 지역/전역 변수 모두.
재귀적 정의: 접근 가능한 객체가 가리키는 모든 객체 또한 접근 가능

이런 접근 가능한 객체는 포인터 추적 방식에서 사용하는 개념이다. 포인터 추적 방식은 가리키는 대상의 유무에 따라 해제할 객체인지, 남겨둘 객체인지 판별한다.

표시하고 쓸기(mark and sweep) 기법

1. 할당된 메모리 영역에서 1비트만 표시 영역으로 남겨둔다
2. 표시 단계에서 접근 가능한 객체를 모두 "사용 중"으로 표시한다.
3. 표시가 끝나면 "사용 중" 표시가 없는 객체는 해제 대상 객체가 된다.
4. 쓸기 단계에서 해제 대상 객체를 모두 해제한다.

단점

• 표시 단계에서 메모리 변경이 없어야 하므로, 전체 시스템이 정지된다.
• 메모리 페이징을 사용하는 운영체제에서 성능이 저하된다.

삼색 표시(tri-color mark) 기법

1. 접근 불가능 객체를 흰색, 검사 안한 객체를 회색, 흰색이 아닌 객체를 검은 색으로 표시한다. GC 시작 시 root 변수가 가리키는 객체는 회색으로, 그 외 모든 객체는 흰색으로 표시한다.
2. 회색 객체를 모두 검은 색으로 표시하고 이들이 가리키는 객체를 회색으로 표시한다.
3. 회색 객체가 하나도 없어질 때까지 위 과정을 반복한다.
4. 반복 후 남은 흰색 객체는 접근 불가능 객체이므로 모두 해제 한다.

객체 이동 기법

해제할 객체 표시를 완료하고 해제하지 않은 객체를 메모리의 다른 영역으로 복사하는 기법이다. 다음과 같은 실용적인 장점이 있다.

• 재사용 영역과 사용 중인 영역을 표시하기 위한 추가 작업이 필요 없다. → 할당과 해제가 빠르게 이뤄진다.
• 할당된 메모리들이 단편화(fragmentation)되는 걸 막을 수 있다.
• 연결 리스트와 같은 연결형 자료구조에서 연결된 객체들이 메모리 상 가까운 위치에 할당될 확률이 높아진다. → 캐시와 관련해서 성능이 향상된다.

하지만 주기적으로 메모리 주소가 변경되어 포인터 연산을 사용할 수 없다.

세대 단위 GC

객체를 할당한 시간에 따라 세대 별로 구분한다. 각 세대는 다른 메모리 영역에 할당된다. 현재 메모리 영역이 꽉 차면 해당 객체들을 메모리 영역으로 옮긴다. 즉 현재 세대에서 살아남은 객체를 더 오랜 세대로 옮긴다.

• 새로 할당된 영역에서는 대부분 객체들이 빠르게 해제됨
• 오래된 영역에서는 객체가 변하지 않을 확률이 높음
• 메모리 일부 영역만 주기적으로 수집한다. → 효율적 메모리 관리
• Java, .NET Framework등 현대적 언어들이 대부분 이 기법을 사용한다.

참조 횟수(reference counting) 계산 방식

객체의 참조 횟수를 기억하여 0이 되면 객체를 해제한다.

장점	단점
객체가 접근 불가능해지는 즉시 해제 → 프로그래머가 해제 시점을 어느 정도 예측할 수 있다.	두개 이상의 객체가 서로를 가리키는 순환 참조 문제 → CPython에서는 약한 참조로 이를 해결한다.
객체가 사용 직후 해제된다. → 캐시에 저장되어 있을 확률이 높아 빠른 해제 가능	멀티스레드 환경에서 스레드끼리 공유하는 객체의 참조 횟수 계산을 위해 Atomic 혹은 락(GIL)을 걸어야 한다. → 리눅스 커널에서는 스레드 참조 횟수가 0이 될때만 전역 참조 횟수를 확인
	참조 횟수가 0이 되면, 해당 객체가 가리키는 다른 객체들도 0으로 만드는 작업 → 실시간 시스템에 적합하지 않을 수도 있다.

+ C++<memory> 헤더를 include해 사용하는 스마트 포인터도 참조 횟수 계산 방식을 사용한다. std::unique_ptr, std::shared_ptr 객체를 생성하면 참조 카운트가 0이 되면 자동 해제되는 방식이다.

CPython의 GC

CPython은 내부적으로 C언어로 구성되었다. 우선 CPython에서 GC 동작을 알아보기 전에 앞서 언급한 순환 참조 문제를 어떻게 다루는 지 알아보자.

C-level에서 보기

StackOverflow를 참고했다.

// Where `obj` is the object who's references we want to find
traverseproc traverse;
if (! PyObject_IS_GC(obj))
    continue;
traverse = Py_TYPE(obj)->tp_traverse;
if (! traverse)
    continue;
if (traverse(obj, (visitproc)referentsvisit, result)) {
    Py_DECREF(result);
    return NULL;
}

이 코드에서 주목할 내용은 tp_traverse이다. tp_traverse는 객체 내부적으로 참조하는 객체를 탐색하는 함수이다. 예를 들어 list형 객체에서는 각 원소를 탐색하는 방식이다. 객체 타입(Py_TYPE())에 따라 tp_traverse가 가리키는 함수가 달라진다. 예를 들어 CPython에서 str 객체의 경우 tp_traverse는 NULL이 되고, list 객체의 경우 tp_traverse는 list_traverse를 가리킨다.

다음 코드는 list_traverse 구현부이다.

static int
list_traverse(PyListObject *o, visitproc visit, void *arg)
{
    Py_ssize_t i;

    for (i = Py_SIZE(o); --i >= 0; )
        Py_VISIT(o->ob_item[i]);
    return 0;
}

Python-level에서 보기

이번에는 조금 추상화된 객체에서 순환 참조를 살펴보자. Python Developer's Guide를 참고했다. 위 블로그에서 4개 예시를 보여준다.

1. 예외 처리: __traceback__ 내부에서 접근하여 자체 예외를 다시 접근할 수 있다.
2. 모듈 수준의 함수: __globals__ 딕셔너리에 모듈 함수 이름으로 자신을 참조할 수 있다.
3. 인스턴스가 참조하는 상위(super) 객체: 인스턴스는 자신의 클래스를 참조하고, 클래스는 자신의 모듈을 참조할 수 있다. 이때 다시 자신의 모듈에서 내부 클래스를 참조하고, 클래스에서 내부 인스턴스를 참조하면서 순환 참조가 일어날 수 있다.
4. Circular 그래프: 그래프에서 두 개 이상 노드가 서로를 참조하면서 순환할 수 있다. 가장 보편적으로 생각할 수 있는 순환 참조이다.

그 중 4번 예시를 통해 Python의 GC를 설명하겠다.

import gc
import sys

gc.collect() # 기존에 메모리 영역에 있는 접근 불가 객체 지우기

class Link:
    def __init__(self, next_link=None):
        self.next_link = next_link
        
link_3 = Link()
link_2 = Link(link_3)
link_1 = Link(link_2)

link_3.next_link = link_1

A = link_1
print(f"link_1: {sys.getrefcount(link_1)}, ", end="")
print(f"link_2: {sys.getrefcount(link_2)}, ", end="")
print(f"link_3: {sys.getrefcount(link_3)}")
del link_1, link_2, link_3

link_4 = Link()
link_4.next_link = link_4
print(f"link_4: {sys.getrefcount(link_4)}")
del link_4

print(f"unreachable: {gc.collect()}")

link_1: 4, link_2: 3, link_3: 3
link_4: 3
unreachable: 1

sys.getrefcount(obj)는 참조 카운트 + 1 만큼 반환한다. 그럼에도 Link로 생성된 객체들이 예상 숫자 + 1 만큼 반환되는 걸 볼 수 있다. 이는 sys.getrefcount()의 인자로 넘어가면서 한 번 더 참조되어 그렇다. 위 코드를 그림으로 살펴보면 다음과 같다.

GC 스캔은 객체의 참조 카운트가 0이 될 때까지 모든 객체의 참조 카운트를 1씩 감소하며 동작한다.

이들 중 link 3과 link 4는 참조 카운트가 0이 된 객체가 참조하고 있으므로 접근 불가 객체라고 임시 판단한다.

하지만 외부 변수 A는 link 1을 가리키고 있어 접근 가능한 객체이다. 이 때 link 1이 가리키는 link 2 또한 접근 가능하고 따라서 link 3도 접근 가능하다.

Cyclic GC에서 한계

조금만 생각해보면 이런 GC 방식은 매우 느리다는 걸 알 수 있다. 만약 이런 linked list의 노드가 수 만 개가 된다면? 실제로 파이썬의 built-in list 자료형은 더블 포인터로 구현되어 있다. 이 말은 각 요소가 연속된 메모리 공간에 할당된 것이 아닌, paging된 메모리에 할당되었음을 알 수 있다. 위 방법만 사용하면 모든 객체에서 reference graph를 그리며 접근 불가능한 cycle을 찾아야 하므로 메모리 해제가 느리게 일어난다.

이런 문제를 해결하기 위해 파이썬에서는 JVM 계열 언어의 GC 방식인 Generation 최적화를 사용한다. 대부분의 객체는 짧은 수명을 가진다. 오랜 수명을 가지는 객체는 전역 변수처럼 메모리에서 해제될 필요가 없다. 이 가설을 바탕으로 GC를 수행할 때마다 특정 generation 객체들만 스캔한다. young generation 객체는 자주, old generation 객체는 가끔 스캔하여 GC 동작을 관리한다.

---

내용을 자세하게 살피다 보니 글이 길어졌다. 다음 포스팅에서 이어서 JVM 계열 언어의 GC 방식과 Python Generation GC의 차이점을 중점적으로 다루겠다.