Python FreeList内存重用机制一瞥

一次被人问起为什么下面这段Python代码两次调用返回的List对象id相同:

def foo(a=[]):
  return a

print id(foo([]))==id(foo([]))

这很简单,只要认真读文档就会明白,因为Python中id方法的返回值,只保证在该对象存活期内是唯一的,两个存活期不同的对象可能会有相同的id:

id(object)
Return the “identity” of an object. This is an integer (or long integer) which is guaranteed to be unique and constant for this object during its lifetime. Two objects with non-overlapping lifetimes may have the same id() value.
CPython implementation detail: This is the address of the object in memory.

比如print id([])==id([]),其执行过程是先创建一个临时List #1,获取它的地址,然后List #1被Free,随后再创建新的List #2时,则有可能重用刚才被释放的List #1的内存,所以地址就有可能相同。

不过随后又有一个新问题,为什么id([])==id([])始终为True?这也很简单,CPython中List、Tuple、Int等类型,内部实现其实都有一个free_list,当一个对象被销毁时,它的内存并不会被立即回收,而是放到这个池中,当下次再创建新的对象时,则重用上次被销毁对象的内存。从下面的代码可以推测出这个缓冲池的工作方式,按照对象创建销毁的先后次序不同,新的对象会领取到不同的地址:

a=[]; b=[];
print id(a)==id(b)  # 这样肯定是 False 啦

def f1():
  a=[]
  return a

"""
执行一次 id(f1()) 大致过程为(假设free_list不为空):
a=free_list.pop(); _tmp=id(a);
free_list.append(a); del a
每次都领到相同的free_list[-1]
所以始终为True
"""
print id(f1())==id(f1())

def f2():
  b=[]; a=[]
  return a

"""
执行 id(f2())的大致过程为
b=free_list.pop()
a=free_list.pop()
因为b在函数退出后即被销毁,所以先执行
free_list.append(b); del b;
_tmp=id(a)
free_list.append(a); del a;
因为 append与pop操作不对称,
所以始终为False
"""
print id(f2())==id(f2())

# 并且可以推断出下面的调用始终为True
i=id(f2()) ; f2();
print i==id(f2())

可还有一个问题,为什么id(list())==id(list())却为False呢?这还真没注意过,原来list()和ListLiteral内存分配的方法并不一样。先看看free_list实现在哪,见listobject.c

94
95
96
97
98
99
/* 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,下面是创建List方法PyList_New

113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
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;
    }
    printf("\nCall PyList_New\n");
    /* 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]; /* free_list.pop() */
        _Py_NewReference((PyObject *)op);
#ifdef SHOW_ALLOC_COUNT
        count_reuse++;
#endif
    } else {/*free_list中没有可用元素则新建*/
        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; /* Why? */
    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;
}

与之对应的则是List对象回收list_dealloc方法,需将对象放到free_list中以备后用:

298
299
300
301
302
303
304
305
306
307
308
309
310
311
312
313
314
315
316
317
318
319
320
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);/*虽然Free了内容但未设置成NULL,不知为何*/
    }
    if (numfree < PyList_MAXFREELIST && PyList_CheckExact(op))
        free_list[numfree++] = op; /* free_list.append(op) */
    else
        Py_TYPE(op)->tp_free((PyObject *)op);
    Py_TRASHCAN_SAFE_END(op)
}

这些就是free_list的实现源码,不单List类型,其它的Tuple、Set、Int等内建类型都有类似的实现。接着再看list()[]两种形式Python解释器具体如何解释。直接看反编译得到的ByteCode:

Python代码 反编译输出
import dis
def f():
  a=[]
  b=list()
dis.dis(f)
 0 BUILD_LIST               0
 3 STORE_FAST               0 (a)

 6 LOAD_GLOBAL              0 (list)
 9 CALL_FUNCTION            0
12 STORE_FAST               1 (b)
15 LOAD_CONST               0 (None)
18 RETURN_VALUE

也没什么奇怪的东西,一个是执行BUILD_LIST指令,一个是调用函数。再看看BUILD_LIST指令的具体是如何实现的,见ceval.c,可以看到它直接调用了PyList_New函数,所以它会用到free_list

2202
2203
2204
2205
2206
2207
2208
2209
2210
2211
2212
case BUILD_LIST:
  x =  PyList_New(oparg);
  if (x != NULL) {
    for (; --oparg >= 0;) {
      w = POP();
      PyList_SET_ITEM(x, oparg, w);
    }
    PUSH(x);
    continue;
  }
  break;

list()则是直接调用类型构造方法,对应于listobject.cPyList_Type结构:

2767
2768
2769
2770
2771
2772
2773
2774
2775
2776
2777
2778
PyTypeObject PyList_Type = {
    PyVarObject_HEAD_INIT(&PyType_Type, 0)
    "list",
    sizeof(PyListObject),
    0,
    (destructor)list_dealloc,                   /* tp_dealloc */
    /*  ............  */
    (initproc)list_init,                        /* tp_init */
    PyType_GenericAlloc,                        /* tp_alloc */
    PyType_GenericNew,                          /* tp_new */
    PyObject_GC_Del,                            /* tp_free */
};

其中tp_new字段就是该类型的New方法,可以看到List类型只用了PyType_GenericNew函数,该方法并不会使用free_list,但是List类型的析构方法依然是list_dealloc,所以id(list())==id([])仍然为True。为什么List类型默认的New方法不使用缓冲池呢?我也不太明白。也许是因为按照标准文档中指示的原则,Mutable类型的tp_new方法不应作过多的初始化操作:

PyTypeObject.tp_new
A good rule of thumb is that for immutable types, all initialization should take place in tp_new, while for mutable types, most initialization should be deferred to tp_init.

类似的dict类型也是如此,而int、set、tuple这些Immutable类型则两种创建方式都会使用free_list