PyList_SetItem is ~2.7x slower per item on the free-threaded build

Bug report

Extensions built for the stable ABI can't use PyList_SET_ITEM, so they fill new lists with PyList_SetItem. On the free-threaded build each call costs about 2.7x what it does on the GIL-enabled build, while PyTuple_SetItem costs about the same on both builds. Converting native sequences (pointer arrays, vectors) to lists is a hot path for bindings, so this becomes a visible slowdown when a project switches from abi3 to abi3t wheels. For example, in tokenizers a getter that returns three lists runs about 2x slower (see huggingface/tokenizers#2488 (comment)).

Reproducer

fill.c:

#include <Python.h>

static PyObject *fill_list(PyObject *m, PyObject *arg) {
    Py_ssize_t n = PyLong_AsSsize_t(arg);
    PyObject *list = PyList_New(n);
    for (Py_ssize_t i = 0; i < n; i++)
        PyList_SetItem(list, i, Py_NewRef(Py_None));
    return list;
}

static PyObject *fill_tuple(PyObject *m, PyObject *arg) {
    Py_ssize_t n = PyLong_AsSsize_t(arg);
    PyObject *tuple = PyTuple_New(n);
    for (Py_ssize_t i = 0; i < n; i++)
        PyTuple_SetItem(tuple, i, Py_NewRef(Py_None));
    return tuple;
}

static PyMethodDef methods[] = {
    {"fill_list", fill_list, METH_O, NULL},
    {"fill_tuple", fill_tuple, METH_O, NULL},
    {NULL},
};
PyABIInfo_VAR(abi_info);
static PySlot slots[] = {
    PySlot_DATA(Py_mod_abi, &abi_info),
    PySlot_DATA(Py_mod_name, "fill"),
    PySlot_STATIC_DATA(Py_mod_methods, methods),
    PySlot_DATA(Py_mod_gil, Py_MOD_GIL_NOT_USED),
    PySlot_END,
};
PyMODEXPORT_FUNC PyModExport_fill(void) { return slots; }

bench.py:

import sys, timeit, fill

n = 1000
print(sys.version.split()[0], "free-threaded" if not sys._is_gil_enabled() else "GIL", fill.__file__.rsplit("/", 1)[-1])
for name in ("fill_list", "fill_tuple"):
    f = getattr(fill, name)
    t = min(timeit.repeat(lambda: f(n), number=2000, repeat=9)) / 2000
    print(f"  {name}: {t / n * 1e9:.1f} ns/item")

Build one copy for abi3 and one for abi3t, then run them:

mkdir abi3 abi3t
gcc -O2 -shared -fPIC -DPy_LIMITED_API=0x030f0000 -I"$(python3.15 -c 'import sysconfig; print(sysconfig.get_path("include"))')" fill.c -o abi3/fill.abi3.so
gcc -O2 -shared -fPIC -DPy_TARGET_ABI3T=0x030f0000 -I"$(python3.15t -c 'import sysconfig; print(sysconfig.get_path("include"))')" fill.c -o abi3t/fill.abi3t.so
PYTHONPATH=abi3 python3.15 bench.py
PYTHONPATH=abi3t python3.15 bench.py
PYTHONPATH=abi3t python3.15t bench.py

Results

3.15.0rc2, x86-64 Linux, gcc -O2:

3.15.0rc2 GIL fill.abi3.so
  fill_list: 7.2 ns/item
  fill_tuple: 7.6 ns/item
3.15.0rc2 GIL fill.abi3t.so
  fill_list: 6.6 ns/item
  fill_tuple: 7.5 ns/item
3.15.0rc2 free-threaded fill.abi3t.so
  fill_list: 19.8 ns/item
  fill_tuple: 9.6 ns/item

CPython versions tested on:

3.15

Operating systems tested on:

Linux

Linked PRs

I think we might be able to add a fast path to PyList_SetItem that checks _PyObject_IsUniquelyReferenced to see if the list is shared and if not, doesn't acquire the critical section. Of course that adds a small overhead for shared lists, but I would think unshared lists are a lot more common.

@kumaraditya303

Per @kumaraditya303 in a chat message with me:

Avoiding locks by checking for unique reference is a bad idea in general, in many cases there is a single ref to object but it gets mutated by many threads concurrently because of borrowed refs.

So that won't work.

@vstinner

My 2 cents:

I think it's the downside of the Stable ABI: stability at the cost of performance and I'm afraid we can't really do anything here. I think that's the tradeoff users need to accpet when using the stable ABI (at least according to the docs, AFAIU).

So what leaves us is:

improve the interpreter overall so that this specific case isn't slower (I don't know if it's possible)
silly idea that I haven't checkde at all: create a tuple and then call PySequence_List. Depending on the size of your desired list, you might be faster (I haven't checked). But it can also be dramatically slower.

