# ex: set ts=2 et tw=78:

Efficiently Dealing With a List of Timers


Say we have a queue of timers (T) that represent a series of tasks that must
be done in the future. Timers may be added into T. The maxmimum resolution
of any timer T[i] is R.

The simplest way to maintain this queue is:

  timer_add(t):
    T.append t

  timer_check() every R:
    for t in T
      if t.due
        t.run
        T.remove t

  Assuming R is sufficiently large in contrast to CPU speed and T.length
  doesn't get too long, this algorithm will work.
 
  Its time/work properties:
    timer_add O(1)
    timer_check O(n)

This doesn't look bad, really; but in real-life timer_check() will be run
overwhelmingly more than timer_add(). What we want to do is trade performance
characteristics of the two functions to make timer_check() as quick as
possible by making timer_add() a bit less efficient.

We can do that like so:

  timer_add(t):
    i = 0
    while i < T.length and T[i] < t
      i++
    T.insert_at(t, i)

  timer_check() every R:
    if T[0].due
      T.pop.run

  This reverses the complexity:
    timer_add O(n)
    timer_check O(1)

  Now we maintain a sorted soonest->latest list of timers, guarenteeing that
  T[0] is always our soonest timer, meaning we only ever have to check T[0]

But we can do even better! Now that T is sorted in ascending order, T[0]
always represents the next event, so instead of checking at each R, we can
simply sleep until T[0] is due. Note that this complicates timer_add() in the
case that we add a timer that is due before the current T[0]:

  timer_add(t):
    i = 0
    while i < T.length and T[i] < t
      i++
    T.insert_at(t, i)
    if i == 0
      update_timer_check(t)

  timer_check() at T[0]:
    T.pop.run

  We stay with the complexities:
    timer_add O(n)
    timer_check O(1)
  
But we can do even better by storing the timers in a red-black tree instead of
a list, giving us:

  timer_add(t):
    T.rb_insert(t)
    if T.rb_root.timer == t
      update_timer_check(t)

  timer_check() at T[0]:
    T.pop.run

  We now have complexities:
    timer_add O(log n)
    timer_check O(1)