Python 扩展在处理大型列表时创建无效指针

Question

我设法为 python 列表实现了一个 Fisher–Yates 随机播放函数，作为习惯扩展 python 的练习。它非常适合相对较小的列表，除非我多次运行该函数。

每当列表大小超过 100 时，我就会遇到各种内存问题:

>>>import evosutil
>>> a=[i for i in range(100)]
>>> evosutil.shuffle(a)
>>> a
[52, 66, 0, 58, 41, 18, 50, 37, 81, 43, 74, 49, 90, 20, 63, 32, 89, 60, 2, 44, 3, 80, 15, 24, 22, 69, 86, 31, 56, 68, 34, 13, 38, 26, 14, 91, 73, 79, 39, 65, 5, 75, 84, 55, 7, 53, 93, 42, 40, 9, 51, 82, 29, 30, 99, 64, 33, 97, 27, 11, 6, 67, 16, 94, 95, 62, 57, 17, 78, 77, 71, 98, 72, 8, 88, 36, 85, 59, 21, 96, 23, 46, 10, 12, 48, 83, 4, 92, 45, 54, 1, 25, 19, 70, 35, 61, 47, 28, 87, 76]
>>> (Ctrl-D)
*** Error in `python3': free(): invalid next size (fast): 0x083fe680 ***

或者，当尝试对包含 1000 个元素的列表进行操作时:

*** Error in `python3': munmap_chunk(): invalid pointer: 0x083ff0e0 ***

或者，

Segmentation fault (core dumped)

这是产生错误的模块的代码:

inline void _List_SwapItems(PyObject* list, Py_ssize_t i1, Py_ssize_t i2){
    PyObject* tmp=PyList_GetItem(list, i2);
    PyList_SetItem(list, i2, PyList_GetItem(list, i1));
    PyList_SetItem(list, i1, tmp);
}

//Naive Fisher–Yates shuffle
static PyObject* shuffle(PyObject* self, PyObject* args){
    PyObject* list;
    PyArg_ParseTuple(args,"O", &list);
    unsigned seed = std::chrono::system_clock::now().time_since_epoch().count();
    std::minstd_rand0 rand(seed);
    Py_ssize_t size = PyList_Size(list);
    for(int i=0; i<size;++i){
        int randIndex = rand()%size;
        _List_SwapItems(list, randIndex, i);
    }
    Py_RETURN_NONE;
}

我觉得我应该能够在某处使用 free() 或 Py_DECREF() 来解决这个问题，但我不知道在哪里。我不认为我正在创建任何对象，只是移动它们。那么内存问题是从哪里来的呢？

Answer 1

在将它们传递给 PyList_SetItem() 之前，您需要 Py_XINCREF() 这两个对象。此外，捕获 i1 == i2 的特殊情况:

inline void _List_SwapItems(PyObject* list, Py_ssize_t i1, Py_ssize_t i2){
    if (i1 == i2) {
        return;
    }
    PyObject* obj1=PyList_GetItem(list, i1);
    PyObject* obj2=PyList_GetItem(list, i2);
    Py_XINCREF(obj1);
    Py_XINCREF(obj2);
    PyList_SetItem(list, i2, obj1);
    PyList_SetItem(list, i1, obj2);
}

PyList_GetItem() 返回一个借用的引用，即它不 INCREF 它返回的对象。如果您没有任何其他引用，则引用计数将为 1(因为它仅从列表中引用)。当您调用 PyList_SetItem(list, i2, ...) 时，列表 Py_XDECREF() 是先前存储在 i2 的对象(你保留在 tmp 中)。此时，引用计数达到 0 并且对象被释放。糟糕。

同样，您不能只调用 PyList_SetItem(list, i, PyList_GetItem())，因为 SetItem 窃取了您传递给它的引用。您不拥有引用，但是，“旧”列表拥有。所以你在这里也需要一个 Py_XINCREF。

参见 list API documentation了解更多详情。

作为进一步的建议，您可能会考虑不直接针对 Python 扩展 API 进行编程。完成任何事情都需要大量代码，而且要保持引用计数正确也非常困难。到目前为止，还有多种其他方法可以将 Python 与 C 或 C++ 连接起来。 CFFI似乎是 Python 生态系统将标准化的低级接口(interface)。 SIP和 SWIG不过，可能会为 C++ 提供更好的支持。有关 SIP 示例，请参阅 this answer .