Skip to content

bpo-45575: Use a less ad-hoc approach to freelists, and use them for int and float freelists. #29165

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

Closed
markshannon wants to merge 8 commits into from
Closed

bpo-45575: Use a less ad-hoc approach to freelists, and use them for int and float freelists. #29165

Show file tree
Hide file tree
Changes from 1 commit
Commits
Show all changes
8 commits
Select commit Hold shift + click to select a range
a136903
Use optimized freelist for ints and floats.
markshannon Oct 21, 2021
db9d9ce
Merge branch 'main' into dry-freelists
markshannon Oct 22, 2021
b82c39d
Tidy up
markshannon Oct 22, 2021
367710e
Add NEWS.
markshannon Oct 22, 2021
4418184
Move stuff around to support address sanitizer.
markshannon Oct 22, 2021
d1ed5f6
Account for non-64bit platforms.
markshannon Oct 24, 2021
69a378c
Make small object freelists per-interpreter.
markshannon Oct 25, 2021
0e9c2d0
Fix typo.
markshannon Oct 25, 2021
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
Make small object freelists per-interpreter.
  • Loading branch information
@markshannon
markshannon committed Oct 25, 2021
commit 69a378c61a1129f8fc74e33ba2959bc15877e2af
22 changes: 5 additions & 17 deletions Include/internal/pycore_interp.h
View file
Open in desktop
Original file line number Diff line number Diff line change
Expand Up @@ -12,6 +12,7 @@ extern "C" {
#include "pycore_ast_state.h" // struct ast_state
#include "pycore_gil.h" // struct _gil_runtime_state
#include "pycore_gc.h" // struct _gc_runtime_state
#include "pycore_pymem.h" // free lists
#include "pycore_warnings.h" // struct _warnings_runtime_state

struct _pending_calls {
Expand Down Expand Up @@ -88,7 +89,6 @@ struct _Py_unicode_state {
#ifndef WITH_FREELISTS
# define WITH_FREELISTS 0
// without freelists
# define PyFloat_MAXFREELIST 0
// for tuples only store empty tuple singleton
# define PyTuple_MAXSAVESIZE 1
# define PyTuple_MAXFREELIST 1
Expand All @@ -99,20 +99,6 @@ struct _Py_unicode_state {
# define PyContext_MAXFREELIST 0
#endif

#ifndef PyFloat_MAXFREELIST
# define PyFloat_MAXFREELIST 100
#endif

struct _Py_float_state {
#if PyFloat_MAXFREELIST > 0
/* Special free list
free_list is a singly-linked list of available PyFloatObjects,
linked via abuse of their ob_type members. */
int numfree;
PyFloatObject *free_list;
#endif
};

/* Speed optimization to avoid frequent malloc/free of small tuples */
#ifndef PyTuple_MAXSAVESIZE
// Largest tuple to save on free list
Expand Down Expand Up @@ -272,6 +258,10 @@ struct _is {

int finalizing;

#if WITH_FREELISTS
_PyFreeList small_object_freelist;
#endif

struct _ceval_state ceval;
struct _gc_runtime_state gc;

Expand Down Expand Up @@ -337,7 +327,6 @@ struct _is {
PyLongObject* small_ints[_PY_NSMALLNEGINTS + _PY_NSMALLPOSINTS];
struct _Py_bytes_state bytes;
struct _Py_unicode_state unicode;
struct _Py_float_state float_state;
/* Using a cache is very effective since typically only a single slice is
created and then deleted again. */
PySliceObject *slice_cache;
Expand All @@ -349,7 +338,6 @@ struct _is {
struct _Py_async_gen_state async_gen;
struct _Py_context_state context;
struct _Py_exc_state exc_state;

struct ast_state ast;
struct type_cache type_cache;
};
Expand Down
2 changes: 1 addition & 1 deletion Include/internal/pycore_pymem.h
View file
Open in desktop
Original file line number Diff line number Diff line change
Expand Up @@ -143,7 +143,7 @@ _PyFreeList_Free(_PyFreeList *list, void *ptr) {
_PyFreeList_FreeToFull(list, ptr);
}

extern _PyFreeList _Py_small_object_freelist;
extern void _PyFreeList_Clear(_PyFreeList *list);
#endif

#ifdef __cplusplus
Expand Down
18 changes: 6 additions & 12 deletions Objects/floatobject.c
View file
Open in desktop
Original file line number Diff line number Diff line change
Expand Up @@ -115,7 +115,8 @@ PyObject *
PyFloat_FromDouble(double fval)
{
#if WITH_FREELISTS
PyFloatObject *op = (PyFloatObject *)_PyFreeList_Alloc(&_Py_small_object_freelist);
PyInterpreterState *interp = _PyInterpreterState_GET();
PyFloatObject *op = (PyFloatObject *)_PyFreeList_Alloc(&interp->small_object_freelist);
#else
PyFloatObject *op = (PyFloatObject *)PyObject_Malloc(sizeof(PyFloatObject));
#endif
Expand Down Expand Up @@ -215,7 +216,8 @@ float_dealloc(PyFloatObject *op)
{
#if WITH_FREELISTS
if (PyFloat_CheckExact(op)) {
_PyFreeList_Free(&_Py_small_object_freelist, op);
PyInterpreterState *interp = _PyInterpreterState_GET();
_PyFreeList_Free(&interp->small_object_freelist, op);
}
else
#endif
Expand Down Expand Up @@ -2008,16 +2010,8 @@ _PyFloat_InitTypes(void)
void
_PyFloat_ClearFreeList(PyInterpreterState *interp)
{
#if PyFloat_MAXFREELIST > 0
struct _Py_float_state *state = &interp->float_state;
PyFloatObject *f = state->free_list;
while (f != NULL) {
PyFloatObject *next = (PyFloatObject*) Py_TYPE(f);
PyObject_Free(f);
f = next;
}
state->free_list = NULL;
state->numfree = 0;
#if WITH_FREELISTS
_PyFreeList_Clear(&interp->small_object_freelist);
#endif
}

Expand Down
11 changes: 7 additions & 4 deletions Objects/longobject.c
View file
Open in desktop
Original file line number Diff line number Diff line change
Expand Up @@ -132,8 +132,9 @@ _PyLong_New(Py_ssize_t size)
return NULL;
}
#if WITH_FREELISTS
if (size <= MAX_DIGITS_FOR_FREELIST) {
result = (PyLongObject *)_PyFreeList_Alloc(&_Py_small_object_freelist);
if (((size_t)size) <= MAX_DIGITS_FOR_FREELIST) {
PyInterpreterState *interp = _PyInterpreterState_GET();
result = (PyLongObject *)_PyFreeList_Alloc(&interp->small_object_freelist);
#else
if (size == 0) {
result = PyObject_Malloc(sizeof(PyLongObject));
Expand Down Expand Up @@ -188,7 +189,8 @@ _PyLong_FromMedium(sdigit x)
assert(!IS_SMALL_INT(x));
assert(is_medium_int(x));
#if WITH_FREELISTS
PyLongObject *v = (PyLongObject *)_PyFreeList_Alloc(&_Py_small_object_freelist);
PyInterpreterState *interp = _PyInterpreterState_GET();
PyLongObject *v = (PyLongObject *)_PyFreeList_Alloc(&interp->small_object_freelist);
#else
PyLongObject *v = (PyLongObject *)PyObject_Malloc(sizeof(PyLongObject));
#endif
Expand Down Expand Up @@ -5767,7 +5769,8 @@ int_dealloc(PyLongObject *op)
{
#if WITH_FREELISTS
if (PyLong_CheckExact(op) && IS_MEDIUM_VALUE(op)) {
_PyFreeList_Free(&_Py_small_object_freelist, op);
PyInterpreterState *interp = _PyInterpreterState_GET();
_PyFreeList_Free(&interp->small_object_freelist, op);
}
else
#endif
Expand Down
29 changes: 15 additions & 14 deletions Objects/obmalloc.c
View file
Open in desktop
Original file line number Diff line number Diff line change
Expand Up @@ -735,20 +735,6 @@ PyObject_Free(void *ptr)

#if WITH_FREELISTS

#define SMALL_OBJECT_FREELIST_SIZE 256

union _small_object {
PyFloatObject f;
PyLongObject l;
};

_PyFreeList _Py_small_object_freelist = {
NULL,
SMALL_OBJECT_FREELIST_SIZE,
sizeof(union _small_object),
SMALL_OBJECT_FREELIST_SIZE
};

void *
_PyFreeList_HalfFillAndAllocate(_PyFreeList *list)
{
Expand All @@ -774,6 +760,21 @@ _PyFreeList_HalfFillAndAllocate(_PyFreeList *list)
return result;
}

void
_PyFreeList_Clear(_PyFreeList *list)
{
int space = 0;
void *head = list->ptr;
while (head) {
void *next = *((void**)head);
PyObject_Free(head);
head = next;
space++;
}
list->ptr = NULL;
list->space += space;
}

void
_PyFreeList_FreeToFull(_PyFreeList *list, void *ptr)
{
Expand Down
14 changes: 14 additions & 0 deletions Python/pystate.c
View file
Open in desktop
Original file line number Diff line number Diff line change
Expand Up @@ -201,6 +201,13 @@ _PyInterpreterState_Enable(_PyRuntimeState *runtime)
return _PyStatus_OK();
}

/* For small object freelist */
#define SMALL_OBJECT_FREELIST_SIZE 256
union _small_object {
PyFloatObject f;
PyLongObject l;
};

PyInterpreterState *
PyInterpreterState_New(void)
{
Expand Down Expand Up @@ -270,6 +277,13 @@ PyInterpreterState_New(void)

interp->audit_hooks = NULL;

#if WITH_FREELISTS
interp->small_object_freelist.ptr = NULL;
interp->small_object_freelist.space = SMALL_OBJECT_FREELIST_SIZE;
interp->small_object_freelist.size = sizeof(union _small_object);
interp->small_object_freelist.capacity = SMALL_OBJECT_FREELIST_SIZE;
#endif

return interp;

out_of_memory:
Expand Down