CPython in Depth [1] — Overview

Introduction

최근에 파이썬을 다룰 일이 많아지면서 내부 동작과 그 구현을 이해해야 할 필요성이 증대하였다. 따라서 CPython Internals 와 같이 좋은 책을 탐구하기 시작하였다. Pycon 2023의 한성민님 발표도 도움이 된다. 이번 시간에는 간단하게 CPython 데이터 타입에 따라 내부 동작이 달라지는 내용을 살펴보고 그 의의에 대해 알아보겠다.

먼저 CPython을 다루려면 크게 다음의 이야기를 해보아야 한다.

1. Scheduler : 명령어를 관리하고 각 코드 조각이 언제 실행되는지를 결정하는 OS 레벨에서의 스케줄러다.
2. Virtual Machine: 런타임 수준의 인터프리터의 CPU 명령을 실행하는 환경을 의미한다.
3. Lexer: 파이썬 코드를 분석한다. 가상 머신의 단위에서 CPU의 명령을 해석하는 단위의 프로그램이다.
4. Optimizer: 불필요한 연산을 제거하는 등의 최적화를 담당하는 프로그램이다.
5. Library: 사전에 작성된 스니펫을 제공하는 모듈 단위의 프로그램이다.

우리가 작성하는 파이썬 프로그램은 일반적으로 Native Library 단위의 애플리케이션과 표준 모듈을 바탕으로 동작하는 데 그 과정에서 파이썬의 런타임이 우리가 작성한 코드를 해석하게 된다. 사용자 레벨에서 Python 프로그램의 소스코드를 작성했다면 이제 컴파일러 단의 레벨에서는 다음의 과정을 수행하게 된다.

• Lexical Analysis
• Syntax Parsing
• Abstract Syntax Tree (AST): 특히 런타임 레벨에서의 데이터 타입은 AST → Bytecode → Interpreter 단위로 넘어가서 진행된다.
• Compile
• Bytecode

이제 최종적으로 가상환경의 런타임 레벨에서는 Code Execution이 실행된다. 여기서 우리가 말하는 컴파일러 단위는 파이썬의 언어 단위의 구현체라고 할 수 있는데 CPython에 대한 생태계의 의존도가 제일 높고 가장 주목해서 보아야 하는 프로젝트이다. 그 외에 RustPython도 최근 인기를 끌고 있다. CPython에서는 AST 구문 분석기가 ast.c 로 표현되고 이를 바이트코드 형태로 표현하는 것을 compile.c 프로그램의 로직에서 확인할 수 있다. 또한 코드를 실행하는 단위는 ceval.c 이고 해당 단위는 인터프리터의 런타임 수준 VM에서 실행한다.

Syntax Parsing

https://www.youtube.com/watch?v=L0tRwS3K3N4

데이터 타입에 따라 구문 분석기가 상이하게 동작할 수 있음을 알아야 한다. 예를 들어 간단한 정수를 할당할 때는 CPython에서는 PyLongObj 라는 struct가 있다. 해당 struct에서는 PyObject.init을 통해 함수를 초기화하고, 이후에 충분한 메모리가 있는지 등의 확인 이후에 PyObject.malloc 을 호출하여 메모리를 할당하게 된다.

            for (cur = start, i = 0; i < slicelength;
                 cur += (size_t)step, i++) {
                garbage[i] = selfitems[cur];
                ins = Py_NewRef(seqitems[i]);
                selfitems[cur] = ins;
            }

            for (i = 0; i < slicelength; i++) {
                Py_DECREF(garbage[i]);
            }

리스트의 경우도 다르다. 예를 들어 리스트 슬라이싱을 확인하면 먼저 바꾸고자 하는 selfitems 의 인덱스에 따라 참조값을 가져와서 garbage Array의 인덱스 값에 할당한 다음, 새로운 레퍼런스를 만들어 할당하고 다시 Reference의 Count를 줄이는 방식으로 구현되어 있다. 즉, 리스트를 슬라이싱하는 과정에서도 GC의 기초가 되는 레퍼런스 카운팅이 이루어진다는 사실을 알 수 있다.

