Python內建型別int原始碼學習

2022-05-17 19:01:05

在計算機系統中，如果某種型別的變數的儲存空間固定，它能表示的數值範圍就是有限的。以int為例，在C語言中，該型別變數長度為32位元，能表示的整數範圍為-2147483648~2147483647。1000000000000顯然是超出範圍的，即發生了整數溢位。但是對於Python中的int，則不會出現這種情況：

>>> 1000000 * 1000000
1000000000000
>>> 10 ** 100
10000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000

1 int物件的設計

1.1 PyLongObject

int物件的結構體：

typedef struct _longobject PyLongObject;
struct _longobject {
    PyObject_VAR_HEAD
    digit ob_digit[1];
};

digit陣列

#if PYLONG_BITS_IN_DIGIT == 30
typedef uint32_t digit;
// ...
#elif PYLONG_BITS_IN_DIGIT == 15
typedef unsigned short digit;
// ...
#endif

digit陣列具體用什麼整數型別來實現，Python提供了兩個版本，一個是32位元的unit32_t，一個是16位元的unsigned short，可以通過宏定義指定選用的版本。至於為什麼這麼設計，這主要是出於記憶體方面的考量，對於範圍不大的整數，用16位元整數表示即可，用32位元會比較浪費。

（注：可以看到PYLONG_BITS_IN_DIGIT宏的值為30或15，也就是說Python只使用了30位或15位，這是為什麼呢——這是Python出於對加法進位的考量。如果全部32位元都用來儲存絕對值，那麼為了保證加法不溢位（產生進位），需要先強制轉化成64位元型別後再進行計算。但犧牲最高1位後，加法運算便不用擔心進位溢位了。那麼，為什麼對32位元時是犧牲最高2位呢？可能是為了和16位元整數方案統一起來：如果選用16位元整數，Python只使用15位；32位元就使用30位。）

實際上，由於PyObject_VAR_HEAD頭部的存在，32位元和16位元的選擇其實差別不大：

整數物件	基本單位16位元	基本單位32位元
1	24 + 2 * 1 = 26	24 + 4 * 1 = 28
1000000	24 + 2 * 2 = 28	24 + 4 * 1 = 28
10000000000	24 + 2 * 3 = 30	24 + 4 * 2 = 32

int物件結構圖示如下：

對於比較大的整數，Python將其拆成若干部分，儲存在ob_digit陣列中。然而我們注意到在結構體定義中，ob_digit陣列長度卻固定為1，這是為什麼呢？這裡資料解釋是：“由於C語言中陣列長度不是型別資訊，我們可以根據實際需要為ob_digit陣列分配足夠的記憶體，並將其當成長度為n的陣列操作。這也是C語言中一個常用的程式設計技巧。”

但是根據我對C語言的理解，陣列是由基址+偏移來確定位置的，初始長度為1的陣列，後續如果強行去索引超過這個長度的位置，不是會出問題嗎？不知道是我理解錯了還是什麼，這裡後續還要進一步考證。

1.2 整數的佈局

整數分為正數、負數和零，這三種不同整數的儲存方式如下：

將整數的絕對值儲存在ob_digit陣列中
ob_digit陣列長度儲存在ob_size欄位，若整數為負，則ob_size為負數
整數零的ob_size為0，ob_digit陣列為空

下面以五個典型的例子來介紹不同情況下的整數儲存情況：

對於整數0，ob_size = 0，ob_digit為空，無需分配

對於整數10，其絕對值儲存在ob_digit陣列中，陣列長度為1，ob_size欄位為1

對於整數-10，其絕對值儲存在ob_digit陣列中，陣列長度為1，ob_size欄位為-1

對於整數1073741824（即2^30），由於Python只使用了32位元的後30位，所以2^30次方需要兩個陣列元素來儲存，整數陣列的長度為2。絕對值這樣計算：

2^0 * 0 + 2^30 * 1 = 1073741824

對於整數-4294967297（即-(2^32 + 1)），同樣需要長度為2的陣列，但ob_size欄位為負數。絕對值這樣計算：

2^0 * 1 + 2^30 * 4 = 4294967297

總結：ob_digit陣列儲存資料時，類似230進位制計算（或215進位制，取決於陣列的型別）

1.3 小整數靜態物件池

問題：通過前面章節的學習，我們知道整數物件是不可變物件，整數運算結果都是以新物件返回的：

>>> a = 1
>>> id(a)
1497146464
>>> a += 1
>>> id(a)
1496146496

Python這樣的設計會帶來一個效能缺陷，程式執行時必定會有大量物件的建立銷燬，即會帶來大量的記憶體分配和回收消耗，嚴重影響效能。例如對於一個迴圈100次的for迴圈，就需要建立100個int物件，這顯然是不能接受的。

對此，Python的解決方法是：預先將常用的整數物件建立好，以後備用，這就是小整數物件池。（和float一樣運用池技術，但是稍有不同，這也是由int和float實際運用的差別導致的）

