Python 가상 머신에서 정수의 구현 원리는 무엇입니까?

데이터 구조

cpython 내부 int 유형의 구현 데이터 구조는 다음과 같습니다.

typedef struct _longobject PyLongObject;
struct _longobject {
    PyObject_VAR_HEAD
    digit ob_digit[1];
};
#define PyObject_VAR_HEAD      PyVarObject ob_base;
typedef struct {
    PyObject ob_base;
    Py_ssize_t ob_size; /* Number of items in variable part */
} PyVarObject;
typedef struct _object {
    _PyObject_HEAD_EXTRA
    Py_ssize_t ob_refcnt;
    struct _typeobject *ob_type;
} PyObject;

위 데이터 구조는 아래와 같이 그래픽으로 표현됩니다.

• ob_refcnt, 이는 객체의 참조를 나타냅니다. 개수는 가비지 수집에 매우 유용합니다. 나중에 가상 머신의 가비지 수집 부분을 자세히 분석하겠습니다.

• ob_type은 이 객체의 데이터 유형을 나타냅니다. Python에서는 때로는 데이터의 데이터 유형을 판단해야 합니다. 예를 들어 isinstance와 type이라는 두 키워드가 이 필드를 사용합니다.

• ob_size, 이 필드는 이 정수 개체 배열 ob_digit에 요소 수를 나타냅니다.

• digit 유형은 실제로 32비트 정수 데이터를 나타내는 uint32_t 유형의 매크로 정의입니다.

PyLongObject 필드의 의미에 대한 심층 분석

우선, 우리는 Python의 정수가 오버플로되지 않는다는 것을 알고 있습니다. 이것이 PyLongObject가 배열을 사용하는 이유입니다. cpython의 내부 구현에서 정수에는 0, 양수, 음수가 포함됩니다. 이와 관련하여 cpython에는 다음과 같은 규정이 있습니다:

• ob_size, ob_size가 0보다 큰 경우. ob_size가 0보다 작으면 음수가 저장됩니다.

• ob_digit는 정수의 절대값을 저장합니다. 앞서 언급했듯이 ob_digit는 32비트 데이터이지만 오버플로 문제를 피하기 위해 cpython에서는 처음 30비트만 내부적으로 사용됩니다.

위의 규칙을 깊이 이해하기 위해 몇 가지 예를 사용하겠습니다.

위 그림에서 ob_size는 0보다 크며 이는 이 숫자가 양수임을 나타내고 ob_digit는 int32 데이터를 가리킵니다. 숫자의 값은 10이므로 위의 숫자는 정수 10을 나타냅니다.

마찬가지로 ob_size는 0보다 작고 ob_digit는 10이므로 위 그림의 데이터는 -10을 나타냅니다.

위는 ob_digit 배열 길이 2의 예입니다. 위에 표시된 데이터는

1⋅2⁰+1⋅2¹+1⋅2²+입니다. .. +1⋅2²⁹+0⋅2³⁰+0⋅2³¹+1⋅2³²

각 배열 요소에 대해 처음 30비트만 사용하므로 두 번째 정수 데이터는 230에 해당합니다. 위의 결과를 바탕으로 전체 계산 과정을 이해할 수 있습니다.

위의 내용은 매우 간단합니다.

−(1⋅2⁰+1⋅2¹+1⋅2²+...+1⋅2²⁹+0&sdot ; 2³⁰+0⋅2³¹+1⋅2³²)

작은 정수 풀

일반적으로 사용되는 정수를 자주 생성하지 않고 프로그램 실행 속도를 높이기 위해 일반적으로 사용되는 정수를 사용할 수 있습니다. 캐시 먼저 이를 수행하고 필요한 경우 데이터를 직접 반환합니다. cpython의 관련 코드는 다음과 같습니다. (작은 정수 풀에서 캐시된 데이터의 간격은 [-5, 256]입니다.)

#define NSMALLPOSINTS           257
#define NSMALLNEGINTS           5
 
static PyLongObject small_ints[NSMALLNEGINTS + NSMALLPOSINTS];

다음 코드를 사용하여 작은 정수 풀이 사용되는지 테스트합니다. 데이터가 사용된 경우 id()의 반환 값은 작은 정수 풀의 데이터와 동일합니다. id 내장 함수는 Python 개체의 메모리 주소를 반환합니다.

>>> a = 1
>>> b = 2
>>> c = 1
>>> id(a), id(c)
(4343136496, 4343136496)
>>> a = -6
>>> c = -6
>>> id(a), id(c)
(4346020624, 4346021072)
>>> a = 257
>>> b = 257
>>> id(a), id(c)
(4346021104, 4346021072)
>>>

위 결과에서 알 수 있는 것은 [-5, 256] 구간의 값에 대해서는 id의 반환값이 사실상 동일하고, 이 구간을 벗어나는 반환값이 다르다는 점입니다.

이 기능을 사용하면 PyLongObject 객체가 차지하는 메모리 공간을 찾는 작은 트릭을 구현할 수도 있습니다. 두 데이터 -5와 256의 첫 번째 메모리 주소를 사용한 다음 이 주소를 뺄 수 있기 때문입니다. 261개의 ​​PyLongObject가 차지하는 메모리 공간의 크기(작은 정수 풀에 262개의 데이터가 있지만 마지막 데이터는 마지막 주소가 아닌 메모리의 첫 번째 주소이므로 261개의 ​​데이터만 있음) PyLongObject 객체의 메모리 크기를 찾을 수 있습니다.

