파이썬의 메모리 관리

참고

- https://github.com/python/cpython

- https://devguide.python.org/compiler/

 

 

파이썬은 메모리 관리를 쉽게 하기 위해 PyArena와 Arena라는 것을 사용한다.

 

이 둘의 차이는 PyArena는 파이썬 코드를 AST로 컴파일한 객체의 메모리 관리를 위해 사용되는 것이고,(.py 파일을 실행할 때 사용됨) Arena는 실제로 우리가 생각하는 객체의 메모리 관리에 사용한다.

그렇다고 둘이 아예 분리해서 생각하면 안 된다. PyArena에서 사용되는 객체(변수, 상수 등 a_objects에 저장)는 Arena에서 관리되기 때문이다.

 

PyArena는 pyarena.h/pyarena.c에 상당히 깔끔한 코드로 구현되어 있고, Arena는 비교적 지저분하게 obmalloc.c에 구현되어 있다.

 

PyArena

struct _arena {
    block *a_head; // 블록 헤더
    block *a_cur; // 현재 블록 커서
    PyObject *a_objects; // 객체 리스트
};

typedef struct _arena PyArena;

#define DEFAULT_BLOCK_SIZE 8192
#define ALIGNMENT             8

typedef struct _block {
    size_t ab_size; // 블록의 크기. 보통 디폴트 사이즈인 8KB가 저장되지만 더 큰 사이즈를 지정할 수도 있다.
    size_t ab_offset; // 현재 사용된 블록의 오프셋
    struct _block *ab_next; // 다음 블록의 포인터
    void *ab_mem; // 해당 블록의 할당 가능한 첫번째 포인터
} block;

 

 

PyArena는 한 프로세스에 하나만 생성되고, N개의 블록을 저장한다.

PyArena에서의 블록은 함수, 클래스, 문법 등을 할당한다.

Arena의 Memory Allocator를 사용하여 할당되지만 Arena에서 512바이트보다 큰 메모리는 stdlib.h의 malloc()으로 할당한다.

블록은 최소 8192바이트이므로 항상 stdlib.h의 malloc()으로 할당되어 OS에게 메모리 관리를 맡기게 된다.

/*
PyArena_Malloc
-> block_alloc
-> -> block_new
순으로 호출되며 메모리를 할당함
*/

void* PyArena_Malloc(PyArena *arena, size_t size)
{
    // 블록 할당
    void *p = block_alloc(arena->a_cur, size);
    // 현재 블록 커서를 이동
    arena->a_cur = arena->a_cur->ab_next;
    return p;
}

// PyArena의 블록을 할당하는 함수
static void* block_alloc(block *b, size_t size)
{
    void *p;
    size = _Py_SIZE_ROUND_UP(size, ALIGNMENT);
    // 이미 할당되어 있는 블록의 남은 사이즈로 충당 가능하면 할당하지 않음
    if (b->ab_offset + size > b->ab_size) {
        block *newbl = block_new(
                        size < DEFAULT_BLOCK_SIZE ?
                        DEFAULT_BLOCK_SIZE : size);
        if (!newbl)
            return NULL;

        b->ab_next = newbl;
        b = newbl;
    }

    p = (void *)(((char *)b->ab_mem) + b->ab_offset);
    b->ab_offset += size;
    return p;
}

static block* block_new(size_t size)
{
	// Arena의 Memory Allocator로 블록 할당
    block *b = (block *)PyMem_Malloc(sizeof(block) + size);
    if (!b)
        return NULL;
    b->ab_size = size;
    b->ab_mem = (void *)(b + 1);
    b->ab_next = NULL;
    b->ab_offset = (char *)_Py_ALIGN_UP(b->ab_mem, ALIGNMENT) -
            (char *)(b->ab_mem);
    return b;
}

 

 

PyArena 멤버의 a_objects는 사실 PyListObject의 포인터이다.

Py_TRACE_REFS 라는 옵션으로 컴파일 시 현재 메모리 상태를 추적할 수 있는데 디버깅용 PyObject의 상위 멤버들과 PyListObject의 상위 멤버의 오프셋이 동일하다.

