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

[ngoldbaum]

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

[ngoldbaum]

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.

[ngoldbaum]

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.

[picnixz]

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

[ngoldbaum]

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.

[picnixz]

This ends up being slower on the GIL-enabled

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

[ngoldbaum]

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.

[vstinner]

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?

[ngoldbaum]

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.