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

Make timers more efficient #5

Open
Matthias247 opened this issue Sep 10, 2019 · 1 comment
Open

Make timers more efficient #5

Matthias247 opened this issue Sep 10, 2019 · 1 comment

Comments

@Matthias247
Copy link
Owner

Currently timers are just stored in a simple double linked list. This list needs to be searched on each timer insertion, which makes the operation O(n) in the already cache-inefficient linked-list. It would be nice to improve the way timers are stored in order to make them better scale to a higher number of timers.

Some ideas:

  • use a skiplist for timer. a timer node could also point n (10/100?) entries forward, and if the to-be-inserted timer is still further ahead we directly jump there.
  • use another two dimensional list for storing timers. E.g. only store timers in an outer linked list (bucket) if they expire in the same ms. Link buckets (different ms intervals) via another linked list.

The downside of such a change is that it would increase the memory utilization of timers by up to 2 extra pointers per node (which is about +50%).

@Matthias247
Copy link
Owner Author

I think this was mostly addressed by #36 . If someone has a better idea for that (ideally including data/tests), we can iterate further on it.

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

No branches or pull requests

1 participant