0x01 PyListObject

typedef struct {
    PyObject_VAR_HEAD
    /* Vector of pointers to list elements.  list[0] is ob_item[0], etc. */
    PyObject **ob_item;

    /* ob_item contains space for 'allocated' elements.  The number
     * currently in use is ob_size.
     * Invariants:
     *     0 <= ob_size <= allocated
     *     len(list) == ob_size
     *     ob_item == NULL implies ob_size == allocated == 0
     * list.sort() temporarily sets allocated to -1 to detect mutations.
     *
     * Items must normally not be NULL, except during construction when
     * the list is not yet visible outside the function that builds it.
     */
    Py_ssize_t allocated;
} PyListObject;

• PyListObject结构图示（内部元素以int为例）

• PyListObject是一个可变长对象，也是一个可变对象。

• ob_item是指向元素列表的指针，即Python中的list[0]就是ob_item[0]。

• ob_item指针和allocated数量正是维护元素列表（PyObjecy *列表）的关键。ob_item指针指向了元素列表所在内存块的首地址，allocated维护了当前列表中可容纳的元素总数。

• ob_size和allocated的关系是什么？

  • PyListObject对象并不是使用多少内存就申请多少内存（这样操作的效率会很低），而是每次申请一大块内存。
  • 这一大块的总内存就是由allocated来维护
  • 实际使用的内存数量由ob_size来管理

0x02 创建PyListObject对象

PyObject *
PyList_New(Py_ssize_t size)
{
    PyListObject *op;
    size_t nbytes;
#ifdef SHOW_ALLOC_COUNT
    static int initialized = 0;
    if (!initialized) {
        Py_AtExit(show_alloc);
        initialized = 1;
    }
#endif

    if (size < 0) {
        PyErr_BadInternalCall();
        return NULL;
    }
    /* Check for overflow without an actual overflow,
     *  which can cause compiler to optimise out */
    if ((size_t)size > PY_SIZE_MAX / sizeof(PyObject *))
        return PyErr_NoMemory();
    nbytes = size * sizeof(PyObject *);
    if (numfree) {
        numfree--;
        op = free_list[numfree];
        _Py_NewReference((PyObject *)op);
#ifdef SHOW_ALLOC_COUNT
        count_reuse++;
#endif
    } else {
        op = PyObject_GC_New(PyListObject, &PyList_Type);
        if (op == NULL)
            return NULL;
#ifdef SHOW_ALLOC_COUNT
        count_alloc++;
#endif
    }
    if (size <= 0)
        op->ob_item = NULL;
    else {
        op->ob_item = (PyObject **) PyMem_MALLOC(nbytes);
        if (op->ob_item == NULL) {
            Py_DECREF(op);
            return PyErr_NoMemory();
        }
        memset(op->ob_item, 0, nbytes);
    }
    Py_SIZE(op) = size;
    op->allocated = size;
    _PyObject_GC_TRACK(op);
    return (PyObject *) op;
}

• 只提供了PyList_New这一个方法来创建PyListObject对象。
• PyListObject对象实际上是分为两部分的：一是PyListObject对象本身；二是PyListObject对象维护的元素列表。
• 首先会根据传入的size计算所需内存数量，进行溢出检查；
• 创建PyListObject对象本身
  • 如果缓冲池可用，使用缓冲池，如果缓冲池没有可用对象，会在系统堆上申请内存创建PyListObject对象；
• 创建PyListObject对象维护的PyObject *对象列表
  • 根据size计算出来的总内存大小，来为PyObject *对象列表申请内存空间。
  • 每一个元素都会被初始化为NULL
• 最后设置ob_size和allocated的大小
• 当然在创建第一个PyListObject对象时，缓冲池还是空的，所以调用PyObject_GC_New函数创建PyListObject对象；假设我们创建6个元素的PyListObject对象，如下图所示
• 新创建的PyListObject对象

设置元素

int
PyList_SetItem(register PyObject *op, register Py_ssize_t i,
               register PyObject *newitem)
{
    register PyObject *olditem;
    register PyObject **p;
    if (!PyList_Check(op)) {
        Py_XDECREF(newitem);
        PyErr_BadInternalCall();
        return -1;
    }
    if (i < 0 || i >= Py_SIZE(op)) {
        Py_XDECREF(newitem);
        PyErr_SetString(PyExc_IndexError,
                        "list assignment index out of range");
        return -1;
    }
    p = ((PyListObject *)op) -> ob_item + i;
    olditem = *p;
    *p = newitem;
    Py_XDECREF(olditem);
    return 0;
}

• 先是类型检查和索引有效性检查
• 然后是新值取代旧值
• 在此期间ob_item指向的内存没有发生变化

插入元素

插入元素可能会导致ob_item指向的内存发生变化

int
PyList_Insert(PyObject *op, Py_ssize_t where, PyObject *newitem)
{
    if (!PyList_Check(op)) {
        PyErr_BadInternalCall();
        return -1;
    }
    return ins1((PyListObject *)op, where, newitem);
}

