diff options
author | Pablo Neira Ayuso <pablo@gnumonks.org> | 2011-09-26 11:45:03 +0200 |
---|---|---|
committer | Harald Welte <laforge@gnumonks.org> | 2011-10-17 13:25:29 +0200 |
commit | 066c912fd3b4554d4475ae0837c1d62ef6c872d1 (patch) | |
tree | 531cf756b6bb7ca55f5033c69abe9ee4135e9c4e /.gitignore | |
parent | f74db0b33d491a3189df7f909d382f93f9152c30 (diff) |
timer: add scalable RB-tree based timer infrastructure
This patch adds RB-tree based timers which scales better than the
previous list-based implementation.
It does not require any API changes. It breaks ABI because the
osmo_timer_list structure has changed though (to avoid this in
the future, we can put internal data in some private structure).
The following table summarizes the worst-case computational complexity
of this new implementation versus the previous one:
rb-tree list-based
------- ----------
calculate next timer to expire O(1) O(n)
insertion of new timer O(log n) O(n)
deletion of timer O(log n) O(1)
timer-fired scheduler O(log n) O(3n)
The most repeated cases are:
* the calculation of the next timer to expire, that happens in every
loop of our select function.
* the timer-fired scheduler execution.
This new implementation only loses in the deletion of timer scenario,
this happens because we may need to rebalance the tree after the
removal.
So I think there is some real gain if we have some situation in which
we have to handle lots of timers.
Diffstat (limited to '.gitignore')
0 files changed, 0 insertions, 0 deletions