Optimize set and frozenset membership lookup (x in s) performance

[rajat315315]

Feature or enhancement

Proposal:

Category

Performance

Description

Currently, set membership testing (x in s) via _PySet_Contains suffers from two performance bottlenecks:

1. Indirect Function Pointer Calls in Probing Loop:
   The table probing function set_do_lookup in Objects/setobject.c receives the comparison function (compare_entry) as a function pointer argument:

   static int
   set_do_lookup(PySetObject *so, setentry *table, size_t mask, PyObject *key,
                 Py_hash_t hash, setentry **epp, compare_func compare_entry)

2. The second optimization targets string comparison overhead during membership lookups on frozenset. By adding a fast-path check using PyUnicode_CheckExact and unicode_eq in set_compare_frozenset before falling back to PyObject_RichCompareBool, we bypass the general comparison overhead for the common case of string lookups:

    if (ep_hash == hash) {
        if (PyUnicode_CheckExact(startkey)
            && PyUnicode_CheckExact(key)
            && unicode_eq(startkey, key)) {
            return SET_LOOKKEY_FOUND;
        }
        int cmp = PyObject_RichCompareBool(startkey, key, Py_EQ);

Linked PRs

• gh-153198 Optimize set and frozenset membership lookup #153199

[methane]

from two performance bottlenecks:

I can see only one...

[rajat315315]

I'm sorry, I missed it.
Updated the Description.