PyObject와 PyListObject는 객체의 메모리 사이즈마저 동일해서 중복코드를 줄이기 위하여 PyObject*로 캐스팅해서 사용하는 것으로 보인다.

PyListObject는 PyObject* 를 저장하기 위해 PyObject 2차원 포인터를 멤버로 가진다.

따라서 PyObject*를 저장할 때마다 ob_item은 Realloc 돼야 하지만 시스템에 무리가 가는 작업이므로 할당 횟수를 줄이기 위해 추가적으로 사이즈를 조금 더 할당해 놓는다. (수열 패턴: 0, 4, 8, 16, 25, 35, 46, 58, 72, 88, ...)

typedef struct {
    PyObject **ob_item; // Arena에 추가된 objects
    Py_ssize_t allocated; // allocated count
} PyListObject;

int PyArena_AddPyObject(PyArena *arena, PyObject *obj)
{
    // Arena에 PyObject 추가
    PyList_Append((PyListObject*)arena->a_objects, obj);
    
    // PyObject는 생성된 후 PyObject_INIT()이 생성자 격으로 호출되는데,
    // 이 때 어디서 참조되지 않아도 Reference Count를 1 증가시킨다.
    // PyArena에 정상 추가된 후 임시로 증가된 Reference Count를 감소시키는 작업이다.
    Py_DECREF(obj);
}

int PyList_Append(PyListObject *op, PyObject *newitem)
{
    // ob_item size를 가져옴
    Py_ssize_t n = PyList_GET_SIZE(self);

    // ob_item Reallocation (Realloc 규칙이 있음: 0, 4, 8, 16, 25, 35, 46, 58, 72, 88, ...)
    list_resize(self, n+1);

    // Reference Count 증가
    Py_INCREF(newitem);
    
    // ob_item에 객체 추가
    PyList_SET_ITEM(self, n, newitem);
    
    return 0;
}

 

 

Garbage Collection

PyListObject에 추가된 객체는 다음 두 가지 조건 중 하나를 만족하면 제거된다.

1. Reference Count가 0이 되었을 때

2. Garbage Collector에 의해 

 

Reference Count가 0이 되면 그냥 제거하면 되지 Garbage Collector이라는 것은 왜 존재하는 것일까?

아래의 파이썬 코드를 참고하면 이유를 알 수 있다.

def func():
    a = [] # a's Ref Count: 1
    b = [] # b's Ref Count: 1
    a.append(b) # b's Ref Count: 2
    b.append(a) # a's Ref Count: 2

func()
# a's Ref Count: 1
# b's Ref Count: 1

 

위 코드에서 변수 a, b는 선언될 때 Arena의 객체 리스트에 추가되며 Reference Count가 각각 1이다.

그런데 서로 참조하는 상황이 생기며 Reference Count는 2가 된다.

func() 호출이 끝나며 Reference Count를 감소시키지만 서로 참조하는 상황이 생겨 Reference Count는 0이 되지 못한다.

 

이 상황을 어떻게 해결할 수 있을까?

객체 전부를 하나씩 순환하며 검사하려는 객체의 Reference Count에서 다른 객체에서 검사하려는 객체를 참조 중인 count를 뺀 값이 0일 때 해제하면 된다.

 

객체가 많을 수록 캐시 미스가 빈번하게 발생하며 CPU 리소스를 크게 잡아먹을 것이다. (인스타그램은 이러한 이슈로 GC 사용을 하지 않는다고 한다)

그래서 파이썬은 기본적으로 threshold cycle마다 GC를 실행한다.

주기는 총 3개로 generation(세대)이라 부르며 각각 700, 10, 10이다.

만들어진지 얼마 되지 않은 객체일 수록 앞세대에 저장되어 있다.

 

객체가 생성되면 0세대에 저장되고, 0세대의 count가 1 증가하지만 1세대는 0세대의 객체가 옮겨질 때 증가하므로 최소 700번에 한 번, 2세대는 1세대의 객체가 옮겨질 때 증가해서 최소 7000번에 한 번 증가한다.

