Skip to content

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

Closed as not planned
Closed as not planned
C API: Add internal C API to build a tuple: _PyTupleBuilder#107137
Labels
topic-C-APItype-featureA feature request or enhancement

Description

@vstinner
vstinner
opened on Jul 23, 2023

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

Activity

  1. vstinner
    added
    type-featureA feature request or enhancement
    topic-C-API
    on Jul 23, 2023
  2. vstinner
    added 3 commits that reference this issue on Jul 23, 2023

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

    4679548

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

    4147a8a

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

    38a4c0c

  3. vstinner commented on Jul 23, 2023

    @vstinner
    vstinner
    on Jul 23, 2023
    MemberAuthor

    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().

  4. vstinner commented on Jul 23, 2023

    @vstinner
    vstinner
    on Jul 23, 2023
    MemberAuthor

    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.

  5. vstinner
    added 5 commits that reference this issue on Jul 23, 2023

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

    e55f80a

    pythongh-107137: Add _PyTuple_NewNoTrack() internal C API

    072f357

    pythongh-107137: Add _PyTuple_NewNoTrack() internal C API

    869cada

    pythongh-107137: Add _PyTuple_NewNoTrack() internal C API

    9c9f4a7

    pythongh-107137: Add _PyTuple_NewNoTrack() internal C API

    55d1b7a

  6. markshannon commented on Aug 15, 2023

    @markshannon
    markshannon
    on Aug 15, 2023
    Member

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

  7. vstinner commented on Aug 15, 2023

    @vstinner
    vstinner
    on Aug 15, 2023
    MemberAuthor

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

  8. markshannon commented on Aug 15, 2023

    @markshannon
    markshannon
    on Aug 15, 2023
    Member

    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.

  9. vstinner commented on Aug 16, 2023

    @vstinner
    vstinner
    on Aug 16, 2023
    MemberAuthor

    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?

  10. erlend-aasland commented on Aug 22, 2023

    @erlend-aasland
    erlend-aasland
    on Aug 22, 2023
    Contributor

    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.

  11. erlend-aasland commented on Aug 22, 2023

    @erlend-aasland
    erlend-aasland
    on Aug 22, 2023
    Contributor

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

  12. erlend-aasland commented on Aug 23, 2023

    @erlend-aasland
    erlend-aasland
    on Aug 23, 2023
    Contributor

    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]*/

  13. vstinner commented on Aug 26, 2023

    @vstinner
    vstinner
    on Aug 26, 2023
    MemberAuthor

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

  14. vstinner
    closed this as completedon Aug 26, 2023
  15. erlend-aasland
    closed this as not plannedon Aug 27, 2023
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment

Metadata

Metadata

Assignees

No one assigned

    Labels

    topic-C-APItype-featureA feature request or enhancement

    Projects

    No projects

      Milestone

      No milestone

      Relationships

      None yet

      Development

      No branches or pull requests

      Issue actions