From de68e0cf0e6d94b087a3b7ae40e50843dff6d918 Mon Sep 17 00:00:00 2001 From: Raymond Hettinger Date: Fri, 5 Jul 2013 18:05:29 -1000 Subject: [PATCH] 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 --- 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 index a8487d2d95..e782b99203 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 b9224754db..781949d48f 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. -- 2.50.1