python · eendebakpt · Feb 7, 2025 · Feb 7, 2025 · Feb 9, 2025 · Feb 9, 2025
@@ -10,6 +10,8 @@ extern "C" {
 
 #  define PyTuple_MAXSAVESIZE 20     // Largest tuple to save on freelist
 #  define Py_tuple_MAXFREELIST 2000  // Maximum number of tuples of each size to save
+#  define PyList_MAXSAVESIZE 13     // Largest list size to save on freelist (minus one)
+#  define Py_small_lists_MAXFREELIST 40
 #  define Py_lists_MAXFREELIST 80
 #  define Py_list_iters_MAXFREELIST 10
 #  define Py_tuple_iters_MAXFREELIST 10
@@ -45,6 +47,7 @@ struct _Py_freelists {
     struct _Py_freelist floats;
     struct _Py_freelist ints;
     struct _Py_freelist tuples[PyTuple_MAXSAVESIZE];
+    struct _Py_freelist small_lists[PyList_MAXSAVESIZE];
     struct _Py_freelist lists;
     struct _Py_freelist list_iters;
     struct _Py_freelist tuple_iters;

diff --git a/Lib/test/test_list.py b/Lib/test/test_list.py
@@ -319,8 +319,9 @@ def test_no_memory(self):
         import_module("_testcapi")
         code = textwrap.dedent("""
         import _testcapi, sys
-        # Prime the freelist
-        l = [None]
+        # Prime the freelist, size needs to larger than the small list freelists
+        l = [None, None, None, None, None, None, None, None, None, None, None,
+             None, None, None, None, None, None, None, None, None,]
         del l
         _testcapi.set_nomemory(0)
         l = [None]

diff --git a/Misc/NEWS.d/next/Core_and_Builtins/2025-04-03-21-23-05.gh-issue-126703.6JpmrR.rst b/Misc/NEWS.d/next/Core_and_Builtins/2025-04-03-21-23-05.gh-issue-126703.6JpmrR.rst
@@ -0,0 +1 @@
+Improve performance of :class:`list` by using dedicated freelists for small sizes.
diff --git a/Objects/listobject.c b/Objects/listobject.c
@@ -230,6 +230,21 @@ _PyList_DebugMallocStats(FILE *out)
                            sizeof(PyListObject));
 }
 
+
+static inline int
+maybe_small_list_freelist_push(PyObject *self)
+{
+    assert(PyList_CheckExact(self));
+
+    PyListObject *op = (PyListObject *)self;
+    Py_ssize_t allocated = op->allocated;
+    if (allocated < PyList_MAXSAVESIZE) {
+        return _Py_FREELIST_PUSH(small_lists[allocated], self, Py_small_lists_MAXFREELIST);
+    }
+    return 0;
+}
+
+
 PyObject *
 PyList_New(Py_ssize_t size)
 {
@@ -238,35 +253,53 @@ PyList_New(Py_ssize_t size)
         return NULL;
     }
 
-    PyListObject *op = _Py_FREELIST_POP(PyListObject, lists);
+    PyListObject *op=0;
+
+    if (size < PyList_MAXSAVESIZE) {
+        op = (PyListObject *)_Py_FREELIST_POP(PyLongObject, small_lists[size]);
+        if (op) {
+            assert (op->allocated >= size);
+            // allocated with ob_item still allocated, but we need to set the other fields
+            Py_SET_SIZE(op, size);
+            if ( size>0) {
+                memset(op->ob_item, 0, size * sizeof(PyObject *));
+            } else {
+                op->ob_item = NULL;
+            }
+        }
+    }
     if (op == NULL) {
-        op = PyObject_GC_New(PyListObject, &PyList_Type);
+        // the size based freelist was empty, so we try the general freelist
+        op = _Py_FREELIST_POP(PyListObject, lists);
         if (op == NULL) {
-            return NULL;
+            op = PyObject_GC_New(PyListObject, &PyList_Type);
+            if (op == NULL) {
+                return NULL;
+            }
         }
-    }
-    if (size <= 0) {
-        op->ob_item = NULL;
-    }
-    else {
-#ifdef Py_GIL_DISABLED
-        _PyListArray *array = list_allocate_array(size);
-        if (array == NULL) {
-            Py_DECREF(op);
-            return PyErr_NoMemory();
+        if (size <= 0) {
+            op->ob_item = NULL;
         }
-        memset(&array->ob_item, 0, size * sizeof(PyObject *));
-        op->ob_item = array->ob_item;
+        else {
+#ifdef Py_GIL_DISABLED
+            _PyListArray *array = list_allocate_array(size);
+            if (array == NULL) {
+                Py_DECREF(op);
+                return PyErr_NoMemory();
+            }
+            memset(&array->ob_item, 0, size * sizeof(PyObject *));
+            op->ob_item = array->ob_item;
 #else
-        op->ob_item = (PyObject **) PyMem_Calloc(size, sizeof(PyObject *));
+            op->ob_item = (PyObject **) PyMem_Calloc(size, sizeof(PyObject *));
+            if (op->ob_item == NULL) {
+                Py_DECREF(op);
+                return PyErr_NoMemory();
+            }
 #endif
-        if (op->ob_item == NULL) {
-            Py_DECREF(op);
-            return PyErr_NoMemory();
         }
+        Py_SET_SIZE(op, size);
+        op->allocated = size;
     }
-    Py_SET_SIZE(op, size);
-    op->allocated = size;
     _PyObject_GC_TRACK(op);
     return (PyObject *) op;
 }
@@ -275,6 +308,14 @@ static PyObject *
 list_new_prealloc(Py_ssize_t size)
 {
     assert(size > 0);
+    if (size < PyList_MAXSAVESIZE) {
+        PyListObject *op = (PyListObject *)_Py_FREELIST_POP(PyLongObject, small_lists[size]);
+        if (op) {
+            assert (op->allocated >= size);
+            return (PyObject *) op;
+        }
+    }
+
     PyListObject *op = (PyListObject *) PyList_New(0);
     if (op == NULL) {
         return NULL;
@@ -544,6 +585,18 @@ PyList_Append(PyObject *op, PyObject *newitem)
 
 /* Methods */
 
+void _Py_small_list_freelist_free(void *obj)
+{
+    PyObject *self = (PyObject *)obj;
+
+    assert(PyList_CheckExact(self));
+    PyListObject *op = (PyListObject *)self;
+    if (op->ob_item != NULL) {
+        free_list_items(op->ob_item, false);
+    }
+    PyObject_GC_Del(op);
+}
+
 static void
 list_dealloc(PyObject *self)
 {
@@ -560,15 +613,24 @@ list_dealloc(PyObject *self)
         while (--i >= 0) {
             Py_XDECREF(op->ob_item[i]);
         }
+    }
+    if (PyList_CheckExact(op)) {
+        if( maybe_small_list_freelist_push(self) ) {
+            goto end;
+        }
+    }
+    if (op->ob_item != NULL) {
         free_list_items(op->ob_item, false);
         op->ob_item = NULL;
     }
     if (PyList_CheckExact(op)) {
-        _Py_FREELIST_FREE(lists, op, PyObject_GC_Del);
+       _Py_FREELIST_FREE(lists, op, PyObject_GC_Del);
     }
     else {
         PyObject_GC_Del(op);
     }
+
+    end:
     Py_TRASHCAN_END
 }
 

diff --git a/Objects/object.c b/Objects/object.c
@@ -916,6 +916,8 @@ free_object(void *obj)
     Py_DECREF(tp);
 }
 
+extern void _Py_small_list_freelist_free(void *);
+
 void
 _PyObject_ClearFreeLists(struct _Py_freelists *freelists, int is_finalization)
 {
@@ -925,6 +927,9 @@ _PyObject_ClearFreeLists(struct _Py_freelists *freelists, int is_finalization)
     for (Py_ssize_t i = 0; i < PyTuple_MAXSAVESIZE; i++) {
         clear_freelist(&freelists->tuples[i], is_finalization, free_object);
     }
+    for (Py_ssize_t i = 0; i < PyList_MAXSAVESIZE; i++) {
+        clear_freelist(&freelists->small_lists[i], is_finalization, _Py_small_list_freelist_free);
+    }
     clear_freelist(&freelists->lists, is_finalization, free_object);
     clear_freelist(&freelists->list_iters, is_finalization, free_object);
     clear_freelist(&freelists->tuple_iters, is_finalization, free_object);
Original file line number	Diff line number	Diff line change
		@@ -0,0 +1 @@
		Improve performance of :class:`list` by using dedicated freelists for small sizes.