From 0468e416c16f5d2ac072628b0d31e129e0b2776f Mon Sep 17 00:00:00 2001 From: Raymond Hettinger Date: Wed, 5 May 2004 05:37:53 +0000 Subject: SF patch #947476: Apply freelist technique to lists Re-use list object bodies. Saves calls to malloc() and free() for faster list instantiation and deallocation. --- Misc/NEWS | 3 +++ Objects/listobject.c | 21 +++++++++++++++++---- 2 files changed, 20 insertions(+), 4 deletions(-) diff --git a/Misc/NEWS b/Misc/NEWS index c26b09b..983c548 100644 --- a/Misc/NEWS +++ b/Misc/NEWS @@ -54,6 +54,9 @@ Core and builtins the overallocation is no more than three elements -- this improves space utilization for applications that have large numbers of small lists. +- Most list bodies now get re-used rather than freed. Speeds up list + instantiation and deletion by saving calls to malloc() and free(). + - The dict.update() method now accepts all the same argument forms as the dict() constructor. This now includes item lists and/or keyword arguments. diff --git a/Objects/listobject.c b/Objects/listobject.c index 7a2cdea..f3aee39 100644 --- a/Objects/listobject.c +++ b/Objects/listobject.c @@ -49,6 +49,11 @@ list_resize(PyListObject *self, int newsize) return 0; } +/* Empty list reuse scheme to save calls to malloc and free */ +#define MAXFREELISTS 80 +static PyListObject *free_lists[MAXFREELISTS]; +static int num_free_lists = 0; + PyObject * PyList_New(int size) { @@ -63,9 +68,14 @@ PyList_New(int size) if (nbytes / sizeof(PyObject *) != (size_t)size) { return PyErr_NoMemory(); } - op = PyObject_GC_New(PyListObject, &PyList_Type); - if (op == NULL) { - return NULL; + if (num_free_lists) { + num_free_lists--; + op = free_lists[num_free_lists]; + _Py_NewReference((PyObject *)op); + } else { + op = PyObject_GC_New(PyListObject, &PyList_Type); + if (op == NULL) + return NULL; } if (size <= 0) { op->ob_item = NULL; @@ -233,7 +243,10 @@ list_dealloc(PyListObject *op) } PyMem_FREE(op->ob_item); } - op->ob_type->tp_free((PyObject *)op); + if (num_free_lists < MAXFREELISTS && PyList_CheckExact(op)) + free_lists[num_free_lists++] = op; + else + op->ob_type->tp_free((PyObject *)op); Py_TRASHCAN_SAFE_END(op) } -- cgit v0.12