Skip to content

gh-112087: Use QSBR technique for list_new/clear for free-thread build #115875

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
corona10 merged 10 commits into from
Mar 1, 2024
Merged

gh-112087: Use QSBR technique for list_new/clear for free-thread build #115875

Show file tree
Hide file tree
Changes from 1 commit
Commits
Show all changes
10 commits
Select commit Hold shift + click to select a range
556c016
gh-112087: Use QSBR technique for list_new/clear for free-thread
corona10 Feb 24, 2024
67a7f32
Replace list_preallocate_exact to list_ensure_capacity
corona10 Feb 24, 2024
6ad0ab4
fix
corona10 Feb 24, 2024
6264094
Update test
corona10 Feb 24, 2024
e514c65
Update list_item
corona10 Feb 24, 2024
df90d37
Revert memory optimization changes
corona10 Feb 28, 2024
e7f3683
Address code review
corona10 Feb 28, 2024
0eb3657
Merge remote-tracking branch 'upstream/main' into gh-115605-qsbr
corona10 Feb 28, 2024
41204cf
Revert list_prealloc
corona10 Mar 1, 2024
9f5d048
nit
corona10 Mar 1, 2024
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
Prev Previous commit
Next Next commit
Revert memory optimization changes
  • Loading branch information
@corona10
corona10 committed Feb 28, 2024
commit df90d37cd25ae21cd414a5bc35249e7793fe5dc9
23 changes: 5 additions & 18 deletions Lib/test/test_sys.py
View file
Open in desktop
Original file line number Diff line number Diff line change
Expand Up @@ -12,7 +12,7 @@
import sysconfig
import test.support
from test import support
from test.support import os_helper, Py_GIL_DISABLED
from test.support import os_helper
from test.support.script_helper import assert_python_ok, assert_python_failure
from test.support import threading_helper
from test.support import import_helper
Expand Down Expand Up @@ -1224,7 +1224,7 @@ def test_pystats(self):
@test.support.cpython_only
@unittest.skipUnless(hasattr(sys, 'abiflags'), 'need sys.abiflags')
def test_disable_gil_abi(self):
self.assertEqual('t' in sys.abiflags, Py_GIL_DISABLED)
self.assertEqual('t' in sys.abiflags, support.Py_GIL_DISABLED)


@test.support.cpython_only
Expand Down Expand Up @@ -1575,22 +1575,9 @@ def get_gen(): yield 1
check(re.finditer('',''), size('2P'))
# list
check(list([]), vsize('Pn'))
if Py_GIL_DISABLED:
check(list([1]), vsize('Pn') + 3*self.P)
check(list([1, 2]), vsize('Pn') + 3*self.P)
check(list([1, 2, 3]), vsize('Pn') + 3*self.P)
check(list([1, 2, 3, 4]), vsize('Pn') + 7*self.P)
check(list([1, 2, 3, 4, 5]), vsize('Pn') + 7*self.P)
check(list([1, 2, 3, 4, 5, 6]), vsize('Pn') + 7*self.P)
check(list([1, 2, 3, 4, 5, 6, 7]), vsize('Pn') + 7*self.P)
else:
check(list([1]), vsize('Pn') + 2*self.P)
check(list([1, 2]), vsize('Pn') + 2*self.P)
check(list([1, 2, 3]), vsize('Pn') + 4*self.P)
check(list([1, 2, 3, 4]), vsize('Pn') + 4*self.P)
check(list([1, 2, 3, 4, 5]), vsize('Pn') + 6*self.P)
check(list([1, 2, 3, 4, 5, 6]), vsize('Pn') + 6*self.P)
check(list([1, 2, 3, 4, 5, 6, 7]), vsize('Pn') + 8*self.P)
check(list([1]), vsize('Pn') + 2*self.P)
check(list([1, 2]), vsize('Pn') + 2*self.P)
check(list([1, 2, 3]), vsize('Pn') + 4*self.P)
# sortwrapper (list)
# XXX
# cmpwrapper (list)
Expand Down
120 changes: 10 additions & 110 deletions Objects/listobject.c
View file
Open in desktop
Original file line number Diff line number Diff line change
Expand Up @@ -31,96 +31,8 @@ get_list_freelist(void)
}
#endif

