Python扩展在操作大列表时创建无效指针

Question

我设法为python列表实现了一个Fisher–Yates shuffle函数，作为练习，我习惯于扩展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个元素的列表进行操作时：

^{pr2}$

或者

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是首选方法，但（难看的）选项是使用^{}宏，它可以避免执行递增：

void PyList_SET_ITEM(PyObject *list, Py_ssize_t i, PyObject *o)

Macro form of PyList_SetItem() without error checking. This is normally only used to fill in new lists where there is no previous content.

Note

This macro “steals” a reference to item, and, unlike PyList_SetItem(), does not discard a reference to any item that is being replaced; any reference in list at position i will be leaked.

因此，PyList_SET_ITEM既不增加也不减少任何引用计数器，这适合我们，因为元素最初和最后都在同一个列表中。在

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

请注意，这根本不做任何错误检查，因此您需要确保您的索引在边界内（这是for循环负责的）。在

---

您的代码还有一个尚未讨论的坏问题—完全缺乏错误检查。例如，当传入一个非列表对象时，应该引发一个TypeError。现在代码将在^{}失败，返回-1并设置一个内部异常，这可能导致未来所有C扩展的错误行为：

同样，如果传入的参数数目不正确，^{}can和将失败，因此您必须检查其返回值；在这种情况下，list可能未初始化，并且您的代码将具有完全未定义的行为。在

C-API文档states the following：

When a function must fail because some function it called failed, it generally doesn’t set the error indicator; the function it called already set it. It is responsible for either handling the error and clearing the exception or returning after cleaning up any resources it holds (such as object references or memory allocations); it should not continue normally if it is not prepared to handle the error. If returning due to an error, it is important to indicate to the caller that an error has been set. If the error is not handled or carefully propagated, additional calls into the Python/C API may not behave as intended and may fail in mysterious ways.

因此，以下是编写扩展函数的正确方法：

^{pr2}$