gh-160147: Add PyFrozenSetWriter C API - #160154

Documentation build overview

📚 cpython-previews | 🛠️ Build #35430246 | 📁 Comparing f40fbc0 against main (c72b435)

  🔍 Preview build  

Updating Modules/marshal.c to use PyFrozenSetWriter is more complicated, I prefer to do it in a follow-up PR.

cc @corona10

This C API is just an abstraction on top of existing PySet functions. PyFrozenSetWriter_Create() doesn't allocate a PyFrozenSetWriter structure. In fact, it's just a PySetObject* pointer! It is the same design than the PyLongWriter API.

The edits to Modules/_abc.c, Modules/_asynciomodule.c, Modules/_hashopenssl.c, and Modules/_ssl.c all add more code than they replace. I don't see how the new API adds value.

@rhettinger:

I don't see how the new API adds value.

There multiple advantages of this new API.

The current PySet_Add() API requires that there is exactly a single reference to the frozenset, otherwise it fails with SystemError. The frozenset can leak to other C functions or even to Python before it's fully initialized. The proposed Writer API doesn't have this issue.

The internal frozenset is not tracked by the GC until Finish() is called (when the frozenset is fully initialized). So it's not possible to observe a frozenset being modified in Python (which must not be possible, frozenset are immutable, right?). See for example #159730 for recent examples of fixed bugs.

Also, I think that's a bad design to have a PySet_Add() function to modify an immutable (frozenset) object. We should avoid such API. So I propose deprecating calling PySet_Add() on a frozenset (replaced with this new Writer API). See issues:

• Avoid creating incomplete/invalid objects api-evolution#36
• Disallow mutating immutable objects api-evolution#20
• Disallow creation of incomplete/inconsistent objects problems#56

When you're done making the requested changes, leave the comment: I have made the requested changes; please review again.

Updates:

• Add size parameter to PyFrozenSetWriter_Create()
• Add PyFrozenSetWriter_AddSteal() function
• Add PyFrozenSetWriter_UpdateArray() and PyFrozenSetWriter_UpdateArraySteal() functions
• PyFrozenSetWriter_Finish() now always tracks the frozenset in the GC, instead of only tracking them if at least one item is tracked by the GC -- same behavior than PyFrozenSet_New(iterable)

UPDATE: I re-ran the benchmark on the latest PR (Finish now untracks properly the frozenset from the GC) using CPU isolation, sudo python -m pyperf system tune, and PYTHONHASHSEED=0.

I ran a benchmark on Linux (gcc -O3) to look at performance:

• frozenset_new: call PyFrozenSet_New(). Use the Python iterator protocol to consume the input.
• writer_update: call PyFrozenSetWriter_Update(). Use the Python iterator protocol to consume the input.
• writer_add: call PyFrozenSetWriter_Add() size times. Resize the frozenset table multiple times.
• writer_update_array: call PyFrozenSetWriter_UpdateArray().

writer_update calls the same code than frozenset_new, it just adds the PyFrozenSetWriter abstraction. Since the writer_update performance is basically the same as frozenset_new, it means that the abstraction is basically free in terms of performance.

The 3 writer benchmarks use PyFrozenSetWriter_Create(0): don't give a hint on the final frozenset size.

frozenset_new, writer_update and writer_update_array resizes the frozenset table at once, whereas writer_add has to resize the table multiple time (less efficient).

frozenset_new and writer_update are tested with a tuple. They call PyObject_GetIter() and then loop on PyIter_Next(). frozenset_add and writer_update_array iterates on a C array of Python objects (no Python iterator protocol).

size=0 and size=4 cases use the frozenset "small table": don't allocate a separated table on the heap.

PyFrozenSetWriter_UpdateArray() is the fastest method to create a frozenset: 1.54x faster than PyFrozenSet_New() in average.

Compare PyFrozenSetWriter_UpdateArray() to PyFrozenSetWriter_Add():

Note: It might be interesting to optimize PyFrozenSet_New() and PyFrozenSetWriter_Update() for tuple and list (not call the "slow" iterator protocol), but it can be investigated in a separated issue.

Note: I didn't test Free Threading since PySet_Add() and PyFrozenSetWriter avoid locking (critical section) anyway.

Python benchmark script bench.py:

import pyperf, functools, _testcapi

