description
timeout.c implements hierarchical
timing wheels as described in "Hashed and
Hierarchical Timing Wheels: Data Structures for the
Efficient Implementation of a Timer Facility" by
George Varghese and Tony Lauck, ACM
089791-242-X/87/0011/0025, pp. 25-38. This data
structure implements timers in O(1) worst-case time
for all operations including insertion, deletion,
and expiration.
timeout.c is tickless.
Traditional implementations utilize an external
periodic timer which interrupts at intervals equal
to the granularity of the clock to progress the
timing wheel by one tick. timeout.c
uses bitmaps and bitfield manipulation to optimize
aperiodic wheel progression, and in particular
reduces calculation of the next minimum update
interval to a small O(1) in the worst case. This
makes timing wheels practicable in pure software.
Why a timing wheel? The critical feature of timing wheels is O(1) insertion and deletion. Timeouts rarely expire in network server software; they're hedges by software for when other expected events fail to occur. Timeouts are often installed and cancelled repeatedly for even the simplest of actions. But the typical timeout implementation uses a red-black tree or priority queue, where insertion and deletion are O(log N) operations. Timing wheels are considerably more efficient algorithmically, while this implementation in particular tries to address potential fixed cost and latency issues, particularly for sparsely populated wheels.
news
2014-01-15
Renamed project page to timeout.c.html and Git repositories to timeout.git.
2014-01-10
Fixed bug by adding a bit fill operation which had been removed earlier.
Preliminary benchmarking against libevent's binary heap-based timer implementation is proving very promising, both algorithmically and in absolute terms.
2013-12-14
Extensive refactoring. Renamed the API to use the prefix timeouts_ and timeout_, because POSIX protects timer_. Removed some unused code, added some comments (I forgot how most of it worked over the past several months), and fleshed out the API.
2013-05-28
Public release.
usage
The timing wheels are fundamentally dimensionless. Neither the algorithm nor the implementation necessarily conceives of seconds, milliseconds, microseconds, etc, per se. It is the application's responsibility to use consistent units. Whatever the units, the clock source should be monotonic, though successive timestamps do not need to increase.
An opaque 64-bit integer type is used for relative and absolute time values, and expiration times are segmented bit-wise and mapped to wheels according to the compile-time parameters WHEEL_NUM and WHEEL_BIT (see source for more details).
[more to come]
license
Copyright (c) 2013, 2014 William Ahern
Permission is hereby granted, free of charge, to any person obtaining a copy of this software and associated documentation files (the "Software"), to deal in the Software without restriction, including without limitation the rights to use, copy, modify, merge, publish, distribute, sublicense, and/or sell copies of the Software, and to permit persons to whom the Software is furnished to do so, subject to the following conditions:
The above copyright notice and this permission notice shall be included in all copies or substantial portions of the Software.
THE SOFTWARE IS PROVIDED "AS IS", WITHOUT WARRANTY OF ANY KIND, EXPRESS OR IMPLIED, INCLUDING BUT NOT LIMITED TO THE WARRANTIES OF MERCHANTABILITY, FITNESS FOR A PARTICULAR PURPOSE AND NONINFRINGEMENT. IN NO EVENT SHALL THE AUTHORS OR COPYRIGHT HOLDERS BE LIABLE FOR ANY CLAIM, DAMAGES OR OTHER LIABILITY, WHETHER IN AN ACTION OF CONTRACT, TORT OR OTHERWISE, ARISING FROM, OUT OF OR IN CONNECTION WITH THE SOFTWARE OR THE USE OR OTHER DEALINGS IN THE SOFTWARE.
source
git clone http://25thandClement.com/~william/projects/timeout.git
Or browse the source code from the Github mirror at https://github.com/wahern/timeout.