René's URL Explorer Experiment

Title: gh-123471: Make itertools.product and itertools.combinations thread-safe by eendebakpt · Pull Request #132814 · python/cpython · GitHub

Open Graph Title: gh-123471: Make itertools.product and itertools.combinations thread-safe by eendebakpt · Pull Request #132814 · python/cpython

X Title: gh-123471: Make itertools.product and itertools.combinations thread-safe by eendebakpt · Pull Request #132814 · python/cpython

Description: We make concurrent iteration over itertools.combinations and itertools.product thread safe in the free-threading build. The original combinations_next is renamed to combinations_next_with_lock_held and combinations_next is now calling combinations_next_with_lock_held with a lock (similar for itertools.product) We use a lock because it is easy to implement and avoids quite a bit of complexity (we have two pieces of mutable state to deal with: op->indices and op->result). Issues that can occur without the locks: On initialization of the results structure the op->result can be overwritten, resulting in memory leaks cpython/Modules/itertoolsmodule.c Line 2342 in a4ea80d PyTuple_SET_ITEM(result, i, elem); The increment of op->indices[i] at https://github.com/python/cpython/blob/main/Modules/itertoolsmodule.c#L2379 is not safe. It can go out-of-bounds since the check is done earlier. This can lead to a segfault The refcount check for re-use of the result tuple https://github.com/python/cpython/blob/main/Modules/itertoolsmodule.c#L2346 is not valid in the FT build. Not sure whether this leads to crashes, but it will result in memory leaks. Updating the indices is not atomic itertoolsmodule.c#L2380-L2381. Non-atomic updates can lead to out-of-bounds issues. The tests in this PR trigger some of these issues, although some are not visible (e.g. the memory leak), and it typically requires more iterations to result in a segfault. On my system > 2000 iterations gives a very high probability of triggering a segfault. The number of iterations is set much lower to keep the duration of the test < 0.1 second. Performance with the locks is about 5% less for a single-thread (see the corresponding issue). I refactored the tests to avoid duplicated code. Currently combinations and product are in the test, but cwr and permutations have the same style and could be added as well (in a followup PR). Could we do this without a full lock? It depends a bit on the iterator. For product we could make the rollover check safe by changing indices[i] == PyTuple_GET_SIZE(pool) into indices[i] >= PyTuple_GET_SIZE(pool) and use atomic operations in all operations dealing with op->indices or op->result. That would still leave memory leaks, but these are not crashes. And determining whether this actually safe (not crashing) requires some very careful reviews. Issue: gh-123471

Open Graph Description: We make concurrent iteration over itertools.combinations and itertools.product thread safe in the free-threading build. The original combinations_next is renamed to combinations_next_with_lock_hel...

X Description: We make concurrent iteration over itertools.combinations and itertools.product thread safe in the free-threading build. The original combinations_next is renamed to combinations_next_with_lock_hel...

Opengraph URL: https://github.com/python/cpython/pull/132814

X: @github

direct link

Domain: github.com

Links:

Viewport: width=device-width