[Python-checkins] cpython: Speed-up deque indexing by changing the deque block length to a power of two.

[raymond.hettinger]

http://hg.python.org/cpython/rev/6d278f426417
changeset:   84452:6d278f426417
parent:      84450:d5536c06a082
user:        Raymond Hettinger <python at rcn.com>
date:        Fri Jul 05 18:05:29 2013 -1000
summary:
  Speed-up deque indexing by changing the deque block length to a power of two.

The division and modulo calculation in deque_item() can be compiled
to fast bitwise operations when the BLOCKLEN is a power of two.

Timing before:

 ~/cpython $ py -m timeit -r7 -s 'from collections import deque' -s 'd=deque(range(10))' 'd[5]'
10000000 loops, best of 7: 0.0627 usec per loop

Timing after:

~/cpython $ py -m timeit -r7 -s 'from collections import deque' -s 'd=deque(range(10))' 'd[5]'
10000000 loops, best of 7: 0.0581 usec per loop

files:
  Lib/test/test_deque.py       |  2 +-
  Modules/_collectionsmodule.c |  2 +-
  2 files changed, 2 insertions(+), 2 deletions(-)


diff --git a/Lib/test/test_deque.py b/Lib/test/test_deque.py
--- a/Lib/test/test_deque.py
+++ b/Lib/test/test_deque.py
@@ -536,7 +536,7 @@
 
     @support.cpython_only
     def test_sizeof(self):
-        BLOCKLEN = 62
+        BLOCKLEN = 64
         basesize = support.calcobjsize('2P4nlP')
         blocksize = struct.calcsize('2P%dP' % BLOCKLEN)
         self.assertEqual(object.__sizeof__(deque()), basesize)
diff --git a/Modules/_collectionsmodule.c b/Modules/_collectionsmodule.c
--- a/Modules/_collectionsmodule.c
+++ b/Modules/_collectionsmodule.c
@@ -14,7 +14,7 @@
  * division/modulo computations during indexing.
  */
 
-#define BLOCKLEN 62
+#define BLOCKLEN 64
 #define CENTER ((BLOCKLEN - 1) / 2)
 
 /* A `dequeobject` is composed of a doubly-linked list of `block` nodes.

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