10000 bpo-38373: Change list overallocating strategy. by serhiy-storchaka · Pull Request #18952 · python/cpython · GitHub
[go: up one dir, main page]
Skip to content

bpo-38373: Change list overallocating strategy. #18952

New issue

Have a question about this project? Sign up for a free GitHub account to open an issue and contact its maintainers and the community.

Sign up for GitHub

By clicking “Sign up for GitHub”, you agree to our terms of service and privacy statement. We’ll occasionally send you account related emails.

Already on GitHub? Sign in to your account

Merged
merged 1 commit into from
Mar 17, 2020
Merged

bpo-38373: Change list overallocating strategy. #18952

Show file tree
Hide file tree
Changes from all commits
Commits
Show all changes
1 commit
Select commit
File filter

Filter by extension

Filter by extension
Conversations
Failed to load comments.
Loading
Jump to
Jump to file
Failed to load files.
Loading
Diff view
Diff view
bpo-38373: Change list overallocating strategy. 
* 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.
  • Loading branch information
@serhiy-storchaka
serhiy-storchaka committed Mar 12, 2020
commit 771dde2d0959bf7e28c4a41987d6bbdbb5ce0443
2 changes: 2 additions & 0 deletions Misc/NEWS.d/next/Core and Builtins/2020-03-11-12-28-16.bpo-38373.FE9S21.rst
View file
Open in desktop
Original file line number Diff line number Diff line change
@@ -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.
14 changes: 8 additions & 6 deletions Objects/listobject.c
View file
Open in desktop
Original file line number Diff line number Diff line change
791B Expand Up @@ -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;
Expand Down
0