I would however say that PyList_FromArray may be a good (new) candidate (there is already PyTuple_FromArray but it's not in the Stable ABI either).

An alternative is to add functions that are less safe in the stable ABI but I'm not sure the C API wg wants that. Having PyList_SET_ITEM in the stable ABI (but not as a macro) would solve your issue I guess but that means we lose the safety the ABI was promising =/

cc @vstinner @encukou

An alternative is to add functions that are less safe in the stable ABI but I'm not sure the C API wg wants that. Having PyList_SET_ITEM in the stable ABI (but not as a macro) would solve your issue I guess but that means we lose the safety the ABI was promising =/

I don't think we should do that.

silly idea that I haven't checkde at all: create a tuple and then call PySequence_List. Depending on the size of your desired list, you might be faster (I haven't checked). But it can also be dramatically slower.

This ends up being slower on the GIL-enabled build but faster under free-threading. It's a little unsatisfying because each extension needs #ifdef Py_GIL_DISABLED to individually work around this but it'll certainly help tokenizers in practice.

This ends up being slower on the GIL-enabled

Yeah that's expected. How faster are we talking about here?

improve the interpreter overall so that this specific case isn't slower (I don't know if it's possible)

There is one way: PyO3's bindings could acquire a critical section on the unshared list and then CPython could add a second early check for recursive critical section acquisition that currently lives here:

cpython/Python/critical_section.c

Lines 24 to 45 in 81c50e9

    
           // As an optimisation for locking the same object recursively, skip 
        
           // locking if the mutex is currently locked by the top-most critical 
        
           // section. 
        
           // If the top-most critical section is a two-mutex critical section, 
        
           // then locking is skipped if either mutex is m. 
        
           if (tstate->critical_section) { 
        
               PyCriticalSection *prev = untag_critical_section(tstate->critical_section); 
        
               if (prev->_cs_mutex == m) { 
        
                   c->_cs_mutex = NULL; 
        
                   c->_cs_prev = 0; 
        
                   return; 
        
               } 
        
               if (tstate->critical_section & _Py_CRITICAL_SECTION_TWO_MUTEXES) { 
        
                   PyCriticalSection2 *prev2 = (PyCriticalSection2 *) 
        
                       untag_critical_section(tstate->critical_section); 
        
                   if (prev2->_cs_mutex2 == m) { 
        
                       c->_cs_mutex = NULL; 
        
                       c->_cs_prev = 0; 
        
                       return; 
        
                   } 
        
               } 
        
           }

See https://github.com/python/cpython/compare/main...ngoldbaum:cpython:recursive-cs-extra-check?expand=1.

This amortizes the critical section acquisition cost over the whole list.

This unfortunately makes every other critical section acquisition that doesn't hit the existing check a little slower. Probably not worth it?

I checked and if PyO3's safe bindings acquire the critical section around the unshared list it actually already helps a bit, it's just not as fast as it possibly could be if we move the recursive critical section check. See PyO3/pyo3#6478.

Yeah that's expected. How faster are we talking about here?

~40% slower on the GIL-enabled build but ~30% faster on the free-threaded build. Both compared with initializing a list directly using PyList_SetItem. So it doesn't buy you all the performance back but it does make the comparison a little better. Building a unshared list is only ~50% slower rather than 170% slower.

@ngoldbaum

