Make concurrent iteration over pairwise, combinations, permutations, cwr, product, etc. from itertools safe under free-threading

[eendebakpt]

Bug report

Bug description:

Several methods from the C implementation of the itertools module are not yet safe to use under the free-threading build. In this issue we list several issues to be addressed. The issues below are discussed for itertools.product, but the issues are similar for the other classes.

• When iterating over product the result tuple is re-used when the reference count is 1. We can use the new _PyObject_IsUniquelyReferenced method to perform the check whether we can re-use the tuple. (this issue was also reported in enum_next and pairwise_next can result in tuple elements with zero reference count in free-threading build #121464)

• On the first invocation of product a new result is constructed.

cpython/Modules/itertoolsmodule.c

Lines 2038 to 2044 in 58ce131

	if (result == NULL) {
	/* On the first pass, return an initial tuple filled with the
	first element from each pool. */
	result = PyTuple_New(npools);
	if (result == NULL)
	goto empty;
	lz->result = result;

This is not thread-safe, as multiple threads could have result == NULL evaluate to true. We could move the construction of the productobject.result to the constructor of product. This does mean that product will use more memory before the first invocation of next. This seems to be acceptable, as constructing a product without iterating over it seems rare in practice.
The tuple also needs to be filled with data. For product it seems safe to do this in the constructor, as the data is coming
from productobject->pools which is a tuple of tuples. But for pairwise the data is coming from an iterable

cpython/Modules/itertoolsmodule.c

Lines 337 to 343 in 58ce131

	if (old == NULL) {
	old = (*Py_TYPE(it)->tp_iternext)(it);
	Py_XSETREF(po->old, old);
	if (old == NULL) {
	Py_CLEAR(po->it);
	return NULL;
	}

which could be a generator. Reading data from the iterator before the first invocation of pairwise_next seems like a behavior change we do not want to make.

An alternative is to use some kind of locking inside product_next, but the locking should not add any overhead in the common path otherwise the single-thread performance will suffer.

• In case iterables are exhausted some cleaning up is done. For example in pairwise_next at

cpython/Modules/itertoolsmodule.c

Lines 352 to 356 in 58ce131

	if (new == NULL) {
	Py_CLEAR(po->it);
	Py_CLEAR(po->old);
	Py_DECREF(old);
	return NULL;

This cleaning up is not safe in concurrent iteration. Instead we can defer the cleaning up untill the object itself is decallocated (this approach was used for reversed, see https://github.com/python/cpython/pull/120971/files#r1653313765)

• Actually constructing the new result requires some care as well. Even if we are fine with having funny results under concurrent iteration (see the discussion Sequence iterator thread-safety #120496), the concurrent iteration should not corrupt the interpreter. For example this code is not safe:

cpython/Modules/itertoolsmodule.c

Lines 2077 to 2088 in 58ce131

	indices[i]++;
	if (indices[i] == PyTuple_GET_SIZE(pool)) {
	/* Roll-over and advance to next pool */
	indices[i] = 0;
	elem = PyTuple_GET_ITEM(pool, 0);
	Py_INCREF(elem);
	oldelem = PyTuple_GET_ITEM(result, i);
	PyTuple_SET_ITEM(result, i, elem);
	Py_DECREF(oldelem);
	} else {
	/* No rollover. Just increment and stop here. */
	elem = PyTuple_GET_ITEM(pool, indices[i]);

If two threads both increment indices[i] the check on line 2078 is never true end we end up indexing pool with PyTuple_GET_ITEM outside the bounds on line 2088. Here we could change the check into indices[i] >= PyTuple_GET_SIZE(pool). That is equivalent for the single-threaded case, but does not lead to out-of-bounds indexing in the multi-threaded case (although it does lead to funny results!)

@rhettinger @colesbury Any input on the points above would be welcome.

CPython versions tested on:

CPython main branch

Operating systems tested on:

No response

Linked PRs

• gh-123471: Make concurrent iteration over itertools.pairwise safe under free-threading  #123848
• Draft: gh-123471: Make concurrent iteration over itertools.pairwise safe under free-threading #125417
• gh-123471: make itertools.batched thread-safe #129416
• gh-123471: Make concurrent iteration over itertools.cycle safe under free-threading #131212
• gh-123471: Make concurrent iteration over itertools.repeat safe under free-threading #131247
• gh-123471: Make itertools.product and itertools.combinations thread-safe #132814
• gh-123471: Make itertools.chain thread-safe #135689
• gh-123471: Make concurrent iteration over itertools.permutations and itertools.combinations_with_replacement thread-safe #144402
• gh-123471: Make concurrent iteration over itertools.accumulate thread-safe #144486
• gh-123471: Make concurrent iteration over itertools.pairwise thread-safe #144489
• gh-123471: Make concurrent iteration over itertools.islice thread-safe #144528
• gh-123471: Make itertools.dropwhile and itertools.takewhile safe in the FT build #146021
• gh-123471: Make itertools.zip_longest safe in the FT build #146033

[rhettinger]

Can we talk about this at the sprint? I would like to have a sound overall strategy for how all of these should be approached (what guarantees can be made, what is most useful, decide whether to add locks, redesign from scratch or just provide an alternative code path, what is the least destabilizing changes that can be made, how close can be make this to generator equivalents, how to defend against reentrancy, how to not damage the stable existing implementation for non-freethreading builds, etc).

Also, I would like to start by evaluating itertools.tee() which currently throws a 'RuntimeError` even on the non-freethreading build. The may be a useful behavior there that involves adding locks.

Thinking just about pairwise(), I not even sure what the desirable behavior would be (other than not crashing). Is there any legit use case for two threads to race non-deterministically for a feed of successive pairs. ISTM like this would almost always be the wrong thing to do. Perhaps raising a 'RuntimeError` like tee does would be the most useful thing to do.

I definitely think we should not be creating PRs on this issue until we've made a conscious decision about the right overall approach.

[eendebakpt]

@rhettinger Great idea. When making the PRs I already noticed it is hard to make trade-offs between the different implementation options. I was considering writing a message on DPO to get some more people involved, but having it discussed at the sprint first is also good. I won't be there, but would be interested in the outcome!

[eendebakpt]

Notes from the sprint are here: #124397 Strategy for Iterators in Free Threading

[serhiy-storchaka]

There is a simple Python implementation in the documentation. I believe it has sane behavior in multi-threading (not crash, not leak, not hangs). The C implementation should be equivalent. The current C implementation has some shortcuts for performance, they are optional and can be removed in the free-threading build.

For example, you can remove the result tuple caching in the free-threading build. It should not affect the behavior in most cases, it is simply an optimization. I believe that it is possible to use the same code for both builds if define macros for few elementary operations instead of wrapping larger parts of code in #ifdef/#endif.

But all tests that do not depend on race conditions should pass in both builds.

[eendebakpt]

@serhiy @rhettinger For itertools.pairwise I created a new draft PR. Comments on the PR would be appreciated. In particular:

• In the PR several ideas to address access to the cleared po->it are mentioned. I picked the option with the easiest implementation.
• For re-entrant usage of pairwise some special code was added to address bugs with borrowed references. In the free-threaded build in the PR we use normal references. I believe we can then remove the special code, although this will change the exact behavior. I left the special path in for now, but can remove it if you believe this simplifies the code.
• We can optimize (also for the GIL build)

    if (_PyObject_IsUniquelyReferenced(result)) {
        Py_INCREF(result);
        PyObject *last_old = PyTuple_GET_ITEM(result, 0);
        PyObject *last_new = PyTuple_GET_ITEM(result, 1);
        PyTuple_SET_ITEM(result, 0, Py_NewRef(old));
        PyTuple_SET_ITEM(result, 1, Py_NewRef(new));
        Py_DECREF(last_old);
        Py_DECREF(last_new);
        // bpo-42536: The GC may have untracked this result tuple. Since we're
        // recycling it, make sure it's tracked again:
        if (!_PyObject_GC_IS_TRACKED(result)) {
            _PyObject_GC_TRACK(result);
        }
    }
    else {
        result = PyTuple_New(2);
        if (result != NULL) {
            PyTuple_SET_ITEM(result, 0, Py_NewRef(old));
            PyTuple_SET_ITEM(result, 1, Py_NewRef(new));
        }
    }

    Py_XSETREF(po->old, new);
    Py_DECREF(old); // instead of the decref here we could borrow the reference above
    Py_DECREF(it);

into

    if (_PyObject_IsUniquelyReferenced(result)) {
        Py_INCREF(result);
        PyObject *last_old = PyTuple_GET_ITEM(result, 0);
        PyObject *last_new = PyTuple_GET_ITEM(result, 1);
        PyTuple_SET_ITEM(result, 0, old);
        PyTuple_SET_ITEM(result, 1, Py_NewRef(new));
        Py_DECREF(last_old);
        Py_DECREF(last_new);
        // bpo-42536: The GC may have untracked this result tuple. Since we're
        // recycling it, make sure it's tracked again:
        if (!_PyObject_GC_IS_TRACKED(result)) {
            _PyObject_GC_TRACK(result);
        }
    }
    else {
        result = PyTuple_New(2);
        if (result != NULL) {
            PyTuple_SET_ITEM(result, 0, old);
            PyTuple_SET_ITEM(result, 1, Py_NewRef(new));
        } else {
			Py_DECREF(old);
		}
    }

    Py_XSETREF(po->old, new);
    Py_DECREF(it);

This saves an incref/decref in the common case. Is this worthwhile to add?