#ifdef Py_GIL_DISABLED
static size_t
list_good_size(Py_ssize_t size)
{
// 4, 8, 16, 24, 32, 40, 48, 64, 80, ...
// NOTE: we add one here so that the rounding accounts for the "allocated"
size_t reqsize = (size_t)size + 1;
if (reqsize <= 4) {
reqsize = 4;
}
else if (reqsize <= 48) {
reqsize = (reqsize + 7) & ~7;
}
else {
reqsize = (reqsize + 15) & ~15;
if (reqsize <= MI_MEDIUM_OBJ_WSIZE_MAX) {
reqsize = mi_good_size(reqsize * sizeof(PyObject *))/sizeof(PyObject*);
}
else {
// ensure geometric spacing for large arrays
size_t shift = mi_bsr(reqsize) - 2;
reqsize = ((reqsize >> shift) + 1) << shift;
}
}
return reqsize - 1;
}

static PyObject**
list_allocate_items(size_t capacity)
{
if (capacity > PY_SSIZE_T_MAX / sizeof(PyObject *) - 1) {
return NULL;
}
PyObject **items = PyMem_Malloc(capacity * sizeof(PyObject *));
return items;
}

/* Ensure ob_item has room for at least newsize elements, and set
* ob_size to newsize. If newsize > ob_size on entry, the content
* of the new slots at exit is undefined heap trash; it's the caller's
* responsibility to overwrite them with sane values.
* The number of allocated elements may grow, shrink, or stay the same.
* Note that self->ob_item may change, and even if newsize is less
* than ob_size on entry.
*/
static int
list_ensure_capacity_slow(PyListObject *self, Py_ssize_t base, Py_ssize_t extra)
{
if (base > PY_SSIZE_T_MAX/(Py_ssize_t)sizeof(PyObject*) - extra) {
PyErr_NoMemory();
return -1;
}

Py_ssize_t reqsize = base + extra;
Py_ssize_t allocated = self->allocated;
if (allocated >= reqsize) {
assert(self->ob_item != NULL || reqsize == 0);
return 0;
}

if (!_Py_IsOwnedByCurrentThread((PyObject *)self)) {
_PyObject_GC_SET_SHARED(self);
}

size_t capacity = list_good_size(reqsize);
PyObject **items = list_allocate_items(capacity);
if (items == NULL) {
PyErr_NoMemory();
return -1;
}
PyObject **old = self->ob_item;
if (self->ob_item) {
memcpy(items, self->ob_item, allocated * sizeof(PyObject*));
}
_Py_atomic_store_ptr_release(&self->ob_item, items);
self->allocated = capacity;
if (old) {
if (_PyObject_GC_IS_SHARED(self)) {
_PyMem_FreeDelayed(old);
}
else {
PyMem_Free(old);
}
}
return 0;
}
#endif