static int
ins1(PyListObject *self, Py_ssize_t where, PyObject *v)
{
    Py_ssize_t i, n = Py_SIZE(self);
    PyObject **items;
    if (v == NULL) {
        PyErr_BadInternalCall();
        return -1;
    }
    if (n == PY_SSIZE_T_MAX) {
        PyErr_SetString(PyExc_OverflowError,
            "cannot add more objects to list");
        return -1;
    }

    if (list_resize(self, n+1) == -1)
        return -1;

    if (where < 0) {
        where += n;
        if (where < 0)
            where = 0;
    }
    if (where > n)
        where = n;
    items = self->ob_item;
    for (i = n; --i >= where; )
        items[i+1] = items[i];
    Py_INCREF(v);
    items[where] = v;
    return 0;
}

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 > PY_SIZE_MAX - newsize) {
        PyErr_NoMemory();
        return -1;
    } else {
        new_allocated += newsize;
    }

    if (newsize == 0)
        new_allocated = 0;
    items = self->ob_item;
    if (new_allocated <= (PY_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;
}

• 实际调用的是内部的ins1函数；
• 为了完成插入元素的工作，需要先确保PyListObject对象的列表容量是否充足，所以调用list_resize函数来保证容量一定充足。
  • 先判断总大小（allocated）是否大于等于ob_size+1，并且ob_size+1大于等于总大小（allocated）的一半（allocated >= newsize && newsize >= (allocated >> 1)），如果是的话就不需要重新分配内存块
  • 如果不是第一种情况，就需要重新分配内存；按照规则计算出需要另外申请的内存大小，最终调用C的realloc函数（作用：就是在之前使用malloc申请的内存后面再增加一些内存空间）申请内存空间
  • 另外需要注意的是：如果ob_size+1的大小小于总大小的一半，还需要对之前的内存大小进行收缩，以免浪费空间（真是锱铢必较啊，大师就是大师，细节拿捏的这么精确）
• 元素列表内存空间调整完以后，接下来是实际的插入元素。
  • 确定元素的插入点。因为Python支持负索引，所以需要考虑负数的情况

还有PyListObject对象的append方法，和insert差不多，只是它添加元素的位置是ob_size+1，而不是allocated+1的位置。

删除元素

static PyObject *
listremove(PyListObject *self, PyObject *v)
{
    Py_ssize_t i;

    for (i = 0; i < Py_SIZE(self); i++) {
        int cmp = PyObject_RichCompareBool(self->ob_item[i], v, Py_EQ);
        if (cmp > 0) {
            if (list_ass_slice(self, i, i+1,
                               (PyObject *)NULL) == 0)
                Py_RETURN_NONE;
            return NULL;
        }
        else if (cmp < 0)
            return NULL;
    }
    PyErr_SetString(PyExc_ValueError, "list.remove(x): x not in list");
    return NULL;
}

• 遍历列表内的每一个元素，通过PyObject_RichCompareBool函数判断元素是否与待删除元素相同，相同的话返回值大于0；
• 如果相同调用list_ass_slice函数删除该元素

0x03 缓冲池

PyIntObject和PyStringObject对象都有相应的缓冲池机制，PyListObject也不例外。

#define PyList_MAXFREELIST 80

static PyListObject *free_list[PyList_MAXFREELIST];
static int numfree = 0;

• Python初始化的时候，free_list数组内的指针都是NULL（数组内最多缓存的对象个数为80个），numfree也是0；即没有任何PyListObject对象缓存，那么是何时对PyListObject对象进行缓存的呢？

static void
list_dealloc(PyListObject *op)
{
    Py_ssize_t i;
    PyObject_GC_UnTrack(op);
    Py_TRASHCAN_SAFE_BEGIN(op)
    if (op->ob_item != NULL) {
        /* Do it backwards, for Christian Tismer.
           There's a simple test case where somehow this reduces
           thrashing when a *very* large list is created and
           immediately deleted. */
        i = Py_SIZE(op);
        while (--i >= 0) {
            Py_XDECREF(op->ob_item[i]);
        }
        PyMem_FREE(op->ob_item);
    }
    if (numfree < PyList_MAXFREELIST && PyList_CheckExact(op))
        free_list[numfree++] = op;
    else
        Py_TYPE(op)->tp_free((PyObject *)op);
    Py_TRASHCAN_SAFE_END(op)
}

• 其实是在销毁一个PyListObject对象的时候进行了缓存处理
  • 第一步：销毁了PyListObject对象维护的PyObject *列表的内存。
  • 第二步：如果缓冲池大小没有超过80，将PyListObject对象本身加入到free_list缓冲池中，以供下次使用,；否则直接释放内存给系统。
• 思考：为什么不对Pyobject *对象列表进行缓存呢？
  • 如果真的想对PyObject *对象列表进行缓存，是完全可以的。
  • 但是缓存的PyObject *对象内存只能PyListObject对象来使用，其他对象无法使用。
  • 所以虽然这样做可以节省创建元素列表时的开销，但是收益不是很高，而且会过多消耗系统内存
  • 所以Python采用将元素列表内存归还给系统堆，以时间换取空间。
• PyListObject对象缓冲池

---

欢迎关注微信公众号（coder0x00）或扫描下方二维码关注，我们将持续搜寻程序员必备基础技能包提供给大家。