小整數物件池相關原始碼：

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

NSMALLPOSINTS宏規定了物件池正數個數（包括0），預設257個NSMALLNEGINTS宏規定了物件池負數個數，預設為5個small_ints是一個整數物件陣列，儲存預先建立好的小整數物件

以預設設定為例，Python啟動後靜態建立一個包含262個元素的整數陣列，並依次初始化-5到-1，0，和1到256這些整數物件。小整數物件池結構如下：

1.4 範例

範例1：

>>> a = 1 + 0
>>> b = 1 * 1
>>> id(a), id(b)
(1541936120048, 1541936120048)

由於1 + 0的計算結果為1，在小整數範圍內，Python會直接從靜態物件池中取出整數1；1 * 1也是同理。名字a和b其實都跟一個物件繫結（有關名字繫結的內容可以看這篇部落格：Python原始碼學習筆記：Python作用域與名稱空間），即小整數物件池中的整數1，因此它們的id相同。

範例2：

>>> c = 1000 + 0
>>> d = 1000 * 1
>>> id(c), id(d)
(3085872130224, 3085872130256)

1000 + 0 和1000 * 1的計算結果都是1000，但由於1000不在小整數池範圍內，Python會分別建立物件並返回，因此c和d繫結的物件id也就不同了。

注：這裡大家如果使用Pycharm來執行的話就會發現它們的id是一樣的：

這裡的原因本質上是和位元組碼相關的，在IDLE中，每個命令都會單獨去編譯，而在Pycharm中是編譯整個py檔案，在同一上下文（這裡“同一上下文”其實比較模糊，筆者水平有限，解釋得也不太好）中的相同值的整數就是同一個物件，可以試著把位元組碼列印出來看一下（有關位元組碼的內容可以看下這篇部落格：Python原始碼學習筆記：Python程式執行過程與位元組碼）。

2 大整數運算

問題：在之前我們瞭解到了整數物件的內部結構，對於Python如何應對“整數溢位”這個問題有了一個初步的認識。但是真正的難點在於大整數數學運算的實現。

2.1 整數運算概述

整數物件的運算由整數型別物件中的tp_as_number、tp_as_sequence、tp_as_mapping這三個欄位所決定。整數型別物件PyLong_Type原始碼如下：（只列出部分欄位）

PyTypeObject PyLong_Type = {
    PyVarObject_HEAD_INIT(&PyType_Type, 0)
    "int",                                      /* tp_name */
    offsetof(PyLongObject, ob_digit),           /* tp_basicsize */
    sizeof(digit),                              /* tp_itemsize */
    
    // ...
    
    &long_as_number,                            /* tp_as_number */
    0,                                          /* tp_as_sequence */
    0,                                          /* tp_as_mapping */
    
    // ...
};

整數物件僅支援數值型操作long_as_number：

static PyNumberMethods long_as_number = {
    (binaryfunc)long_add,       /*nb_add*/
    (binaryfunc)long_sub,       /*nb_subtract*/
    (binaryfunc)long_mul,       /*nb_multiply*/
    long_mod,                   /*nb_remainder*/
    long_divmod,                /*nb_divmod*/
    long_pow,                   /*nb_power*/
    (unaryfunc)long_neg,        /*nb_negative*/
    (unaryfunc)long_long,       /*tp_positive*/
    (unaryfunc)long_abs,        /*tp_absolute*/
    (inquiry)long_bool,         /*tp_bool*/
    (unaryfunc)long_invert,     /*nb_invert*/
    long_lshift,                /*nb_lshift*/
    (binaryfunc)long_rshift,    /*nb_rshift*/
    long_and,                   /*nb_and*/
    long_xor,                   /*nb_xor*/
    long_or,                    /*nb_or*/
    long_long,                  /*nb_int*/
    0,                          /*nb_reserved*/
    long_float,                 /*nb_float*/
    0,                          /* nb_inplace_add */
    0,                          /* nb_inplace_subtract */
    0,                          /* nb_inplace_multiply */
    0,                          /* nb_inplace_remainder */
    0,                          /* nb_inplace_power */
    0,                          /* nb_inplace_lshift */
    0,                          /* nb_inplace_rshift */
    0,                          /* nb_inplace_and */
    0,                          /* nb_inplace_xor */
    0,                          /* nb_inplace_or */
    long_div,                   /* nb_floor_divide */
    long_true_divide,           /* nb_true_divide */
    0,                          /* nb_inplace_floor_divide */
    0,                          /* nb_inplace_true_divide */
    long_long,                  /* nb_index */
};

至此，我們明確了整數物件支援的全部數學運算，以及對應的處理常式：（只列出部分函數）

數學運算	處理常式	範例
加法	long_add	a + b
減法	long_sub	a - b
乘法	long_mul	a * b
取模	long_mod	a % b
除法	long_divmod	a / b
指數	long_pow	a ** b

