[Python-checkins] bpo-38373: Change list overallocating strategy. (GH-18952)
Serhiy Storchaka
webhook-mailer at python.org
Tue Mar 17 17:46:04 EDT 2020
https://github.com/python/cpython/commit/2fe815edd6778fb9deef8f8044848647659c2eb8
commit: 2fe815edd6778fb9deef8f8044848647659c2eb8
branch: master
author: Serhiy Storchaka <storchaka at gmail.com>
committer: GitHub <noreply at github.com>
date: 2020-03-17T23:46:00+02:00
summary:
bpo-38373: Change list overallocating strategy. (GH-18952)
* Add padding to make the allocated size multiple of 4.
* Do not overallocate if the new size is closer to overalocated size
than to the old size.
files:
A Misc/NEWS.d/next/Core and Builtins/2020-03-11-12-28-16.bpo-38373.FE9S21.rst
M Objects/listobject.c
diff --git a/Misc/NEWS.d/next/Core and Builtins/2020-03-11-12-28-16.bpo-38373.FE9S21.rst b/Misc/NEWS.d/next/Core and Builtins/2020-03-11-12-28-16.bpo-38373.FE9S21.rst
new file mode 100644
index 0000000000000..83d60e01e7d00
--- /dev/null
+++ b/Misc/NEWS.d/next/Core and Builtins/2020-03-11-12-28-16.bpo-38373.FE9S21.rst
@@ -0,0 +1,2 @@
+Chaged list overallocation strategy. It no longer overallocates if the new
+size is closer to overalocated size than to the old size and adds padding.
diff --git a/Objects/listobject.c b/Objects/listobject.c
index 46bc7779218bc..4e2b6a9c1609a 100644
--- a/Objects/listobject.c
+++ b/Objects/listobject.c
@@ -54,15 +54,17 @@ list_resize(PyListObject *self, Py_ssize_t newsize)
* enough to give linear-time amortized behavior over a long
* sequence of appends() in the presence of a poorly-performing
* system realloc().
- * The growth pattern is: 0, 4, 8, 16, 25, 35, 46, 58, 72, 88, ...
+ * Add padding to make the allocated size multiple of 4.
+ * The growth pattern is: 0, 4, 8, 16, 24, 32, 40, 52, 64, 76, ...
* Note: new_allocated won't overflow because the largest possible value
* is PY_SSIZE_T_MAX * (9 / 8) + 6 which always fits in a size_t.
*/
- new_allocated = (size_t)newsize + (newsize >> 3) + (newsize < 9 ? 3 : 6);
- if (new_allocated > (size_t)PY_SSIZE_T_MAX / sizeof(PyObject *)) {
- PyErr_NoMemory();
- return -1;
- }
+ new_allocated = ((size_t)newsize + (newsize >> 3) + 6) & ~(size_t)3;
+ /* Do not overallocate if the new size is closer to overalocated size
+ * than to the old size.
+ */
+ if (newsize - Py_SIZE(self) > (Py_ssize_t)(new_allocated - newsize))
+ new_allocated = ((size_t)newsize + 3) & ~(size_t)3;
if (newsize == 0)
new_allocated = 0;
More information about the Python-checkins
mailing list