sizes = (0, 4, 100, 1_000, 100_000)
benchmarks = {
    # Call PyFrozenSet_New() once:
    # call PyObject_GetIter() and then loop on PyIter_Next()
    'PyFrozenSet_New': _testcapi.bench_frozenset_new,

    # Call PyFrozenSetWriter_Update() once:
    # call PyObject_GetIter() and then loop on PyIter_Next()
    'PyFrozenSetWriter_Update': _testcapi.bench_writer_update,

    # Call PyFrozenSetWriter_Create(0) + PyFrozenSetWriter_Add() once per item
    'PyFrozenSetWriter_Add': _testcapi.bench_writer_add,

    # Call PyFrozenSetWriter_Create(0) + PyFrozenSetWriter_UpdateArray() once
    'PyFrozenSetWriter_UpdateArray': _testcapi.bench_writer_update_array,
}

def add_cmdline_args(cmd, args):
    cmd.append(args.bench)

runner = pyperf.Runner(add_cmdline_args=add_cmdline_args)
runner.argparser.add_argument('bench', choices=sorted(benchmarks))
args = runner.parse_args()

bench = args.bench
bench = benchmarks[bench]
for size in sizes:
    test_tuple = tuple(range(size))
    func = functools.partial(bench, test_tuple)
    runner.bench_time_func(f'size={size:,}', func)

Shell script bench.sh:

set -e -x
export PYTHONHASHSEED=0
./python bench.py PyFrozenSet_New -o frozenset_new.json --inherit-environ=PYTHONHASHSEED
./python bench.py PyFrozenSetWriter_Update -o writer_update.json --inherit-environ=PYTHONHASHSEED
./python bench.py PyFrozenSetWriter_Add -o writer_add.json --inherit-environ=PYTHONHASHSEED
./python bench.py PyFrozenSetWriter_UpdateArray -o writer_update_array.json --inherit-environ=PYTHONHASHSEED
./python -m pyperf compare_to frozenset_new.json writer_update.json writer_add.json writer_update_array.json

Patch adding _testcapi functions:

diff --git a/Modules/_testcapimodule.c b/Modules/_testcapimodule.c
index 033ee3234cf..b2a881b4b4a 100644
--- a/Modules/_testcapimodule.c
+++ b/Modules/_testcapimodule.c
@@ -2889,6 +2889,139 @@ uptime_bsd(PyObject *Py_UNUSED(self), PyObject *Py_UNUSED(args))
 #endif