#define NUM_GENERATIONS 3

unsigned int collect_generations(struct _gc_runtime_state *state)
{
    int i;
    // 오래된 세대부터 검사. 오래된 세대가 가비지컬렉션 실행 조건에 걸리면 하위 세대들도 같이 검사
    for(int current_generation = NUM_GENERATIONS - 1; current_generation >= 0; current_generation--)
    {
        // threshold 주기를 초과하면 GC 실행
        if (state->generations[current_generation].count > state->generations[current_generation].threshold)
        {
            // 다음 세대가 마지막 세대가 아니면 다음 세대의 count 증가
            if (current_generation + 1 < NUM_GENERATIONS)
                state->generations[current_generation + 1].count += 1;
            
            // 검사하려는 세대 이하 세대들의 count를 0으로 초기화
            for (i = 0; i <= current_generation; i++)
                state->generations[i].count = 0;

            // 검사하려는 세대보다 적은 세대들을 merge함. (검사하려는 세대 뒤에 붙이는 형식)
            for (i = 0; i < generation; i++)
                gc_list_merge(GEN_HEAD(state, i), GEN_HEAD(state, current_generation));
            
            // young: 현재 검사하려는 세대
            // old: 현재 검사하려는 세대의 다음 세대 (검사하려는 세대가 마지막이면 young과 같은 세대)
            PyGC_Head *young, *old;
            young = GEN_HEAD(state, current_generation);
            if (current_generation < NUM_GENERATIONS - 1)
                old = GEN_HEAD(state, current_generation + 1);
            else
                old = young;
            
            // 도달할 수 없는 객체를 찾아서 unreachable에 저장
            PyGC_Head *unreachable;
            deduce_unreachable(young, &unreachable);
            
            // 도달할 수 없는 객체들을 다음 세대로 병합
            if (young != old)
            {
                gc_list_merge(young, old);
            }
            else
            {
                // long_lived_pending: 한 세대만 검사를 해서 전체 세대의 검사를 기다리고 있는 팬딩 객체 (마지막 세대는 해당사항이 없어서 0으로 초기화)
                // long_lived_total: 마지막 세대의 reachable 객체 개수
                state->long_lived_pending = 0;
                state->long_lived_total = gc_list_size(young);
            }
            
            // unreachable 객체 중 소멸자가 정의된 객체들을 finalizers로 이동 (복사 x)
            move_legacy_finalizers(&unreachable, &finalizers);
            
            // finalizers 객체의 정보를 순회하며 도달 가능한 객체를 finalizers에 추가
            move_legacy_finalizer_reachable(&finalizers);
            
            // unreachable에서 콜백이 있는 일부 약한참조를 회수
            Py_ssize_t collected_count = handle_weakrefs(&unreachable, old);
            
            // 소멸자가 있는 경우 호출
            finalize_garbage(&unreachable);
            
            // 소멸자 호출 후 살 수 있는 객체들을 final_unreachable에 병합
            PyGC_Head final_unreachable;
            handle_resurrected_objects(&unreachable, &final_unreachable, old);
            
            // collected_count: 가비지 컬렉터가 제거한 객체 개수
            // uncollected_count: 가비지 컬렉터가 제거하지 못한 객체 개수
            collected_count += gc_list_size(&final_unreachable);
            uncollected_count = gc_list_size(&finalizers);
            
            // 가비지 객체 제거
            delete_garbage(state, &final_unreachable, old);
            
            // 수집하지 못한 객체들을 다음 세대로 병합시킴
            handle_legacy_finalizers(state, &finalizers, old);
        }
    }
}

