跳到主要內容

《CPython 源碼剖析》讀書心得 - ch2 - int

PyIntObject

展開巨集後的定義

typedef struct {
   Py_ssize_t ob_refcnt;
   struct _typeobject *ob_type;
   long ob_ival;
} PyIntObject;

基本操作

這篇記了加法的實作: 加完後檢查溢位,若溢位的話, 改用大數 PyLongObject。

PyInt_AS_LONG vs. PyInt_ASLong

在運算過程中, 視情況會用不同方式取出 ob_ival:

  • 前者是巨集, 沒檢查 type, 速度快
  • 後者是函式, 有檢查 type, 速度慢

其它 type 也會看到類似的操作。

immutable

不可變的物件有許多好處, 包括可以任意被所有程式共享, 不用擔心造成依賴關係, 會不小心互炸。代價是各項操作後, 時常需要產生新的物件, 可能會拖慢速度。若會用到大量物件的話, 通常會搭配 object pool 減少生成物件的次數, 藉此簡省計算時間, 或是進一步在生成前先檢查是否已存在同樣物件, 有的話直接共享同一物件, 不生成重覆的物件。

在後面的例子會看到, CPython 有用 object pool 處理 int, 但也付出無限擴大記憶體的代價; 另外, CPython 只針對小部份範圍的數字共用物件, 以取得效率平衡。

memory management

intobject.c 開頭寫下為了減少 malloc 次數, 而採取的作法, 以及它造成的問題:

/* Integers are quite normal objects, to make object handling uniform.
(Using odd pointers to represent integers would save much space
but require extra checks for this special case throughout the code.)
Since a typical Python program spends much of its time allocating
and deallocating integers, these operations should be very fast.
Therefore we use a dedicated allocation scheme with a much lower
overhead (in space and time) than straight malloc(): a simple
dedicated free list, filled when necessary with memory from malloc().

block_list is a singly-linked list of all PyIntBlocks ever allocated,
linked via their next members. PyIntBlocks are never returned to the system before shutdown (PyInt_Fini).

free_list is a singly-linked list of available PyIntObjects, linked via abuse of their ob_type members.
*/

CPython 配了一塊記憶體自己管 int object 的生成和回收, 這塊記憶體只會愈長愈大, 永遠不會變小, 換句話說, 在 64 bit OS 上, 同時用到五千萬的整數後 (e.g., range(50000000)), 即使之後不會再同時用到五千萬個整數, 還是會占去 8*3*50000000 = 約 1G 不會回收的空間。

PyIntBlocks 和 free_list

#define BLOCK_SIZE  1000    /* 1K less typical malloc overhead */
#define BHEAD_SIZE  8   /* Enough for a 64-bit pointer */
#define N_INTOBJECTS    ((BLOCK_SIZE - BHEAD_SIZE) /
sizeof(PyIntObject))

struct _intblock {
   struct _intblock *next;
   PyIntObject objects[N_INTOBJECTS];
};

typedef struct _intblock PyIntBlock;

static PyIntBlock *block_list = NULL;
static PyIntObject *free_list = NULL;  // the head of next-to-new int object

static PyIntObject *
fill_free_list(void)
{
   PyIntObject *p, *q;
   /* Python's object allocator isn't appropriate for large blocks. */
   p = (PyIntObject *) PyMem_MALLOC(sizeof(PyIntBlock));
   if (p == NULL)
       return (PyIntObject *) PyErr_NoMemory();
   ((PyIntBlock *)p)->next = block_list;
   block_list = (PyIntBlock *)p;
   /* Link the int objects together, from rear to front, then return
      the address of the last int object in the block. */
   p = &((PyIntBlock *)p)->objects[0];
   q = p + N_INTOBJECTS;
   while (--q > p)
       q->ob_type = (struct _typeobject *)(q-1);
   q->ob_type = NULL;
   return p + N_INTOBJECTS - 1;
}

這裡用了不少 trick, 若沒先看書, 大概要讀一陣子吧。首先讓 PyIntBlock 不要占超過 1k, 大概是這樣 kernel 比較好找空間, 效率比較高。

