]> granicus.if.org Git - python/commit
Speed-up deque indexing by changing the deque block length to a power of two.
authorRaymond Hettinger <python@rcn.com>
Sat, 6 Jul 2013 04:05:29 +0000 (18:05 -1000)
committerRaymond Hettinger <python@rcn.com>
Sat, 6 Jul 2013 04:05:29 +0000 (18:05 -1000)
commitde68e0cf0e6d94b087a3b7ae40e50843dff6d918
tree9413154444e873a334d1885e0a78ef9181708fab
parent6597aa16b6044d8b5e31e176fed1865471499f08
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
Modules/_collectionsmodule.c