Skip to content
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.

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

Fix WheelTimer implementation that can expired timeout early #17850

Merged
merged 9 commits into from
Nov 5, 2024

Conversation

udovichenkoAlexander
Copy link
Contributor

@udovichenkoAlexander udovichenkoAlexander commented Oct 18, 2024

When entries insert in the end of timer queue, then unnecessary entry inserted (with duplicated key).
This can lead to some timeouts expired early and consume memory.

This can be checked with following test (to this file)

def test_multi_insert_then_past(self) -> None:
    wheel: WheelTimer[object] = WheelTimer(bucket_size=5)

    obj1 = object()
    obj2 = object()
    obj3 = object()
    wheel.insert(100, obj1, 150)
    wheel.insert(100, obj2, 160)
    wheel.insert(100, obj3, 155)
    
    self.assertListEqual(wheel.fetch(110), [])
    self.assertListEqual(wheel.fetch(158), [obj1])

Look at the entries after obj2 insert:

_Entry(end_key=21, elements=set())
_Entry(end_key=22, elements=set())
_Entry(end_key=23, elements=set())
_Entry(end_key=24, elements=set())
_Entry(end_key=25, elements=set())
_Entry(end_key=26, elements=set())
_Entry(end_key=27, elements=set())
_Entry(end_key=28, elements=set())
_Entry(end_key=29, elements=set())
_Entry(end_key=30, elements=set())
_Entry(end_key=31, elements={<object object at 0x7a129fb7ab80>})
_Entry(end_key=31, elements=set()) <-- this entry has duplicate key
_Entry(end_key=32, elements=set())
_Entry(end_key=33, elements={<object object at 0x7a129fb7ab70>})

gaps and duplicates cause errors when search Entry to insert in the middle of queue:
self.entries[max(min_key, then_key) - min_key].elements.add(obj)

This Pull request fix this with some minor refactoring (remove current_tick unused variable) and add this test case to unit tests.

@udovichenkoAlexander udovichenkoAlexander requested a review from a team as a code owner October 18, 2024 14:33
@CLAassistant
Copy link

CLAassistant commented Oct 18, 2024

CLA assistant check
All committers have signed the CLA.

Copy link
Contributor

@MadLittleMods MadLittleMods left a comment

Choose a reason for hiding this comment

The reason will be displayed to describe this comment to others. Learn more.

Nice catch! Makes sense after going through the motions

Strictly just needs the changelog fix. Updating tests also seems like a good change but we can always do that in a follow-up PR.

tests/util/test_wheel_timer.py Outdated Show resolved Hide resolved
changelog.d/17850.bugfix Outdated Show resolved Hide resolved
@udovichenkoAlexander udovichenkoAlexander force-pushed the wheel_fix branch 2 times, most recently from 1acb2cc to 511f88e Compare November 1, 2024 13:02
@udovichenkoAlexander
Copy link
Contributor Author

I fixed changelog and refactored wheel tests to use strings intead of objects

@MadLittleMods MadLittleMods merged commit 211c31d into element-hq:develop Nov 5, 2024
39 checks passed
@MadLittleMods
Copy link
Contributor

Thanks for the contribution @udovichenkoAlexander 🐄

@udovichenkoAlexander udovichenkoAlexander deleted the wheel_fix branch November 6, 2024 08:07
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment
Labels
None yet
Projects
None yet
Development

Successfully merging this pull request may close these issues.

3 participants