copy.copy and copy.deepcopy scale poorly with free-threading

[eendebakpt]

The copy.copy and copy.deepcopy operations running on different objects in different threads should be able to run independently. The scaling is not good: output of the ftscalingbench.py with added benchmarks:

Running benchmarks with 8 threads
shallow_copy 4.6x slower
deepcopy 2.3x slower
object_cfunction 5.9x faster
cmodule_function 5.9x faster
object_lookup_special 5.5x faster
mult_constant 5.6x faster
generator 4.9x faster
pymethod 5.2x faster
pyfunction 4.5x faster
module_function 5.0x faster
load_string_const 5.6x faster
load_tuple_const 5.9x faster
create_pyobject 2.3x faster
create_closure 7.1x faster
create_dict 3.3x faster
thread_local_read 3.3x faster

There are at least two reasons:

• The copy module uses module level variables in the copy.copy and copy.deepcopy methods.
• The _copy_atomic_types (and some similar data structures) is a set which requires locking for membership testing.

Linked PRs

• gh-132657: Add free-threading scaling benchmark for copy.copy and copy.deepcopy #132658
• gh-132657: Avoid locking in frozenset.__contains__ #132659
• gh-132657: Avoid locks and refcounts in frozenset operations #136107
• GH-132657: Add lock-free set contains implementation #132290
• gh-132657: Make deepcopy and copy scale with free-threading #138429
• gh-132657: optimize PySet_Contains for frozensets #141183
• [3.14] gh-132657: avoid locks and refcounting in frozenset lookups (GH-136107) #141772
• [3.14] gh-132657: optimize PySet_Contains for frozenset (GH-141183) #141773
• gh-132657: revert lock-free set contains #142733
• gh-132657: Use stronger memory ordering for so->mask. #142735
• gh-132657: Add maybe_enable_deferred_ref_count(). #142843
• gh-132657: Improve performance in specialize_dict_access_hint() via adding specialization for PY_GIL_DISABLED #144886

[eendebakpt]

I have no good approach yet to improve performance of the module level variables. This diff

diff --git a/Lib/copy.py b/Lib/copy.py
index c64fc076179..084b2873b65 100644
--- a/Lib/copy.py
+++ b/Lib/copy.py
@@ -67,7 +67,8 @@ def copy(x):

 cls = type(x)

- if cls in _copy_atomic_types:
+ _local_atomic_types = {int, float, bool, complex, bytes, str, type, range, property}
+ if cls in _local_atomic_types or cls in _atomic_types:
 return x
 if cls in _copy_builtin_containers:
 return cls.copy(x)

improves the scaling of copy.deepcopy a lot, but the solution is not very elegant and does not work for all test cases.

[colesbury]

The copy module uses module level variables in the copy.copy and copy.deepcopy methods

We've discussed making module level variables use deferred reference counting, which would address this problem, but haven't decided exactly how we want to implement it. (All global variables? Only some frequently accessed ones?)

[eendebakpt]

Ok, I will leave this open until the deferred reference counting is in place. I tried making the relevant variables (e.g. copy._copy_atomic_types immortal, but that did not seem to improve performance).

[eendebakpt]

There is a bit more going on than just refcount contention. The code

s = frozenset({1, 2, 3})
z in s

scales poorly in the FT build.

• The reason is that the z in s is specialized to _CONTAINS_OP_SET which calls _PySet_Contains (here) which has a lock

cpython/Objects/setobject.c

Lines 2235 to 2242 in 0d76dcc

	_PySet_Contains(PySetObject *so, PyObject *key)
	{
	int rv;
	Py_BEGIN_CRITICAL_SECTION(so);
	rv = set_contains_lock_held(so, key);
	Py_END_CRITICAL_SECTION();
	return rv;
	}

• A second reason is there might be refcount contention in set_lookkey

cpython/Objects/setobject.c

Lines 103 to 110 in 0d76dcc

	table = so->table;
	Py_INCREF(startkey);
	cmp = PyObject_RichCompareBool(startkey, key, Py_EQ);
	Py_DECREF(startkey);
	if (cmp < 0)
	return NULL;
	if (table != so->table || entry->key != startkey)
	return set_lookkey(so, key, hash);

The increment is there because startkey is a borrowed reference and the rich compare might remove startkey from the set. For a frozenset this cannot happen, so we can skip the incref/decref. For a frozenset we can also skip the guard if (table != so->table || entry->key != startkey).

To address the issues we can either

• Make dedicated methods for frozenset (this requires some duplication of code and a new _CONTAINS_OP_FROZENSET bytecode)
• Add a quick check using PyFrozenSet_CheckExact at the appropriate places and act accordingly.

@colesbury @markshannon Any opinion on which way to go?

[colesbury]

I think adding a code path for PyFrozenSet_CheckExact that avoids the locking and incref/decref makes sense.