From d9c116ca403a6fa15d1af414dabc726e862714e7 Mon Sep 17 00:00:00 2001 From: Raymond Hettinger Date: Tue, 9 Jul 2013 00:13:21 -0700 Subject: Add a spacing saving heuristic to deque's extend methods --- Lib/test/test_deque.py | 4 ++-- Modules/_collectionsmodule.c | 16 ++++++++++++++++ 2 files changed, 18 insertions(+), 2 deletions(-) diff --git a/Lib/test/test_deque.py b/Lib/test/test_deque.py index e782b99..ae1de9a 100644 --- a/Lib/test/test_deque.py +++ b/Lib/test/test_deque.py @@ -543,8 +543,8 @@ class TestBasic(unittest.TestCase): check = self.check_sizeof check(deque(), basesize + blocksize) check(deque('a'), basesize + blocksize) - check(deque('a' * (BLOCKLEN // 2)), basesize + blocksize) - check(deque('a' * (BLOCKLEN // 2 + 1)), basesize + 2 * blocksize) + check(deque('a' * (BLOCKLEN - 1)), basesize + blocksize) + check(deque('a' * BLOCKLEN), basesize + 2 * blocksize) check(deque('a' * (42 * BLOCKLEN)), basesize + 43 * blocksize) class TestVariousIteratorArgs(unittest.TestCase): diff --git a/Modules/_collectionsmodule.c b/Modules/_collectionsmodule.c index 9924b63..67ff55b 100644 --- a/Modules/_collectionsmodule.c +++ b/Modules/_collectionsmodule.c @@ -332,6 +332,14 @@ deque_extend(dequeobject *deque, PyObject *iterable) return result; } + /* Space saving heuristic. Start filling from the left */ + if (Py_SIZE(deque) == 0) { + assert(deque->leftblock == deque->rightblock); + assert(deque->leftindex == deque->rightindex+1); + deque->leftindex = 1; + deque->rightindex = 0; + } + it = PyObject_GetIter(iterable); if (it == NULL) return NULL; @@ -385,6 +393,14 @@ deque_extendleft(dequeobject *deque, PyObject *iterable) return result; } + /* Space saving heuristic. Start filling from the right */ + if (Py_SIZE(deque) == 0) { + assert(deque->leftblock == deque->rightblock); + assert(deque->leftindex == deque->rightindex+1); + deque->leftindex = BLOCKLEN - 1; + deque->rightindex = BLOCKLEN - 2; + } + it = PyObject_GetIter(iterable); if (it == NULL) return NULL; -- cgit v0.12