이제 RichCompareBool 에 대해서도 살펴보자. RichCompare란 주어진 두 개의 PyObject 에 대하여 동일성을 비교하게 된다. 만약 객체의 데이터 타입 자체가 동일하면 직접 비교할 수 있겠지만, 만약 데이터 타입이 다르다고 한다면 PyObject_RichCompare 메소드를 호출하게 된다.

===
.. c:function:: int PyObject_RichCompareBool(PyObject *o1, PyObject *o2, int opid)

   Compare the values of *o1* and *o2* using the operation specified by *opid*,
   which must be one of :c:macro:`Py_LT`, :c:macro:`Py_LE`, :c:macro:`Py_EQ`,
   :c:macro:`Py_NE`, :c:macro:`Py_GT`, or :c:macro:`Py_GE`, corresponding to ``<``,
   ``<=``, ``==``, ``!=``, ``>``, or ``>=`` respectively. Returns ``-1`` on error,
   ``0`` if the result is false, ``1`` otherwise. This is the equivalent of the
   Python expression ``o1 op o2``, where ``op`` is the operator corresponding to
   *opid*.

.. note::
   If *o1* and *o2* are the same object, :c:func:`PyObject_RichCompareBool`
   will always return ``1`` for :c:macro:`Py_EQ` and ``0`` for :c:macro:`Py_NE`.
===

/* Perform a rich comparison with integer result.  This wraps
   PyObject_RichCompare(), returning -1 for error, 0 for false, 1 for true. */
int
PyObject_RichCompareBool(PyObject *v, PyObject *w, int op)
{
    PyObject *res;
    int ok;

    /* Quick result when objects are the same.
       Guarantees that identity implies equality. */
    if (v == w) {
        if (op == Py_EQ)
            return 1;
        else if (op == Py_NE)
            return 0;
    }

    res = PyObject_RichCompare(v, w, op);
    if (res == NULL)
        return -1;
    if (PyBool_Check(res))
        ok = (res == Py_True);
    else
        ok = PyObject_IsTrue(res);
    Py_DECREF(res);
    return ok;
}

해당 메소드는 do_richcompare 메소드를 다시 호출하게 되는데, 해당 메소드는 먼저 주어진 두 개의 타입을 PyTYPE 의 struct 형태로 변환한 다음에 두 개의 타입이 서로 다른 타입이면서도 한 쪽이 subtype인지를 확인하게 된다. 만약 subtype인데 한 쪽의 Type에서 비교할 수 있는 target operation이 slot에 등록되어 있지 않다면, 상대 쪽의 type을 확인하여 비교한 다음에 그 값을 swap하는 로직이 _Py_SwappedOp 에 구현되어 있다. 이는 특정한 타입이 비교하는 과정에서 한 쪽으로의 비교만 존재하고 다른 쪽으로의 비교가 구현되어 있지 않을 때 inverse하게 역방향 확인하는 과정이 포함된 것이다.

이제 PyBool_Check 를 통하여 RichCompare 메소드의 반환 값이 만약 bool 형태가 아니라면 bool 형태로 변환하여 응답하게 된다. 이러한 RichCompare를 진행할 때는 내부적으로 레퍼런스 카운팅을 올리게 되기 때문에 RichCompareBool 메소드를 종료하기 직전에는 레퍼런스 카운팅을 내리고 RichCompareBool 메소드를 종료하게 된다.

okay, how does `do_richcompare_` works

