diff options
| author | Raymond Hettinger <python@rcn.com> | 2013-07-06 04:05:29 (GMT) |
|---|---|---|
| committer | Raymond Hettinger <python@rcn.com> | 2013-07-06 04:05:29 (GMT) |
| commit | de68e0cf0e6d94b087a3b7ae40e50843dff6d918 (patch) | |
| tree | 9413154444e873a334d1885e0a78ef9181708fab | |
| parent | 6597aa16b6044d8b5e31e176fed1865471499f08 (diff) | |
| download | cpython-de68e0cf0e6d94b087a3b7ae40e50843dff6d918.zip cpython-de68e0cf0e6d94b087a3b7ae40e50843dff6d918.tar.gz cpython-de68e0cf0e6d94b087a3b7ae40e50843dff6d918.tar.bz2 | |
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
| -rw-r--r-- | Lib/test/test_deque.py | 2 | ||||
| -rw-r--r-- | 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 index a8487d2..e782b99 100644 --- a/Lib/test/test_deque.py +++ b/Lib/test/test_deque.py @@ -536,7 +536,7 @@ class TestBasic(unittest.TestCase): @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 index b922475..781949d 100644 --- 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. |