從 Python 源碼來分析列表的 Resize 機制
“ resize 是增加列表開銷的重要因素。”
Python 列表底層是通過存儲對象指針的變長數組來實現的，使用數組帶來的好處就是可以通過索引隨機訪問列表中的元素。
然而，由于 list 屬于可變數據類型，我們可以動態地在 list 中增減元素，當底層數組不足以容納新元素時，就要調整其大小了。這正是“變長”的含義所在。
那么，list 使用的變長數組是如何調整其大小呢?我們通過閱讀 Python 源碼來做下簡單分析。
【列表初始內存分配機制】
先來了解一下，創建一個 list 時，list 底層數組是什么樣子的。
list___init__() 是創建 list 對象的接口函數。它調用了 list___init___impl(self, iterable)。list___init___impl 接受一個 iterable 作為初始化源。這和我們通常初始化一個 list 對象的方式是一致的。
list___init___impl 做了哪些初始化工作呢?
list___init___impl() 首先將入參 self 指向的對象清空，原因是：Python 為提升創建 list 對象的效率，維護了一個 free_list 對象池。它可以回收不再使用的 list 對象，并重新分配給新 list 對象使用。
- /* Empty list reuse scheme to save calls to malloc and free */
- #ifndef PyList_MAXFREELIST
- # define PyList_MAXFREELIST 80
- #endif
- static PyListObject *free_list[PyList_MAXFREELIST];
- static int numfree = 0;
這個 list 內存池的大小為 80.
如果 self 指向的是一個緩存池中的對象，則需要先將它清理干凈。
然后，list___init___impl() 調用 list_preallocate_exact() 為 self 的變長數組分配一塊內存，這個數組中元素的個數和 iterable 中元素的個數相同。
這樣，list 對象使用的變長數組就創建好了。
【列表 resize 的實現算法】
那么，變長數組是使用什么算法來調整其大小呢?
這個邏輯是在 list_resize() 函數中實現的。先看代碼。
- static int
- list_resize(PyListObject *self, Py_ssize_t newsize)
- {
- PyObject **items;
- size_t new_allocated, num_allocated_bytes;
- Py_ssize_t allocated = self->allocated;
- /*Step 1*/
- if (allocated >= newsize && newsize >= (allocated >> 1)) {
- assert(self->ob_item != NULL || newsize == 0);
- Py_SET_SIZE(self, newsize);
- return 0;
- }
- /*Step 2*/
- new_allocated = ((size_t)newsize + (newsize >> 3) + 6) & ~(size_t)3;
- /* Do not overallocate if the new size is closer to overalocated size
- * than to the old size.
- */
- if (newsize - Py_SIZE(self) > (Py_ssize_t)(new_allocated - newsize))
- new_allocated = ((size_t)newsize + 3) & ~(size_t)3;
- if (newsize == 0)
- new_allocated = 0;
- /*Step 3*/
- num_allocated_bytes = new_allocated * sizeof(PyObject *);
- items = (PyObject **)PyMem_Realloc(self->ob_item, num_allocated_bytes);
- if (items == NULL) {
- PyErr_NoMemory();
- return -1;
- }
- /*Step 4*/
- self->ob_item = items;
- Py_SET_SIZE(self, newsize);
- self->allocated = new_allocated;
- return 0;
- }
list_resize() 的處理邏輯為：
- 先判斷原 list 對象已分配的空間是否滿足新需求：大于 newsize，且不超過 newsize 的兩倍(超過 newsize 兩倍時，需要縮短已分配空間)。滿足，則無需再調整。
- 計算新數組的需要容納的元素的數目：new_allocated。這個算法有點難理解：它會額外分配一些內存，并將這塊內存以 4 的倍數進行對齊。可以不用去細究為什么要這樣計算。
- 計算需要重新分配的內存大小：num_allocated_bytes。
- 調用 PyMem_Realloc() 分配內存。
更新 self 指向對象的相關屬性：調整變長數組指針的指向，設置 list 中元素的個數，設置已分配空間的大小。
【哪些操作會導致列表 resize?】
我們已經了解了 resize 的執行邏輯。那么 list 會在什么情況下 resize 底層數組呢?
- 數組內存不夠用的時候
insert、append、extend、切片賦值，這些操作都有可能需要分配更多的內存。
- 數組內存冗余的時候
pop、remove 可能需要縮減數組的空間，避免浪費。
看起來，凡是修改 list 元素數目的操作都有可能導致 resize 的發生。這些操作函數(定義在 listobject.c 中)確實也全部調用了 list_resize() 函數。
根據上邊的 resize 算法，如果你的 list 中的元素數目抖動很大，發生 resize 的概率就大很多。
因此，我們在開發中應盡量避免頻繁大幅度增減 list 元素的情況，以提升程序的運行效率。
本文轉載自微信公眾號「python學與思」，可以通過以下二維碼關注。轉載本文請聯系python學與思公眾號。