>>> a = -5
>>> b = 256
>>> (id(b) - id(a)) / 261
32.0
>>>

위 출력에서 ​​PyLongObject 객체가 32바이트를 차지하는 것을 볼 수 있습니다. 다음 C 프로그램을 사용하여 PyLongObject가 차지하는 실제 메모리 공간을 볼 수 있습니다.

#include "Python.h"
#include <stdio.h>
 
int main()
{
  printf("%ld\n", sizeof(PyLongObject));
  return 0;
}

위 프로그램의 출력은 다음과 같습니다.

위 두 결과가 동일하므로 우리의 아이디어도 검증되었습니다.

작은 정수 풀에서 데이터를 얻는 핵심 코드는 다음과 같습니다.

static PyObject *
get_small_int(sdigit ival)
{
    PyObject *v;
    assert(-NSMALLNEGINTS <= ival && ival < NSMALLPOSINTS);
    v = (PyObject *)&small_ints[ival + NSMALLNEGINTS];
    Py_INCREF(v);
    return v;
}

整数的加法实现

如果你了解过大整数加法就能够知道，大整数加法的具体实现过程了，在 cpython 内部的实现方式其实也是一样的，就是不断的进行加法操作然后进行进位操作。

#define Py_ABS(x) ((x) < 0 ? -(x) : (x)) // 返回 x 的绝对值
#define PyLong_BASE	((digit)1 << PyLong_SHIFT)
#define PyLong_MASK	((digit)(PyLong_BASE - 1))
 
 
static PyLongObject *
x_add(PyLongObject *a, PyLongObject *b)
{
    // 首先获得两个整型数据的 size 
    Py_ssize_t size_a = Py_ABS(Py_SIZE(a)), size_b = Py_ABS(Py_SIZE(b));
    PyLongObject *z;
    Py_ssize_t i;
    digit carry = 0;
    // 确保 a 保存的数据 size 是更大的
    /* Ensure a is the larger of the two: */
    if (size_a < size_b) {
        { PyLongObject *temp = a; a = b; b = temp; }
        { Py_ssize_t size_temp = size_a;
            size_a = size_b;
            size_b = size_temp; }
    }
    // 创建一个新的 PyLongObject 对象，而且数组的长度是 size_a + 1
    z = _PyLong_New(size_a+1);
    if (z == NULL)
        return NULL;
    // 下面就是整个加法操作的核心
    for (i = 0; i < size_b; ++i) {
        carry += a->ob_digit[i] + b->ob_digit[i];
        // 将低 30 位的数据保存下来
        z->ob_digit[i] = carry & PyLong_MASK;
        // 将 carry 右移 30 位，如果上面的加法有进位的话 刚好可以在下一次加法当中使用（注意上面的 carry）
        // 使用的是 += 而不是 =
        carry >>= PyLong_SHIFT; // PyLong_SHIFT = 30
    }
    // 将剩下的长度保存 （因为 a 的 size 是比 b 大的）
    for (; i < size_a; ++i) {
        carry += a->ob_digit[i];
        z->ob_digit[i] = carry & PyLong_MASK;
        carry >>= PyLong_SHIFT;
    }
    // 最后保存高位的进位
    z->ob_digit[i] = carry;
    return long_normalize(z); // long_normalize 这个函数的主要功能是保证 ob_size 保存的是真正的数据的长度 因为可以是一个正数加上一个负数 size 还变小了
}
 
PyLongObject *
_PyLong_New(Py_ssize_t size)
{
    PyLongObject *result;
    /* Number of bytes needed is: offsetof(PyLongObject, ob_digit) +
       sizeof(digit)*size.  Previous incarnations of this code used
       sizeof(PyVarObject) instead of the offsetof, but this risks being
       incorrect in the presence of padding between the PyVarObject header
       and the digits. */
    if (size > (Py_ssize_t)MAX_LONG_DIGITS) {
        PyErr_SetString(PyExc_OverflowError,
                        "too many digits in integer");
        return NULL;
    }
    // offsetof 会调用 gcc 的一个内嵌函数 __builtin_offsetof 
    // offsetof(PyLongObject, ob_digit)  这个功能是得到 PyLongObject 对象 字段 ob_digit 之前的所有字段所占的内存空间的大小
    result = PyObject_MALLOC(offsetof(PyLongObject, ob_digit) +
                             size*sizeof(digit));
    if (!result) {
        PyErr_NoMemory();
        return NULL;
    }
    // 将对象的 result 的引用计数设置成 1
    return (PyLongObject*)PyObject_INIT_VAR(result, &PyLong_Type, size);
}
 
 
static PyLongObject *
long_normalize(PyLongObject *v)
{
    Py_ssize_t j = Py_ABS(Py_SIZE(v));
    Py_ssize_t i = j;
 
    while (i > 0 && v->ob_digit[i-1] == 0)
        --i;
    if (i != j)
        Py_SIZE(v) = (Py_SIZE(v) < 0) ? -(i) : i;
    return v;
}

위 내용은 Python 가상 머신에서 정수의 구현 원리는 무엇입니까?의 상세 내용입니다. 자세한 내용은 PHP 중국어 웹사이트의 기타 관련 기사를 참조하세요!