free_list 机制

List 对象比 String 对象更简单，主要维护一个 Object * 数组，所以 List 对象的创建也更简单。其代码如下：

// Objects/listobject.c:156
PyObject *
PyList_New(Py_ssize_t size)
{
    PyListObject *op;

    if (size < 0) {
        PyErr_BadInternalCall();
        return NULL;
    }
    // 注意这里，free_list 是一个全局数组，保存的是已经不再使用的 List Object。
    if (numfree) {
        numfree--;
        op = free_list[numfree];
        _Py_NewReference((PyObject *)op);
    } else {
        op = PyObject_GC_New(PyListObject, &PyList_Type);
        if (op == NULL)
            return NULL;
    }
    if (size <= 0)
        op->ob_item = NULL;
    else {
        op->ob_item = (PyObject **) PyMem_Calloc(size, sizeof(PyObject *));
        if (op->ob_item == NULL) {
            Py_DECREF(op);
            return PyErr_NoMemory();
        }
    }
    Py_SIZE(op) = size;
    op->allocated = size;
    _PyObject_GC_TRACK(op);
    return (PyObject *) op;
}

过程并不复杂，除过一些错误处理代码，首先会尝试从 free_list 中复用闲置的 List Object 对象，如果没有闲置 List Object 对象就不得不申请内存了，所以 List Object 结构体是可回收利用的，关于 free_list 稍晚再看，让我们尽快创建 List Object。List Object 的实际数据区域是其 ob_item 成员，在获得 List Object 结构后，需要通过 PyMem_Calloc 从内存池中分配空间，空间大小由参数 size 指定。最后 4 行代码说明，一个新建的 List Object 的allocated 和 size 是相同的。

free_list 机制

Python 作为一种动态语言，即使是非常基本的数据，也需要一些额外的头部来保存类型信息，这使得 Python 中数据创建的开销比较大，在很多地方 Python 都采用了一些缓存、池方案，进行内存方面的优化，比如 String Object 中的 interned 机制、静态的 latin 字母表等。

free_list 是针对 List Obejct 的优化，Python 准备了一个全局数组，用于回收那些可被 reuse 的 List Object，而不是频繁的销毁、创建 List Object。

// Objects/listobject.c:120
/* 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;

可以看到 free_list 的大小是 80，在 Python 刚启动的时候，这是一个空数组，numfree 为 0。什么时候 free_list 才会被填充呢？一种方法是在 Python 启动之初就预分配 80 个空的 List Object 对象，并将这些指针填充到 free_list 中，Python 选择了另外一种更紧凑的做法，在 List Object 的析构方法（C 语言当然没有“析构”的概念，其实说的 list_dealloc 函数）中有如下代码：

// Objects/listobject.c:359
static void
list_dealloc(PyListObject *op)
{
    Py_ssize_t i;
    PyObject_GC_UnTrack(op);
    Py_TRASHCAN_BEGIN(op, list_dealloc)
    if (op->ob_item != NULL) {
       // 释放 ob_item 数组，该数组不是 GC 内存。
        while (--i >= 0) {
            Py_XDECREF(op->ob_item[i]);
        }
        PyMem_FREE(op->ob_item);
    }

    // 如果 free_list 还没满，就把当前 List Object 插入 free_list 的结尾。
    if (numfree < PyList_MAXFREELIST && PyList_CheckExact(op))
        free_list[numfree++] = op;
    else
        Py_TYPE(op)->tp_free((PyObject *)op);
    Py_TRASHCAN_END
}

在 List Object 析构中，优先考虑将其放回 free_list 中 reuse，如果 free_list 已经满了才会真正释放 List Object。当 free_list 中有 2 个可用对象时，free_list 看起来是这样。

此时有一个新的 List Object 被析构，其 ob_item 被释放后，List Object 结构会被追加在 free_list 的尾部。

numfree 实际上标明了 free_list 的最大可用区域。当需要创建 List Object 时，则反之，numfree 减少，free_list 尾部左移一个元素，直到用尽 free_list.

Think In Python

15. List 对象的创建

free_list 机制