[Python-checkins] cpython: Issue #16398: Optimize deque.rotate()

[raymond.hettinger]

http://hg.python.org/cpython/rev/9fb793b60e79
changeset:   81438:9fb793b60e79
user:        Raymond Hettinger <python at rcn.com>
date:        Fri Jan 11 22:29:50 2013 -0800
summary:
  Issue #16398: Optimize deque.rotate()

files:
  Misc/NEWS                    |   3 +
  Modules/_collectionsmodule.c |  72 +++++++++++++++++++----
  2 files changed, 61 insertions(+), 14 deletions(-)


diff --git a/Misc/NEWS b/Misc/NEWS
--- a/Misc/NEWS
+++ b/Misc/NEWS
@@ -221,6 +221,9 @@
   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
--- a/Modules/_collectionsmodule.c
+++ b/Modules/_collectionsmodule.c
@@ -414,9 +414,10 @@
 _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 @@
             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;
 }

-- 
Repository URL: http://hg.python.org/cpython