Efficient Timer Algorithm

8
votes

What is the best algorithm to implement a simple timer library. The library should allow the following:

  1. Timers to be started
  2. Timers to be stopped
  3. Timers to be checked whether they are still running

On Timer expiry a callback function will be called.

The timer module will allow timers to have a time resolution of Ns and the module shall be given a kick every Ns to prompt the module to check for expired timers.

Many timers may be simultaneously active.

The best algorithm needs to meet the following goals

  1. Be Robust to timers being started / stopped while processing a timer expiry callback
  2. Allow timers to be started, stopped and checked quickly
  3. Have a small memory footprint

Regards

3
algorithmtimer
What language should the solution be in? - Liran Orevi
I am more interested in the algorithm than the implementation. If it helps you to know I would most likely implement it in C. Regards - Howard May

3 Answers

14
votes

Best algorithm I have seen for timers is a timer wheel found in the research paper Hashed and Hierarchical Timing Wheels: Data Structures for the Efficient Implementation of a Timer Facility

I know in Java there is an implementation with Netty, JBoss and I am sure elsewhere too that you can use, if you are writing in Java.

3
votes

Timers are typically best implemented in an operating system kernel, at the assembly/C level, making use of platform-specific features like APIC timers wherever possible.

You might like to look at http://lwn.net/Articles/167897/ for details on the Linux implementation, and dig through the Linux source code to see working implementations.

1
votes

On POSIX-ish systems, you can use the timer_create/timer_settime family of functions to provide a lot of this "for free."