Monday, March 24, 2008

The magic of a timer wheel

I was looking for a decent C library, which would implement a simple timer callback functionality - i.e. I want to start a callback in 100 milliseconds from now... Apparently even allmighty glib does not have anything like this... I guess this is mostly because it goes with the threading model.

I might be biased - but my experience with the threads has been that they are much harder to debug than the code with "explicit multitasking" (i.e. the non-blocking IO loop) - I'll see if I am wrong with this assumption, but so far it was the case.

So, I went ahead and written a simple implementation of the timer wheel in its simplest form - just having an array of the next ticks, and list of timers to fire within that tick.

As I'm not doing all this in kernel space, I can take a reasonably wasteful size of the wheel - I took it to be 10000, which at a 100 ticks per second gives reasonable precision and reasonable maximum time - 100 seconds.

Since using the timer structures as pointers in memory is prone to the same errors as double-free (except that the double-stop is something that is definitely more possible), I've taken a decision to avoid using the pointers as much as I can - and using a growable array instead. And to combat a bit the reusal of the stale timers, I've taken an approach of having a "generation number" assigned to the timer - so it takes 256 reuses of the same timer index before the erroneous operation for the error to get unnoticed.

The result - on an Intel Core Duo 1.8 Ghz - I get around 10% CPU being used during the execution of the test with 200000 timers firing in at the same time. I think this can be optimized a bit, but for now I am pretty happy with the result - I will try to not need so many timers :)

The overhead (besides the static 40K of the timer wheel structure), is around 96 bytes per timer.

By far not very economical, but has the features I need - and the code is only 400 lines, including the volumious comments.

No comments: