C API: Add internal C API to build a tuple: _PyTupleBuilder · Issue #107137 · python/cpython · GitHub

The current Python C API PyTuple_New() to build a tuple has multiple flaws:

The Python tuple object is immediately tracked by the GC, whereas its items are initialized to NULL (inconsistent tuple)
The PyTuple_SET_ITEM() function must only used on a tuple while is being created

I propose adding a new internal C API to build a tuple: _PyTupleBuilder.

User of the API doesn't access the tuple directly but uses higher API
Over-allocate the tuple (by 25%) to reduce the number of _PyTuple_Resize() calls
_PyTupleBuild_Append() grows the tuple if needed
_PyTupleBuild_AppendUnsafe() is a thin wrapper to PyTuple_SET_ITEM()
Only track the tuple once its fully initialized: correct size, all items are set
Less error-prone API

Later, once we will consider this API stable, we can add it to the public C API and deprecate the old API to create an incomplete tuple:

PyTuple_New()
PyTuple_SetItem()
PyTuple_SET_ITEM()
_PyTuple_Resize()

See capi-workgroup/problems#56 for details on problems caused by API which let creating incomplete/inconsistent objects.

Linked PRs

pythongh-107137: Add _PyTupleBuilder API to the internal C API

This API is for creating tuples when the final size is not known in advance. For known size, use existing APIs like PyTuple_Pack() or Py_BuildValue().

This API is a fix for this old issue: #59313 "Incomplete tuple created by PyTuple_New() and accessed via the GC can trigged a crash" which was closed as "not a bug" in 2021 by @pablogsal.

pythongh-107137: Add _PyTupleBuilder API to the internal C API

pythongh-107137: Add _PyTuple_NewNoTrack() internal C API

What's the benefit of this over building a list then calling PyList_AsTuple()?

You avoid creating a temporary list and then destroy it. It may be faster.

How is creating a temporary tuple builder better than creating a temporary list?

If building a list is slow, we should fix that. It would be far more beneficial than adding a new API.

How is creating a temporary tuple builder better than creating a temporary list?

Code using PyList_AsTuple() requires to creates a temporary list object and then create the final tuple object: two objects.

My proposed API only creates a single Python object: less memory allocations, no conversion of list items to tuple items (copy + INCREF).

If building a list is slow, we should fix that. It would be far more beneficial than adding a new API.

How do you plan to optimize list creation?

This API is a fix for this old issue: #59313 "Incomplete tuple created by PyTuple_New() and accessed via the GC can trigged a crash" which was closed as "not a bug" in 2021 by @pablogsal.

FTR, we can fix the sqlite3 issue by using the internal _PyTuple_FromArray API. I've been discouraged from using internal API in the sqlite3 module earlier, but lately, a lot of private API snuck into that extension module, so perhaps we can reconsider _PyTuple_FromArray for that particular crasher.

Hm, PyList_AsTuple is just a thin wrapper for _PyTuple_FromArray. @markshannon's proposal of building a list should be performant enough.

Here's a quick and non-scientific benchmark:

$ ./python.exe -m timeit "buildtuple(10)"
2000000 loops, best of 5: 140 nsec per loop
$ ./python.exe -m timeit "buildtuple(100)"
500000 loops, best of 5: 864 nsec per loop
$ ./python.exe -m timeit "buildtuple(1000)"
5000 loops, best of 5: 57.8 usec per loop
$ ./python.exe -m timeit "buildtuple(10000)"
500 loops, best of 5: 715 usec per loop

$ ./python.exe -m timeit "buildlist(10)"
1000000 loops, best of 5: 246 nsec per loop
$ ./python.exe -m timeit "buildlist(100)"
200000 loops, best of 5: 1.16 usec per loop
$ ./python.exe -m timeit "buildlist(1000)"
5000 loops, best of 5: 59.6 usec per loop
$ ./python.exe -m timeit "buildlist(10000)"
500 loops, best of 5: 764 usec per loop

Code

diff --git a/Python/bltinmodule.c b/Python/bltinmodule.c
index 787f53fae3..638556c8e5 100644
--- a/Python/bltinmodule.c
+++ b/Python/bltinmodule.c
@@ -2745,6 +2745,66 @@ builtin_issubclass_impl(PyObject *module, PyObject *cls,
     return PyBool_FromLong(retval);
 }
 
