复制列表元素时 Python 做了什么

4/5/2019

缘起

而刚刚学习 Python 的人常常会遇到一个问题，如下

# 意图是获取包含 10 个空 list 的列表
>>> li = [[]] * 10

# print 出来感觉没问题
>>> li
[[], [], [], [], [], [], [], [], [], []]

# 尝试往第一个 list 添加一个元素，并打印
>>> li[0].append(1)
>>> li
[[1], [1], [1], [1], [1], [1], [1], [1], [1], [1]]

# 结果发现每个 list 里面都包含了新添加的元素，而预期中应该是
>>> li[0].append(1)
>>> li
[[1], [], [], [], [], [], [], [], [], []]

# 原因是当 Python 执行 [obj] * count 时，新的 list 中的 item 拷贝的是原 obj 的引用，而不会进行复制。
# 如果想要初始化全新的 list 的话，则需要按如下方式初始化
>>> li = [[] for _ in range(10)]
>>> li[0].append(1)
>>> li
[[1], [], [], [], [], [], [], [], [], []]

一探究竟

最近在看《Python源码剖析》，让我们看看 [obj] * count 在 Python 底层是如何实现的。

字节码

Python 所有的代码都会编译成字节码之后执行，而类似 [obj] * count 的表达式，编译成字节码之后为

>>> import dis
>>> def test(): return [obj] * count
>>> dis.dis(test)

# 构建 [obj]
  1           0 LOAD_GLOBAL              0 (obj)
              2 BUILD_LIST               1

# 读取 count
              4 LOAD_GLOBAL              1 (count)

# 实现 [obj] * count
              6 BINARY_MULTIPLY

# 函数返回值
              8 RETURN_VALUE

具体指令实现

而 BINARY_MULTIPLY 指令在源码中的实现为

        TARGET(BINARY_MULTIPLY) {
             # 获取 count
            PyObject *right = POP();
             # 获取 [obj]
            PyObject *left = TOP();

            # 重点来了，在这里获取相乘的结果
            PyObject *res = PyNumber_Multiply(left, right);

            Py_DECREF(left);
            Py_DECREF(right);
            SET_TOP(res);
            if (res == NULL)
                goto error;
            DISPATCH();
        }

PyNumber_Multiply 实现

指令的核心便是 PyNumber_Multiply，Python 源码中对该函数的注解

/* This is the equivalent of the Python expression: o1 * o2. */
PyAPI_FUNC(PyObject *) PyNumber_Multiply(PyObject *o1, PyObject *o2);

原来 Python 中所有 o1 * o2 的操作最后都是通过该函数实现，而 [obj] * count 也不例外。

PyNumber_Multiply 的实现如下：

PyObject *
PyNumber_Multiply(PyObject *v, PyObject *w)
{
        // ......
        // v 为 [obj]，w 为 count
       // v->ob_type 就是 [obj]  的类型 list,  而 tp_as_sequence 是其实现的一组与 sequence 相关的函数集合。
        PySequenceMethods *mv = v->ob_type->tp_as_sequence;
        PySequenceMethods *mw = w->ob_type->tp_as_sequence;
        Py_DECREF(result);
        
        if  (mv && mv->sq_repeat) {
            // 因为 [obj] 定义了 tp_as_sequence->sq_repeat 所以最后会进入这里
            return sequence_repeat(mv->sq_repeat, v, w);
        }
        else if (mw && mw->sq_repeat) {
            return sequence_repeat(mw->sq_repeat, w, v);
        }

    return result;
}

而 sequence_repeat 仅仅是简单进行了一些类型检查，最后直接 call repeatfunc，也即外界传入的 sq_repeat

static PyObject *
sequence_repeat(ssizeargfunc repeatfunc, PyObject *seq, PyObject *n)
{
    // 略过
    return (*repeatfunc)(seq, count);
}

sq_repeat 到底是什么？

该函数在 list 类型的实现为

// list_as_sequence 实现了一组与 list 相关的操作
static PySequenceMethods list_as_sequence = {
    // 比如 list 的长度
    (lenfunc)list_length,                       /* sq_length */
     // 这就是最终调用的函数
    (ssizeargfunc)list_repeat,                  /* sq_repeat */

   ...
};

list_repeat 实现源码

经过寻找，我们最后终于找到了最终实现 [obj] * count 的代码。

下面是 list_repeat 简化后的代码:

static PyObject *
list_repeat(PyListObject *a, Py_ssize_t n)
{
    ...
    PyObject *elem;
    # np 指向新分配的 count 大小的 list 对象
    np = (PyListObject *) PyList_New(size);

    items = np->ob_item;

    # 如果 [obj] 的对象大小为 1 的话，我们这里就是如此
    if (Py_SIZE(a) == 1) {

        # 获取 obj，即这里的 elem
        elem = a->ob_item[0];

        for (i = 0; i < n; i++) {
            # 因为 elem 是指针，所以这里新的 list 的 items 里面包含的是原有的 obj 的引用，而不是复制
            items[i] = elem;
            Py_INCREF(elem);
        }
        return (PyObject *) np;
    }
    ...
}

所以 [obj] * count 最后获得是包含 count 个 obj 引用的新 list

结尾

最后我们可以看到实际上最后实现该功能的函数是

obj->ob_type->tp_as_sequence->sq_repeat = list_repeat

Python 为什么经过那么多层的抽象呢？因为 C 本身并不支持 class，而 Python 本身却是万物皆对象，而基于 C 实现的 Python 自然就需要通过大量的抽象来模拟实现面向对象的功能。

结尾安利下《Python源码剖析》，虽然书有点老了，而且基于 Python 2.5 ，但是 Python 整体的大框架并没有改变很多，还是非常值得一看。