整數物件、整數型別物件以及整數數學運算處理常式之間的關係：

2.2 大整數運算處理過程

以加法為例，來認識大整數運算的處理過程。

加法處理常式long_add()

1.long_add()原始碼：

static PyObject *
long_add(PyLongObject *a, PyLongObject *b)
{
    PyLongObject *z;

    CHECK_BINOP(a, b);

    if (Py_ABS(Py_SIZE(a)) <= 1 && Py_ABS(Py_SIZE(b)) <= 1) {
        return PyLong_FromLong(MEDIUM_VALUE(a) + MEDIUM_VALUE(b));
    }
    if (Py_SIZE(a) < 0) {
        if (Py_SIZE(b) < 0) {
            z = x_add(a, b);
            if (z != NULL) {
                /* x_add received at least one multiple-digit int,
                   and thus z must be a multiple-digit int.
                   That also means z is not an element of
                   small_ints, so negating it in-place is safe. */
                assert(Py_REFCNT(z) == 1);
                Py_SIZE(z) = -(Py_SIZE(z));
            }
        }
        else
            z = x_sub(b, a);
    }
    else {
        if (Py_SIZE(b) < 0)
            z = x_sub(a, b);
        else
            z = x_add(a, b);
    }
    return (PyObject *)z;
}

主體邏輯如下：

第4行：定義變數z用於臨時儲存計算結果
第8~10行：如果兩個物件陣列長度均不超過1，用MEDIUM_VALUE宏將其轉化成C整數進行運算（這種優化也是可以學習的）
第13~17行：如果兩個整數均為負數，呼叫x_add計算兩者絕對值之和，再將結果符號設定為負（16行處）
第20行：如果a為負數，b為正數，呼叫x_sub計算b和a的絕對值之差即為最終結果
第24行：如果a為正數，b為負數，呼叫x_sub計算a和b的絕對值之差即為最終結果
第26行：如果兩個整數均為正數，呼叫x_add計算兩個絕對值之和即為最終結果

因此，long_add函數實際上將整數加法轉化成了絕對值加法x_add和絕對值減法x_sub，以及MEDIUM_VALUE。絕對值加法和絕對值減法不用考慮符號對計算結果的影響，實現較為簡單，這是Python將整數運算轉化成絕對值運算的原因。（這裡也可以學習下）

大整數運算涉及到兩個陣列之間的加法，整數數值越大，整數物件底層陣列就越長，運算開銷也會越大。但是運算處理常式提供了一個快速通道：如果參與運算的整數物件底層陣列長度均不超過1，直接將整數物件轉化成C整數型別進行運算，效能耗損極小。滿足這個條件的整數範圍在-1073741823~1073747823之間，足以覆蓋大部分運算情況了。

2.絕對值加法x_add()

下面我們來看一下Python是如何對陣列進行加法運算的。x_add()原始碼：

/* Add the absolute values of two integers. */

static PyLongObject *
x_add(PyLongObject *a, PyLongObject *b)
{
    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;

    /* 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; }
    }
    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];
        z->ob_digit[i] = carry & PyLong_MASK;
        carry >>= PyLong_SHIFT;
    }
    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);
}

原始碼分析：

第10~15行：如果a陣列長度比較小，將a、b交換，陣列長度較大的那個在前面（感覺做演演算法題有時候就需要交換下，方便統一處理）

第16~18行：建立新整數物件，用於儲存計算結果（注意到長度必須要比a大，因為可能要進位）

第19~23行：遍歷b底層陣列，與a對應部分相機啊並儲存在z中，需要注意到進位（可以看到這裡是用按位元與和右移進行計算的，通過位於算來處理也是很高效的，演演算法題中也比較常見）

第24~28行：遍歷a底層陣列的剩餘部分，與進位相加後儲存在z中，同樣要注意進位運算

第29行：將進位寫入z底層陣列最高位單元中

第30行：標準化z，去除計算結果z底層陣列中前面多餘的0

3 其他

大整數轉float溢位

至此，我們對int和float有了一定的認識，也自然會有一個問題：將大整數int轉化為float時發生溢位怎麼辦？

範例：

>>>i = 111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111
>>> f = float(i)
Traceback (most recent call last):
  File "<pyshell#1>", line 1, in <module>
    f = float(i)
OverflowError: int too large to convert to float

由於float是有長度限制的，它的大小也是有上限的，因此當我們將一個很大的int轉化為float時，如果超出上限就會報錯。對此我們可以使用Decimal來解決：（這裡只介紹了使用方式，具體原理大家可以去了解一下）

>>> from decimal import Decimal
>>>d = Decimal(i)
>>>f2 = float(d)
>>> f2
inf

可以看到將i通過Decimal()轉化後就不會報錯了。

以上就是Python內建型別int原始碼學習的詳細內容，更多關於Python內建型別int的資料請關注it145.com其它相關文章！