Minor performance tweak for deque.index() with a start argument #9440
Conversation
Modules/_collectionsmodule.c
Outdated
| @@ -1050,8 +1050,10 @@ deque_index(dequeobject *deque, PyObject *const *args, Py_ssize_t nargs) | |||
| start = stop; | |||
| assert(0 <= start && start <= stop && stop <= Py_SIZE(deque)); | |||
|
|
|||
| /* XXX Replace this loop with faster code from deque_item() */ | |||
| for (i=0 ; i<start ; i++) { | |||
| for (i=0 ; i<start-BLOCKLEN ; i+=BLOCKLEN) { | |||
There was a problem hiding this comment.
Please make the new code conforming PEP 7:
for (i = 0; i < start - BLOCKLEN; i += BLOCKLEN) {for (; i < start; i++) {There was a problem hiding this comment.
I think that these two loops can be replaced with a single loop:
index = deque->leftindex + start;
for (; index >= BLOCKLEN; index -= BLOCKLEN) {
b = b->rightlink;
}
n = stop - start;(not tested)
There was a problem hiding this comment.
I find that harder to reason about.
There was a problem hiding this comment.
It took me a time to understand the code in this PR, but it looks cryptic again the next day. The code proposed by me is simpler and more efficient. I have tested it, it works. What a problem do you have with it?
| @@ -288,6 +288,11 @@ def test_index(self): | |||
| else: | |||
| self.assertEqual(d.index(element, start, stop), target) | |||
|
|
|||
| # Test large start argument | |||
| d = deque(range(0, 10000, 10)) | |||
There was a problem hiding this comment.
Is leftindex == 0 in this case? Would be nice to test also cases when leftindex != 0 and when (leftindex + start) % BLOCKLEN < leftindex.
| @@ -1050,8 +1050,10 @@ deque_index(dequeobject *deque, PyObject *const *args, Py_ssize_t nargs) | |||
| start = stop; | |||
| assert(0 <= start && start <= stop && stop <= Py_SIZE(deque)); | |||
|
|
|||
| /* XXX Replace this loop with faster code from deque_item() */ | |||
| for (i=0 ; i<start ; i++) { | |||
| for (i=0 ; i < start - BLOCKLEN ; i += BLOCKLEN) { | |||
There was a problem hiding this comment.
PEP 7 requires spaces around = and no spaces before ;.
There was a problem hiding this comment.
Please use your talents to focus on something relevant. Over-aggressive interpretations of PEP 7 are waste of time.
Modules/_collectionsmodule.c
Outdated
| @@ -1050,8 +1050,10 @@ deque_index(dequeobject *deque, PyObject *const *args, Py_ssize_t nargs) | |||
| start = stop; | |||
| assert(0 <= start && start <= stop && stop <= Py_SIZE(deque)); | |||
|
|
|||
| /* XXX Replace this loop with faster code from deque_item() */ | |||
| for (i=0 ; i<start ; i++) { | |||
| for (i=0 ; i<start-BLOCKLEN ; i+=BLOCKLEN) { | |||
There was a problem hiding this comment.
It took me a time to understand the code in this PR, but it looks cryptic again the next day. The code proposed by me is simpler and more efficient. I have tested it, it works. What a problem do you have with it?
Fix an old TODO to optimize the start argument for deque.index(). In the search for the starting block/index pair, make bounding jumps one block at a time rather than a single index at a time.