You signed in with another tab or window. Reload to refresh your session.You signed out in another tab or window. Reload to refresh your session.You switched accounts on another tab or window. Reload to refresh your session.Dismiss alert
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%).
The text was updated successfully, but these errors were encountered:
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:
n
(10/100?) entries forward, and if the to-be-inserted timer is still further ahead we directly jump there.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%).
The text was updated successfully, but these errors were encountered: