Issue 47009: Streamline list.append for the common case (original) (raw)

Created on 2022-03-14 04:57 by Dennis Sweeney, last changed 2022-04-11 14:59 by admin. This issue is now closed.

| Messages (8) | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | ------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------ | ------------------------------------------------------------------------------------------------------------------------------------- | ------------------------------------------------------------------------------------------------------------------------------------------------------------------ | ---------------------------- | | ------------------------------------------------------------------------------------------- | ------------ | ------- | --------------------- | --------------------- | | ---------- | ------- | --------------------- | --------------------- | | ------------- | ------- | --------------------- | --------------------- | | ----------- | ------- | --------------------- | --------------------- | | -------------- | ------ | --------------------- | -------------------- | | ------------ | ------ | -------------------- | -------------------- | | --------------- | ------- | -------------------- | --------------------- | | ------------- | ------- | --------------------- | --------------- | | -------------- | ----- | ------------ | ------------ | | | msg415116 - (view) | Author: Dennis Sweeney (Dennis Sweeney) * | Date: 2022-03-14 04:57 | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | list_resize is a long function that probably won't get inlined. But for the vast majority of cases in list.append, we just need to check whether the list is big enough (not whether it's small enough, or whether it's null or the wrong type), then insert and update the size. This can be inlined, with an actual call only taking place whenever we need to resize. We can also add a reference-consuming version of PyList_Append to elide an INCREF/DECREF pair. | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | msg415121 - (view) | Author: Inada Naoki (methane) * | Date: 2022-03-14 08:19 | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | Hmm. Would you measure benefit from inlining and skipping incref/decref separately? If benefit of inlining is very small, making _PyList_AppendTakeRef() as regular internal API looks better to me. | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | msg415127 - (view) | Author: Dennis Sweeney (Dennis Sweeney) * | Date: 2022-03-14 10:35 | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | The attached _PyList_AppendTakeRef.diff has the ceval.c, but this implementation: int _PyList_AppendTakeRef(PyListObject *self, PyObject *newitem) { assert(self != NULL && newitem != NULL); assert(PyList_Check(self)); Py_ssize_t len = PyList_GET_SIZE(self); Py_ssize_t allocated = self->allocated; assert((size_t)len + 1 < PY_SSIZE_T_MAX); if (allocated > len) { PyList_SET_ITEM(self, len, newitem); Py_SET_SIZE(self, len + 1); return 0; } if (list_resize(self, len + 1) < 0) { Py_DECREF(newitem); return -1; } PyList_SET_ITEM(self, len, newitem); return 0; } Results: | Benchmark | main | PR 31864 | _PyList_AppendTakeRef.diff | | -----------------|:-----------------:|:---------------------:|:--------------------------:| | listcomp 100 | 1.61 us | 1.33 us: 1.21x faster | 1.55 us: 1.04x faster | | append 100 | 2.11 us | 1.82 us: 1.15x faster | 2.05 us: 1.03x faster | | listcomp 1000 | 12.6 us | 9.83 us: 1.28x faster | 11.9 us: 1.06x faster | | append 1000 | 18.1 us | 15.3 us: 1.18x faster | 17.6 us: 1.03x faster | | listcomp 10000 | 121 us | 93.2 us: 1.29x faster | 114 us: 1.06x faster | | append 10000 | 175 us | 150 us: 1.17x faster | 172 us: 1.02x faster | | listcomp 100000 | 1.17 ms | 923 us: 1.26x faster | 1.15 ms: 1.02x faster | | append 100000 | 1.70 ms | 1.49 ms: 1.14x faster | not significant | | Geometric mean | (ref) | 1.21x faster | 1.03x faster | | | msg415327 - (view) | Author: Inada Naoki (methane) * | Date: 2022-03-16 04:00 | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | Thank you. I agree that inlining is worth enough. But we already inlined too many functions in ceval and there is an issue caused by it... (bpo-45116) | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | msg416481 - (view) | Author: Mark Shannon (Mark.Shannon) * | Date: 2022-04-01 10:24 | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | New changeset a0ea7a116ce52a178c02d42b684089758bd7f355 by Dennis Sweeney in branch 'main': bpo-47009: Streamline list.append for the common case (GH-31864) https://github.com/python/cpython/commit/a0ea7a116ce52a178c02d42b684089758bd7f355 | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | msg416766 - (view) | Author: Mark Shannon (Mark.Shannon) * | Date: 2022-04-05 10:18 | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | New changeset 6c6e0408a663c1f53dad403f54a18d444da39cb7 by Dennis Sweeney in branch 'main': bpo-47009: Let PRECALL_NO_KW_LIST_APPEND do its own POP_TOP (GH-32239) https://github.com/python/cpython/commit/6c6e0408a663c1f53dad403f54a18d444da39cb7 | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | msg416786 - (view) | Author: Christian Heimes (christian.heimes) * | Date: 2022-04-05 16:18 | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | New changeset 9e88b572fb904b172f9e344069fb7118f1cee517 by Christian Heimes in branch 'main': bpo-47009: Fix assert on big endian (GH-32332) https://github.com/python/cpython/commit/9e88b572fb904b172f9e344069fb7118f1cee517 | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | msg416841 - (view) | Author: Dennis Sweeney (Dennis Sweeney) * | Date: 2022-04-06 03:19 | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | Buildbots are passing, so I'm closing this. Thanks for the catch and fix! | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | |