파이썬 int 내부구조 (Python int Internals)

Python 버젼 2.2 이후로는 파이썬에서의 정수는 언제나 int 타입을 가집니다 (이전에는 short int, long int 2가지로 나뉘어 있었습니다)[2]. 그리고 int 타입의 크기는 오로지 가용한 메모리 사이즈로 인해 제한 받습니다.

파이썬 int가 가질 수 있는 max 값(바이트로)은 아래와 같은 sys.maxsize를 통해 구할 수 있는데요:

import sys

print(sys.maxsize)
# 9223372036854775807

 

이번 글에서는 파이썬 int가 cpython에서 어떻게 구성되는지 살펴보겠습니다:

 

• cpython longobject 내부구조
• 파이썬의 다양한 int 값은 실제 어떻게 cpython longobject에 저장되나

---

cpython longobject 내부구조

intobject.h is no longer included by Python.h. The remains were moved to longobject.h. It still exists to define several aliases from PyInt to PyLong functions. [6]

 

파이썬의 int는 cpython의 아래와 같은 longobject로 이루어져 있습니다 (PyLong_Type):

Image from Author inspired by [3]

위와 같이 PyLongObject는 PyTupleObject와 매우 유사한 구조를 가지고 있습니다. PyLongObject의 ob_digit 필드는 digit을 가르키는 포인터로 필요하다면 더 메모리를 assign(malloc)하여 더 많은 데이터를 저장할 수 있습니다 [7]. 

 

digit 타입은 환경에 따라 다르기 때문에 어떻게 digit 크기가 결정되는지 살펴보겠습니다.

 

digit 타입의 결정과 크기

digit 타입은 아래와 같이 cpython/Include/longintrepr.h에서 결정됩니다:

 

#if PYLONG_BITS_IN_DIGIT == 30
typedef uint32_t digit;
typedef int32_t sdigit; /* signed variant of digit */
typedef uint64_t twodigits;
typedef int64_t stwodigits; /* signed variant of twodigits */
#define PyLong_SHIFT    30
#define _PyLong_DECIMAL_SHIFT   9 /* max(e such that 10**e fits in a digit) */
#define _PyLong_DECIMAL_BASE    ((digit)1000000000) /* 10 ** DECIMAL_SHIFT */
#elif PYLONG_BITS_IN_DIGIT == 15
typedef unsigned short digit;
typedef short sdigit; /* signed variant of digit */
typedef unsigned long twodigits;
typedef long stwodigits; /* signed variant of twodigits */
#define PyLong_SHIFT    15
#define _PyLong_DECIMAL_SHIFT   4 /* max(e such that 10**e fits in a digit) */
#define _PyLong_DECIMAL_BASE    ((digit)10000) /* 10 ** DECIMAL_SHIFT */
#else
#error "PYLONG_BITS_IN_DIGIT should be 15 or 30"
#endif
#define PyLong_BASE     ((digit)1 << PyLong_SHIFT)
#define PyLong_MASK     ((digit)(PyLong_BASE - 1))

digit 타입을 결정하는 조건문에 사용되는 PYLONG_BITS_IN_DIGIT는 아래 cpython/Include/pyport.h에서 설정되는데요. 여러가지 제약으로 인해 현재 15 또는 30으로 고정된 2가지 값 중 하나를 가집니다.

 

/* If PYLONG_BITS_IN_DIGIT is not defined then we'll use 30-bit digits if all
   the necessary integer types are available, and we're on a 64-bit platform
   (as determined by SIZEOF_VOID_P); otherwise we use 15-bit digits. */

#ifndef PYLONG_BITS_IN_DIGIT
#if SIZEOF_VOID_P >= 8
#define PYLONG_BITS_IN_DIGIT 30
#else
#define PYLONG_BITS_IN_DIGIT 15
#endif
#endif

 

다른 객체 구조에도 많은 영향을 미치는 변수 SIZEOF_VOID_P를 기준으로 설정되는 것을 알 수 있습니다. SIZEOF_VOID_P는 64 bit 머신에서는 8(mac)이기에(__LP64__) PYLONG_BITS_IN_DIGIT는 30인 것을 알 수 있습니다 [5]. (cpython/configure도 관여하는 것으로 보입니다).

 

