diff options
author | Raymond Hettinger <python@rcn.com> | 2007-11-10 01:54:03 (GMT) |
---|---|---|
committer | Raymond Hettinger <python@rcn.com> | 2007-11-10 01:54:03 (GMT) |
commit | d3ffd341b8370f0bd134ecc6c1b634a12f35446d (patch) | |
tree | 53c0603668446a8362f0610ee2d39e2b7ed68876 | |
parent | 34448790db8ce27eee5a72f7175c47cd4a8f8940 (diff) | |
download | cpython-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.c | 34 |
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; |