Use per-thread freelists in --disable-gil builds

[colesbury]

Feature or enhancement

CPython uses freelists for frequently allocated Python objects, like dict, list, and slice. There freelists are generally stored in the per-interpreter state, which is not thread-safe without the GIL. In --disable-gil builds, the freelists should be stored in the per-thread state (i.e., PyThreadState). I think we probably want to keep the freelists in the interpreter state for the default build. This will probably require some refactoring.

Freelists:

• float
• slice (slice_cache)
• tuple
• list
• dict (PyDictKeysObject and PyDictObject)
• generator (value_freelist and asend_freelist)
• PyContext

For context, here are similar changes in the nogil-3.12 fork, but I expect the changes in CPython 3.13 to be a bit different:

• colesbury/nogil-3.12@07f5f8c318
• colesbury/nogil-3.12@2a4c17e896

Linked PRs

• gh-111968: Introduce _PyFreeListState and _PyFreeListState_GET API #113584
• gh-111968: Use per-thread freelists for float in free-threading #113886
• gh-111968: Unify naming scheme for freelist #113919
• gh-111968: Use per-thread freelists for tuple in free-threading #113921
• gh-111968: Explicit handling for finalized freelist #113929
• gh-111968: Use per-thread slice_cache in free-threading #113972
• gh-111968: Use per-thread freelists for PyContext in free-threading #114122
• gh-111968: Use per-thread freelists for generator in free-threading #114189
• gh-111968: Fix --without-freelists build #114270
• gh-111968: Use per-thread freelists for dict in free-threading #114323
• gh-111968: Unify freelist naming schema to Eric's suggestion #114581
• gh-111968: Refactor _PyXXX_Fini to integrate with _PyObject_ClearFreeLists #114899
• gh-111968: Rename freelist related struct names to Eric's suggestion #115329
• gh-111968: Split _Py_dictkeys_freelist out of _Py_dict_freelist #115505
• gh-111968: Split _Py_async_gen_asend_freelist out of _Py_async_gen_fr… #115546

[Yaro1]

Hi!
I'm new here, but if you don't mind I would like to take that issue

[colesbury]

Hi @Yaro1, thanks for volunteering. You are welcome to take this on, but I don't think it's a great first issue. There are some subtleties and it also depends on #112776.

[Yaro1]

Got it, thanks.
Can I take please in that case some of the issues from #108219 ?

[colesbury]

I don't think there are any good issues right now that are scoped out and not blocked on other work.

[Yaro1]

Okay, got it. Thank you

[corona10]

@colesbury I would like to take a look at this issue, Is there any pending issues that are related to this issue?

[colesbury]

@corona10, thanks! I think the issues were fixed (problems with PyThreadState_Clear() being called by the wrong interpreter)

[corona10]

#113584 will introduce seamless management of freelists that runtimes do not need to care about the implementation detail :)

graph TD;
    PerThread --> FreeList;
    PerInterpreter --> FreeList;
    GC -- if free-threaded --> gc_freethreading;
    GC -- if default build --> gc_gil;
    gc_freethreading --> PerThread;
    gc_gil --> PerInterpreter;
    _PyFreeListState -- if free-threaded --> PerThread;
    _PyFreeListState -- if default build --> PerInterpreter;
    Runtime -- _PyFreeListState_GET --> _PyFreeListState;
    list --> Runtime;
    tuple --> Runtime;
    slice --> Runtime;
    float --> Runtime;
    dict --> Runtime;
    generator --> Runtime;
    PyContext --> Runtime;

Loading

[corona10]

Final diagram:

graph TD;
    PerThread --> FreeList;
    PerInterpreter --> FreeList;
    GC -- if free-threaded --> gc_freethreading;
    GC -- if default build --> gc_gil;
    gc_freethreading --> PerThread;
    gc_gil --> PerInterpreter;
    _Py_object_freelists -- if free-threaded --> PerThread;
    _Py_object_freelists -- if default build --> PerInterpreter;
    Runtime -- _Py_object_freelists_GET --> _Py_object_freelists;
    list --> Runtime;
    tuple --> Runtime;
    slice --> Runtime;
    float --> Runtime;
    dict --> Runtime;
    dictkey --> Runtime;
    async_gen --> Runtime;
    _PyContext --> Runtime;
   object_stack --> Runtime;

Loading

[ericsnowcurrently]

(from #111968 (comment))

As noted in review comments in gh-114323, I think the following should be adjusted:

• change the various type-specific _PyXXX_Fini() signatures back to taking a single PyInterpreterState * argument
• change the type-specific struct names, e.g. struct _Py_float_state, to something more specific, e.g. struct _Py_float_freelist
• change the struct name _Py_freelist_state to _Py_freelists or, better, _PyObject_freelists
• change PyInterpreterState.freelist_state to PyInterpreterState.freelists or, even better, to PyInterpreterState.object_state.freelists
• split struct _Py_dictkeys_freelist out of struct _Py_dict_freelist

Thanks for taking care of these, @corona10!

FWIW, there are definitely a bunch of things we could do to simplify our use of freelists and make our implementation more maintainable, but all that mostly pre-dates this issue and is certainly something to be considered separately from this issue. 😄

[corona10]

@ericsnowcurrently @colesbury
Thanks for all the feedback on this issue!