PyType_GenericAlloc might over-allocate memory

[nascheme]

BPO	37200
Nosy	@nascheme
Files	generic_alloc_sentinel.txt generic_alloc_sentinel_v2.txt

^{Note: these values reflect the state of the issue at the time it was migrated and might not reflect the current state.}

Show more details

GitHub fields:

assignee = None
closed_at = None
created_at = <Date 2019-06-07.19:32:16.774>
labels = ['interpreter-core', 'performance']
title = 'PyType_GenericAlloc might over-allocate memory'
updated_at = <Date 2019-06-07.23:11:45.704>
user = 'https://github.com/nascheme'

bugs.python.org fields:

activity = <Date 2019-06-07.23:11:45.704>
actor = 'nascheme'
assignee = 'none'
closed = False
closed_date = None
closer = None
components = ['Interpreter Core']
creation = <Date 2019-06-07.19:32:16.774>
creator = 'nascheme'
dependencies = []
files = ['48403', '48404']
hgrepos = []
issue_num = 37200
keywords = []
message_count = 2.0
messages = ['345002', '345014']
nosy_count = 1.0
nosy_names = ['nascheme']
pr_nums = []
priority = 'low'
resolution = None
stage = 'patch review'
status = 'open'
superseder = None
type = 'performance'
url = 'https://bugs.python.org/issue37200'
versions = []

Linked PRs

• gh-81381: Reduce allocated size of PyType_GenericAlloc if possible #100855
• GH-81381: Add longer comment _PyType_AllocNoTrack(). #100954

[nascheme]

In the process of working on some garbage collector/obmalloc experiments, I noticed what seems to be a quirk about PyType_GenericAlloc(). It calls:

size = _PyObject_VAR_SIZE(type, nitems+1);

Note the "+1" which is documented as "for the sentinel". That code dates back to change "e5c691abe3946ddbaa00730b92f3b96f96903f7d" when Guido added support for heap types. This extra item is not added by _PyObject_GC_NewVar(). Also, the documentation for tp_alloc says that the size of the allocated block should be:

tp_basicsize + nitems*tp_itemsize, rounded up to a multiple of sizeof(void*);

The "+1" for the sentinel is definitely needed in certain cases. I think it might only be needed if 'type' is a subtype of 'type'. I.e. if Py_TPFLAGS_TYPE_SUBCLASS is set on 'type'.

I haven't done enough analysis to fully understand this quirk yet but I think we are allocating extra memory quite regularly. Quite a lot of types use tp_alloc = PyType_GenericAlloc. E.g. the 'list' type or a subclass of the tuple type.

It seems with the attached patch, unit tests still pass. Perhaps the +1 could be removed on the non-GC branch of the code as well.

[nascheme]

Updated patch is attached. It appears that the extra item is only needed if Py_TPFLAGS_TYPE_SUBCLASS set. In all other cases, it seems we don't need the extra space for the sentinel. At least, the unit tests pass with this change. It could be that some extension module depends on this extra allocated spaced.

The number of types affected by this change seem relatively small. The 'list' type is not affected because tp_itemsize is 0. I did a little test by running some unit tests, here are some type names that have a smaller amount of memory allocated for them:

_NamedIntConstant
CodecInfo
Point
TestResults
madtuple

[mdickinson]

Closed #100659 as a duplicate of this issue.

[nascheme]

Closing as fixed even though it still over-allocates for some types. I added a comment to the source code and we can consider it expected behaviour.

[nascheme]

FYI, also related is GH-100637