fill_free_list 用 ob_type 當作 singly-linked list 的 next, 反正等產生 PyIntObject 時, 就會將它指到正確的值, 開頭的註解有先消毒了, 說會 "abuse of their ob_type members", 好奇 grep 了一下 2.5.2 的程式, 幸好 "abuse" 只出現 29 次 ...。

PyObject *
PyInt_FromLong(long ival)
{
   register PyIntObject *v;
   /*--- Begin of #1 ---*/
#if NSMALLNEGINTS + NSMALLPOSINTS > 0
   if (-NSMALLNEGINTS <= ival && ival < NSMALLPOSINTS) {
       v = small_ints[ival + NSMALLNEGINTS];
       Py_INCREF(v);
       return (PyObject *) v;
   }
#endif
   /*--- End of #1 ---*/
   if (free_list == NULL) {
       if ((free_list = fill_free_list()) == NULL)
           return NULL;
   }
   /* Inline PyObject_New */
   v = free_list;
   free_list = (PyIntObject *)v->ob_type;
   PyObject_INIT(v, &PyInt_Type);
   v->ob_ival = ival;
   return (PyObject *) v;
}

先略過 #1 的部份, 後面再解釋。free_list 指到 linked list 的頭, 準備產生 int object, 在 deallocation 時, 會將 free_list 改指到用不到的 PyIntObject, 所以這塊 int object 的記憶體不會有 memory leak, 只是當 free_list 這串超長, 一堆空間用不到時, 它也不會釋放空間就是了。

small_ints

CPython 初始化時, 會先配置一塊空間存 [-5, 256] 的整數, 改變巨集重編 CPython 可改變這個範圍。

之後用到這範圍整數時, 不會重新產生新的 PyIntObject。上面 #1 那塊程式碼就是從 small_ints 取值, small_ints 也是用 PyIntBlocks 裡的空間。

透過下面的操作說明 small_ints 的效果 (id 會傳回 memroy address):

In [1]: id(-5)
Out[1]: 7747448

In [2]: id(-5)
Out[2]: 7747448  # 沒變, 同一個物件

In [3]: id(-6)
Out[3]: 8558280

In [4]: id(-6)
Out[4]: 8557608  # 變了, 表示這個 -6 是新的物件

In [5]: id(256)
Out[5]: 7753136

In [6]: id(256)
Out[6]: 7753136  # 沒變

In [7]: id(257)
Out[7]: 8557512

In [8]: id(257)
Out[8]: 8557440  # 變了

我原本以為 CPython 像多數語言有共用字串那樣, 有共用所有整數。沒想到只有共用小範圍的整數。仔細想想也有道理, 若每次取數字都要 hash, 效率也會很差吧, 這之間的平衡真難拿捏。

了解 PyIntOjbect 的實作方式後, 才明白為何 CPython 會吃掉這麼多記憶體, 還有為何像 psyco 能在不改 code 的情況下讓 CPython 大幅加速科學計算, 一部份的原因是省下一些生成 PyIntObject 的時間

留言

這個網誌中的熱門文章

virtualbox 使用 USB 裝置

2012-12-16 更新 現在 (4.x 版) 似乎無需做任何設定, 只要有裝 Oracle VM VirtualBox Extension Pack, 在 VirtualBox 視窗右下角按 USB 的圖示, 再點目標裝置, 即可加入或移除該裝置 同一時間只有 host 或 guest 可擁有該裝置, 所以從 guest OS 移除, 相當於接回 host OS 目前 VirtualBox 只支援 USB 2.0 的插槽, 若偵測不到時, 注意一下是否為這個問題 有時拔拔插插, VirtualBox 會進入奇怪的狀態, 接上去 guest OS 無法連接且跳出 device is busy 的錯誤訊息。試看看拔除該裝置, 重開 guest OS (續上則) 若重開 guest OS 無效, 並且 host OS 已移除該裝置, VirtualBox 的 USB 清單卻仍顯示 "captured", 試看看拔除該裝置, 重開 host OS原文網路上搜一下, 比較多是 Ubuntu 當 host 的解法, 我的情況是 Win7 當 host, Ubuntu 當 guest。 這兩篇說明很詳細《Learn How to Set Up USB and Networking Options in VirtualBox》《幻影千瞳的部落格: VirtualBox 使用筆記(二):使用 USB 裝置》 現在的版本圖形介面很好用了, 不用像第二篇說的那樣用指令操作。這裡記下我的操作步驟: 關掉 guest OS 在 VirtualBox 選單, 選擇 guest OS -> Settings -> USB -> Enable USB 2.0 會出現訊息框, 說明要安裝 Oracle VM VirtualBox Extension Pack。下載後安裝它 host OS 插入 USB 隨身碟 在 VirtualBox 選單, 選擇 guest OS -> Settings -> USB, 點右邊有綠色 "+" 的 USB 頭的圖示, 選擇該 USB 隨身碟, 加入它的 filter 從 host OS 移除 USB 隨身碟 開啟 guest OS 插入 USB 隨身碟, 於是 guest OS 會自動偵測…

