原文地址作者简介渣渣飞，一个不愿意透漏真名的网易游戏运维与基础架构部高级运维工程师。长年在票圈深夜放毒，是网易游戏高级运维工程师，对代码性能及系统原理饶有兴趣，三人行，必有我师。现负责监控相关业务开发。前言Python 的列表（list）是一个非常灵活的数组，可以随意调整长度。正是因为这种便利，使得我们会情不自禁地去修改数组以满足我们的需求，其中相比于insert,pop等等而言，append用法更常见。有像这样使用：>>> test = >>> test.append(1) >>> test.append({2}) >>> test.append([3]) >>> print test # 输出 [1, set([2]), [3]]
也有像这样使用的：test = for i in range(4): test.append(i) print test # 输出 [0, 1, 2, 3]
这样用很开心，也很满足。但其实只要遇到能够动态修改数据长度场景，我们都应该马上反应过来一点，那就是内存管理的问题。如果运行效率和便捷性同时满足的话，那简直就是大大的福音呀。然而，上帝为你开启一扇窗的同时肯定也已经关上了一扇门了！吝啬的初始化深受预分配知识的熏陶，我们也是觉得 list 在初始化是有分配一定的长度的，要不然每次都申请内存那得多 ”low“ 啊。然后实际上 list 真的就是这么 ”low“:import sys test = test_1 = [1] print sys.getsizeof(test) print sys.getsizeof(test_1) - sys.getsizeof(test) # 输出 72 # 空列表内存大小，也是 list 对象的总大小 8 # 代表增加一个成员，list 增加的大小 ( 此大小为对象指针的长度 )
我们的猜测是，list 在定义之后，会预先分配好一个一定大小的池用来塞数据，以避免动不动就申请内存。但是在上面的实验看出，一个成员的列表，比一个空列表，长度仅仅只是大了 8 字节（对象指针的大小），如果真的存在这样一个预分配的池，那么在预分配个数之内添加成员，两者的内存大小应该是保持不变才对。所以可以猜测这块 list应该是没有这样的一个预分配内存池。这里需要来个实锤：PyObject * PyList_New(Py_ssize_t size) { PyListObject *op; size_t nbytes; if (size < 0) { PyErr_BadInternalCall; return ; } /* 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; // list对象指针的缓存 if (numfree) { numfree--; op = free_list[numfree]; _Py_NewReference((PyObject *)op); } else { op = PyObject_GC_New(PyListObject, &PyList_Type); if (op == ) return ; } // list 成员的内存申请 nbytes = size * sizeof(PyObject *); if (size <= 0) op->ob_item = ; else { op->ob_item = (PyObject **) PyMem_MALLOC(nbytes); if (op->ob_item == ) { 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; }
当我们在执行 test = [1]时，实际上只做了两件事：- 根据成员的数目，构建相应长度的空列表；(上述代码)
- 一个个将这些成员塞进去；
可能有童鞋会觉得，在塞成员的那一步，说不定会触发什么机制使它变大？很可惜，因为初始化用的方法是 PyList_SET_ITEM, 所以这里是木有的触发什么机制，只是简单的数组成员赋值而已：#define PyList_SET_ITEM(op, i, v) (((PyListObject *)(op))->ob_item[i] = (v))
所以整个 list 的初始化，还真的就是木有预分配的内存池，直接按需申请，一个萝卜一个坑，实在得狠；可变长的关键初始化过程是这样还可以理解，如果运行中还这样的话，那就有点说不过去了。试想下，在文章开头用 append的例子中，如果每append一个元素就申请一次内存，那么list可能要被吐槽到怀疑人生了, 所以很明显，在对于内存的申请，它还是有自己的套路的。在 list里面，不管是insert、pop还是append，都会遇到list_resize，故名思义，这个函数就是用来调整list对象的内存占用的。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 != || 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 = ; if (items == ) { PyErr_NoMemory; return -1; } self->ob_item = items; Py_SIZE(self) = newsize; self->allocated = new_allocated; return 0; }
在上面的代码中，频繁看到两个名词：newsize和new_allocated, 这里需要解释下，newsize并不是增加/减少的个数，而是增加/减少之后的成员总数目。比方说：a = [1, 2, 3] a.append(1)
上面的 append触发list_resize时，newsize是 3 + 1， 而不是 1；这边比较重要，因为在pop这类减少列表成员时候，就是传入缩减后的总数目。在 list 的结构定义中，关于长度的定义有两个，分别是 ob_size(实际的成员数)，allocated(总成员数)它们之间的关系就是： 0 <= ob_size <= allocated len(list) == ob_size
所以 new_allocated就很好理解了，这个就是新的总坑数。当名词含义理解得差不多时，我们就能顺藤摸瓜知道一个列表在list_resize之后，大小会变成怎样？方法其实从上面注释和代码都说得很明白了，这里再简单整理下：- 先确定一个基数：
new_allocated = (newsize >> 3) + (newsize < 9 ? 3 : 6); - 判断下
new_allocated + newsize有没有超过PY_SIZE_MAX, 如果超过了，直接报错； - 最终确定新的总坑数是：
new_allocated + newsize， 如果newsize是 0, 那么总坑数直接为 0 ；
下面演示下：#coding: utf8 import sys test = raw_size = sys.getsizeof(test) test.append(1) print "1 次 append 减去空列表的内存大小：%s " % (sys.getsizeof(test) - raw_size) test.append(1) print "2 次 append 减去空列表的内存大小：%s " % (sys.getsizeof(test) - raw_size) test.append(1) print "3 次 append 减去空列表的内存大小：%s " % (sys.getsizeof(test) - raw_size) test.append(1) print "4 次 append 减去空列表的内存大小：%s " % (sys.getsizeof(test) - raw_size) test.append(1) print "5 次 append 减去空列表的内存大小：%s " % (sys.getsizeof(test) - raw_size) test.append(1) print "6 次 append 减去空列表的内存大小：%s " % (sys.getsizeof(test) - raw_size)
# 输出结果 1 次 append 减去空列表的内存大小：32 2 次 append 减去空列表的内存大小：32 3 次 append 减去空列表的内存大小：32 4 次 append 减去空列表的内存大小：32 5 次 append 减去空列表的内存大小：64 6 次 append 减去空列表的内存大小：64
开始简单的代入法一步步算：其中：new_allocated = (newsize >> 3) + (newsize < 9 ? 3 : 6) + newsize （因为下面的 newsize > 0）当原allocated >= newsize 并且 newsize >= 原allocated / 2 时，不改变 allocated 不申请内存直接返回
| 第 n 次 append | 列表原长度 | 新增成员数 | 原 allocated | newsize | new_allocated |
|---|
| 1 | 0 | 1 | 0 | 0 + 1 = 1 | 3 + 1 = 4 | | 2 | 1 | 1 | 4 | 1 + 1 = 2 | 无需改变 | | 3 | 2 | 1 | 4 | 2 + 1 = 3 | 无需改变 | | 4 | 3 | 1 | 4 | 3 + 1 = 4 | 无需改变 | | 5 | 4 | 1 | 4 | 4 + 1 = 5 | 3 + 5 = 8 | | 6 | 5 | 1 | 8 | 5 + 1 = 6 | 无需改变 |
通过上面的表格，应该比较清楚看到什么时候会触发改变 allocated，并且当触发时它们是如何计算的。为什么我们需要这样关注allocated？理由很简单，因为这个值决定了整个 list 的动态内存的占用大小；扩容是这样，缩容也是照猫画虎。反正都是算出新的 allocated， 然后由 PyMem_RESIZE来处理。#define PyMem_REALLOC(p, n) ((size_t)(n) > (size_t)PY_SSIZE_T_MAX ? : realloc((p), (n) ? (n) : 1)) #define PyMem_RESIZE(p, type, n) ( (p) = ((size_t)(n) > PY_SSIZE_T_MAX / sizeof(type)) ? : (type *) PyMem_REALLOC((p), (n) * sizeof(type))
基本上，就是判断是否超过最大数，否则的话就是和 C resize 函数近似了，以下摘抄了一段关于该函数的描述：
多说几句综上所述，在一些明确列表成员或者简单处理再塞入列表的情况下，我们不应该再用下面的方式：test = for i in xrange(4): test.append(i) print test
而是应该用列表推导式：test = [i for i in xrange(4)]。为什么推荐列表推导呢？显而易见的效果就有：简练、清晰；用多少就申请多少，不会因为 append触发PyMem_RESIZE申请过多内存；容易造成内存浪费；相比 for i in xxx，列表推导方式直接增加元素，少了一些函数调用，如：SETUP_LOOP、CALL_FUNCTION等；但是上面的推荐肯定也是在某些前提条件下才合适咯：- 真的只是为了得到一个列表；
- 循环体内逻辑简单，没有太复杂的处理、判断、调用等等；
PS： 切记勿为了使用列表推导而使用，合理使用才是科学之道； 本文仅代表作者个人观点，不代表巅云官方发声，对观点有疑义请先联系作者本人进行修改，若内容非法请联系平台管理员，邮箱2522407257@qq.com。更多相关资讯，请到巅云www.yx10011.com学习互联网营销技术请到巅云建站www.yx10011.com。 | 
