From 3bb19873abd572879cc9a8810b1db9db1f704070 Mon Sep 17 00:00:00 2001 From: Raymond Hettinger Date: Thu, 25 Mar 2021 13:32:23 -0700 Subject: Revert "bpo-40521: Remove freelist from collections.deque() (GH-21073)" (GH-24944) This reverts commit 32f2eda85957365d208f499b730d30b7eb419741. It can be re-applied if the subinterpreter PEP is approved. Otherwise, the commit degraded performance with no offsetting benefit. --- Modules/_collectionsmodule.c | 23 +++++++++++++++++++++-- 1 file changed, 21 insertions(+), 2 deletions(-) diff --git a/Modules/_collectionsmodule.c b/Modules/_collectionsmodule.c index ca63f71..8b01a7f 100644 --- a/Modules/_collectionsmodule.c +++ b/Modules/_collectionsmodule.c @@ -118,9 +118,23 @@ static PyTypeObject deque_type; #define CHECK_NOT_END(link) #endif +/* A simple freelisting scheme is used to minimize calls to the memory + allocator. It accommodates common use cases where new blocks are being + added at about the same rate as old blocks are being freed. + */ + +#define MAXFREEBLOCKS 16 +static Py_ssize_t numfreeblocks = 0; +static block *freeblocks[MAXFREEBLOCKS]; + static block * newblock(void) { - block *b = PyMem_Malloc(sizeof(block)); + block *b; + if (numfreeblocks) { + numfreeblocks--; + return freeblocks[numfreeblocks]; + } + b = PyMem_Malloc(sizeof(block)); if (b != NULL) { return b; } @@ -131,7 +145,12 @@ newblock(void) { static void freeblock(block *b) { - PyMem_Free(b); + if (numfreeblocks < MAXFREEBLOCKS) { + freeblocks[numfreeblocks] = b; + numfreeblocks++; + } else { + PyMem_Free(b); + } } static PyObject * -- cgit v0.12