Python 解释器实现:list类型处理
目录

object and type

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;

Python和CPP std中的vector很像,ob_size记录当前ob_item中已插入的PyObject*个数,allocated记录着分配的ob_item数组大小。

PyTypeObject PyList_Type = {
PyVarObject_HEAD_INIT(&amp;PyType_Type, 0)
"list",
sizeof(PyListObject),
0,
(destructor)list_dealloc,                   /* tp_dealloc */
(printfunc)list_print,                      /* tp_print */
0,                                          /* tp_getattr */
0,                                          /* tp_setattr */
0,                                          /* tp_compare */
(reprfunc)list_repr,                        /* tp_repr */
0,                                          /* tp_as_number */
&amp;list_as_sequence,                          /* tp_as_sequence */
&amp;list_as_mapping,                           /* tp_as_mapping */
(hashfunc)PyObject_HashNotImplemented,      /* tp_hash */
0,                                          /* tp_call */
0,                                          /* tp_str */
PyObject_GenericGetAttr,                    /* tp_getattro */
0,                                          /* tp_setattro */
0,                                          /* tp_as_buffer */
Py_TPFLAGS_DEFAULT | Py_TPFLAGS_HAVE_GC |
Py_TPFLAGS_BASETYPE | Py_TPFLAGS_LIST_SUBCLASS,         /* tp_flags */
list_doc,                                   /* tp_doc */
(traverseproc)list_traverse,                /* tp_traverse */
(inquiry)list_clear,                        /* tp_clear */
list_richcompare,                           /* tp_richcompare */
0,                                          /* tp_weaklistoffset */
list_iter,                                  /* tp_iter */
0,                                          /* tp_iternext */
list_methods,                               /* tp_methods */
0,                                          /* tp_members */
0,                                          /* tp_getset */
0,                                          /* tp_base */
0,                                          /* tp_dict */
0,                                          /* tp_descr_get */
0,                                          /* tp_descr_set */
0,                                          /* tp_dictoffset */
(initproc)list_init,                        /* tp_init */
PyType_GenericAlloc,                        /* tp_alloc */
PyType_GenericNew,                          /* tp_new */
PyObject_GC_Del,                            /* tp_free */
};

PyListObject pool

list对象在这里也使用到了缓冲池技术:

/* 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;

对于不再使用的PyListObject对象,先放到free_list中,直接供下次申请PyListObject对象时直接使用,减少了内存申请操作。

allocated大小

对于分配的allocated大小,符合以下几个规则:

  • 首次分配时 allocated == ob_size;
  • 如果 allocated/2 <= newsize <= allocated,那么allocated不变,调整ob_size至new_size,也就是说allocated不会超过newsize的2倍;
  • 如果 newsize < allocated/2,那么allocated = newsize + newsize/8 + (newsize < 9 ? 3 : 6),也就是说allocated是newsize的1.125倍多一点点;

发表评论