Python 列表的二进制布局

Question

我正在编写一个程序，我需要了解 Python / Cython 中不同数据容器的效率（内存方面）。所述容器之一是标准Pythonlist。

Python 列表让我很困惑，因为我不知道它在二进制级别上是如何工作的。与Python不同，C的数组很容易理解，因为所有元素都是相同的类型，并且空间是提前声明的。这意味着当程序员想要进入并索引数组时，程序从数学上知道要转到哪个内存地址。但问题是，Python 列表可以存储许多不同的数据类型，甚至可以存储列表内的嵌套列表。这些数据结构的大小一直在变化，并且列表仍然保存它们，说明这些变化。是否存在额外的分隔符内存以使列表保持动态？

如果可以的话，我会很感激 RAM 中示例列表的实际二进制布局，并用每个字节代表的内容进行注释。这将帮助我完全理解列表的内部工作原理，因为我正在二进制级别上工作。

Answer 1

列表对象在 中定义Include/listobject.h。结构非常简单：

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;

并PyObject_VAR_HEAD定义为

typedef struct _object {
    _PyObject_HEAD_EXTRA
    Py_ssize_t ob_refcnt;
    struct _typeobject *ob_type;
} PyObject;

typedef struct {
    PyObject ob_base;
    Py_ssize_t ob_size; /* Number of items in variable part */
} PyVarObject;

基本上，列表对象看起来像这样：

[ssize_t ob_refcnt]
[type *ob_type]
[ssize_t ob_size]
[object **ob_item] -> [object *][object *][object *]...
[ssize_t allocated]

请注意，len检索 的值ob_size。

ob_item指向一个PyObject *指针数组。列表中的每个元素都是一个 Python 对象，并且 Python 对象始终通过引用传递（在 C-API 级别，作为指向实际PyObjects 的指针）。因此，列表仅存储指向对象的指针，而不存储对象本身。

当列表填满时，它将被重新分配。allocated跟踪列表最多可以容纳多少个元素（在重新分配之前）。重新分配算法如下Objects/listobject.c：

/* Ensure ob_item has room for at least newsize elements, and set
 * ob_size to newsize.  If newsize > ob_size on entry, the content
 * of the new slots at exit is undefined heap trash; it's the caller's
 * responsibility to overwrite them with sane values.
 * The number of allocated elements may grow, shrink, or stay the same.
 * Failure is impossible if newsize <= self.allocated on entry, although
 * that partly relies on an assumption that the system realloc() never
 * fails when passed a number of bytes <= the number of bytes last
 * allocated (the C standard doesn't guarantee this, but it's hard to
 * imagine a realloc implementation where it wouldn't be true).
 * Note that self->ob_item may change, and even if newsize is less
 * than ob_size on entry.
 */
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;
}

正如您从评论中看到的，列表增长相当缓慢，按以下顺序：

0, 4, 8, 16, 25, 35, 46, 58, 72, 88, ...