Implementing Software Timers (1990) | Hacker News Reader

Implementing Software Timers (1990)

kohala.com

66 pointsingve10 comments

That's O(N^2). Each time a timer expires, the code linearly scans the table for the next timer. You can do a lot better than that. The really good solution, O(log N) with an upper bound, was developed in 1987.[1] The better algorithms all involve tree structures, as you'd expect.

[1] https://en.wikipedia.org/wiki/Order-maintenance_problem [2] http://www.cs.cmu.edu/~sleator/papers/maintaining-order.pdf

Dumb question - why is just a heap not sufficient? You can efficiently remove from a heap by having each element track its index.

Pedantic people will argue that a heap is a technically tree - but you're right when it comes to the actual implementation.

Timers have unique properties which permit more optimal solutions. A hierarchical timing wheel is O(1) to start, O(1) to cancel, and O(1) to expire.

Finding the next minimum timer isn't O(1), but you don't actually need to know that information to process the timing wheels. It's O(1) to figure out the next _set_ of timers to process. They're populating a shared bucket. If they're in a higher-level wheel you would need to linearly search them to find the minimum. But normally you only care about when the next cascade operation needs to occur, which is the minimum within the granularity of that wheel, and _that's_ O(1).

See "Hashed and Hierarchical Timing Wheels: Data Structures for the Efficient Implementation of a Timer Facility" by George Varghese and Tony Lauck. And specifically appendix A for the O(1) expire.

http://www.cs.columbia.edu/~nahum/w6998/papers/ton97-timing-...

In somewhat of a defense of "Implementing Software Timers", the code seems to be for an embedded system in 1990, as hinted at by the disabling of interrupts. Chances are it will not have hundreds of timers, and that code size may be more important than efficiency.

This is an excerpt from a book "Obfuscated C and Other Mysteries", one of the stranger programming books I've ever owned. About half the chapters are discussions like this one -- taking a (relatively) small, practical programming task and going into detail how to address it. There's a grab-bag of subjects, and it doesn't even adhere strictly to C, as a couple of chapters discuss the use of Tcl in C programs. The majority of the book, however, discusses the winners of the first few years of the International Obfuscated C Code Contents. He not only presents the source code and explains what they do, but he also goes into some detail (sometimes great detail) as to how they work. There's nothing else like it that I know of, and it is one of my favorite programming books of all time.

The TimerWheel abstraction, implemented for example: - https://github.com/facebook/folly/blob/master/folly/io/async... (Facebook/Folly) - https://github.com/real-logic/Agrona/blob/886d7744fa15fc3de1... (Real-Logic/Argona) and in turn based on the Linux Kernel's "Timer Wheel" data structure (see here: https://lwn.net/Articles/646950/) are particularly elegant algorithms; great performance characteristics, except that you really can't get in O(1) the time when the next timer is going to fire, in order to implement a tickless scheduler, etc.

In that article, a new timer wheel draft is described - that solves most of the shortcomings of the original TW design.

Other/better implementations:

http://1wt.eu/articles/ebtree/

http://25thandclement.com/~william/projects/timeout.c.html

That domain name brings back memories. Registration dates back to 1989. It's WR Stevens' website, isn't it?

Yes it is. Recommend browsing for great UNIX / TCP history.

Reply on news.ycombinator.com