summaryrefslogtreecommitdiffstats
diff options
context:
space:
mode:
authorRaymond Hettinger <python@rcn.com>2007-11-10 01:54:03 (GMT)
committerRaymond Hettinger <python@rcn.com>2007-11-10 01:54:03 (GMT)
commitd3ffd341b8370f0bd134ecc6c1b634a12f35446d (patch)
tree53c0603668446a8362f0610ee2d39e2b7ed68876
parent34448790db8ce27eee5a72f7175c47cd4a8f8940 (diff)
downloadcpython-d3ffd341b8370f0bd134ecc6c1b634a12f35446d.zip
cpython-d3ffd341b8370f0bd134ecc6c1b634a12f35446d.tar.gz
cpython-d3ffd341b8370f0bd134ecc6c1b634a12f35446d.tar.bz2
Use a freelist to speed-up block allocation and deallocation in collections.deque().
-rw-r--r--Modules/_collectionsmodule.c34
1 files changed, 27 insertions, 7 deletions
diff --git a/Modules/_collectionsmodule.c b/Modules/_collectionsmodule.c
index ca24be7..e5c3218 100644
--- a/Modules/_collectionsmodule.c
+++ b/Modules/_collectionsmodule.c
@@ -51,6 +51,10 @@ typedef struct BLOCK {
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 @@ newblock(block *leftlink, block *rightlink, int len) {
"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 @@ deque_pop(dequeobject *deque, PyObject *unused)
} 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 @@ deque_popleft(dequeobject *deque, PyObject *unused)
} 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 @@ deque_dealloc(dequeobject *deque)
if (deque->leftblock != NULL) {
deque_clear(deque);
assert(deque->leftblock != NULL);
- PyMem_Free(deque->leftblock);
+ freeblock(deque->leftblock);
}
deque->leftblock = NULL;
deque->rightblock = NULL;