(C/C++ ) 如何在 Linux 上使用自行編譯的第三方函式庫

以使用 LevelDB 為例。 抓好並編好相關檔案,編譯方式見第三方函式庫附的說明:$ ls include/ # header files leveldb/ $ ls out-shared/libleveldb.so* # shared library out-shared/libleveldb.so@ out-shared/libleveldb.so.1@ out-shared/libleveldb.so.1.20* 下面的例子用 clang++ 編譯,這裡用到的參數和 g++ 一樣。 問題一:找不到 header$ clang++ sample.cpp sample.cpp:5:10: fatal error: 'leveldb/db.h' file not found #include "leveldb/db.h" ^ 1 error generated. 解法:用 -I 指定 header 位置 問題二:找不到 shared library$ clang++ sample.cpp -I include/ /tmp/sample-2e7dd8.o: In function `main': sample.cpp:(.text+0x1e): undefined reference to `leveldb::Options::Options()' sample.cpp:(.text+0x6f): undefined reference to `leveldb::DB::Open(leveldb::Options const&, std::string const&, leveldb::DB**)' sample.cpp:(.text+0x10c): undefined reference to `leveldb::Status::ToString() const' sample.cpp:(.text+0x7d0): undefined reference to `leveldb::Status::ToString() const' clang: error: linker command failed with exit code 1 (u…

解決 undefined symbol / reference

C++ 新手上路, 有錯還請幫忙指正。 基本觀念相較於 script language 或 Java 來說, C/C++ 有完整的「編譯 -> 連結 -> 執行」三個階段, 各階段都可能發生 undefined symbol。在解決惱人的 undefined symbol 前, 得先明白整個編譯流程: 編譯 .c / .cpp 為 .o (object file) 時, 需要提供 header 檔 (用到 gcc 參數 -I)。事實上, 在編譯單一檔案時, gcc/g++ 根本不在意真正的 symbol 是否存在, 反正有宣告它就信了, 所以有引對 header 即可。這也是可分散編譯的原因 (如 distcc ), 程式之間在編譯成 .o 檔時, 並沒有相依性。 用 linker (ld 或 gold) 將 *.o 連結成 dynamic library 或執行檔時, 需要提供要連結的 library (用到 gcc 參數 -L 指定目錄位置, 用 -l 指定要連什麼函式庫)。不同於前一步, 此時 symbol 一定要在。 執行的時候, 會再動態開啟 shared library 讀出 symbol。換句話說, 前一個步驟只是檢查是否有。檢查通過也連結成 executable 或 shared library 後, 若執行時對應的檔案不見了, 仍會在執行期間找不到 symbol。若位置沒設好, 可能需要用 LIB_LIBRARY_PATH 指定動態函式的位置, 但不建議這麼做, 最好在執行 linker 時就指定好位置。原因見《Why LD_LIBRARY_PATH is bad》。明白這點後, 就看 undefined symbol 發生在那個階段, 若是編 object file 時發生, 就是沒和編譯器說 header 檔在那, 記得用 -I 告訴它。若在 linking 時發生, 就要同時設好 -L 和 -l。不過難就難在要去那找 undefined symbol 的出處。 解決問題的流程首先是判斷 symbol 是不是自己用到的原始碼裡, 可配合 id-utils 找看看 (我是用 gj, 比較方便一點)。或是看有沒有 man page, 有 man page 的話, 裡面會記錄用到的 header 和該怎麼下連結參數。若在專案裡找不到, …