diff options
| -rw-r--r-- | Misc/NEWS | 3 | ||||
| -rw-r--r-- | Modules/_collectionsmodule.c | 72 |
2 files changed, 61 insertions, 14 deletions
@@ -221,6 +221,9 @@ Library duplication. Thanks to Ronan Lamy for the report and taking an initial stab at the problem. +- Issue #16398: Optimize deque.rotate() so that it only moves pointers + and doesn't touch the underlying data with increfs and decrefs. + - Issue #16900: Issue a ResourceWarning when an ssl socket is left unclosed. - Issue #13899: \A, \Z, and \B now correctly match the A, Z, and B literals diff --git a/Modules/_collectionsmodule.c b/Modules/_collectionsmodule.c index 1ff95ff..6e7f1e7 100644 --- a/Modules/_collectionsmodule.c +++ b/Modules/_collectionsmodule.c @@ -414,9 +414,10 @@ static int _deque_rotate(dequeobject *deque, Py_ssize_t n) { Py_ssize_t i, len=deque->len, halflen=(len+1)>>1; - PyObject *item, *rv; + PyObject *item; + block *prevblock, *leftblock, *rightblock; - if (len == 0) + if (len <= 1) return 0; if (n > halflen || n < -halflen) { n %= len; @@ -426,23 +427,66 @@ _deque_rotate(dequeobject *deque, Py_ssize_t n) n += len; } + assert(deque->len > 1); + deque->state++; + leftblock = deque->leftblock; + rightblock = deque->rightblock; for (i=0 ; i<n ; i++) { - item = deque_pop(deque, NULL); + item = rightblock->data[deque->rightindex]; assert (item != NULL); - rv = deque_appendleft(deque, item); - Py_DECREF(item); - if (rv == NULL) - return -1; - Py_DECREF(rv); + deque->rightindex--; + if (deque->rightindex == -1) { + assert(rightblock != NULL); + prevblock = rightblock->leftlink; + assert(leftblock != rightblock); + freeblock(rightblock); + prevblock->rightlink = NULL; + deque->rightblock = rightblock = prevblock; + deque->rightindex = BLOCKLEN - 1; + } + if (deque->leftindex == 0) { + block *b = newblock(NULL, leftblock, deque->len); + if (b == NULL) { + deque->len--; + Py_DECREF(item); + return -1; + } + assert(leftblock->leftlink == NULL); + leftblock->leftlink = b; + deque->leftblock = leftblock = b; + deque->leftindex = BLOCKLEN; + } + deque->leftindex--; + leftblock->data[deque->leftindex] = item; } for (i=0 ; i>n ; i--) { - item = deque_popleft(deque, NULL); + assert(leftblock != NULL); + item = leftblock->data[deque->leftindex]; assert (item != NULL); - rv = deque_append(deque, item); - Py_DECREF(item); - if (rv == NULL) - return -1; - Py_DECREF(rv); + deque->leftindex++; + if (deque->leftindex == BLOCKLEN) { + assert(leftblock != rightblock); + prevblock = leftblock->rightlink; + freeblock(leftblock); + assert(prevblock != NULL); + prevblock->leftlink = NULL; + deque->leftblock = leftblock = prevblock; + deque->leftindex = 0; + } + if (deque->rightindex == BLOCKLEN-1) { + block *b = newblock(rightblock, NULL, deque->len); + if (b == NULL) { + deque->len--; + Py_DECREF(item); + return -1; + } + assert(rightblock->rightlink == NULL); + rightblock->rightlink = b; + deque->rightblock = rightblock = b; + deque->rightindex = -1; + } + deque->rightindex++; + rightblock->data[deque->rightindex] = item; } return 0; } |