快捷導(dǎo)航

深入理解Python虛擬機(jī)中整型(int)的實(shí)現(xiàn)原理及源碼剖析

更新時(shí)間：2023年03月13日 09:27:29 作者：一無(wú)是處的研究僧

在本篇文章當(dāng)中主要給大家介紹在 cpython 內(nèi)部是如何實(shí)現(xiàn)整型數(shù)據(jù) int 的，主要是分析 int 類(lèi)型的表示方式，分析 int 類(lèi)型的巧妙設(shè)計(jì)

數(shù)據(jù)結(jié)構(gòu)

在 cpython 內(nèi)部的 int 類(lèi)型的實(shí)現(xiàn)數(shù)據(jù)結(jié)構(gòu)如下所示：

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;

上面的數(shù)據(jù)結(jié)構(gòu)用圖的方式表示出來(lái)如下圖所示：

ob_refcnt，表示對(duì)象的引用記數(shù)的個(gè)數(shù)，這個(gè)對(duì)于垃圾回收很有用處，后面我們分析虛擬機(jī)中垃圾回收部分在深入分析。
ob_type，表示這個(gè)對(duì)象的數(shù)據(jù)類(lèi)型是什么，在 python 當(dāng)中有時(shí)候需要對(duì)數(shù)據(jù)的數(shù)據(jù)類(lèi)型進(jìn)行判斷比如 isinstance, type 這兩個(gè)關(guān)鍵字就會(huì)使用到這個(gè)字段。
ob_size，這個(gè)字段表示這個(gè)整型對(duì)象數(shù)組 ob_digit 當(dāng)中一共有多少個(gè)元素。
digit 類(lèi)型其實(shí)就是 uint32_t 類(lèi)型的一個(gè) 宏定義，表示 32 位的整型數(shù)據(jù)。

深入分析 PyLongObject 字段的語(yǔ)意

首先我們知道在 python 當(dāng)中的整數(shù)是不會(huì)溢出的，這正是 PyLongObject 使用數(shù)組的原因。在 cpython 內(nèi)部的實(shí)現(xiàn)當(dāng)中，整數(shù)有 0 、正數(shù)、負(fù)數(shù)，對(duì)于這一點(diǎn)在 cpython 當(dāng)中有以下幾個(gè)規(guī)定：

ob_size，保存的是數(shù)組的長(zhǎng)度，ob_size 大于 0 時(shí)保存的是正數(shù)，當(dāng) ob_size 小于 0 時(shí)保存的是負(fù)數(shù)。
ob_digit，保存的是整數(shù)的絕對(duì)值。在前面我們談到了，ob_digit 是一個(gè) 32 位的數(shù)據(jù)，但是在 cpython 內(nèi)部只會(huì)使用其中的前 30 位，這只為了避免溢出的問(wèn)題。

我們下面使用幾個(gè)例子來(lái)深入理解一下上面的規(guī)則：

在上圖當(dāng)中 ob_size 大于 0 ，說(shuō)明這個(gè)數(shù)是一個(gè)正數(shù)，而 ob_digit 指向一個(gè) int32 的數(shù)據(jù)，數(shù)的值等于 10，因此上面這個(gè)數(shù)表示整數(shù) 10 。

同理 ob_size 小于 0，而 ob_digit 等于 10，因此上圖當(dāng)中的數(shù)據(jù)表示 -10 。

上面是一個(gè) ob_digit 數(shù)組長(zhǎng)度為 2 的例子，上面所表示數(shù)據(jù)如下所示：

1⋅2⁰+1⋅2¹+1⋅2²+...+1⋅2²⁹+0⋅2³⁰+0⋅2³¹+1⋅2³²

因?yàn)閷?duì)于每一個(gè)數(shù)組元素來(lái)說(shuō)我們只使用前 30 位，因此到第二個(gè)整型數(shù)據(jù)的時(shí)候正好對(duì)應(yīng)著 230，大家可以對(duì)應(yīng)著上面的結(jié)果了解整個(gè)計(jì)算過(guò)程。

