Re: No 100 HZ timer!

[Jamie Lokier <lk@tantalophile.demon.co.uk>]

george anzinger wrote:
> Horst von Brand wrote:
> > 
> > Ben Greear <greearb@candelatech.com> said:
> > 
> > [...]
> > 
> > > Wouldn't a heap be a good data structure for a list of timers?  Insertion
> > > is log(n) and finding the one with the least time is O(1), ie pop off the
> > > front....  It can be implemented in an array which should help cache
> > > coherency and all those other things they talked about in school :)
> > 
> > Insertion and deleting the first are both O(log N). Plus the array is fixed
> > size (bad idea) and the jumping around in the array thrashes the caches.
> > --
> And your solution is?

Note that jumping around the array thrashes no more cache than
traversing a tree (it touches the same number of elements).  I prefer
heap-ordered trees though because fixed size is always a bad idea.

Insertion is O(1) if entries can be predicted to be near
enough some place in the list, be that the beginning, the end, or some
marked places in the middle.

By the way, the current timer implementation only appears to be O(1) if
you ignore the overhead of having to do a check on every tick, and the
extra processing on table rollover.  For random timer usage patterns,
that overhead adds up to O(log n), the same as a heap.

However for skewed usage patterns (likely in the kernel), the current
table method avoids the O(log n) sorting overhead because long-delay
timers are often removed before percolating down to the smallest tables.
It is possible to produce a general purpose heap which also has this
property.

-- Jamie