Reduce deque repeat execution when maxlen exist and size is not 1

[mlouielu]

BPO	29634
Nosy	@rhettinger, @serhiy-storchaka, @mlouielu
PRs	bpo-29634: Reduce deque repeat execution when maxlen exist and size is not 1 #255

^{Note: these values reflect the state of the issue at the time it was migrated and might not reflect the current state.}

Show more details

GitHub fields:

assignee = 'https://github.com/rhettinger'
closed_at = <Date 2017-02-24.04:00:41.070>
created_at = <Date 2017-02-23.16:39:23.008>
labels = ['extension-modules', 'type-feature', '3.7']
title = 'Reduce deque repeat execution when maxlen exist and size is not 1'
updated_at = <Date 2017-03-24.23:49:14.308>
user = 'https://github.com/mlouielu'

bugs.python.org fields:

activity = <Date 2017-03-24.23:49:14.308>
actor = 'rhettinger'
assignee = 'rhettinger'
closed = True
closed_date = <Date 2017-02-24.04:00:41.070>
closer = 'rhettinger'
components = ['Extension Modules']
creation = <Date 2017-02-23.16:39:23.008>
creator = 'louielu'
dependencies = []
files = []
hgrepos = []
issue_num = 29634
keywords = []
message_count = 7.0
messages = ['288460', '288462', '288463', '288496', '288501', '288507', '290415']
nosy_count = 3.0
nosy_names = ['rhettinger', 'serhiy.storchaka', 'louielu']
pr_nums = ['255']
priority = 'normal'
resolution = 'fixed'
stage = 'resolved'
status = 'closed'
superseder = None
type = 'enhancement'
url = 'https://bugs.python.org/issue29634'
versions = ['Python 3.7']

[mlouielu]

There is a XXX in v3.5.0 shows that need to dealing with deque maxlen setting case in deque_repeat.

Although there have common case for deque size 1 with maxlen, other size of deque with maxlen still using for-loop to extend the deque, without any detection.

Adding this fast break will reduce the execution speed when repeat deque with maxlen.

---

$ cat tests.py
from collections import deque
for _ in range(10:
    d = deque(maxlen=100_000)
    d.insert(0, 0)
    d.insert(0, 10)
    d * 10_000_000
$ time ./python_with_patch tests.py
$ time ./python tests.py

[serhiy-storchaka]

Wouldn't be better to update the number of repeats before the loop rather than checking at every iteration?

if (deque->maxlen >= 0 && n * size > deque->maxlen)
n = (deque->maxlen + size - 1) / size;

[mlouielu]

Serhiy: yes, your advice is better than checking inside the loop.

I have updated this to the commit, thanks!

[rhettinger]

The code looks fine. Please change the comment to something like:

/* Reduce the number of repetitions when maxlen would be exceeded */

[mlouielu]

Raymond: comment has changed, pushed on to GitHub.

[serhiy-storchaka]

There is an opportunity of further optimisation. For example deque(range(100000), maxlen=100001) *= 2 copies 100000 elements while it is enough to copy just 1 element. But I don't know whether it is worth to optimise this.

[rhettinger]

New changeset 357bad7 by Raymond Hettinger (Louie Lu) in branch 'master':
bpo-29634: Reduce deque repeat execution when maxlen exist and size is not 1 (#255) (#255)
357bad7