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 類型其實就是 uint32_t 類型的 巨集定義，表示 32 位元的整數資料。

深入分析 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⋅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 的回傳值確實是一樣的，不在這個區間之內的回傳值就是不一樣的。

我們也可以這個特性實作一個小的trick，就是求一個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中文網其他相關文章！