上面也就很簡(jiǎn)單了：

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

小整數(shù)池

為了避免頻繁的創(chuàng)建一些常用的整數(shù)，加快程序執(zhí)行的速度，我們可以將一些常用的整數(shù)先緩存起來(lái)，如果需要的話(huà)就直接將這個(gè)數(shù)據(jù)返回即可。在 cpython 當(dāng)中相關(guān)的代碼如下所示：（小整數(shù)池當(dāng)中緩存數(shù)據(jù)的區(qū)間為[-5, 256]）

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

我們使用下面的代碼進(jìn)行測(cè)試，看是否使用了小整數(shù)池當(dāng)中的數(shù)據(jù)，如果使用的話(huà)，對(duì)于使用小整數(shù)池當(dāng)中的數(shù)據(jù)，他們的 id() 返回值是一樣的，id 這個(gè)內(nèi)嵌函數(shù)返回的是 python 對(duì)象的內(nèi)存地址。

>>> 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)
>>>

從上面的結(jié)果我們可以看到的是，對(duì)于區(qū)間[-5, 256]當(dāng)中的值，id 的返回值確實(shí)是一樣的，不在這個(gè)區(qū)間之內(nèi)的返回值就是不一樣的。

我們還可以這個(gè)特性實(shí)現(xiàn)一個(gè)小的 trick，就是求一個(gè) PyLongObject 對(duì)象所占的內(nèi)存空間大小，因?yàn)槲覀兛梢允褂?-5 和 256 這兩個(gè)數(shù)據(jù)的內(nèi)存首地址，然后將這個(gè)地址相減就可以得到 261 個(gè) PyLongObject 所占的內(nèi)存空間大?。ㄗ⒁怆m然小整數(shù)池當(dāng)中一共有 262 個(gè)數(shù)據(jù)，但是最后一個(gè)數(shù)據(jù)是內(nèi)存首地址，并不是尾地址，因此只有 261 個(gè)數(shù)據(jù)），這樣我們就可以求一個(gè) PyLongObject 對(duì)象的內(nèi)存大小。

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

從上面的輸出結(jié)果我們可以看到一個(gè) PyLongObject 對(duì)象占 32 個(gè)字節(jié)。我們可以使用下面的 C 程序查看一個(gè) PyLongObject 真實(shí)所占的內(nèi)存空間大小。

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

上面的程序的輸出結(jié)果如下所示：

上面兩個(gè)結(jié)果是相等的，因此也驗(yàn)證了我們的想法。

從小整數(shù)池當(dāng)中獲取數(shù)據(jù)的核心代碼如下所示：

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;
}

整數(shù)的加法實(shí)現(xiàn)

關(guān)于 PyLongObject 的操作有很多，我們看一下加法的實(shí)現(xiàn)，見(jiàn)微知著，剩下的其他的方法我們就不介紹了，大家感興趣可以去看具體的源代碼。

如果你了解過(guò)大整數(shù)加法就能夠知道，大整數(shù)加法的具體實(shí)現(xiàn)過(guò)程了，在 cpython 內(nèi)部的實(shí)現(xiàn)方式其實(shí)也是一樣的，就是不斷的進(jìn)行加法操作然后進(jìn)行進(jìn)位操作。

