frozenset changes for 3.14 backport

frozenset_opt.patch

diff --git a/Misc/NEWS.d/next/Core_and_Builtins/2025-07-09-21-27-14.gh-issue-132657.kSA8R3.rst b/Misc/NEWS.d/next/Core_and_Builtins/2025-07-09-21-27-14.gh-issue-132657.kSA8R3.rst
new file mode 100644
index 00000000000..99f7a990875
--- /dev/null
+++ b/Misc/NEWS.d/next/Core_and_Builtins/2025-07-09-21-27-14.gh-issue-132657.kSA8R3.rst
@@ -0,0 +1 @@
+Improve performance of :class:`frozenset` by removing locks in the free-threading build.
diff --git a/Misc/NEWS.d/next/Core_and_Builtins/2025-10-22-12-48-05.gh-issue-140476.F3-d1P.rst b/Misc/NEWS.d/next/Core_and_Builtins/2025-10-22-12-48-05.gh-issue-140476.F3-d1P.rst
new file mode 100644
index 00000000000..a24033208c5
--- /dev/null
+++ b/Misc/NEWS.d/next/Core_and_Builtins/2025-10-22-12-48-05.gh-issue-140476.F3-d1P.rst
@@ -0,0 +1,2 @@
+Optimize :c:func:`PySet_Add` for :class:`frozenset` in :term:`free threaded
+<free threading>` build.
diff --git a/Objects/setobject.c b/Objects/setobject.c
index 83004e57b66..ce9a7be09f5 100644
--- a/Objects/setobject.c
+++ b/Objects/setobject.c
@@ -86,6 +86,8 @@ set_lookkey(PySetObject *so, PyObject *key, Py_hash_t hash)
     int probes;
     int cmp;
 
+    int frozenset = PyFrozenSet_CheckExact(so);
+
     while (1) {
         entry = &so->table[i];
         probes = (i + LINEAR_PROBES <= mask) ? LINEAR_PROBES: 0;
@@ -102,13 +104,20 @@ set_lookkey(PySetObject *so, PyObject *key, Py_hash_t hash)
                     && unicode_eq(startkey, key))
                     return entry;
                 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);
+                if (frozenset) {
+                    cmp = PyObject_RichCompareBool(startkey, key, Py_EQ);
+                    if (cmp < 0)
+                        return NULL;
+                } else {
+                    // incref startkey because it can be removed from the set by the compare
+                    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);
+                }
                 if (cmp > 0)
                     return entry;
                 mask = so->mask;
@@ -2234,10 +2243,16 @@ set_contains_lock_held(PySetObject *so, PyObject *key)
 int
 _PySet_Contains(PySetObject *so, PyObject *key)
 {
+    assert(so);
+
     int rv;
-    Py_BEGIN_CRITICAL_SECTION(so);
-    rv = set_contains_lock_held(so, key);
-    Py_END_CRITICAL_SECTION();
+    if (PyFrozenSet_CheckExact(so)) {
+        rv = set_contains_lock_held(so, key);
+    } else {
+        Py_BEGIN_CRITICAL_SECTION(so);
+        rv = set_contains_lock_held(so, key);
+        Py_END_CRITICAL_SECTION();
+    }
     return rv;
 }
 
@@ -2731,7 +2746,9 @@ PySet_Contains(PyObject *anyset, PyObject *key)
         PyErr_BadInternalCall();
         return -1;
     }
-
+    if (PyFrozenSet_CheckExact(anyset)) {
+        return set_contains_key((PySetObject *)anyset, key);
+    }
     int rv;
     Py_BEGIN_CRITICAL_SECTION(anyset);
     rv = set_contains_key((PySetObject *)anyset, key);
@@ -2757,17 +2774,24 @@ PySet_Discard(PyObject *set, PyObject *key)
 int
 PySet_Add(PyObject *anyset, PyObject *key)
 {
-    if (!PySet_Check(anyset) &&
-        (!PyFrozenSet_Check(anyset) || !_PyObject_IsUniquelyReferenced(anyset))) {
-        PyErr_BadInternalCall();
-        return -1;
+    if (PySet_Check(anyset)) {
+        int rv;
+        Py_BEGIN_CRITICAL_SECTION(anyset);
+        rv = set_add_key((PySetObject *)anyset, key);
+        Py_END_CRITICAL_SECTION();
+        return rv;
     }
 
-    int rv;
-    Py_BEGIN_CRITICAL_SECTION(anyset);
-    rv = set_add_key((PySetObject *)anyset, key);
-    Py_END_CRITICAL_SECTION();
-    return rv;
+    if (PyFrozenSet_Check(anyset) && _PyObject_IsUniquelyReferenced(anyset)) {
+        // We can only change frozensets if they are uniquely referenced. The
+        // API limits the usage of `PySet_Add` to "fill in the values of brand
+        // new frozensets before they are exposed to other code". In this case,
+        // this can be done without a lock.
+        return set_add_key((PySetObject *)anyset, key);
+    }
+
+    PyErr_BadInternalCall();
+    return -1;
 }
 
 int