이러한 정보는 ctypes, sys 모듈을 통해 접근 가능합니다 [8]:

 

import ctypes
print(ctypes.sizeof(ctypes.c_void_p))
# 8

import sys
sys.int_info
# sys.int_info(bits_per_digit=30, sizeof_digit=4)

 

PYLONG_BITS_IN_DIGIT == 30으로 가정할 때에, 'digit' 타입은 (1 << 30) - 1의 숫자를 저장할 수 있습니다. 이는 아래의 PyLong_BASE의 정의를 통해,

#define PyLong_BASE     ((digit)1 << PyLong_SHIFT)

다음과 같이 계산될 수 있습니다:

max_int_in_a_digit = (1 << 30) - 1
print(f"{max_int_in_a_digit:032b}")
# 00111111111111111111111111111111

이로써 32자리 2진수의 가장 왼쪽 2개의 reserved bit 빼고 모두 1인 숫자까지 하나의 digit이 표현할 수 있음을 알 수 있습니다. reserved bit은 아래 섹션에서 추후에 깊게 살펴보도록 하겠습니다.

 

파이썬의 다양한 int 값은 실제 어떻게 cpython longobject에 저장되나

위에서 digit 타입까지 이해한 후에는 파이썬의 다양한 int값들이 실제로 cpython의 longobject에 어떻게 저장되는지 살펴보면서 구조를 좀 더 자세히 이해할 수 있습니다. 

 

int 0

아래와 같은 0 값을 가진 int는 PyVarObject의 ob_size에 0이 저장되어 나타내게 됩니다:

i = 0

Image from Author inspired by [3]

그리고 cpython 코드에서는 0에 대한 판단을 아래와 같이 Py_SIZE(a) == 0를 통해 0을 판별하는 것을 볼 수 있습니다:

if (Py_SIZE(a) == 0) {
    return PyLong_FromLong(0);
}
// ...

 

int 1, (1 << 30) - 1, (1 << 30)

int 1은 아래와 같이 ob_size에 1, ob_digit[1]이고 첫 원소에 '00000000 00000000 00000000 00000001'가 저장됩니다.

Image from Author inspired by [3]

이러한 long 객체를 파이썬 int로 계산하는 공식은 2가지 순서로 진행됩니다. 먼저, 1) int의 절대값을 구하고, 2) ob_size의 부호에 따라 양수, 음수를 정해주는 것(1 또는 -1을 곱하는 것)입니다. 

 

1. 절대값은 SUM(for i=0 through abs(ob_size)-1) ob_digit[i] * 2**(SHIFT*i) 같은 공식을 통해 구해집니다.
2. 그리고 ob_size < 0이라면 -1을 곱하여 음수로 만듭니다.

 

파이썬에서 아래와 같은 코드를 통해 cpython의 내부를 살펴볼 수 있습니다 [7]: 

 

import ctypes

class PyLongObject(ctypes.Structure):
    _fields_ = [
      ("ob_refcnt", ctypes.c_long),
      ("ob_type", ctypes.c_void_p),
      ("ob_size", ctypes.c_ulong),
      ("ob_digit", ctypes.c_uint * 100)
    ]


def get_digits(bignum):
  obj = PyLongObject.from_address(id(bignum))
  return obj.ob_digit[:obj.ob_size]


nums = [1, (1 << 30) - 1, (1 << 30)]
for num in nums:
    digits = get_digits(num)
    print(num, digits)
    print()
    
# output
1 [1]

1073741823 [1073741823]

1073741824 [0, 1]

 

위의 출력 결과에서 볼 수 있듯이 1073741823, 1073741824는 아래와 같이 저장되는 것을 알 수 있습니다.:

Image from Author

int -1

위의 계산식(ob_size가 음수이면 int 값도 음수)에서 알 수 있듯이, -1과 같은 경우 절대값만을 ob_digit에 표현하고 ob_size에 -1를 넣어 음수임을 나타냅니다:

Image from Author

 

 

Reference

[1] How does Python manage int and long?

[2] PEP-237

[3] CPython Internals - Long

[4] cpython/Objects/longobjects.c

[5] Python 3.1 Build and C API Changes

[6] cpython/Misc/HISTORY

[7] How python implements super long integers?

[8] ctypes — A foreign function library for Python

[9] Hacking PyLongObject on Python 3.2