本系列文章是一系列学习笔记，希望较为深入地分析Python3中的原理、性能，文章中绝大部分观点都是原作作者的观点（如下），本人对书中示例加以实践和总结，并结合相应的Python的C语言源码(3.6.1)，分享出来。原著：

• 《High Performance Python》by O'Relly Media，作者Micha Gorelick，Ian Ozsvald
• 《Fluent Python》by O'Relly Media，作者Luciano Ramalho

---

从内存利用和CPU利用开始了解List和Tuple的优缺点

定义

List：动态数组，元素可变，可改变大小（append，resize）
Tuple：静态数组，不可变，数据一旦创建后不可改变

List的内存利用

• 当创建N个元素的List时，Python的动态内存分配长N＋1个元素的内存，第一个元素存储列表长度，和列表的元信息。
• 当Append一个元素时，Python将创建一个足够大的列表，来容纳N个元素和将要被追加的元素。重新创建的列表长度大于N＋1（虽然我们只触发一次append操作），实际上，为了未来的Append操作，M个元素长度（M>N+1)的内存将会被额外分配，然后，旧列表中的数据被copy到新列表中，旧列表销毁。
• 额外内存的分配，只会发生在第一次Append操作时，当我们创建普通列表时，不会额外分配内存。
• 这里的哲学是，一个Append操作很可能是很多Append操作的开始，通过额外分配内存来减少可能的内存分配和内存copy的次数。
• 那么，对于一个具有N个元素的列表，当一次Append操作发生时，新列表要分配多少内存（额外M个元素，需多分配一个元素存储长度）呢？答案是：

** M = (N >> 3) + (N <9 ? 3 : 6) + 1 **

我们来看Python3.6.1的列表resize过程，源代码位于Objects/listobject.c中的list_resize函数：

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;
}

结合C源码我们来举个例子，当一个list长度为8时，发生append操作后：
1）new_size = 原有的size ＋ append一个对象 = 8 + 1 = 9
2）newsize为9，二进制是 1001，9 >> 3 = 1
3）new_allocated = 9 >> 3 + 6 = 7
4）new_allocated += new_size，为9 + 7 ＝ 16
4）列表的最终大小为Py_SIZE = 16

---

Tuple的内存利用

• 虽然Tuple不支持resize，但是我们可以粘贴两个元祖组成一个新的元组，这个操作类似于List的append，但是又不会额外的分配内存。但我们不能把它当成append，因为每次都会进行一个分配内存和内存copy操作。
• 另一个Tuple的静态本质带来的好处是，resource caching。Python是garbage collected，当一个变量不用了，内存会被回收并交回给OS。但是，对于一个20个元素的Tuple，当它不再被用时，内存不会立即返还给OS，而是为了以后应用而暂缓保留，当一个新的Tuple被创建时，我们不会向OS重新申请分配内存，而是用现有reserved的free memory。
• 也就是，Tuple的创建很简单并且避免频繁与OS申请内存，创建一个具有10个元素的Tuple比创建一个List要快不少，55ns VS 280 ns。

我们可以通过Python源码看到上面的结论，代码位于Objects/tupleobject.c，我们可以清楚的看到tuple的粘贴过程：

• 新的大小等于两个tuple大小之和
• 重新分配内存
• 对于分配好的新内存，通过两个for循环将原来的两个元组拷贝到新的元组上

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
}

• 在分配内存函数PyTuple_New中，当大小小于20时，Python会直接从一个空闲的内存表中拿出来，不会重新申请，这减少了小元组的内存访问次数，宏PyTuple_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;
}