[Python-checkins] cpython: Speed-up deque indexing by changing the deque block length to a power of two.
raymond.hettinger
python-checkins at python.org
Sat Jul 6 06:06:03 CEST 2013
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
More information about the Python-checkins
mailing list