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.
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 *