```c
/* Perform a rich comparison, raising TypeError when the requested comparison
   operator is not supported. */
static PyObject *
do_richcompare(PyThreadState *tstate, PyObject *v, PyObject *w, int op)
{
    richcmpfunc f;
    PyObject *res;
    int checked_reverse_op = 0;

    if (!Py_IS_TYPE(v, Py_TYPE(w)) &&
        PyType_IsSubtype(Py_TYPE(w), Py_TYPE(v)) &&
        (f = Py_TYPE(w)->tp_richcompare) != NULL) {
        checked_reverse_op = 1;
        res = (*f)(w, v, _Py_SwappedOp[op]);
        if (res != Py_NotImplemented)
            return res;
        Py_DECREF(res);
    }
    if ((f = Py_TYPE(v)->tp_richcompare) != NULL) {
        res = (*f)(v, w, op);
        if (res != Py_NotImplemented)
            return res;
        Py_DECREF(res);
    }
    if (!checked_reverse_op && (f = Py_TYPE(w)->tp_richcompare) != NULL) {
        res = (*f)(w, v, _Py_SwappedOp[op]);
        if (res != Py_NotImplemented)
            return res;
        Py_DECREF(res);
    }
    /* If neither object implements it, provide a sensible default
       for == and !=, but raise an exception for ordering. */
    switch (op) {
    case Py_EQ:
        res = (v == w) ? Py_True : Py_False;
        break;
    case Py_NE:
        res = (v != w) ? Py_True : Py_False;
        break;
    default:
        _PyErr_Format(tstate, PyExc_TypeError,
                      "'%s' not supported between instances of '%.100s' and '%.100s'",
                      opstrings[op],
                      Py_TYPE(v)->tp_name,
                      Py_TYPE(w)->tp_name);
        return NULL;
    }
    return Py_NewRef(res);
}
```

우리가 Py_EQ 라고 하는 객체를 먼저 확인할 수 있게 된다. 해당 객체의 경우 어떤 데이터 타입이 들어왔는가에 따라서 비교하는 전략이 다소 달라진다. 예를 들어 Set의 데이터 타입이 들어왔다면, 해당 데이터 타입의 크기가 다르면 바로 같지 않다고 판단하도록 첫 번째 로직으로 고정되어 있다. 이후에는 해시값을 비교하는데, 만약 해시 값이 사전에 캐싱되어 있다면 빠르게 비교할 수 있게 된다. 하지만 Set의 경우에는 불변성을 띄지 않기 때문에 해시값이 계속 변할 수 있고, 해시 충돌의 가능성도 존재한다.

따라서 만약 기존에 해시했던 값과 다르다고 판단하면 오류, 즉 비교할 수 없다고 판단하고 -1 을 반환한다. Py_EQ 의 case에서는 hash 메소드의 값이 -1이 반환될 경우 다음 로직을 실행하게 된다. 최종적으로는 set_issubset 메소드를 호출하게 되는데, 해당 메소드는 v가 w의 부분집합인지 확인하는 과정이다. 상당히 비싼 값이다. 해시 충돌을 방지하는 로직이 들어가있기 때문에 최소한은 O(1) 만 비교해도 되지만, 최악의 경우 O(len(n)) 만큼 비교해야 하는 경우가 발생할 수 있다.

Both set and frozenset use the set_richcompare() function for equality tests. There’s no difference here. set_richcompare(), as the other answers mention, compares sizes and then hashes. Then, it checks whether one is a subset of the other, which just loops over every element in set 1, and checks if it is in set 2. This check is otherwise identical to checking whether an element is in a set. This is done by hash-table lookup, with a linear search over items with equal hashes. The complexity for the existence check is O(1) amortized or O(len(s)) worst-case, so the check for set_issubset() has a complexity of O(len(s1)) amortized, or O(len(s1)*len(s2)) worst-case. — StackOverflow

그런데 Tuple의 경우도 역시 다르다. Tuple은 우리가 모두 알고 있다시피 불변성이 보장된다. 우리 모두가 알다시피 만약 Id 단위로 비교할 수 있게 된다면 메모리 주소값을 통하여 동일성을 비교할 수 있게 된다. 하지만 만약 Id를 통해 비교할 수 없는 경우가 된다면 모두 경우를 해싱하여 처리해야 한다. 예를 들어 pickle을 통해 파이썬 객체를 직렬화해서 가져오고 이를 비교하게 된다면 별도의 아이디가 없는 경우가 발생하고 전체 해싱을 처리해서 비교하게 되는데 이 경우에는 메모리 주소값을 통해서 비교하는 경우에 비해 약 100배 이상 느려질 수 있다.

따라서 내가 사용하고자 하는 데이터 타입의 내부 Syntax Parsing이 어떻게 구현되어 있는지를 깊이 있게 이해하여야 효율적인 파이썬 프로그램을 짤 수 있다고 할 수 있겠다. 당장 위의 경우만 보더라도 튜플 타입에서 해시 함수가 별도로 적용이 되어 있고 해당 해시 함수에 따라서 해싱이 진행된다는 것을 이해해볼 수 있기 때문이다.