1 files changed, 46 insertions, 4 deletions

diff --git a/Modules/_collectionsmodule.c b/Modules/_collectionsmodule.c
index c1aa9a30bc..c6c8666d81 100644
--- a/Modules/_collectionsmodule.c
+++ b/Modules/_collectionsmodule.c
@@ -3,7 +3,7 @@
 
 /* collections module implementation of a deque() datatype
    Written and maintained by Raymond D. Hettinger <python@rcn.com>
-   Copyright (c) 2004-2013 Python Software Foundation.
+   Copyright (c) 2004-2014 Python Software Foundation.
    All rights reserved.
 */
 
@@ -145,6 +145,12 @@ typedef struct {
 
 static PyTypeObject deque_type;
 
+/* XXX Todo: 
+   If aligned memory allocations become available, make the
+   deque object 64 byte aligned so that all of the fields
+   can be retrieved or updated in a single cache line.
+*/
+
 static PyObject *
 deque_new(PyTypeObject *type, PyObject *args, PyObject *kwds)
 {
@@ -454,6 +460,31 @@ deque_inplace_concat(dequeobject *deque, PyObject *other)
     return (PyObject *)deque;
 }
 
+/* The rotate() method is part of the public API and is used internally
+as a primitive for other methods.
+
+Rotation by 1 or -1 is a common case, so any optimizations for high
+volume rotations should take care not to penalize the common case.
+
+Conceptually, a rotate by one is equivalent to a pop on one side and an
+append on the other.  However, a pop/append pair is unnecessarily slow
+because it requires a incref/decref pair for an object located randomly
+in memory.  It is better to just move the object pointer from one block
+to the next without changing the reference count.
+
+When moving batches of pointers, it is tempting to use memcpy() but that
+proved to be slower than a simple loop for a variety of reasons.
+Memcpy() cannot know in advance that we're copying pointers instead of
+bytes, that the source and destination are pointer aligned and
+non-overlapping, that moving just one pointer is a common case, that we
+never need to move more than BLOCKLEN pointers, and that at least one
+pointer is always moved.
+
+For high volume rotations, newblock() and freeblock() are never called
+more than once.  Previously emptied blocks are immediately reused as a
+destination block.  If a block is left-over at the end, it is freed.
+*/
+
 static int
 _deque_rotate(dequeobject *deque, Py_ssize_t n)
 {
@@ -1800,18 +1831,29 @@ _count_elements(PyObject *self, PyObject *args)
     if (mapping_get != NULL && mapping_get == dict_get &&
         mapping_setitem != NULL && mapping_setitem == dict_setitem) {
         while (1) {
+            Py_hash_t hash;
+
             key = PyIter_Next(it);
             if (key == NULL)
                 break;
-            oldval = PyDict_GetItem(mapping, key);
+
+            if (!PyUnicode_CheckExact(key) ||
+                (hash = ((PyASCIIObject *) key)->hash) == -1)
+            {
+                hash = PyObject_Hash(key);
+                if (hash == -1) 
+                    goto done;
+            }
+
+            oldval = _PyDict_GetItem_KnownHash(mapping, key, hash);
             if (oldval == NULL) {
-                if (PyDict_SetItem(mapping, key, one) == -1)
+                if (_PyDict_SetItem_KnownHash(mapping, key, one, hash) == -1)
                     break;
             } else {
                 newval = PyNumber_Add(oldval, one);
                 if (newval == NULL)
                     break;
-                if (PyDict_SetItem(mapping, key, newval) == -1)
+                if (_PyDict_SetItem_KnownHash(mapping, key, newval, hash) == -1)
                     break;
                 Py_CLEAR(newval);
             }