Adding an internal C-API for dynamic arrays

[ZeroIntensity]

Feature or enhancement

Proposal:

Per the leak introduced in #124776, it would be nice if we had an internal structure for dynamically allocated arrays, similar to how we have _Py_hashtable_t.

cc @Eclips4 for bikeshedding the name and API (_Py_dynarray_t right now)

Has this already been discussed elsewhere?

No response given

Links to previous discussion of this feature:

Discussed on discord

Linked PRs

• gh-125543: Add an internal C API for dynamic arrays #125554

[Eclips4]

Note for others: the general idea is to have a structure like a Python list that does not affect the reference counter state._Py_hashtable_t is an example of an analogue of Python dict that does not affect reference counter.

[colesbury]

How would this API address the leak in #124776?

[ZeroIntensity]

From my understanding, (part of) the leak in that PR was caused by incorrectly setting up a dynamic array--that could have been prevented with a proper internal API for it.

[vstinner]

I'm not convinced that we need such API. Do you have more examples of code which would benefit of such API?

[ZeroIntensity]

There are a number of array-like structures throughout the interpreter, namely on the interpreter and thread state off the top of my head. It would be nice if we didn't have to reinvent the wheel every time we wanted to do that :)

The idea here is to get a nice unified interface in place, and then migrate some (but not all!) of the internal dynamic arrays to _PyDynArray, which should make maintaining easier.

[vstinner]

There are a number of array-like structures throughout the interpreter, namely on the interpreter and thread state off the top of my head.

Do you have concrete examples? Can you point me to the code?

[ZeroIntensity]

Some that I found: _PyErr_StackItem, _PyStackChunk, PyInterpreterState.pythreads, PyInterpreterState.executor_list_head, PyInterpreterState.mem_free_queue.head, _PyRuntime.pyinterpreters. Granted, most of these are linked lists rather than C arrays, but I'm guessing that's just because they're much easier to implement.

My issue with this approach of creating a new linked list every time we need a new array internally is that a). linked lists have lower performance when used in this way (e.g. indexing is O(n) rather than O(1), and you generally have to make an allocation for every addition) and b). without a unified interface, we have to deal with fixing things on a case-by-case basis (for example, most of the structures that I linked had to each get their own mutex field for free threading--wouldn't it have been better to just do that once?)

[colesbury]

This is still not the level of explanation and concrete motivating examples that I'd like to see before adding a new abstraction. It's not clear to me that any of these fields are better suited to a generic dynamic array API than their currently implementations. _PyStackChunk and PyInterpreterState.mem_free_queue.head in particular are linked lists of fixed-size chunks.

linked lists have lower performance when used in this way (e.g. indexing is O(n) rather than O(1), and you generally have to make an allocation for every addition)

Most of these examples do not require indexing arbitrary elements. They also do not require an allocation for every addition. The linked list pointers are embedded in the structures.

I don't think a generic _Py_dynarray_t is a good fit even for the fields where we may want to use an array in the future, like PyInterpreterState.pythreads and possibly _PyRuntime.pyinterpreters. A major motivation would be to avoid require locking while iterating over them, but that requires special handling of allocation and resizing, which isn't a good fit for a generic dynamic array API. Additionally, we probably don't want terminating a thread to require an O(N) _PyDynArray_Remove call.

[ZeroIntensity]

Yeah, the ones that I found certainly shouldn't all be dynamic arrays--I was just making a point that we have a lot of array-like structures internally :)

Agreeing with most of what you said--I don't really want to target this toward the interpreter core (though, I'm sure there are cases somewhere). The main beneficiaries here would be stdlib extensions. For example, asyncio has a linked list for futures, which causes complicated changes like this to exist for improvements.