#define Py_ABS(x) ((x) < 0 ? -(x) : (x)) // 返回 x 的絕對(duì)值
#define PyLong_BASE	((digit)1 << PyLong_SHIFT)
#define PyLong_MASK	((digit)(PyLong_BASE - 1))
 
 
static PyLongObject *
x_add(PyLongObject *a, PyLongObject *b)
{
    // 首先獲得兩個(gè)整型數(shù)據(jù)的 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 保存的數(shù)據(jù) 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; }
    }
    // 創(chuàng)建一個(gè)新的 PyLongObject 對(duì)象，而且數(shù)組的長(zhǎng)度是 size_a + 1
    z = _PyLong_New(size_a+1);
    if (z == NULL)
        return NULL;
    // 下面就是整個(gè)加法操作的核心
    for (i = 0; i < size_b; ++i) {
        carry += a->ob_digit[i] + b->ob_digit[i];
        // 將低 30 位的數(shù)據(jù)保存下來(lái)
        z->ob_digit[i] = carry & PyLong_MASK;
        // 將 carry 右移 30 位，如果上面的加法有進(jìn)位的話(huà) 剛好可以在下一次加法當(dāng)中使用（注意上面的 carry）
        // 使用的是 += 而不是 =
        carry >>= PyLong_SHIFT; // PyLong_SHIFT = 30
    }
    // 將剩下的長(zhǎng)度保存 （因?yàn)?a 的 size 是比 b 大的）
    for (; i < size_a; ++i) {
        carry += a->ob_digit[i];
        z->ob_digit[i] = carry & PyLong_MASK;
        carry >>= PyLong_SHIFT;
    }
    // 最后保存高位的進(jìn)位
    z->ob_digit[i] = carry;
    return long_normalize(z); // long_normalize 這個(gè)函數(shù)的主要功能是保證 ob_size 保存的是真正的數(shù)據(jù)的長(zhǎng)度 因?yàn)榭梢允且粋€(gè)正數(shù)加上一個(gè)負(fù)數(shù) 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 會(huì)調(diào)用 gcc 的一個(gè)內(nèi)嵌函數(shù) __builtin_offsetof 
    // offsetof(PyLongObject, ob_digit)  這個(gè)功能是得到 PyLongObject 對(duì)象 字段 ob_digit 之前的所有字段所占的內(nèi)存空間的大小
    result = PyObject_MALLOC(offsetof(PyLongObject, ob_digit) +
                             size*sizeof(digit));
    if (!result) {
        PyErr_NoMemory();
        return NULL;
    }
    // 將對(duì)象的 result 的引用計(jì)數(shù)設(shè)置成 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;
}

總結(jié)

在本篇文章當(dāng)中主要給大家介紹了 cpython 內(nèi)部是如何實(shí)現(xiàn)整型數(shù)據(jù) int 的，分析了 int 類(lèi)型的表示方式和設(shè)計(jì)。int 內(nèi)部使用 digit 來(lái)表示 32 位的整型數(shù)據(jù)，同時(shí)為了避免溢出的問(wèn)題，只會(huì)使用其中的前 30 位。在 cpython 內(nèi)部的實(shí)現(xiàn)當(dāng)中，整數(shù)有 0 、正數(shù)、負(fù)數(shù)，對(duì)于這一點(diǎn)有以下幾個(gè)規(guī)定：

ob_size，保存的是數(shù)組的長(zhǎng)度，ob_size 大于 0 時(shí)保存的是正數(shù)，當(dāng) ob_size 小于 0 時(shí)保存的是負(fù)數(shù)。
ob_digit，保存的是整數(shù)的絕對(duì)值。
此外，為避免頻繁創(chuàng)建一些常用的整數(shù)，cpython 使用了小整數(shù)池的技術(shù)，將一些常用的整數(shù)先緩存起來(lái)。最后，本文還介紹了整數(shù)的加法實(shí)現(xiàn)，即不斷進(jìn)行加法操作然后進(jìn)行進(jìn)位操作。

cpython 使用這種方式的主要原理就是大整數(shù)的加減乘除，本篇文章主要是介紹了加法操作，大家如果感興趣可以自行閱讀其他的源程序。

以上就是深入理解Python虛擬機(jī)中整型(int)的實(shí)現(xiàn)原理及源碼剖析的詳細(xì)內(nèi)容，更多關(guān)于Python虛擬機(jī)整型的資料請(qǐng)關(guān)注腳本之家其它相關(guān)文章！

您可能感興趣的文章: