From 10c74d28e44050577b59dc26be31fbe257c9c665 Mon Sep 17 00:00:00 2001 From: Benjamin Peterson Date: Sat, 22 Jun 2013 11:16:36 -0700 Subject: [PATCH] backout 5accb0ac8bfb; needs more discussion on python-dev --- Lib/test/test_deque.py | 2 +- Modules/_collectionsmodule.c | 18 +++++++++++------- 2 files changed, 12 insertions(+), 8 deletions(-) diff --git a/Lib/test/test_deque.py b/Lib/test/test_deque.py index 98b203edb60a..595a0c4a35ca 100644 --- a/Lib/test/test_deque.py +++ b/Lib/test/test_deque.py @@ -522,7 +522,7 @@ class TestBasic(unittest.TestCase): @test_support.cpython_only def test_sizeof(self): - BLOCKLEN = 64 + BLOCKLEN = 62 basesize = test_support.calcobjsize('2P4PlP') blocksize = struct.calcsize('2P%dP' % BLOCKLEN) self.assertEqual(object.__sizeof__(deque()), basesize) diff --git a/Modules/_collectionsmodule.c b/Modules/_collectionsmodule.c index f175fcaa0ea1..abd80e06c431 100644 --- a/Modules/_collectionsmodule.c +++ b/Modules/_collectionsmodule.c @@ -8,13 +8,12 @@ */ /* The block length may be set to any number over 1. Larger numbers - * reduce the number of calls to the memory allocator, give faster - * indexing and rotation, and reduce the link::data overhead ratio. - * Ideally, the block length should be a power-of-two for faster - * division/modulo computations during indexing. + * reduce the number of calls to the memory allocator but take more + * memory. Ideally, BLOCKLEN should be set with an eye to the + * length of a cache line. */ -#define BLOCKLEN 64 +#define BLOCKLEN 62 #define CENTER ((BLOCKLEN - 1) / 2) /* A `dequeobject` is composed of a doubly-linked list of `block` nodes. @@ -59,8 +58,13 @@ static block *freeblocks[MAXFREEBLOCKS]; static block * newblock(block *leftlink, block *rightlink, Py_ssize_t len) { block *b; - /* To prevent len from overflowing PY_SSIZE_T_MAX on 32-bit machines, we - * refuse to allocate new blocks if the current len is nearing overflow. */ + /* To prevent len from overflowing PY_SSIZE_T_MAX on 64-bit machines, we + * refuse to allocate new blocks if the current len is dangerously + * close. There is some extra margin to prevent spurious arithmetic + * overflows at various places. The following check ensures that + * the blocks allocated to the deque, in the worst case, can only + * have PY_SSIZE_T_MAX-2 entries in total. + */ if (len >= PY_SSIZE_T_MAX - 2*BLOCKLEN) { PyErr_SetString(PyExc_OverflowError, "cannot add more blocks to the deque"); -- 2.47.3