Skip to content

pick deque instead of list #7849

New issue

Have a question about this project? Sign up for a free GitHub account to open an issue and contact its maintainers and the community.

Sign up for GitHub

By clicking “Sign up for GitHub”, you agree to our terms of service and privacy statement. We’ll occasionally send you account related emails.

Already on GitHub? Sign in to your account

Jump to bottom
Merged
merged 1 commit into from
Mar 25, 2021
Merged

pick deque instead of list #7849

merged 1 commit into from
Mar 25, 2021

Conversation

zhan9san
Copy link
Contributor

Description

Currently, a list object, self.history, is used for storing request history.
self.history.insert(0, self.now) in function throttle_success and self.history.pop() in function allow_request, are used to insert and remove request history, respectively.

If deque is picked, we would have fast insertion and removal at both ends.

Please see the information below for more details about deque.

Though list objects support similar operations, they are optimized for fast fixed-length operations and incur O(n) memory movement costs for pop(0) and insert(0, v) operations which change both the size and position of the underlying data representation.

Would it be possible to review and approve this change?

@tomchristie
Copy link
Member

Sure, makes sense.

@tomchristie
Copy link
Member

Wondering what the likelihood is of us introducing a breakage for any folks with a custom throttling implementation that's currently assuming self.history will have a list API. Does deque provide a strict superset of the list API?

@zhan9san
Copy link
Contributor Author

Hi @tomchristie ,
Thanks for your quick reply. DRF is really a great project and I have created many projects based on it.

Regarding custom throttling implementation, self.history is invoked in three functions, allow_request, throttle_success and wait. All of these method calls are compatible with deque.

Technically, deque is not a superset of the list, but probably, we won't need all of list API.
Regarding this real scenario, throttling, it's more like a first-in-first-out structure.

Besides, I verified deque works well with both default cache(django.core.cache.backends.locmem.LocMemCache) and django-redis(django_redis.cache.RedisCache).

Please kindly let me know what you think.

@zhan9san
Copy link
Contributor Author

Hi @tomchristie
Is there anything else that I can do to help verify this code change?

@tomchristie
Copy link
Member

Okay, let's go with it.

@tomchristie tomchristie merged commit ebcb8d5 into encode:master Mar 25, 2021
@zhan9san zhan9san deleted the throttling-history-performance branch March 25, 2021 10:54
@tomchristie tomchristie mentioned this pull request Mar 25, 2021
Merged
tomchristie added a commit that referenced this pull request Mar 26, 2021
@tomchristie
Revert "pick deque instead of list (#7849)"
83d570f 
This reverts commit ebcb8d5.
@tomchristie tomchristie mentioned this pull request Mar 26, 2021
Merged
tomchristie added a commit that referenced this pull request Mar 26, 2021
@tomchristie
Revert "pick deque instead of list (#7849)" (#7872)
72c155d 
This reverts commit ebcb8d5.
This was referenced Mar 26, 2021
Merged
Closed
@tomchristie tomchristie mentioned this pull request Aug 3, 2021
Closed
sigvef pushed a commit to sigvef/django-rest-framework that referenced this pull request Dec 3, 2022
@zhan9san @sigvef
pick deque instead of list (encode#7849)
d061c9e 
Co-authored-by: Jack Zhang <jack.zhang@aspiraconnect.com>
sigvef pushed a commit to sigvef/django-rest-framework that referenced this pull request Dec 3, 2022
@tomchristie @sigvef
Revert "pick deque instead of list (encode#7849)" (encode#7872)
54bae60 
This reverts commit ebcb8d5.
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment
Reviewers
No reviews
Assignees
No one assigned
Labels
None yet
Projects
None yet
Milestone
No milestone
Development

Successfully merging this pull request may close these issues.
2 participants
@zhan9san @tomchristie