// 도달 불가능 객체 탐지 함수
inline void deduce_unreachable(PyGC_Head *base, PyGC_Head *unreachable)
{
    // base에서 물고 있는 오브젝트(gc runtime)의 Reference Count를 실제 사용되고 있는 오브젝트의 Reference Count로 초기화
    update_refs(base);
    
    // 리스트를 순회하며 자기 자신의 참조 카운트를 감소시킴
    // 객체의 타입마다 선언되어 있는 tp_traverse()를 호출하고, tp_traverse()에서 visit_decref()를 콜백으로 호출하여 감소시키는 방식
    traverseproc traverse;
    for (PyGC_Head *gc = GC_NEXT(base); gc != base; gc = GC_NEXT(gc))
    {
        PyObject *op = FROM_GC(gc);
        
        (void)Py_TYPE(op)->tp_traverse(
                                          FROM_GC(gc),
                                          (visitproc)visit_decref,
                                          op
                                      );
    }
    
    // Reference Count를 검사하여 도달 불가능한 객체(Ref Count: 0)들을 unreachable에 저장
    move_unreachable(base, unreachable);
}

// tp_traverse에서 콜백으로 호출하는 참조 카운트를 감소시키는 함수 (deduce_unreachable에서 사용됨)
static int visit_decref(PyObject *op, void *parent)
{
    if (PyObject_IS_GC(op)) {
        PyGC_Head *gc = AS_GC(op);
        if (gc_is_collecting(gc)) {
            gc_decref(gc);
        }
    }
    return 0;
}

 

 

Arena

이제 일반 객체를 관리하는 Arena에 대해 알아보자.

Arena는 메모리 풀을 관리하는 용도로 사용된다.

메모리 풀은 블럭을 관리하는 데에 사용된다. 블럭은 객체가 저장될 공간이다.

 

그림으로 간단하게 표현하면 이런 구조이다.

Arena, Pool, Block 구조

 

 

 

풀과 블럭의 메모리는 아레나를 할당할 때 할당한 메모리를 사용한다.

대부분의 객체는 이런 구조로 할당되지만 512바이트가 넘는 객체는 OS의 Memory Allocator(malloc)를 사용하여 할당된다.

#define SMALL_REQUEST_THRESHOLD 512

// 객체 메모리 할당 함수
static void* _PyObject_Malloc(void *ctx, size_t nbytes)
{
    void* ptr = pymalloc_alloc(ctx, nbytes);
    if (LIKELY(ptr != NULL)) {
        return ptr;
    }

    // 일반 malloc()이 호출됨
    ptr = PyMem_RawMalloc(nbytes);
    if (ptr != NULL) {
        raw_allocated_blocks++;
    }
    return ptr;
}

static inline void* pymalloc_alloc(void *ctx, size_t nbytes)
    ...

    // 512바이트보다 크면 NULL 리턴
    if (UNLIKELY(nbytes > SMALL_REQUEST_THRESHOLD)) {
        return NULL;
    }
    ...
}

 

 

아레나는 힙 파편화를 줄이기 위해 Windows 계열이면 VirtualAlloc()을, 리눅스 계열이면 mmap()을 사용하여 256KB를 페이지 단위로 lazy allocation한다.

둘 다 아닌 경우 stdlib.h의 malloc()을 사용한다.

 

아레나에 풀은 64개씩 존재하며, 파편화 방지를 위하여 할당하려는 바이트 수마다 풀의 인덱스와 할당되는 바이트 크기가 다르다.

예를 들면 할당하려는 객체가 27바이트면 32바이트가 할당되고, 인덱스 3의 풀에 할당이 된다.

하나의 풀의 크기는 4KB이다.

/* Request in bytes     Size of allocated block      Size class idx
 * ----------------------------------------------------------------
 *        1-8                     8                       0
 *        9-16                   16                       1
 *       17-24                   24                       2
 *       25-32                   32                       3
 *       33-40                   40                       4
 *       41-48                   48                       5
 *       49-56                   56                       6
 *       57-64                   64                       7
 *       65-72                   72                       8
 *        ...                   ...                     ...
 *      497-504                 504                      62
 *      505-512                 512                      63
 *
 *      0, SMALL_REQUEST_THRESHOLD + 1 and up: routed to the underlying
 *      allocator.
 */

 

 

 

다시 아레나의 구조를 조금 더 자세히 그려보면 이렇게 된다.

Arena 구조