[Python-checkins] r58927 - python/trunk/Modules/_collectionsmodule.c
raymond.hettinger
python-checkins at python.org
Sat Nov 10 02:54:04 CET 2007
Author: raymond.hettinger
Date: Sat Nov 10 02:54:03 2007
New Revision: 58927
Modified:
python/trunk/Modules/_collectionsmodule.c
Log:
Use a freelist to speed-up block allocation and deallocation in collections.deque().
Modified: python/trunk/Modules/_collectionsmodule.c
==============================================================================
--- python/trunk/Modules/_collectionsmodule.c (original)
+++ python/trunk/Modules/_collectionsmodule.c Sat Nov 10 02:54:03 2007
@@ -51,6 +51,10 @@
PyObject *data[BLOCKLEN];
} block;
+#define MAXFREEBLOCKS 10
+static int numfreeblocks = 0;
+static block *freeblocks[MAXFREEBLOCKS];
+
static block *
newblock(block *leftlink, block *rightlink, int len) {
block *b;
@@ -66,16 +70,32 @@
"cannot add more blocks to the deque");
return NULL;
}
- b = PyMem_Malloc(sizeof(block));
- if (b == NULL) {
- PyErr_NoMemory();
- return NULL;
+ if (numfreeblocks) {
+ numfreeblocks -= 1;
+ b = freeblocks[numfreeblocks];
+ } else {
+ b = PyMem_Malloc(sizeof(block));
+ if (b == NULL) {
+ PyErr_NoMemory();
+ return NULL;
+ }
}
b->leftlink = leftlink;
b->rightlink = rightlink;
return b;
}
+void
+freeblock(block *b)
+{
+ if (numfreeblocks < MAXFREEBLOCKS) {
+ freeblocks[numfreeblocks] = b;
+ numfreeblocks++;
+ } else {
+ PyMem_Free(b);
+ }
+}
+
typedef struct {
PyObject_HEAD
block *leftblock;
@@ -161,7 +181,7 @@
} else {
prevblock = deque->rightblock->leftlink;
assert(deque->leftblock != deque->rightblock);
- PyMem_Free(deque->rightblock);
+ freeblock(deque->rightblock);
prevblock->rightlink = NULL;
deque->rightblock = prevblock;
deque->rightindex = BLOCKLEN - 1;
@@ -198,7 +218,7 @@
} else {
assert(deque->leftblock != deque->rightblock);
prevblock = deque->leftblock->rightlink;
- PyMem_Free(deque->leftblock);
+ freeblock(deque->leftblock);
assert(prevblock != NULL);
prevblock->leftlink = NULL;
deque->leftblock = prevblock;
@@ -559,7 +579,7 @@
if (deque->leftblock != NULL) {
deque_clear(deque);
assert(deque->leftblock != NULL);
- PyMem_Free(deque->leftblock);
+ freeblock(deque->leftblock);
}
deque->leftblock = NULL;
deque->rightblock = NULL;
More information about the Python-checkins
mailing list