您好,登錄后才能下訂單哦!
這篇文章主要介紹“Python虛擬機(jī)中整型的實(shí)現(xiàn)原理是什么”的相關(guān)知識(shí),小編通過實(shí)際案例向大家展示操作過程,操作方法簡單快捷,實(shí)用性強(qiáng),希望這篇“Python虛擬機(jī)中整型的實(shí)現(xiàn)原理是什么”文章能幫助大家解決問題。
在 cpython 內(nèi)部的 int 類型的實(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)用圖的方式表示出來如下圖所示:
ob_refcnt,表示對(duì)象的引用記數(shù)的個(gè)數(shù),這個(gè)對(duì)于垃圾回收很有用處,后面我們分析虛擬機(jī)中垃圾回收部分在深入分析。
ob_type,表示這個(gè)對(duì)象的數(shù)據(jù)類型是什么,在 python 當(dāng)中有時(shí)候需要對(duì)數(shù)據(jù)的數(shù)據(jù)類型進(jìn)行判斷比如 isinstance, type 這兩個(gè)關(guān)鍵字就會(huì)使用到這個(gè)字段。
ob_size,這個(gè)字段表示這個(gè)整型對(duì)象數(shù)組 ob_digit 當(dāng)中一共有多少個(gè)元素。
digit 類型其實(shí)就是 uint32_t 類型的一個(gè) 宏定義,表示 32 位的整型數(shù)據(jù)。
首先我們知道在 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ù)組的長度,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 位,這只為了避免溢出的問題。
我們下面使用幾個(gè)例子來深入理解一下上面的規(guī)則:
在上圖當(dāng)中 ob_size 大于 0 ,說明這個(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ù)組長度為 2 的例子,上面所表示數(shù)據(jù)如下所示:
1⋅20+1⋅21+1⋅22+...+1⋅229+0⋅230+0⋅231+1⋅232
因?yàn)閷?duì)于每一個(gè)數(shù)組元素來說我們只使用前 30 位,因此到第二個(gè)整型數(shù)據(jù)的時(shí)候正好對(duì)應(yīng)著 230,大家可以對(duì)應(yīng)著上面的結(jié)果了解整個(gè)計(jì)算過程。
上面也就很簡單了:
−(1⋅20+1⋅21+1⋅22+...+1⋅229+0⋅230+0⋅231+1⋅232)
為了避免頻繁的創(chuàng)建一些常用的整數(shù),加快程序執(zhí)行的速度,我們可以將一些常用的整數(shù)先緩存起來,如果需要的話就直接將這個(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ù),如果使用的話,對(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)存空間大小(注意雖然小整數(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ù)加法的具體實(shí)現(xiàn)過程了,在 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ù)組的長度是 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ù)保存下來 z->ob_digit[i] = carry & PyLong_MASK; // 將 carry 右移 30 位,如果上面的加法有進(jìn)位的話 剛好可以在下一次加法當(dāng)中使用(注意上面的 carry) // 使用的是 += 而不是 = carry >>= PyLong_SHIFT; // PyLong_SHIFT = 30 } // 將剩下的長度保存 (因?yàn)?nbsp;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ù)的長度 因?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; }
關(guān)于“Python虛擬機(jī)中整型的實(shí)現(xiàn)原理是什么”的內(nèi)容就介紹到這里了,感謝大家的閱讀。如果想了解更多行業(yè)相關(guān)的知識(shí),可以關(guān)注億速云行業(yè)資訊頻道,小編每天都會(huì)為大家更新不同的知識(shí)點(diǎn)。
免責(zé)聲明:本站發(fā)布的內(nèi)容(圖片、視頻和文字)以原創(chuàng)、轉(zhuǎn)載和分享為主,文章觀點(diǎn)不代表本網(wǎng)站立場,如果涉及侵權(quán)請(qǐng)聯(lián)系站長郵箱:is@yisu.com進(jìn)行舉報(bào),并提供相關(guān)證據(jù),一經(jīng)查實(shí),將立刻刪除涉嫌侵權(quán)內(nèi)容。