I would however say that PyList_FromArray may be a good (new) candidate (there is already PyTuple_FromArray but it's not in the Stable ABI either).

Adding functions which would process multiple items per call sounds like an efficient approach and it would be a good API.

@ngoldbaum: What API would you need? Create a list from an array of objects? Set multiple list items from an array?

What API would you need? Create a list from an array of objects? Set multiple list items from an array?

In this case, the former. Something like the PyBytes_Writer API but for lists would help here.

I checked and if PyO3's safe bindings acquire the critical section around the unshared list it actually already helps a bit, it's just not as fast as it possibly could be if we move the recursive critical section check

Nope never mind, this is actually slower on a Mac aarch64 build. I've only measured it to be faster on x86_64 Linux.

@picnixz

I got a little nerdsniped this weekend and spent a decent chunk of time thinking about this.

I ended up landing on a workaround I'm happy enough with that I opened PyO3/pyo3#6532.

The solution I ended up with is to define an iterator type in PyO3 that defines tp_iternext. When CPython builds a list from the iterator, it takes a single outer critical section on the list, bypassing the overhead of repeatedly entering a critical section on the list for each list item. It relies on smuggling a pointer into tp_iternext via a thread local without incurring interpreter overhead to get it from the type data for the iterator type. It's possible to use type data but it ends up being slower.

It doesn't help for small lists but it helps a lot for large lists, so I also had to introduce a threshold list size to start using this optimization.

I also experimented with @picnixz's "built a tuple then convert via PySequence_List" idea. That performs decently on x86_64 for objects that already exist and for moderately sized lists, but it performs poorly or is a wash otherwise. Because atomics are cheaper on aarch64, it always ends up being a wash or even marginally slower on ARM.

Taking an outer critical section also performs decently on x86_64 and is a wash or an outright loser on aarch64.

This is all summarized in this plot:

All four panels show the time relative to the "default" abi3t path using PyList_SetItem. So larger than 1 is slower and smaller than one is faster. I also show measurements for each of these ideas. The blue line shows the iterator approach described above, with measurements below the 32 item cutoff I chose for PyO3 plotted as a dashed line.

The PyList_SET_ITEM measurements are from a version-specific extension and shows the theoretical maximum performance in the current C API.

Each panel is a different OS/CPU combo, using the two I can easily test in my home setup.

I also looked at performance of this idea for abi3 extensions, see this plot:

Here all times are relative to the PyList_SetItem path under abi3. Interestingly, the iterator approach beats PyList_SetItem for very large lists on Linux! I'm not sure why.

If you're curious what the C extension looks like, I packaged everything up in a git repository. Take a look at the minimal example which does the whole thing in ~130 lines of C. This is heavily AI-assisted code for what it's worth.

Also while the iterator idea is neat and IMO is worth it for extension generators like PyO3, I still think a proper builder API for lists is needed. That would allow much better performance.

Python 3.15 adds https://docs.python.org/dev/c-api/tuple.html#c.PyTuple_FromArray which creates a tuple object from a C array of objects. Do you need a function similar to that?

Or do you need an API to modify a list, something like PyList_ExtendFromArray()?

PyList_FromArray helps when there is a native array already built but doesn't help with an iterator or other data stream that should be converted into a list. That's why I think a builder API like PyBytesWriter is the most useful thing.

PyList_FromArray helps when there is a native array already built but doesn't help with an iterator or other data stream that should be converted into a list. That's why I think a builder API like PyBytesWriter is the most useful thing.

Either that or a batched function such as:

int PyList_SetItems(PyObject* list, Py_ssize_t start, PyObject** items, Py_ssize_t nitems)

A batched function allows using a stack-allocated array for items (of whatever size the caller finds comfortable), eliminating any intermediate allocation.

Note that a builder API would also benefit from allowing batched append calls.

pythongh-158660: Add PyListWriter C API

pythongh-158660: Add `PyListWriter` C API

Maybe we can reconsider dictonary for this kind of pattern?
For frozendict: https://peps.python.org/pep-0839/

I created #160127 to add a new PyListWriter C API. It's similar to the PyList C API, but it avoids locking the list to append items.

pythongh-158660: Add `PyFrozenSetWriter` C API

If a new API is added (such as proposed PyListWriter), IMO it should be added to the limuted C API, since such API would be added to fix the abi3t performance issue.

An alternative to #160127 PyListWriter API with PyListWriter_Append() / PyListWriter_Extend() functions would be to design a PyListWriter API exposing a raw PyObject **array, similar to PyBytesWriter_Create() and PyLongWriter_Create() do. But I'm less excited by a "raw" array of PyObject* since such API would be more error prone. The caller would be responsible to set all items, handle reference counting, and check the array bounds.

Navigation Menu

Repository navigation

`PyList_SetItem` is ~2.7x slower per item on the free-threaded build #158660

Bug report

Reproducer

Results

CPython versions tested on:

Operating systems tested on:

Linked PRs

Metadata

Assignees

Labels

Projects

Milestone

Relationships

Development

	// As an optimisation for locking the same object recursively, skip
	// locking if the mutex is currently locked by the top-most critical
	// section.
	// If the top-most critical section is a two-mutex critical section,
	// then locking is skipped if either mutex is m.
	if (tstate->critical_section) {
	PyCriticalSection *prev = untag_critical_section(tstate->critical_section);
	if (prev->_cs_mutex == m) {
	c->_cs_mutex = NULL;
	c->_cs_prev = 0;
	return;
	}
	if (tstate->critical_section & _Py_CRITICAL_SECTION_TWO_MUTEXES) {
	PyCriticalSection2 prev2 = (PyCriticalSection2 )
	untag_critical_section(tstate->critical_section);
	if (prev2->_cs_mutex2 == m) {
	c->_cs_mutex = NULL;
	c->_cs_prev = 0;
	return;
	}
	}
	}

PyList_SetItem is ~2.7x slower per item on the free-threaded build #158660

Description

Bug report

Reproducer

Results

CPython versions tested on:

Operating systems tested on:

Linked PRs

Activity

ngoldbaum commented on Oct 3, 2026

ngoldbaum commented on Oct 3, 2026

picnixz commented on Oct 3, 2026

ngoldbaum commented on Oct 3, 2026

picnixz commented on Oct 3, 2026

ngoldbaum commented on Oct 3, 2026

vstinner commented on Oct 3, 2026

ngoldbaum commented on Oct 4, 2026

ngoldbaum commented on Oct 16, 2026

ngoldbaum commented on Oct 17, 2026

ngoldbaum commented on Oct 17, 2026

vstinner commented on Oct 20, 2026

ngoldbaum commented on Oct 20, 2026

pitrou commented on Oct 21, 2026

corona10 commented on Oct 21, 2026

vstinner commented on Oct 21, 2026

vstinner commented on Oct 22, 2026

vstinner commented on Oct 22, 2026

Metadata

Metadata

Assignees

Labels

Projects

Milestone

Relationships

Development

Issue actions

`PyList_SetItem` is ~2.7x slower per item on the free-threaded build #158660