static PyListObject *
list_new(Py_ssize_t size)
list_new_prealloc(Py_ssize_t size)
{
PyListObject *op;
assert(size >= 0);
Expand All @@ -145,13 +57,8 @@ list_new(Py_ssize_t size)
op->allocated = 0;
}
else {
#ifdef Py_GIL_DISABLED
size_t capacity = list_good_size(size);
PyObject **items = list_allocate_items(capacity);
#else
size_t capacity = size;
PyObject **items = (PyObject **) PyMem_Calloc(size, sizeof(PyObject *));
Comment thread
corona10 marked this conversation as resolved.
Outdated
#endif
if (items == NULL) {
op->ob_item = NULL;
Py_DECREF(op);
Expand Down Expand Up @@ -234,14 +141,8 @@ list_resize(PyListObject *self, Py_ssize_t newsize)
}

static int
list_ensure_capacity(PyListObject *self, Py_ssize_t base, Py_ssize_t extra)
list_preallocate_exact(PyListObject *self, Py_ssize_t size)
{
#ifdef Py_GIL_DISABLED
if (base > self->allocated - extra) {
return list_ensure_capacity_slow(self, base, extra);
}
#else
Py_ssize_t size = extra;
assert(self->ob_item == NULL);
assert(size > 0);

Expand All @@ -258,7 +159,6 @@ list_ensure_capacity(PyListObject *self, Py_ssize_t base, Py_ssize_t extra)
}
self->ob_item = items;
self->allocated = size;
#endif
return 0;
}

Expand Down Expand Up @@ -297,7 +197,7 @@ PyList_New(Py_ssize_t size)
PyErr_BadInternalCall();
return NULL;
}
PyListObject *op = list_new(size);
PyListObject *op = list_new_prealloc(size);
if (op && op->ob_item) {
PyObject **items = op->ob_item;
for (Py_ssize_t i = 0, n = op->allocated; i < n; i++) {
Expand Down Expand Up @@ -446,7 +346,7 @@ PyList_Insert(PyObject *op, Py_ssize_t where, PyObject *newitem)
int
_PyList_AppendTakeRefListResize(PyListObject *self, PyObject *newitem)
{
Py_ssize_t len = PyList_GET_SIZE(self);
Py_ssize_t len = Py_SIZE(self);
assert(self->allocated == -1 || self->allocated == len);
if (list_resize(self, len + 1) < 0) {
Py_DECREF(newitem);
Expand Down Expand Up @@ -624,7 +524,7 @@ list_slice(PyListObject *a, Py_ssize_t ilow, Py_ssize_t ihigh)
if (len <= 0) {
return PyList_New(0);
}
np = (PyListObject *) list_new(len);
np = (PyListObject *) list_new_prealloc(len);
if (np == NULL)
return NULL;

Expand Down Expand Up @@ -676,7 +576,7 @@ list_concat_lock_held(PyListObject *a, PyListObject *b)
if (size == 0) {
return PyList_New(0);
}
np = (PyListObject *) list_new(size);
np = (PyListObject *) list_new_prealloc(size);
if (np == NULL) {
return NULL;
}
Expand Down Expand Up @@ -726,7 +626,7 @@ list_repeat_lock_held(PyListObject *a, Py_ssize_t n)
return PyErr_NoMemory();
Py_ssize_t output_size = input_size * n;

PyListObject *np = (PyListObject *) list_new(output_size);
PyListObject *np = (PyListObject *) list_new_prealloc(output_size);
if (np == NULL)
return NULL;

Expand Down Expand Up @@ -1093,7 +993,7 @@ list_extend_fast(PyListObject *self, PyObject *iterable)
// an overflow on any relevant platform.
assert(m < PY_SSIZE_T_MAX - n);
if (self->ob_item == NULL) {
if (list_ensure_capacity(self, m, n) < 0) {
if (list_preallocate_exact(self, n) < 0) {
return -1;
}
Py_SET_SIZE(self, n);
Expand Down Expand Up @@ -1141,7 +1041,7 @@ list_extend_iter(PyListObject *self, PyObject *iterable)
*/
}
else if (self->ob_item == NULL) {
if (n && list_ensure_capacity(self, m, n) < 0)
if (n && list_preallocate_exact(self, n) < 0)
goto error;
}
else {
Expand Down Expand Up @@ -3218,7 +3118,7 @@ list_subscript(PyObject* _self, PyObject* item)
return list_slice(self, start, stop);
}
else {
result = (PyObject *)list_new(slicelength);
result = (PyObject *)list_new_prealloc(slicelength);
if (!result) return NULL;

src = self->ob_item;
Expand Down