本系列文章是一系列學(xué)習(xí)筆記籍茧，希望較為深入地分析Python3中的原理肮塞、性能襟齿，文章中絕大部分觀點(diǎn)都是原作作者的觀點(diǎn)（如下），本人對(duì)書中示例加以實(shí)踐和總結(jié)枕赵，并結(jié)合相應(yīng)的Python的C語言源碼(3.6.1)猜欺，分享出來。原著：
- 《High Performance Python》by O'Relly Media烁设，作者M(jìn)icha Gorelick替梨，Ian Ozsvald
- 《Fluent Python》by O'Relly Media，作者Luciano Ramalho
從內(nèi)存利用和CPU利用開始了解List和Tuple的優(yōu)缺點(diǎn)
定義
List：動(dòng)態(tài)數(shù)組装黑，元素可變副瀑，可改變大小（append恋谭，resize）
Tuple：靜態(tài)數(shù)組糠睡，不可變，數(shù)據(jù)一旦創(chuàng)建后不可改變
List的內(nèi)存利用
- 當(dāng)創(chuàng)建N個(gè)元素的List時(shí)疚颊，Python的動(dòng)態(tài)內(nèi)存分配長N＋1個(gè)元素的內(nèi)存狈孔，第一個(gè)元素存儲(chǔ)列表長度，和列表的元信息材义。
- 當(dāng)Append一個(gè)元素時(shí)均抽，Python將創(chuàng)建一個(gè)足夠大的列表，來容納N個(gè)元素和將要被追加的元素其掂。重新創(chuàng)建的列表長度大于N＋1（雖然我們只觸發(fā)一次append操作）油挥，實(shí)際上，為了未來的Append操作款熬，M個(gè)元素長度（M>N+1)的內(nèi)存將會(huì)被額外分配深寥，然后，舊列表中的數(shù)據(jù)被copy到新列表中贤牛，舊列表銷毀惋鹅。
- 額外內(nèi)存的分配，只會(huì)發(fā)生在第一次Append操作時(shí)殉簸，當(dāng)我們創(chuàng)建普通列表時(shí)闰集，不會(huì)額外分配內(nèi)存沽讹。
- 這里的哲學(xué)是，一個(gè)Append操作很可能是很多Append操作的開始返十，通過額外分配內(nèi)存來減少可能的內(nèi)存分配和內(nèi)存copy的次數(shù)妥泉。
- 那么，對(duì)于一個(gè)具有N個(gè)元素的列表洞坑，當(dāng)一次Append操作發(fā)生時(shí)盲链，新列表要分配多少內(nèi)存（額外M個(gè)元素，需多分配一個(gè)元素存儲(chǔ)長度）呢迟杂？答案是：
** M = (N >> 3) + (N <9 ? 3 : 6) + 1 **
我們來看Python3.6.1的列表resize過程刽沾，源代碼位于Objects/listobject.c中的list_resize函數(shù)：
static int
list_resize(PyListObject *self, Py_ssize_t newsize)
{
PyObject **items;
size_t new_allocated;
Py_ssize_t allocated = self->allocated;
/* Bypass realloc() when a previous overallocation is large enough
to accommodate the newsize. If the newsize falls lower than half
the allocated size, then proceed with the realloc() to shrink the list.
*/
if (allocated >= newsize && newsize >= (allocated >> 1)) {
assert(self->ob_item != NULL || newsize == 0);
Py_SIZE(self) = newsize;
return 0;
}
/* This over-allocates proportional to the list size, making room
* for additional growth. The over-allocation is mild, but is
* enough to give linear-time amortized behavior over a long
* sequence of appends() in the presence of a poorly-performing
* system realloc().
* The growth pattern is: 0, 4, 8, 16, 25, 35, 46, 58, 72, 88, ...
*/
new_allocated = (newsize >> 3) + (newsize < 9 ? 3 : 6);
/* check for integer overflow */
if (new_allocated > SIZE_MAX - newsize) {
PyErr_NoMemory();
return -1;
} else {
new_allocated += newsize;
}
if (newsize == 0)
new_allocated = 0;
items = self->ob_item;
if (new_allocated <= (SIZE_MAX / sizeof(PyObject *)))
PyMem_RESIZE(items, PyObject *, new_allocated);
else
items = NULL;
if (items == NULL) {
PyErr_NoMemory();
return -1;
}
self->ob_item = items;
Py_SIZE(self) = newsize;
self->allocated = new_allocated;
return 0;
}
結(jié)合C源碼我們來舉個(gè)例子，當(dāng)一個(gè)list長度為8時(shí)排拷，發(fā)生append操作后：
1）new_size = 原有的size ＋ append一個(gè)對(duì)象 = 8 + 1 = 9
2）newsize為9侧漓，二進(jìn)制是 1001，9 >> 3 = 1
3）new_allocated = 9 >> 3 + 6 = 7
4）new_allocated += new_size监氢，為9 + 7 ＝ 16
4）列表的最終大小為Py_SIZE = 16
Tuple的內(nèi)存利用
- 雖然Tuple不支持resize布蔗，但是我們可以粘貼兩個(gè)元祖組成一個(gè)新的元組，這個(gè)操作類似于List的append浪腐，但是又不會(huì)額外的分配內(nèi)存纵揍。但我們不能把它當(dāng)成append，因?yàn)槊看味紩?huì)進(jìn)行一個(gè)分配內(nèi)存和內(nèi)存copy操作议街。
- 另一個(gè)Tuple的靜態(tài)本質(zhì)帶來的好處是泽谨，resource caching。Python是garbage collected特漩，當(dāng)一個(gè)變量不用了吧雹，內(nèi)存會(huì)被回收并交回給OS。但是涂身，對(duì)于一個(gè)20個(gè)元素的Tuple雄卷，當(dāng)它不再被用時(shí)，內(nèi)存不會(huì)立即返還給OS蛤售，而是為了以后應(yīng)用而暫緩保留龙亲，當(dāng)一個(gè)新的Tuple被創(chuàng)建時(shí)，我們不會(huì)向OS重新申請(qǐng)分配內(nèi)存悍抑，而是用現(xiàn)有reserved的free memory。
- 也就是杜耙，Tuple的創(chuàng)建很簡單并且避免頻繁與OS申請(qǐng)內(nèi)存搜骡，創(chuàng)建一個(gè)具有10個(gè)元素的Tuple比創(chuàng)建一個(gè)List要快不少，55ns VS 280 ns佑女。
我們可以通過Python源碼看到上面的結(jié)論记靡，代碼位于Objects/tupleobject.c谈竿，我們可以清楚的看到tuple的粘貼過程：
- 新的大小等于兩個(gè)tuple大小之和
- 重新分配內(nèi)存
- 對(duì)于分配好的新內(nèi)存，通過兩個(gè)for循環(huán)將原來的兩個(gè)元組拷貝到新的元組上
static PyObject *
tupleconcat(PyTupleObject *a, PyObject *bb)
{
Py_ssize_t size;
Py_ssize_t i;
PyObject **src, **dest;
PyTupleObject *np;
if (!PyTuple_Check(bb)) {
PyErr_Format(PyExc_TypeError,
"can only concatenate tuple (not \"%.200s\") to tuple",
Py_TYPE(bb)->tp_name);
return NULL;
}
#define b ((PyTupleObject *)bb)
if (Py_SIZE(a) > PY_SSIZE_T_MAX - Py_SIZE(b))
return PyErr_NoMemory();
size = Py_SIZE(a) + Py_SIZE(b);
np = (PyTupleObject *) PyTuple_New(size);
if (np == NULL) {
return NULL;
}
src = a->ob_item;
dest = np->ob_item;
for (i = 0; i < Py_SIZE(a); i++) {
PyObject *v = src[i];
Py_INCREF(v);
dest[i] = v;
}
src = b->ob_item;
dest = np->ob_item + Py_SIZE(a);
for (i = 0; i < Py_SIZE(b); i++) {
PyObject *v = src[i];
Py_INCREF(v);
dest[i] = v;
}
return (PyObject *)np;
#undef b
}
- 在分配內(nèi)存函數(shù)PyTuple_New中摸吠，當(dāng)大小小于20時(shí)空凸，Python會(huì)直接從一個(gè)空閑的內(nèi)存表中拿出來，不會(huì)重新申請(qǐng)寸痢，這減少了小元組的內(nèi)存訪問次數(shù)呀洲，宏P(guān)yTuple_MAXSAVESIZE為20
PyObject *
PyTuple_New(Py_ssize_t size)
{
PyTupleObject *op;
Py_ssize_t i;
if (size < 0) {
PyErr_BadInternalCall();
return NULL;
}
#if PyTuple_MAXSAVESIZE > 0
if (size == 0 && free_list[0]) {
op = free_list[0];
Py_INCREF(op);
#ifdef COUNT_ALLOCS
tuple_zero_allocs++;
#endif
return (PyObject *) op;
}
if (size < PyTuple_MAXSAVESIZE && (op = free_list[size]) != NULL) {
free_list[size] = (PyTupleObject *) op->ob_item[0];
numfree[size]--;
#ifdef COUNT_ALLOCS
fast_tuple_allocs++;
#endif
/* Inline PyObject_InitVar */
#ifdef Py_TRACE_REFS
Py_SIZE(op) = size;
Py_TYPE(op) = &PyTuple_Type;
#endif
_Py_NewReference((PyObject *)op);
}
else
#endif
{
/* Check for overflow */
if ((size_t)size > ((size_t)PY_SSIZE_T_MAX - sizeof(PyTupleObject) -
sizeof(PyObject *)) / sizeof(PyObject *)) {
return PyErr_NoMemory();
}
op = PyObject_GC_NewVar(PyTupleObject, &PyTuple_Type, size);
if (op == NULL)
return NULL;
}
for (i=0; i < size; i++)
op->ob_item[i] = NULL;
#if PyTuple_MAXSAVESIZE > 0
if (size == 0) {
free_list[0] = op;
++numfree[0];
Py_INCREF(op); /* extra INCREF so that this is never freed */
}
#endif
#ifdef SHOW_TRACK_COUNT
count_tracked++;
#endif
_PyObject_GC_TRACK(op);
return (PyObject *) op;
}