+
+/*[clinic input]
+buildtuple as builtin_buildtuple
+    n: int
+    /
+[clinic start generated code]*/
+
+static PyObject *
+builtin_buildtuple_impl(PyObject *module, int n)
+/*[clinic end generated code: output=eaed9c56019027a6 input=1c9950e2c501d16a]*/
+{
+    PyObject *tuple = PyTuple_New(n);
+    if (tuple == NULL) {
+        goto error;
+    }
+    for (int i = 0; i < n; i++) {
+        PyObject *item = PyLong_FromLong(i);
+        if (item == NULL) {
+            goto error;
+        }
+        PyTuple_SET_ITEM(tuple, i, item);
+    }
+    return tuple;
+
+error:
+    Py_XDECREF(tuple);
+    return NULL;
+}
+
+/*[clinic input]
+buildlist as builtin_buildlist = buildtuple
+[clinic start generated code]*/
+
+static PyObject *
+builtin_buildlist_impl(PyObject *module, int n)
+/*[clinic end generated code: output=227ae994f7278b23 input=f8333bb7e2c7f2ce]*/
+{
+    PyObject *list = PyList_New(n);
+    if (list == NULL) {
+        goto error;
+    }
+    for (int i = 0; i < n; i++) {
+        PyObject *item = PyLong_FromLong(i);
+        if (item == NULL) {
+            goto error;
+        }
+        PyList_SET_ITEM(list, i, item);
+    }
+    PyObject *tuple = PyList_AsTuple(list);
+    if (tuple == NULL) {
+        goto error;
+    }
+    Py_DECREF(list);
+    return tuple;
+
+error:
+    Py_XDECREF(list);
+    return NULL;
+}
+
 typedef struct {
     PyObject_HEAD
     Py_ssize_t tuplesize;
@@ -3060,6 +3120,8 @@ static PyMethodDef builtin_methods[] = {
     BUILTIN_SETATTR_METHODDEF
     BUILTIN_SORTED_METHODDEF
     BUILTIN_SUM_METHODDEF
+    BUILTIN_BUILDTUPLE_METHODDEF
+    BUILTIN_BUILDLIST_METHODDEF
     {"vars",            builtin_vars,       METH_VARARGS, vars_doc},
     {NULL,              NULL},
 };
diff --git a/Python/clinic/bltinmodule.c.h b/Python/clinic/bltinmodule.c.h
index 7540de6828..9da527ed3a 100644
--- a/Python/clinic/bltinmodule.c.h
+++ b/Python/clinic/bltinmodule.c.h
@@ -1212,4 +1212,58 @@ builtin_issubclass(PyObject *module, PyObject *const *args, Py_ssize_t nargs)
 exit:
     return return_value;
 }
-/*[clinic end generated code: output=daeee81b018824f4 input=a9049054013a1b77]*/
+
+PyDoc_STRVAR(builtin_buildtuple__doc__,
+"buildtuple($module, n, /)\n"
+"--\n"
+"\n");
+
+#define BUILTIN_BUILDTUPLE_METHODDEF    \
+    {"buildtuple", (PyCFunction)builtin_buildtuple, METH_O, builtin_buildtuple__doc__},
+
+static PyObject *
+builtin_buildtuple_impl(PyObject *module, int n);
+
+static PyObject *
+builtin_buildtuple(PyObject *module, PyObject *arg)
+{
+    PyObject *return_value = NULL;
+    int n;
+
+    n = _PyLong_AsInt(arg);
+    if (n == -1 && PyErr_Occurred()) {
+        goto exit;
+    }
+    return_value = builtin_buildtuple_impl(module, n);
+
+exit:
+    return return_value;
+}
+
+PyDoc_STRVAR(builtin_buildlist__doc__,
+"buildlist($module, n, /)\n"
+"--\n"
+"\n");
+
+#define BUILTIN_BUILDLIST_METHODDEF    \
+    {"buildlist", (PyCFunction)builtin_buildlist, METH_O, builtin_buildlist__doc__},
+
+static PyObject *
+builtin_buildlist_impl(PyObject *module, int n);
+
+static PyObject *
+builtin_buildlist(PyObject *module, PyObject *arg)
+{
+    PyObject *return_value = NULL;
+    int n;
+
+    n = _PyLong_AsInt(arg);
+    if (n == -1 && PyErr_Occurred()) {
+        goto exit;
+    }
+    return_value = builtin_buildlist_impl(module, n);
+
+exit:
+    return return_value;
+}
+/*[clinic end generated code: output=a3a6068cbca21e95 input=a9049054013a1b77]*/

I close the issue, see: #107139 (comment)

C API: Add internal C API to build a tuple: _PyTupleBuilder · Issue #107137 · python/cpython · GitHub

Repository navigation

C API: Add internal C API to build a tuple: _PyTupleBuilder #107137

Linked PRs

Metadata

Assignees

Labels

Projects

Milestone

Relationships

Development

C API: Add internal C API to build a tuple: _PyTupleBuilder · Issue #107137 · python/cpython · GitHub

Repository navigation

C API: Add internal C API to build a tuple: _PyTupleBuilder #107137

Description

Linked PRs

Activity

vstinner commented on Jul 23, 2023

vstinner commented on Jul 23, 2023

markshannon commented on Aug 15, 2023

vstinner commented on Aug 15, 2023

markshannon commented on Aug 15, 2023

vstinner commented on Aug 16, 2023

erlend-aasland commented on Aug 22, 2023

erlend-aasland commented on Aug 22, 2023

erlend-aasland commented on Aug 23, 2023

vstinner commented on Aug 26, 2023

Metadata

Metadata

Assignees

Labels

Projects

Milestone

Relationships

Development

Issue actions