+static PyObject*
+bench_frozenset_new(PyObject *Py_UNUSED(self), PyObject *args)
+{
+    PyObject *iterable;
+    Py_ssize_t loops;
+    if (!PyArg_ParseTuple(args, "On", &iterable, &loops)) {
+        return NULL;
+    }
+
+    PyTime_t t1, t2;
+    (void)PyTime_PerfCounterRaw(&t1);
+    for (Py_ssize_t i=0; i < loops; i++) {
+        PyObject *result = PyFrozenSet_New(iterable);
+        if (result == NULL) {
+            return NULL;
+        }
+        Py_DECREF(result);
+    }
+    (void)PyTime_PerfCounterRaw(&t2);
+
+    return PyFloat_FromDouble(PyTime_AsSecondsDouble(t2 - t1));
+}
+
+
+static PyObject*
+bench_writer_add(PyObject *Py_UNUSED(self), PyObject *args)
+{
+    PyObject *tuple;
+    Py_ssize_t loops;
+    if (!PyArg_ParseTuple(args, "On", &tuple, &loops)) {
+        return NULL;
+    }
+
+    Py_ssize_t len = PyTuple_GET_SIZE(tuple);
+
+    PyTime_t t1, t2;
+    (void)PyTime_PerfCounterRaw(&t1);
+    for (Py_ssize_t i=0; i < loops; i++) {
+        PyFrozenSetWriter *writer = PyFrozenSetWriter_Create(0);
+        if (writer == NULL) {
+            return NULL;
+        }
+
+        for (Py_ssize_t j=0; j < len; j++) {
+            PyObject *item = PyTuple_GET_ITEM(tuple, j);
+            if (PyFrozenSetWriter_Add(writer, item) < 0) {
+                PyFrozenSetWriter_Discard(writer);
+                return NULL;
+            }
+        }
+
+        PyObject *result = PyFrozenSetWriter_Finish(writer);
+        if (result == NULL) {
+            return NULL;
+        }
+        Py_DECREF(result);
+    }
+    (void)PyTime_PerfCounterRaw(&t2);
+
+    return PyFloat_FromDouble(PyTime_AsSecondsDouble(t2 - t1));
+}
+
+
+static PyObject*
+bench_writer_update(PyObject *Py_UNUSED(self), PyObject *args)
+{
+    PyObject *iterable;
+    Py_ssize_t loops;
+    if (!PyArg_ParseTuple(args, "On", &iterable, &loops)) {
+        return NULL;
+    }
+
+    PyTime_t t1, t2;
+    (void)PyTime_PerfCounterRaw(&t1);
+    for (Py_ssize_t i=0; i < loops; i++) {
+        PyFrozenSetWriter *writer = PyFrozenSetWriter_Create(0);
+        if (writer == NULL) {
+            return NULL;
+        }
+
+        if (PyFrozenSetWriter_Update(writer, iterable) < 0) {
+            PyFrozenSetWriter_Discard(writer);
+            return NULL;
+        }
+
+        PyObject *result = PyFrozenSetWriter_Finish(writer);
+        if (result == NULL) {
+            return NULL;
+        }
+        Py_DECREF(result);
+    }
+    (void)PyTime_PerfCounterRaw(&t2);
+
+    return PyFloat_FromDouble(PyTime_AsSecondsDouble(t2 - t1));
+}
+
+
+static PyObject*
+bench_writer_update_array(PyObject *Py_UNUSED(self), PyObject *args)
+{
+    PyObject *tuple;
+    Py_ssize_t loops;
+    if (!PyArg_ParseTuple(args, "On", &tuple, &loops)) {
+        return NULL;
+    }
+    PyObject **items = &PyTuple_GET_ITEM(tuple, 0);
+    Py_ssize_t len = PyTuple_GET_SIZE(tuple);
+
+    PyTime_t t1, t2;
+    (void)PyTime_PerfCounterRaw(&t1);
+    for (Py_ssize_t i=0; i < loops; i++) {
+        PyFrozenSetWriter *writer = PyFrozenSetWriter_Create(0);
+        if (writer == NULL) {
+            return NULL;
+        }
+
+        if (PyFrozenSetWriter_UpdateArray(writer, items, len) < 0) {
+            PyFrozenSetWriter_Discard(writer);
+            return NULL;
+        }
+
+        PyObject *result = PyFrozenSetWriter_Finish(writer);
+        if (result == NULL) {
+            return NULL;
+        }
+        Py_DECREF(result);
+    }
+    (void)PyTime_PerfCounterRaw(&t2);
+
+    return PyFloat_FromDouble(PyTime_AsSecondsDouble(t2 - t1));
+}
+
+
 static PyMethodDef TestMethods[] = {
     {"set_errno",               set_errno,                       METH_VARARGS},
     {"test_config",             test_config,                     METH_NOARGS},
@@ -2988,6 +3121,10 @@ static PyMethodDef TestMethods[] = {
 #ifdef HAVE_SYSCTLBYNAME
     {"uptime_bsd", uptime_bsd, METH_NOARGS},
 #endif
+    {"bench_frozenset_new", bench_frozenset_new, METH_VARARGS},
+    {"bench_writer_add", bench_writer_add, METH_VARARGS},
+    {"bench_writer_update", bench_writer_update, METH_VARARGS},
+    {"bench_writer_update_array", bench_writer_update_array, METH_VARARGS},
     {NULL, NULL} /* sentinel */
 };

PyFrozenSetWriter_Finish() now always tracks the frozenset in the GC, instead of only tracking them if at least one item is tracked by the GC -- same behavior than PyFrozenSet_New(iterable)

I was wrong: PyFrozenSet_New(iterable) iterates on items to untrack the frozenset if an item is not tracked by the GC.

I updated the PR. PyFrozenSetWriter_Finish() no longer always track the frozenset in the GC.

PyFrozenSet_New() only tracks the frozenset if at least one item is tracked by the GC: PyFrozenSetWriter_Finish() should do the same. PyFrozenSetWriter_Finish() should not always track the frozenset.

PyFrozenSet_New(NULL) + PySet_Add(frozenset, item) always track the GC, but that should maybe be fixed in the future.

I also ran benchmarks on "Steal" variants on Free Threading.

PyFrozenSetWriter_AddSteal() compared to PyFrozenSetWriter_Add():

PyFrozenSetWriter_UpdateArraySteal() compared to PyFrozenSetWriter_UpdateArray():

Benchmark hidden because not significant (1): size=4

The difference is about -1 ns per item for PyFrozenSetWriter_AddSteal() and about -0.5 ns per item for PyFrozenSetWriter_UpdateArraySteal().

Hum, I'm not sure that it's really worth it to add these two "Steal" variant functions.